Building a Scrabble Word, One Letter at a Time

This week’s Riddler Express challenged us to find the longest word that can be built 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.)

To solve this, I needed a database table of valid Scrabble words. I googled ‘scrabble dictionary text file’ and found jonbcard‘s github project that included a large text file with a bunch of words. Looks good to me.

I started a new Laravel project to track my work. That was probably overkill for this problem, but I’d like to maintain it as I solve more problems.

Once I got the scrabble_words table seeded with my dictionary file, I knew I could cobble together a query to solve this problem.

My first “gotcha” was a problem seeding the table. I exploded the words file on the new-line character. It was actually delimited by a new-line character AND a carriage-return. Oops. I figured this out when I was running a query like this:

select word, length(word) from scrabble_words limit 10;

And I got a result like this.

word length(word)
AA 3

Phantom character!

Anyways, a quick

update scrabble_words set word = substring(word, 1, length(word) – 1);

solved this problem.

It seemed that I’d need to have a ‘join’ on the scrabble_words table for each unique length. If the table was huge, I’d have added a column to the table which would hold the length of the word, so that I could index it. But we only have 178,691 words. So no biggie.

So, I wanted to see if I was thinking about the query correctly.

select w2.word, w3.word, w4.word
from (select word, id from scrabble_words where length(word) = 4) w4
inner join (select word, id from scrabble_words where length(word) = 3) w3 on w3.word = substring(w4.word, 1, 3) and w3.id <> w4.id
inner join (select word, id from scrabble_words where length(word) = 2) w2 on w2.word = substring(w4.word, 1, 2) and w2.id <> w4.id
limit 10;

That gave me:

word word word
AA AAH AAHS
AA AAL AALS
AB ABA ABAS
AB ABO ABOS
AB ABY ABYE
AB ABY ABYS
AD ADD ADDS
AD ADO ADOS
AD ADZ ADZE
AG AGA AGAR

So it looked like I was on the right track.

A few more iterations landed me on this query. (Sorry, it looks kinda nasty here. But if you copy it into MySQL Workbench, it’s beautiful!)

select w2.word, w3.word, w4.word, w5.word, w6.word, w7.word, w8.word
from (select word, id from scrabble_words where length(word) = 8) w8
inner join (select word, id from scrabble_words where length(word) = 7) w7 on w7.word = substring(w8.word, 1, 7) and w7.id <> w8.id
inner join (select word, id from scrabble_words where length(word) = 6) w6 on w6.word = substring(w8.word, 1, 6) and w6.id <> w8.id
inner join (select word, id from scrabble_words where length(word) = 5) w5 on w5.word = substring(w8.word, 1, 5) and w5.id <> w8.id
inner join (select word, id from scrabble_words where length(word) = 4) w4 on w4.word = substring(w8.word, 1, 4) and w4.id <> w8.id
inner join (select word, id from scrabble_words where length(word) = 3) w3 on w3.word = substring(w8.word, 1, 3) and w3.id <> w8.id
inner join (select word, id from scrabble_words where length(word) = 2) w2 on w2.word = substring(w8.word, 1, 2) and w2.id <> w8.id
limit 10;

Which gave me (what looked to be) a more correct answer: 8

word word word word word word word
BA BAR BARB BARBE BARBEL BARBELL BARBELLS
MA MAX MAXI MAXIM MAXIMA MAXIMAL MAXIMALS
PA PAS PAST PASTE PASTER PASTERN PASTERNS
RE REP REPO REPOS REPOSE REPOSER REPOSERS

I added another join to the query to get it up to 9 (I’ll spare you the even nastier query), and got zero results. So my final answer is…. a 4-way tie at 8!

Glad to see Barb made it in. Long live Barb.

Edit: OOPS! I just realized I was only considering a Scrabble move that adds a letter to the END of the word. Back to the queries!

Okay… I updated the query to account for my discovery

