## Element Words

### April 14, 2017

Today’s exercise is either an interview question or somebody’s homework, I’m not sure:

Given a list of all the symbols of the chemicals in the periodic table, and a list of all the words in the English language, find the longest word that can be made using symbols of the chemicals in the periodic table.

Your task is to write a program to find the longest word that can be formed from the periodic table. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 8 Responses to “Element Words”

1. Paul said

In Python using an english dictionary of about 125000 words.

```from string import ascii_lowercase
from glob import glob

WORDS = [w.strip().lower()
for f in glob("D:\Data\Development\spell\en\english.?")
for w in open(f)]
WORDS = sorted(WORDS, key=len, reverse=True)

ECHAR = """H He Li Be B C N O F Ne Na Mg Al Si P S Cl Ar K Ca Sc Ti V Cr Mn Fe
Co Ni Cu Zn Ga Ge As Se Br Kr Rb Sr Y Zr Nb Mo Tc Ru Rh Pd Ag Cd In Sn Sb Te I
Xe Cs Ba La Ce Pr Nd Pm Sm Eu Gd Tb Dy Ho Er Tm Yb Lu Hf Ta W Re Os Ir Pt Au
Hg Tl Pb Bi Po At Rn Fr Ra Ac Th Pa U Np Pu Am Cm Bk Cf Es Fm Md No Lr Rf Db
Sg Bh Hs Mt""".lower().split()

ECOMB = {c: set(w for w in ECHAR if w.startswith(c)) for c in ascii_lowercase}

def check_word(word):
Q = [(word, [])]
while Q:
remaining, elements = Q.pop()
if not remaining:
return elements
for e in ECOMB.get(remaining, "???"):
if remaining.startswith(e):
Q.append((remaining[len(e):], elements+[e]))
return False

print("Number of words:", len(WORDS))
for word in WORDS:
res = check_word(word)
if res:
print(word, len(word), " ".join(res))

# Number of words: 125346
# nonrepresentationalism 22 no n re p re se n ta ti o na li sm
```
2. matthew said

Stand back, I know Regular Expressions:

```\$ egrep '^(h|he|li|be|b|c|n|o|f|ne|na|mg|al|si|p|s|cl|ar|k|ca|sc|ti|v|cr|mn|fe|co|ni|cu|zn|ga|ge|as|se|br|kr|rb|sr|y|zr|nb|mo|tc|ru|rh|pd|ag|cd|in|sn|sb|te|i|xe|cs|ba|la|ce|pr|nd|pm|sm|eu|gd|tb|dy|ho|er|tm|yb|lu|hf|ta|w|re|os|ir|pt|au|hg|tl|pb|bi|po|at|rn|fr|ra|ac|th|pa|u|np|pu|am|cm|bk|cf|es|fm|md|no|lr|rf|db|sg|bh|hs|mt)*\$' /usr/share/dict/words |
awk 'length > max_length { max_length = length; longest_line = \$0 } END { print longest_line }'
nonrepresentational
```

I don’t awk though and nicked that bit from ДМИТРИЙ МАЛИКОВ on Stack Exchange: https://unix.stackexchange.com/questions/24509/how-to-print-the-longest-line-in-a-file

3. john said

Using Perl 5. A dictionary of words should be supplied as a filename or on STDIN.

``` #!/usr/bin/env perl```

``` use strict; use warnings; use v5.22; my @elements = qw(     ac al am sb ar as at     ba bk be bi bh b br     cd ca cf c ce cs cl cr co cu cm     ds db dy     es er eu     fm f fr     gd ga ge au     hf hs he ho h     in i ir fe     kr     la lr pb li lu     mg mn mt md hg mo     nd ne np ni nb n no     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 tb tl th tm sn ti w     uub uuh uuo uup uuq uus uut uuu u     v     xe     yb y     zn zr     ); my \$pattern = '^(' . join('|', @elements) . ')+\$'; ```

