A graph search solution to this week’s scrabble-related riddle from fivethirtyeight.

“What is the longest word you can build in a game of Scrabble one letter at a time? That is, starting with a valid two-letter word, how long a word can you build by playing one letter at a time on either side to form a valid three-letter word, then a valid four-letter word, and so on? (For example, HE could become THE, then THEM, then THEME, then THEMES, for a six-letter result.)”

You can see how I tackled this problem here. To summarize: storing valid scrabble words in a directed graph connecting words of length N to words of length N+1 makes it very easy to build long words using simple graph search algorithms. The most time-consuming portion of this riddle was finding an adequate list of scrabble words. Using this list of english words I was able to find a 10-letter result, but using TWL06 (wiki), the longest result was 9 letters long.

These are the longest solutions I could find for this riddle. Below is a web applet that allows you to construct words in this manner interactively.

la -> las -> lass -> lassi -> lassis -> classis -> classism -> classisms
la -> las -> lass -> lassi -> lassis -> classis -> classist -> classists
la -> las -> lass -> lassi -> lassie -> lassies -> glassies -> glassiest
la -> lap -> laps -> lapse -> elapse -> relapse -> relapser -> relapsers
in -> pin -> ping -> aping -> raping -> craping -> scraping -> scrapings
at -> eat -> eath -> heath -> sheath -> sheathe -> sheather -> sheathers
is -> ais -> rais -> raise -> raiser -> raisers -> praisers -> upraisers