#!/usr/bin/env python
# coding: utf-8

# <div style="text-align: right"><i>Peter Norvig<br>March 2020</i></div>
# 
# # Elemental Spelling
# 
# Here's a problem: 
# 
# > 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). 
# 
# 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&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.)

# 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')


# In[25]:


spellable('hello')


# 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')


# # 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}