```foreach (sort {-length(\$a) <=> -length(\$b)} <>) {     if (m/\$pattern/) {         say;         last;     } } ```

4. Mike said
```import re
from mendeleev import element

symbols='|'.join(e.symbol.lower() for e in element(list(range(1,119))))

regex = re.compile("(" + symbols + ")+")

with open('/data/12dicts/5desk.txt', 'rt') as words:
print(max(filter(regex.match, words), key=len))
```

Builds a regular expression using element symbol information from the mendeleev library. Because re.match() returns a MatchObject (a true value) when there is a match or None (a false value), otherwise, re.match() can be used with filter() to get the words that can be built using the element symbols. max(), with key=len, returns the longest word.

For my wordlist, the longest is “otorhinolaryngologist” at 21 letters.

5. Globules said

Here’s a Haskell version. (I’m currently too lazy to keep track of the parse.)

```import Data.Char (toLower)
import Data.List.Ordered (member, sortBy)
import Data.List (find)
import Data.Ord (Down(..), comparing)

-- Elements from https://en.wikipedia.org/wiki/Periodic_table as of 2017-04-15.
elements :: [String]
elements = words \$ map toLower
"Ac Ag Al Am Ar As At Au B Ba Be Bh Bi Bk Br C Ca Cd Ce Cf Cl Cm \
\Cn Co Cr Cs Cu Db Ds Dy Er Es Eu F Fe Fl Fm Fr Ga Gd Ge H He Hf \
\Hg Ho Hs I In Ir K Kr La Li Lr Lu Lv Mc Md Mg Mn Mo Mt N Na Nb  \
\Nd Ne Nh Ni No Np O Og Os P Pa Pb Pd Pm Po Pr Pt Pu Ra Rb Re Rf \
\Rg Rh Rn Ru S Sb Sc Se Sg Si Sm Sn Sr Ta Tb Tc Te Th Ti Tl Tm   \
\Ts U V W Xe Y Yb Zn Zr"

composedOf :: Ord a => [a] -> [[a]] -> Bool
[]       `composedOf` _    = True
[x]      `composedOf` elts = [x] `member` elts
(x:y:xs) `composedOf` elts = [x, y] `member` elts &&     xs `composedOf` elts ||
[x] `member` elts && (y:xs) `composedOf` elts

main :: IO ()
main = do
ws <- fmap (sortBy (comparing (Down . length)) . words) getContents
case find ((`composedOf` elements) . map toLower) ws of
Nothing -> putStrLn "Didn't find any matching words."
Just w  -> putStrLn \$ "The longest matching word is: " ++ w
```
```\$ ./elemword < /usr/share/dict/words
The longest matching word is: nonrepresentationalism
```
6. Paul said

```regex = re.compile("(" + symbols + ")+\$")
```

