ipynb/ElementSpelling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\"><i>Peter Norvig<br>March 2020</i></div>\n",
    "\n",
    "# Elemental Spelling\n",
    "\n",
    "Here's a problem: \n",
    "\n",
    "> Given a word, decide if it can be spelled using only the symbols in the **[periodic table](https://en.wikipedia.org/wiki/Periodic_table)** of elements. For example, the word \"bananas\" can be spelled with \"BaNaNaS\" (Barium-Sodium-Sodium-Sulfur). Note that there can be multiple possible spellings for a word&mdash;\"coin\" could be \"CoIn\" (Cobalt-Indium) or \"COIN\" (Carbon-Oxygen-Iodine-Nitrogen). \n",
    "\n",
    "Here is a sketch of a recursive algorithm to solve the problem. A word is **spellable** if any of the following are true:\n",
    "- The word is the empty word.\n",
    "- The first 2 letters of the word (capitalized) form an element symbol, and the rest of the word is spellable.\n",
    "- The first 1 letter of the word (capitalized) forms an element symbol, and the rest of the word is spellable.\n",
    "\n",
    "The input to `spellable` should be a string and the output is a boolean. Here is the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def spellable(word: str) -> bool:\n",
    "    \"\"\"Can we spell `word` using the `symbols` of the elements?\"\"\"\n",
    "    return (word == ''\n",
    "            or word[:2].capitalize() in symbols and spellable(word[2:])\n",
    "            or word[:1].capitalize() in symbols and spellable(word[1:]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I felt a bit bad about repeating a line of code above&mdash;violating [DRY](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself)&mdash;but using a subfunction or  `any/for` would add complexity. Here are the 118 currently defined `symbols`. (Note that the symbols are all capitalized, so I capitalize `[word[:2]` and `word[:1]` in `spellable` to make sure they match.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "symbols = set( # Elements in the periodic table\n",
    "    'Ac Al Am Sb Ar As At Ba Bk Be Bi Bh B Br Cd Ca Cf C Ce Cs Cl Cr Co Cn Cu Cm Ds Db  '\n",
    "    'Dy Es Er Eu Fm Fl F Fr Gd Ga Ge Au Hf Hs He Ho H In I Ir Fe Kr La Lr Pb Li Lv Lu   '\n",
    "    'Mg Mn Mt Md Hg Mo Mc Nd Ne Np Ni Nh Nb N No Og Os O Pd P Pt Pu Po K Pr Pm Pa Ra Rn '\n",
    "    'Re Rh Rg Rb Ru Rf Sm Sc Sg Se Si Ag Na Sr S Ta Tc Te Ts Tb Tl Th Tm Sn Ti W U V Xe '\n",
    "    'Yb Y Zn Zr'.split())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now| test the function (on `'Bananas'` and `'hello'`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spellable('Bananas')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spellable('hello')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was easy. \n",
    "\n",
    "But maybe you'd like to see the actual spelling:`'BaNaNaS'`. The function `spelling` does that. The general idea is the same, except:\n",
    "  - We use the subfunction `first_rest_spelling` rather than repeating code.\n",
    "  - Both `spelling` and `first_rest_spelling` return either a string (the spelling) or `None` if no spelling is possible.\n",
    "  - There might be multiple possible spellings; only one is returned.\n",
    "  - We use `lru_cache` to avoid repeated computation and thereby speed up the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache()\n",
    "def spelling(word):\n",
    "    \"The spelling for `word` using `symbols` of the elements; or None if fail.\"\n",
    "    return '' if word == '' else first_rest_spelling(word, 2) or first_rest_spelling(word, 1)\n",
    "\n",
    "def first_rest_spelling(word, k):\n",
    "    \"Resulting spelling from taking off first k characters of word; or None if fail.\"\n",
    "    first, rest = word[:k].capitalize(), word[k:]\n",
    "    if first in symbols and spelling(rest) is not None:\n",
    "        return first + spelling(rest)\n",
    "    else:\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'BaNaNaS'"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spelling('bananas')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Testing\n",
    "\n",
    "Here I define `bad`, a list of words that are **not** spellable, and `good`, a list of words that **are**, and make some assertions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "bad  = 'hello world failure not an alternative'.split() # Unspellable words\n",
    "\n",
    "good = '''howdy sphere falure is notan option           bananas \n",
    "    carbon iron silver silicon copper arsenic tin xenon bismuth\n",
    "    attention copernicus inconspicuous hyperbolic orbits functions\n",
    "    wonky nutso officious psychic unprofessional bilateralism \n",
    "    whippersnappers vichyssois bobbysocks alterabilities capabilities\n",
    "    biostatistical physics floccinaucinihilipilification'''.split() # Spellable words\n",
    "\n",
    "assert len(symbols) == 118\n",
    "assert not any(spellable(w) or  spelling(w) for w in bad) \n",
    "assert     all(spellable(w) and spelling(w) for w in good)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here are the actual spellings for the good words:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'AlTeRaBiLiTiEs',\n",
       " 'ArSeNiC',\n",
       " 'AtTeNTiON',\n",
       " 'BOBBYSOCKS',\n",
       " 'BaNaNaS',\n",
       " 'BiLaTeRaLiSm',\n",
       " 'BiOsTaTiSTiCAl',\n",
       " 'BiSmUTh',\n",
       " 'CaPaBiLiTiEs',\n",
       " 'CaRbON',\n",
       " 'CoPErNiCuS',\n",
       " 'CoPPEr',\n",
       " 'FAlURe',\n",
       " 'FUNCTiONS',\n",
       " 'FlOCCInAuCInIHILiPILiFICaTiON',\n",
       " 'HYPErBOLiC',\n",
       " 'HoWDy',\n",
       " 'IS',\n",
       " 'InCoNSPICuOUS',\n",
       " 'IrON',\n",
       " 'NUTsO',\n",
       " 'NoTaN',\n",
       " 'OFFICIOUS',\n",
       " 'OPtION',\n",
       " 'ORbITs',\n",
       " 'PHYSiCs',\n",
       " 'PSYCHIC',\n",
       " 'SPHeRe',\n",
       " 'SiLiCoN',\n",
       " 'SiLvEr',\n",
       " 'TiN',\n",
       " 'UNPrOFeSSiONAl',\n",
       " 'VICHYSSOIS',\n",
       " 'WHIPPErSNaPPErS',\n",
       " 'WONKY',\n",
       " 'XeNoN'}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{spelling(w) for w in good}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}