This notebook is a copy of https://nbviewer.jupyter.org/github/norvig/pytudes/blob/master/ipynb/ElementSpelling.ipynb by Peter Norvig. I am only rerunning it, not making any changes this time, since my main purpose here and now is to test the Deepnote integration workflows, as suggested by the Deepnote links in the README file of his repo.
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:
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
spellable to make sure they match.)
We can now| test the function (on
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_spellingrather than repeating code.
first_rest_spellingreturn either a string (the spelling) or
Noneif no spelling is possible.
- There might be multiple possible spellings; only one is returned.
- We use
lru_cacheto avoid repeated computation and thereby speed up the function.
Here I define
bad, a list of words that are not spellable, and
good, a list of words that are, and make some assertions:
And here are the actual spellings for the good words: