{"id":9129,"date":"2023-04-06T14:15:54","date_gmt":"2023-04-06T18:15:54","guid":{"rendered":"https:\/\/blogs.mathworks.com\/community\/?p=9129"},"modified":"2023-04-13T10:41:44","modified_gmt":"2023-04-13T14:41:44","slug":"an-algorithmic-spelling-bee","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/community\/2023\/04\/06\/an-algorithmic-spelling-bee\/","title":{"rendered":"An Algorithmic Spelling Bee"},"content":{"rendered":"
\n
Earlier this year I wrote about solving word ladders with MATLAB. There was a lot of interest in that post, so I thought I'd share my investigations regarding another word-based app. In this script, I'm trying to create a puzzle modeled on the NY Times Spelling Bee<\/a> game. Here is the premise: you are given seven letters, and your job is to find all possible words you can make with those seven letters. You can use letters more than once, but they must be four or more letters long, and they must all include the special center letter. Every Spelling Bee puzzle has at least one \"pangram\", which is a word that uses all seven letters.<\/div>\n
As an example, suppose you were given this puzzle.<\/div>\n
\"spellingbee.png\"<\/div>\n
From this puzzle you could create PORE, ADORE, ADOPT, as well as the pangram OPERATED. But you couldn't create POD (too short) or PAPER (doesn't include the center letter \"O\").<\/div>\n
Here I'm not so much interested in solving the puzzle. I want to write a script that can create a Spelling Bee puzzle.<\/div>\n

Build the Dictionary<\/h2>\n
We need some ground truth for all the legal words. Here's Google's 10,000 word English dictionary. It's small, but good enough for our purposes here.<\/div>\n
\n
\n
url = 'https:\/\/raw.githubusercontent.com\/first20hours\/google-10000-english\/master\/google-10000-english.txt'<\/span>;<\/span><\/div>\n<\/div>\n
\n
wordList = webread(url);<\/span><\/div>\n<\/div>\n<\/div>\n
Split the word list into strings.<\/div>\n
\n
\n
words = split(string(wordList));<\/span><\/div>\n<\/div>\n
\n
words = lower(words);<\/span><\/div>\n<\/div>\n<\/div>\n
The Spelling Bee puzzle avoids the letter S so that it never has to deal with plurals. Let's use logical indexing to keep only the words that don't contain an S.<\/div>\n
\n
\n
keep = ~words.contains(\"s\"<\/span>);<\/span><\/div>\n<\/div>\n
\n
words = words(keep);<\/span><\/div>\n<\/div>\n<\/div>\n
Of these, keep only the words that are four letters or longer.<\/div>\n
\n
\n
keep = words.strlength >= 4;<\/span><\/div>\n<\/div>\n
\n
words = words(keep);<\/span><\/div>\n<\/div>\n<\/div>\n
I like how these string commands are easy to read and understand! Just like for us humans, code that communicates clearly keeps its job the longest. We don't want to employ fussy, high-maintenance code.<\/div>\n
How many words do we end up with?<\/div>\n
\n
\n
fprintf(\"The adjusted dictionary now contains %d words\\n\"<\/span>,length(words))<\/span><\/div>\n
\n
\n
The adjusted dictionary now contains 4955 words<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
We've thrown out about half the words in our dictionary.<\/div>\n
We'll be converting from ASCII representation to alphabet number a few times, so let's invest in a little anonymous helper function. It'll make the code below a little easier to read.<\/div>\n
\n
\n
% An anonymous function to translate ASCII values to A=1, B=2, ... Z=26.<\/span><\/span><\/div>\n<\/div>\n
\n
ascii2letter = @(chars) abs(lower(chars))-96;<\/span><\/div>\n<\/div>\n<\/div>\n
Try it out<\/div>\n
\n
\n
ascii2letter('ABCXYZ'<\/span>)<\/span><\/div>\n
\n
\n
\n
\n
ans = <\/span>1\u00d76<\/span><\/div>\n<\/div>\n
\n
1 2 3 24 25 26<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Looks good!<\/div>\n
Build a 26-column sparse matrix to represent unique letter usage for each word. Each word in the dictionary gets one row. Every letter that appears in the word gets a 1.<\/div>\n
\n
\n
dictionaryLength = numel(words);<\/span><\/div>\n<\/div>\n
\n
a = sparse(dictionaryLength,26);<\/span><\/div>\n<\/div>\n
\n
for <\/span>i = 1:dictionaryLength<\/span><\/div>\n<\/div>\n
\n
uniqueLetters = unique(words(i).char);<\/span><\/div>\n<\/div>\n
\n
a(i,ascii2letter(uniqueLetters)) = 1;<\/span><\/div>\n<\/div>\n
\n
end<\/span><\/span><\/div>\n<\/div>\n
\n
<\/div>\n<\/div>\n
\n
nnz(a)\/numel(a)<\/span><\/div>\n
\n
ans = 0.2218<\/div>\n<\/div>\n<\/div>\n<\/div>\n
At 22% full, this matrix isn't terribly sparse as sparse matrices go. But it's a fun excuse to play with SPARSE, so let's carry on. Here's a SPY plot of the matrix.<\/div>\n
\n
\n
spy(a)<\/span><\/div>\n<\/div>\n
\n
set(gca, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTick=1:26, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTickLabel=num2cell('A'<\/span>:'Z'<\/span>), ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTickLabelRotation=0, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XAxisLocation=\"top\"<\/span>, ...<\/span><\/span><\/div>\n<\/div>\n
\n
PlotBoxAspectRatio=[1 1 1])<\/span><\/div>\n
\n
\n
<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
To make much out of this, we need to zoom in. Let's see how the word LABEL is encoded.<\/div>\n
\n
\n
ix = 1002;<\/span><\/div>\n<\/div>\n
\n
% In case you're wondering, I like to use \"ix\" as short for \"index\"<\/span><\/span><\/div>\n<\/div>\n
\n
words(ix)<\/span><\/div>\n
\n
\n
\n
ans = <\/span>\"label\"<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
full(a(ix,:))<\/span><\/div>\n
\n
\n
\n
\n
ans = <\/span>1\u00d726<\/span><\/div>\n<\/div>\n
\n
1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
spy(a(1001:1010,:))<\/span><\/div>\n<\/div>\n
\n
xline([1 2 5 12])<\/span><\/div>\n<\/div>\n
\n
yline(2,Color=\"red\"<\/span>)<\/span><\/div>\n<\/div>\n
\n
set(gca, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTick=1:26, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTickLabel=num2cell('A'<\/span>:'Z'<\/span>), ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTickLabelRotation=0, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XAxisLocation=\"top\"<\/span>, ...<\/span><\/span><\/div>\n<\/div>\n
\n
YTick=1:10, ...<\/span><\/span><\/div>\n<\/div>\n
\n
YTickLabels=words(1001:1010))<\/span><\/div>\n
\n
\n
<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Note that even though the L appears twice in the word, it only has a one in the matrix.<\/div>\n
Just for fun, let's do a histogram of the letters. This can be a useful sanity check that we're on the right track.<\/div>\n
\n
\n
allLetters = ascii2letter(char(join(words,''<\/span>)));<\/span><\/div>\n<\/div>\n
\n
histogram(allLetters)<\/span><\/div>\n<\/div>\n
\n
set(gca, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTick=1:26, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTickLabel=num2cell('A'<\/span>:'Z'<\/span>), ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTickLabelRotation=0)<\/span><\/div>\n
\n
\n
<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
As expected, E is the most commonly appearing letter. Q is the least, but for the fact that we completely wiped out S.<\/div>\n
How many words are composed of exactly seven distinct letters? That is, how many are potential pangrams for a game?<\/div>\n
\n
\n
% Summing letter-use across the rows<\/span><\/span><\/div>\n<\/div>\n
\n
% Use FIND to build an index to all the words that use exactly seven letters<\/span><\/span><\/div>\n<\/div>\n
\n
ix7LetterWords = find(sum(a,2)==7);<\/span><\/div>\n<\/div>\n
\n
length(ix7LetterWords)<\/span><\/div>\n
\n
ans = 790<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Let's look at a few of these seven-letter words.<\/div>\n
\n
\n
num7LetterWords = numel(ix7LetterWords);<\/span><\/div>\n<\/div>\n
\n
ix = ix7LetterWords(1:10);<\/span><\/div>\n<\/div>\n
\n
disp(words(ix(1:10)))<\/span><\/div>\n
\n
\n
\"product\"
\n\"privacy\"
\n\"company\"
\n\"project\"
\n\"american\"
\n\"network\"
\n\"following\"
\n\"including\"
\n\"location\"
\n\"profile\"<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Pick a good one as the \"seed\" pangram for our game.<\/div>\n
\n
\n
ix = ix(9);<\/span><\/div>\n<\/div>\n
\n
disp(words(ix))<\/span><\/div>\n
\n
\n
location<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
How many words can be spelled from those same 7 letters? Find all the words that use nothing but the letters in the seed word<\/div>\n
\n
\n
lettersInSeedWord = a(ix,:);<\/span><\/div>\n<\/div>\n
\n
% Find all the words that have none of the letters from the seed word.<\/span><\/span><\/div>\n<\/div>\n
\n
% We're making sure that all contributions of letters other than<\/span><\/span><\/div>\n<\/div>\n
\n
% the seed letters sum to zero.<\/span><\/span><\/div>\n<\/div>\n
\n
ixWordsFromSeedWord = find(sum(a(:,~lettersInSeedWord),2) == 0);<\/span><\/div>\n<\/div>\n
\n
<\/div>\n<\/div>\n
\n
fprintf('%d words use only the seven letters appearing in the seed word.\\n'<\/span>,numel(ixWordsFromSeedWord))<\/span><\/div>\n
\n
\n
73 words use only the seven letters appearing in the seed word.<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Which letters appear most frequently?<\/div>\n
\n
\n
bar(sum(a(ixWordsFromSeedWord,:)))<\/span><\/div>\n<\/div>\n
\n
set(gca, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTick=1:26, ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTickLabel=num2cell('A'<\/span>:'Z'<\/span>), ...<\/span><\/span><\/div>\n<\/div>\n
\n
XTickLabelRotation=0)<\/span><\/div>\n
\n
\n
<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
We need to designate one letter as the \"center letter\" that must appear in every word. Let's pick the letter that appears least frequently.<\/div>\n
\n
\n
vals = full(sum(a(ixWordsFromSeedWord,:)));<\/span><\/div>\n<\/div>\n
\n
vals(vals==0) = inf;<\/span><\/div>\n<\/div>\n
\n
[~,ixlet] = min(vals);<\/span><\/div>\n<\/div>\n
\n
<\/div>\n<\/div>\n
\n
centerLetter = char(ixlet+96);<\/span><\/div>\n<\/div>\n<\/div>\n
Remove all the words that don't have this letter<\/div>\n
\n
\n
ixRequired = find(a(:,ixlet));<\/span><\/div>\n<\/div>\n
\n
ix2a = intersect(ixWordsFromSeedWord,ixRequired);<\/span><\/div>\n<\/div>\n<\/div>\n
This is the original seed word:<\/div>\n
\n
\n
fprintf(\"%s\\n\"<\/span>, words(ix))<\/span><\/div>\n
\n
\n
location<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Here are the seven unique letters:<\/div>\n
\n
\n
sevenLetters = unique(char(words(ix)));<\/span><\/div>\n<\/div>\n
\n
fprintf(\"%s\\n\"<\/span>, sevenLetters);<\/span><\/div>\n
\n
\n
acilnot<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
The required center letter is:<\/div>\n
\n
\n
fprintf(\"%s\\n\"<\/span>, upper(centerLetter));<\/span><\/div>\n
\n
\n
C<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Here are the pangrams<\/div>\n
\n
\n
ix3 = find(sum(a(ix2a,:),2)==7);<\/span><\/div>\n<\/div>\n
\n
for <\/span>i = 1:numel(ix3)<\/span><\/div>\n<\/div>\n
\n
fprintf(\"%s\\n\"<\/span>,words(ix2a(ix3(i))));<\/span><\/div>\n<\/div>\n
\n
end<\/span><\/span><\/div>\n
\n
\n
location
\ncoalition
\nallocation<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Here is the complete list of words<\/div>\n
\n
\n
for <\/span>i = 1:numel(ix2a)<\/span><\/div>\n<\/div>\n
\n
fprintf(\"%s\\n\"<\/span>,words(ix2a(i)));<\/span><\/div>\n<\/div>\n
\n
end<\/span><\/span><\/div>\n
\n
\n
contact
\nlocal
\nlocation
\ncall
\naction
\ncool
\nclinical
\ncanon
\nicon
\ncontain
\natlantic
\ncotton
\nlincoln
\nclinton
\ncincinnati
\nclinic
\ncoalition
\ncoat
\nallocation
\nncaa
\ncoal
\noclc
\ncoin
\ncitation
\ncolin
\nciao
\ncant
\ncanal
\ncolonial
\nclan
\nitalic
\nincl
\ncolon
\ncannon<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
Some of those are little odd, but we have our dictionary to thank for that.<\/div>\n
\n
\n
sixLetters = setdiff(sevenLetters,centerLetter);<\/span><\/div>\n<\/div>\n
\n
sixLetters = sixLetters(randperm(6));<\/span><\/div>\n<\/div>\n<\/div>\n
Now for the graphics! Make the plot<\/div>\n
\n
\n
% The perimeter hex cells are centered from pi\/6 to 11*pi\/6 radians<\/span><\/span><\/div>\n<\/div>\n
\n
t = 2*pi*(0:5)\/6 + 2*pi\/12;<\/span><\/div>\n<\/div>\n
\n
r = 1.08*sqrt(3);<\/span><\/div>\n<\/div>\n
\n
x = r*cos(t);<\/span><\/div>\n<\/div>\n
\n
y = r*sin(t);<\/span><\/div>\n<\/div>\n
\n
<\/div>\n<\/div>\n
\n
cla<\/span><\/div>\n<\/div>\n
\n
hexplot(0,0,upper(centerLetter),\"#F7DA21\"<\/span>)<\/span><\/div>\n<\/div>\n
\n
hold on<\/span><\/span><\/div>\n<\/div>\n
\n
for <\/span>i = 1:numel(x)<\/span><\/div>\n<\/div>\n
\n
hexplot(x(i),y(i),upper(sixLetters(i)),\"#E6E6E6\"<\/span>)<\/span><\/div>\n<\/div>\n
\n
end<\/span><\/span><\/div>\n<\/div>\n
\n
hold off<\/span><\/span><\/div>\n<\/div>\n
\n
axis equal<\/span><\/span><\/div>\n<\/div>\n
\n
axis off<\/span><\/span><\/div>\n
\n
\n
<\/div>\n
<\/div>\n
<\/div>\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
And there you have it! It's easy to see how valuable a good algorithmically generated game can be. Once you've worked out the logic, you just need to run it once every day and your puzzle is ready to go. Compare this with the labor that goes into a crossword puzzle. Although who knows? Maybe crossword puzzles will be yet another of those things that AI proves to be adept at.<\/div>\n
\n
\n
function <\/span>hexplot(x,y,letter,color)<\/span><\/div>\n<\/div>\n
\n
t = linspace(0,2*pi,7);<\/span><\/div>\n<\/div>\n
\n
patch(cos(t)+x,sin(t)+y,\"white\"<\/span>, ...<\/span><\/span><\/div>\n<\/div>\n
\n
EdgeColor=\"none\"<\/span>, ...<\/span><\/span><\/div>\n<\/div>\n
\n
FaceColor=color)<\/span><\/div>\n<\/div>\n
\n
text(x,y,letter, ...<\/span><\/span><\/div>\n<\/div>\n
\n
FontSize=24, ...<\/span><\/span><\/div>\n<\/div>\n
\n
FontWeight=\"bold\"<\/span>, ...<\/span><\/span><\/div>\n<\/div>\n
\n
HorizontalAlignment=\"center\"<\/span>, ...<\/span><\/span><\/div>\n<\/div>\n
\n
VerticalAlignment=\"middle\"<\/span>)<\/span><\/div>\n<\/div>\n
\n
end<\/span><\/span><\/div>\n<\/div>\n<\/div>\n<\/div>\n