Then the regex matches until the end of the word. The word “otorhinolaryngologist” is not a valid match (only the “o” is matched.

7. matthew said

This reminds me of this problem: https://programmingpraxis.com/2014/07/25/number-words & here’s an adapted version of my C++ solution there – it’s essentially the recursive solution, but using dynamic programming to avoid repeated identical recursions. It also prints the number of ways found to construct each word, and piping the output through sort tells us that as before the 19-letter “nonrepresentational” is longest, but with only 2 variations, but the 17-letter “inconspicuousness” has 24 variations. Interestingly, “casinos”, with a mere 7 letters, has 13 variations:

```c:as:in:os
ca:s:in:os
c:as:i:n:os
ca:s:i:n:os
ca:si:n:os
c:as:i:no:s
ca:s:i:no:s
ca:si:no:s
c:as:in:o:s
ca:s:in:o:s
c:as:i:n:o:s
ca:s:i:n:o:s
ca:si:n:o:s
```
```#include <string.h>
#include <vector>
#include <string>
#include <iostream>

const char *elements[] = {
"h","he","li","be","b","c","n","o","f","ne","na","mg","al","si","p","s",
"cl","ar","k","ca","sc","ti","v","cr","mn","fe","co","ni","cu","zn","ga",
"ge","as","se","br","kr","rb","sr","y","zr","nb","mo","tc","ru","rh",
"pd","ag","cd","in","sn","sb","te","i","xe","cs","ba","la","ce","pr",
"nd","pm","sm","eu","gd","tb","dy","ho","er","tm","yb","lu","hf","ta",
"w","re","os","ir","pt","au","hg","tl","pb","bi","po","at","rn","fr",
"ra","ac","th","pa","u","np","pu","am","cm","bk","cf","es","fm","md",
"no","lr","rf","db","sg","bh","hs","mt"
};
const int NELEMENTS = sizeof(elements)/sizeof(*elements);

struct Node {
Node(Node *p, Node *n, std::string &s)
: prefix(p), next(n), label(s),
count((p ? p->count : 1) + (n ? n->count : 0)) {}
Node *prefix, *next;
std::string label;
long count;
};

int main(int argc, char *argv[]) {
std::string s;
while (std::cin >> s) {
int slen = s.size();
std::vector<Node *> table(slen+1);
for (int i = 1; i <= slen; i++) {
for (int j = 0; j < NELEMENTS; j++) {
std::string label = elements[j];
int llen = label.size();
if (llen <= i && s.compare(i-llen, llen, label) == 0) {
// Check there is a solution to extend
if (i == llen || table[i-llen] != NULL) {
table[i] = new Node(table[i-llen],table[i],label);
}
}
}
}
if (table[slen] != NULL) {
std::cout << s.size() << " " << table[slen]->count << " " << s << "\n";
}
}
}
```
8. Jussi Piitulainen said

Using an HFST (Helsinki Finite-State Tools) component to extract the matching words. Braces in the regex formalism delimit string literals, and 0 stands for the empty string which is mapped to a newline at the end of each match.

```! elemental.pmatch - matches words that consist of elements, adds a
! newline to each match (not sure why boundary conditions are not
! needed in current versions; hoping that there is a nicer way to
! specify a newline; to be investigated)

define element {h} | {he} | {li} | {be} | {b} | {c} | {n} | {o} |
{f} | {ne} | {na} | {mg} | {al} | {si} | {p} | {s} | {cl} | {ar} |
{k} | {ca} | {sc} | {ti} | {v} | {cr} | {mn} | {fe} | {co} | {ni} |
{cu} | {zn} | {ga} | {ge} | {as} | {se} | {br} | {kr} | {rb} | {sr} |
{y} | {zr} | {nb} | {mo} | {tc} | {ru} | {rh} | {pd} | {ag} | {cd} |
{in} | {sn} | {sb} | {te} | {i} | {xe} | {cs} | {ba} | {hf} | {ta} |
{w} | {re} | {os} | {ir} | {pt} | {au} | {hg} | {tl} | {pb} | {bi} |
{po} | {at} | {rn} | {fr} | {ra} | {rf} | {db} | {sg} | {bh} | {hs} |
{mt} | {ds} | {rg} | {cn} | {nh} | {fl} | {mc} | {lv} | {ts} | {og} |
{la} | {ce} | {pr} | {nd} | {pm} | {sm} | {eu} | {gd} | {tb} | {dy} |
{ho} | {er} | {tm} | {yb} | {lu} | {ac} | {th} | {pa} | {u} | {np} |
{pu} | {am} | {cm} | {bk} | {cf} | {es} | {fm} | {md} | {no} | {lr} ;

define TOP element+ 0:{
};
```

Using Bash to run the matcher and extract the longest matches.

```# Compiles elemental.pmatch, runs the transducer on a plain text file
# to match instances of the pattern named TOP on each line, only
# writing out the matches; transducer is made so that this produces
# one word per line; select the longest of those.

hfst-pmatch2fst -i elemental.pmatch -o elemental.hfst

hfst-pmatch --newline --extract-patterns elemental.hfst < ~/pg52108.txt |
sort -u |