Peter Norvig
March 2020

Elemental Spelling

Here's a problem:

Given a word, decide if it can be spelled using only the symbols in the 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).

Here is a sketch of a recursive algorithm to solve the problem. A word is spellable if any of the following are true:

  • The word is the empty word.
  • The first 2 letters of the word (capitalized) form an element symbol, and the rest of the word is spellable.
  • The first 1 letter of the word (capitalized) forms an element symbol, and the rest of the word is spellable.

The input to spellable should be a string and the output is a boolean. Here is the code:

In [22]:
def spellable(word: str) -> bool:
    """Can we spell `word` using the `symbols` of the elements?"""
    return (word == ''
            or word[:2].capitalize() in symbols and spellable(word[2:])
            or word[:1].capitalize() in symbols and spellable(word[1:]))

I felt a bit bad about repeating a line of code above—violating DRY—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.)

In [23]:
symbols = set( # Elements in the periodic table
    '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  '
    '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   '
    '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 '
    '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 '
    'Yb Y Zn Zr'.split())

We can now| test the function (on 'Bananas' and 'hello'):

In [24]:
spellable('Bananas')
Out[24]:
True
In [25]:
spellable('hello')
Out[25]:
False

That was easy.

But maybe you'd like to see the actual spelling:'BaNaNaS'. The function spelling does that. The general idea is the same, except:

  • We use the subfunction first_rest_spelling rather than repeating code.
  • Both spelling and first_rest_spelling return either a string (the spelling) or None if no spelling is possible.
  • There might be multiple possible spellings; only one is returned.
  • We use lru_cache to avoid repeated computation and thereby speed up the function.
In [26]:
from functools import lru_cache

@lru_cache()
def spelling(word):
    "The spelling for `word` using `symbols` of the elements; or None if fail."
    return '' if word == '' else first_rest_spelling(word, 2) or first_rest_spelling(word, 1)

def first_rest_spelling(word, k):
    "Resulting spelling from taking off first k characters of word; or None if fail."
    first, rest = word[:k].capitalize(), word[k:]
    if first in symbols and spelling(rest) is not None:
        return first + spelling(rest)
    else:
        return None
In [27]:
spelling('bananas')
Out[27]:
'BaNaNaS'

Testing

Here I define bad, a list of words that are not spellable, and good, a list of words that are, and make some assertions:

In [6]:
bad  = 'hello world failure not an alternative'.split() # Unspellable words

good = '''howdy sphere falure is notan option           bananas 
    carbon iron silver silicon copper arsenic tin xenon bismuth
    attention copernicus inconspicuous hyperbolic orbits functions
    wonky nutso officious psychic unprofessional bilateralism 
    whippersnappers vichyssois bobbysocks alterabilities capabilities
    biostatistical physics floccinaucinihilipilification'''.split() # Spellable words

assert len(symbols) == 118
assert not any(spellable(w) or  spelling(w) for w in bad) 
assert     all(spellable(w) and spelling(w) for w in good)

And here are the actual spellings for the good words:

In [7]:
{spelling(w) for w in good}
Out[7]:
{'AlTeRaBiLiTiEs',
 'ArSeNiC',
 'AtTeNTiON',
 'BOBBYSOCKS',
 'BaNaNaS',
 'BiLaTeRaLiSm',
 'BiOsTaTiSTiCAl',
 'BiSmUTh',
 'CaPaBiLiTiEs',
 'CaRbON',
 'CoPErNiCuS',
 'CoPPEr',
 'FAlURe',
 'FUNCTiONS',
 'FlOCCInAuCInIHILiPILiFICaTiON',
 'HYPErBOLiC',
 'HoWDy',
 'IS',
 'InCoNSPICuOUS',
 'IrON',
 'NUTsO',
 'NoTaN',
 'OFFICIOUS',
 'OPtION',
 'ORbITs',
 'PHYSiCs',
 'PSYCHIC',
 'SPHeRe',
 'SiLiCoN',
 'SiLvEr',
 'TiN',
 'UNPrOFeSSiONAl',
 'VICHYSSOIS',
 'WHIPPErSNaPPErS',
 'WONKY',
 'XeNoN'}