{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
Peter Norvig
March 2020
\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—\"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—violating [DRY](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself)—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 }