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 input to spellable
should be a string and the output is a boolean. Here is the code:
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.)
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'
):
spellable('Bananas')
True
spellable('hello')
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:
first_rest_spelling
rather than repeating code.spelling
and first_rest_spelling
return either a string (the spelling) or None
if no spelling is possible.lru_cache
to avoid repeated computation and thereby speed up the function.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
spelling('bananas')
'BaNaNaS'
Here I define bad
, a list of words that are not spellable, and good
, a list of words that are, and make some assertions:
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:
{spelling(w) for w in good}
{'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'}