select w2.word, w3.word, w4.word, w5.word, w6.word, w7.word, w8.word, w9.word
from (select word, id from riddler538.scrabble_words where length(word) = 9) w9
inner join (select word, id from riddler538.scrabble_words where length(word) = 8) w8 on instr(w9.word, w8.word) > 0
inner join (select word, id from riddler538.scrabble_words where length(word) = 7) w7 on instr(w8.word, w7.word) > 0
inner join (select word, id from riddler538.scrabble_words where length(word) = 6) w6 on instr(w7.word, w6.word) > 0
inner join (select word, id from riddler538.scrabble_words where length(word) = 5) w5 on instr(w6.word, w5.word) > 0
inner join (select word, id from riddler538.scrabble_words where length(word) = 4) w4 on instr(w5.word, w4.word) > 0
inner join (select word, id from riddler538.scrabble_words where length(word) = 3) w3 on instr(w4.word, w3.word) > 0
inner join (select word, id from riddler538.scrabble_words where length(word) = 2) w2 on instr(w3.word, w2.word) > 0
limit 100;

That query ran for about 175 seconds and yielded these 35 results:

AS ASS LASS LASSI LASSIE GLASSIE GLASSIES GLASSIEST
AS ASS LASS LASSI LASSIE LASSIES GLASSIES GLASSIEST
AS ASS LASS LASSI LASSIS CLASSIS CLASSISM CLASSISMS
AS ASS LASS LASSI LASSIS CLASSIS CLASSIST CLASSISTS
AS LAS LASS LASSI LASSIE GLASSIE GLASSIES GLASSIEST
AS LAS LASS LASSI LASSIE LASSIES GLASSIES GLASSIEST
AS LAS LASS LASSI LASSIS CLASSIS CLASSISM CLASSISMS
AS LAS LASS LASSI LASSIS CLASSIS CLASSIST CLASSISTS
LA LAS LASS LASSI LASSIE GLASSIE GLASSIES GLASSIEST
LA LAS LASS LASSI LASSIE LASSIES GLASSIES GLASSIEST
LA LAS LASS LASSI LASSIS CLASSIS CLASSISM CLASSISMS
LA LAS LASS LASSI LASSIS CLASSIS CLASSIST CLASSISTS
AI AIS RAIS RAISE PRAISE PRAISER PRAISERS UPRAISERS
AI AIS RAIS RAISE PRAISE PRAISER UPRAISER UPRAISERS
AI AIS RAIS RAISE PRAISE UPRAISE UPRAISER UPRAISERS
AI AIS RAIS RAISE RAISER PRAISER PRAISERS UPRAISERS
AI AIS RAIS RAISE RAISER PRAISER UPRAISER UPRAISERS
AI AIS RAIS RAISE RAISER RAISERS PRAISERS UPRAISERS
AI RAI RAIS RAISE PRAISE PRAISER PRAISERS UPRAISERS
AI RAI RAIS RAISE PRAISE PRAISER UPRAISER UPRAISERS
AI RAI RAIS RAISE PRAISE UPRAISE UPRAISER UPRAISERS
AI RAI RAIS RAISE RAISER PRAISER PRAISERS UPRAISERS
AI RAI RAIS RAISE RAISER PRAISER UPRAISER UPRAISERS
AI RAI RAIS RAISE RAISER RAISERS PRAISERS UPRAISERS
AT EAT EATH HEATH SHEATH SHEATHE SHEATHER SHEATHERS
AT EAT HEAT HEATH SHEATH SHEATHE SHEATHER SHEATHERS
IN PIN PING APING RAPING CRAPING SCRAPING SCRAPINGS
IS AIS RAIS RAISE PRAISE PRAISER PRAISERS UPRAISERS
IS AIS RAIS RAISE PRAISE PRAISER UPRAISER UPRAISERS
IS AIS RAIS RAISE PRAISE UPRAISE UPRAISER UPRAISERS
IS AIS RAIS RAISE RAISER PRAISER PRAISERS UPRAISERS
IS AIS RAIS RAISE RAISER PRAISER UPRAISER UPRAISERS
IS AIS RAIS RAISE RAISER RAISERS PRAISERS UPRAISERS
LA LAP LAPS LAPSE ELAPSE RELAPSE RELAPSER RELAPSERS
PI PIN PING APING RAPING CRAPING SCRAPING SCRAPINGS

Now we’re getting closer. Next, I ran the query with words up to 10 characters long. It yielded no results!

So, our answer is a 35-way tie for first place, with 9 characters.

It’s sad to see Barb leave. Again.

2 thoughts on “Building a Scrabble Word, One Letter at a Time”

  1. You actually make it seem so easy with your presentation but I find this matter to be actually something that I think I would never understand.
    It seems too complicated and extremely broad for me.
    I’m looking forward for your next post, I’ll try to get the hang of it!

Leave a Reply

Your email address will not be published. Required fields are marked *