how many five-letter words can you find where together they don't have any letters repeated
so for example you might have a squiz at a panel squeeze and panel both have five
unique letters each with no letters in common between the two words or if that panel was a ROM
now we're up to three words could you do better don't put that Chunk in the mixer it'll be salty
you don't have to make a story that's optional I got a little obsessed with this and the question
is could you find four or maybe five and all started because someone said a problem into the
podcast I do called a problem squared actually can we get the logo excellent so I do that with back
hill some of you may know back hill actually can we get a photo back in can we oh excellent right
so uh if you watch TV in the UK you might have seen back she's got a children's TV show called
make away takeaway so actually we can get that get the photo out perfect excellent so we were
sent a problem in by someone named Daniel who said pretty much this although they framed it in terms
of Wordle they said how many guesses can you have in Wordle before you have to repeat letters and I
should make it very clear this is not going to help you with Wordle this is not a video about
Wordle strategy check out through blue one Brown's video for that this was a Wordle inspired question
and I got pretty obsessed this feels like it could plausibly be done there are 26 different letters
in the Standard English alphabet and we really need well five words with five letters each 25
we'll have one spare and there are five vowels so if we're Frugal with vowels and each word just has
one that should all work and I was like okay I think we can do this and while a lot of people
would approach a word puzzle by thinking about words trying to fit something together I thought
well hang on what if we just check all the words and by all the words I mean all the words we're
not actually all the words if by word you just mean a five character string of letters because
there are over 11 million sets of five letters making up a word most of them entirely nonsensical
and actually a lot of them having duplicate letters if we only have the ones with five unique
letters we're down to just over seven million and most of them don't make any sense whatsoever and
there's no nice simple way of working out which sets of five letters are a real English word
versus a made-up word and this you just download a giant list of all the words which is what I did
and I already had a list of 370 105 different words that's all of them well the meaningful
ones at least I had that from the typewriter video where I want to calculate which words
your finger would travel the greatest distance when typing them on a typewriter a lot of fun
so I took the same list I've removed all the words which didn't have five letters
which whittled us down to just fifteen thousand nine hundred and twenty words and some of those
had repeat letters we don't need those once they're gone we've only got 10 175 left and
some of those are anagrams we don't have to check rearrangements of the same letters if we're just
looking for Unique sets of five letters and if you remove all the anagrams there are a mere
5977 real meaningful words which have five letters that are all different and will removed anagram
duplicates now we just got to check combinations of them and how many can there be a lot there are
a lot of combinations if you've got 5977 words and you need to pick five at a time
5977 choose five is over 63 quadrillion it's a big old number and if we want to check all of them to
see if they have 25 distinct letters well let's say hypothetically we've got a computer that can
check a million every second that's still going to take over 2 000 years and I haven't got that
kind of time so we've got two options we can either get a more powerful computer or we can
be a bit more clever with how we're checking them I went for option b be a bit more clever and this
is always the problem when you're doing some kind of exhaustive search or check involving computers
you've got to be smart at reducing the number of combinations to check as well as being clever with
the amount of computing power you have available until the two meet in the middle and then you can
do it and this was the issue in the second world war when they're trying to crack the Enigma code
Alan Turing was both doing very clever maths to reduce the combinations you had to check as well
as increasing the power of this new thing they just invented called the computer so I really
only had a laptop that I was prepared to run this on I could have you know got Cloud Server time or
more powerful computers or worked out so I could run it on more than one computer but I'm like
no no I want to run something on an old laptop so I can just leave it going I need to get the
combinations down so I can achieve that within my lifetime I decided to go for aggressive pruning by
which I mean cutting off the branching options as soon as possible so instead of going all the
way to the end of looking at every single possible combination of five words any combination of five
you can imagine it as starting with just a pair of two words and then you look at all the ways
to add three more so I checked every single pair of words to see if they had 10 unique letters and
if they didn't I could ignore any other sets that have those two words in them and pairs they're a
way fewer specifically three million two hundred and thirteen thousand six hundred and ninety six
pairs of Words which each had 10 unique letters at this point I didn't remove the kind of two-word
anagram equivalent I kept all of those in and now all I had to do will take every pair of words that
had 10 unique letters compare it to every other pair of words that has 10 unique letters see if
between them they've got 20 unique letters and if they do see if I can find another word to give us
five more now I could have been more clever because there are still loads of duplicates
in the way I was doing it and I could have kept trying to hone the code make it more efficient but
at this point I'm like look I've just got to set the code running and move on to other projects so
I did I just set the code going it ran for over a month sat there churning away it's like I'm about
to say it's like a less useful version of Bitcoin but you be the judge it's sat there churned away
and then one day it finished and it came back with some interesting results if you're curious how the
code actually worked I'll put it all on GitHub you can have a look it could be way better don't send
me ways I could have improved it I know I could have improved it the point is I knew I could just
wait for it to finish and here's what it found my coat had found 538 sets of five words that between
them had 25 unique letters I was super impressed and then I realized 470 of them we're talking 87.3
percent of all successful sets of five words had one word in common they all contained this word
fldx T pronounced fluid extract apparently and it seems my original list of words claimed that
was a word I thought people might be a bit upset in fact when I mentioned this in the podcast back
my co-host was very upset actually can we get that photo of back when I told her fluid extractors oh
there it is right yeah she looked she was so angry she put in a cardigan right so okay we
can take that out now there we go thank you right so back Beck was unimpressed and I figured a lot
of other people would be as well the problem is I had initially cast my word net very wide and that
list of words I used is very very generous with its definition of what a word is it basically
defines a word as any string of characters that someone's likely to use or type at some point
I'll link to the database below if you want to check it out it's useful for things like
uh filling like Auto filling in Auto completing things from people are typing them and what we
actually call a word is a a stricter definition whereas this is just strings of letters people
might use and if you Google fluid extract FLD XT there's over seven thousand or at least there
were over seven thousand responses when I did this and I thought you know what I could use
Google searches as a way to work out which are the most like a word so I wrote little
cheeky script that would take every single word from all the responses I had out of my original
code Google it and then record how many responses popped up when you searched for that word I could
also use this Google Search record the number of results technique to deal with the anagram
problem because some of the solutions I had had words in them where I'd excluded an anagram that
had the same letters and that might be a better word so I also automatically Googled every single
anagram of every word from every solution and then pick the one with the highest number of Google
results to include that in the official charts I then removed all the ones with fluid extract
because apparently that's just a step too far of the remaining 68 I could then rank them by how
much a word Google thought they were and here it is first word is vibex and you're already thinking
two vows oh that's a bold start followed by glyph there you are no vowels all averages
out then months dwarf and jocks and this was the top ranking one because months which is a word
about a type of metal I think that only had 740 000 results on a Google search but that was the
largest minimum value from all the results I got but that didn't feel a little bit arbitrary
instead of dwarf jocks you actually could have had wax fjord there you are Fjord pretty
funny word be pleased with that and there were other options so you could have x p w y that's
pronounced Expressway there you are sure for Expressway uh hdqrs headquarters there's a lot
of abbreviations and then either Flack and jumbo or flock and jumper I you can see how that works
in fact I would almost consider those that's the same solution just with a slight tweet anyways
people are going to hate this no one's going to like Expressway spelled e-x-p-w-y I need a way I
can find which of my Solutions are unambiguously valid Solutions so no one can argue with me and
then I realized that the arbitrator of word truth was right in front of me the whole time
it's Wordle it turns out in the original version of Wordle so before the New York Times bought
it and updated it the original code just had the list of acceptable words baked in actually there
were two lists one was all the answer words and the other one was all the acceptable guess words
that you could use to get to the answers but you combined them and you get the 12 972 acceptable
words in a game of Wordle so I realized this was the definitive list of what is a word that
I needed the whole time so I took all 538 of the results I got I compared each one to the official
Wordle word list to see how many of the five words from each one matched five of my Solutions had
zero words in common with the word or List uh here they are these are the absolute worst there were
then 85 that had a single word in common 210 that had had two words in common 193 had three words
in common 44 had four words in common but when it came to five words in common a complete match all
five words validated by the almighty Wordle there was one one single solution five wordal words that
use 25 unique characters and they are Fjord good old Fjord thank goodness gucks now gucks as in
ah there's some guck on this oh there's some guck on that wait these are different gucks
gucks nymph from both biology and Greek mythology you've also got vibex yeah vibex is back something
to do with veins real word according to Wordle and biologists and finally Waltz and what a fantastic
Waltz we have indeed been on the missing letter q there you are all 25 letters q left over so
there you are that is the only set of five wordal words that contain 25 unique letters I feel like
we've all achieved something here today foreign future Matt here so the podcast episode went out
yesterday and within 24 hours someone says they've written code which will do what took my computer
a month in under a day so let's check it out uh they put it on gitlab I will link to this
below if you want to have a look at it they've got all the files and a bit of a description
down here including and this is I think one of the greatest disses you're ever going to see on gitlab
according to Parker executing Parker's algorithm on a laptop took about a month this appeared to
the author as optimizable in other words Matt's an idiot I can do a lot better so I've already
downloaded all of their code let's go find that and how did they do it well in their tweet here
Benjamin percent I think that's correct um they said they did 22 minutes oh my goodness using
graph Theory so what they actually did was make a network of every five letter word with five
unique letters linked together the ones that have no letters in common and look for complete
sub graphs so five of them that link to all of the four other ones in that subgraph and
if you have a look at the code that I've loaded up here there's two files one that generates the
graph and then another one that then searches for these sub graphs so you know what I'm going
to run it and we'll see actually you know what I'm going to add in I'm going to import time
and then I'm going to uh uh print the time so we can see how long this actually takes so I've put
printing what the current time is at the top and then people are going to yell at me I know you're
not supposed to time code this way I'm going to work that at the bottom okay uh what I'm going
to do oh here we go so there they've specified the file I'm going to put in the complete path I don't
think it's a security risk to show that let's uh you know I'm going to clear that message and try
again oh it's often racing it's building neighborhoods aren't we all aren't we all
done it's writing to the output and it's finished let's see how long it took don't
judge me I pasted the times into Excel 22 and a half seconds okay so that's our running time so
far now I'm gonna do is I'm going to clear the output from that we're going to switch
over to the actual file that does the business I'm going to add in again I'm going to import
time because I want to make sure that this is as fast as everyone's claiming it's gonna be
there we are that goes top and bottom okay so uh here we go oh it's loading the graph
this will take long you know what I'm gonna head
out I'll come back later and we'll see how long this took
okay so I'm back I uh don't worry I just went to the Hotel bar I'm on the road at
the moment and it's evening time here don't be fooled by how sunny it is and it's done 800 131
that's more like on let's open them up and have a look okay I say to Matt is a
um CSV file that I've opened here in Excel looks like it's concatenated them all together but if
you pick on them they're actually they're separated by tabs um and they're all here
and it occurs to me the reason why there are more because I only had like 528 I think uh the reason
there's more is they've included all the anagrams so I stripped out anagrams the way they've done it
they must put anagrams in and the fact that it's roughly one and a half times the size
matches up with the average number of anagrams I had before so let's have a look at how long that
took oh my goodness well let's let's add them all up for completeness sake and there we go
900 seconds oh that's gonna be a really really neat number of minutes oh my goodness 15 minutes
on the nose to find 831 so actually I think that ratio is about right they found 831 I
found 538 and so that's uh let's have a look it's going to be about 40 something percent extra
54 okay I reckon that's just the anagrams I'll double check that later to make sure
um they didn't find any that I didn't because I was exhaustive
um so there you go um well done Benjamin you were able to do what took me 32 days of computing time
in 15 minutes that's less than one thirtieth of a day I'm glad I interrupted my trip for this
back to you past Matt thank you so much for watching the video I'll link to the word list
as well as my code below I know it's terrible code you don't have to tell me and finally a
huge thanks to everyone who listens to a problem squared and my co-host Beck Hill can we get that
picture back back oh we can there we go so actually can we get a different one which is
um I thought we had a cardi for angry back but she's always wearing the same thing so just while
we're waiting for the people to fight they found it there it is wow actually can we get that but
looking uh more pensive taking one out for pensive one so if you go to a problem squared dot that was
quick.com you could now go back to the happy one let's hit the happy one again uh you can
pose problems for the podcast that's good where we all bet is still in the different different
outfit good good we have a bigger library of back photos than I thought so you can pose problems
that we will try to answer all solutions to things we'll try to answer but if you enjoy listening
to podcasts please do check out our problem squared with me and my co-host back hill wow