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.
In Python using an english dictionary of about 125000 words.
Stand back, I know Regular Expressions:
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
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;
}
}
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.
Here’s a Haskell version. (I’m currently too lazy to keep track of the parse.)
@Mike: Your line 6 should read:
Then the regex matches until the end of the word. The word “otorhinolaryngologist” is not a valid match (only the “o” is matched.
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:
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.
Using Bash to run the matcher and extract the longest matches.
The longest match in the document is “kirkaspiirteinen” ‘bright-featured’, at 16 characters.