Can you find: five five-letter words with twenty-five unique letters?
ฝัง
- เผยแพร่เมื่อ 2 ส.ค. 2022
- Five words. Twenty-five letters. Can you find them? That's the Q.
I'm not sure I mentioned this enough, but I have a podcast and it caused this video. Search for "A Problem Squared" wherever you get podcasts and you shall find. aproblemsquared.libsyn.com/
Get ALL THE WORDS as "words_alpha.txt" here: github.com/dwyl/english-words
Here is the vastly superior code that Benjamin sent in: gitlab.com/bpaassen/five_clique
My tweet here: / 1549343218407456769
Against my better judgement, I have put my code on github: github.com/standupmaths/fivel...
You can also see me talk about two lines of the code over on the second channel. • Deleted scene: five wo...
I downloaded the Wordle words from here:
/ a_note_on_wordles_word...
gist.github.com/cfreshman/a03...
gist.github.com/cfreshman/cdc...
3blue1brown video about Wordle: • Solving Wordle using i...
Cheers to my Patreons for motivating me to film a thing from the podcast as a quick youtube video. And helping me justify to Lucie why I need to film a thing while we are "on holidays". / standupmaths
CORRECTIONS
- Nothing yet. Let me know if you spot any mistakes!
That is all! Stop reading the description and go do a better job coding this challenge yourself.
Original question from Daniel Bingham
Filming and editing by Alex Genn-Bash
Additional filming by Matt Parker
Beer by some hotel in Athens
Music by Howard Carter
Design by Simon Wright and Adam Robinson
J̸I̸G̵ ̸C̸O̴U̶L̶D̴ ̶H̵A̵V̵E̸ ̸F̷O̴U̴N̷D̷ ̷A̸L̴L̸ ̵5̵3̶8̷ ̶I̶N̶ ̸U̸N̸D̵E̸R̴ ̶3̴2̷ ̴D̸A̶Y̴S̶ - บันเทิง
There's people out there abbreviating headquarters to HDQRS instead of HQs. This appeared to the author as optimisable
Yeah, I was fine with EXPWY. It was HDQRS I had a problem wit.
Someone was writing to a file way back when we were limited to 8 characters. That's how you get HDQRS.doc. I assume that it then became a thing.
@@dodaexploda (thats 9 characters)
@@-_-.-.._. the extension and dot didn't matter except for the extension itself being limited to 3 characters. But it was 8 characters allowed left of the dot.
Fire comment
"This appeared to the author as optimizable" is a legendary quote with vast meme potential
I really wish he would've said "the Parker algorithm" instead of "Parker's algorithm"
Agreed. Absolutely legendary💀💀
I got it down to 13.7 seconds while still using Python, lol. Definitely optimisable.
I had to give a good laugh at that.
Fr this is exactly what I started thinking when I saw the comments
I think this is a great intersection of Linus's Law, "given enough eyeballs, all bugs are shallow," and Cunningham's Law, "the best way to get the right answer on the internet is not to ask a question; it's to post the wrong answer."
"The best way to get to an optimized algorithm on the internet is to post a naïve implementation and wait for replies."
Should you then post after you ran your own? That still takes a month...
😉
@@landsgevaer you're right, he should have estimated the time his algorithm will take, posted a video 29 days ago, gotten the reply within two days and had the answer way quicker!
Ok Blixor’s Law: If you shake a palm tree hard enough, the train that holds all the turkey slot machine pterodactyl.
@@BizVlogs that's a good one, I'll have to remember it
@@BizVlogs the difference between a duck is that one of its legs is both the same
One fun low-level optimization trick: 32 bit ints have more bits than 27 letters in the alphabet. Since anagrams and duplicate letters are removed, you can just compare the bit patterns.
Can you explain? I don't get it
@@robertr7923 set one for letters that appear in the word, zero for letters that don't. Each word is a 26-bit number up to 64 million or so. So ABOUT would be 00000000000110000100000000000011 or 1,589,251. The nice thing about doing it this way instead of an array of characters or something, is that comparing bits on a computer is very fast. So you AND the two words together and see if the number of bits set to one is 0.
@@letsmakeit110 if you would AND two words with distinct letters in this representation the result would actually be 0, you wouldn't even need to count the bits, very efficient indeed
And fun thing. Someone went and did this and a few other optimizations and solved the entire problem in less than a second.
I used this as an excuse to make the jump from python to C. I created my own implementation of this using your bit trick and it worked wonders (1.5s). Thanks!
I really like that you included your viewer's more optimized code, even though you spent the first half of the video talking about how you didn't want to hear about how your code isn't optimized and you didn't want to hear about it. Stuff like that is just endearing as all heck.
I don't know if you did that on purpose, but you wrote "didn't want to hear about it" twice. Your comment isn't optimized, either, and I love it.
Yo 🔥th-cam.com/video/rdJ9bsN7JAw/w-d-xo.html..
I’m sure that in Matt’s head he was more or less expecting codes that improve the time from 32 days to maybe a week or two.
Not a code that solves the problem in 15 minutes….
And with the follow up code being 3072 times faster (i checked), i guess he just added it on because the extra 15 minutes of verification doesn’t really add much to the total time used to make the final video
@@irgyn this appeared to the author as optimizeable
There is also a difference between, "you should have optimized it using this optimization" and "here is a complete optimized implementation that uses somewhat advanced maths".
To be fair, Matt has never claimed (and in fact, routinely disclaims) that his code would be neat, efficient, or fast.
exactly! and thats ok! hes a mathematician. code is just a tool for him. hes not trained in it
this is a huuuuge difference i keep telling people about. i did a computer science degree. i am a software engineer now. I stand by the fact that programming != computer science
and we see the difference here. programming gets the job done (matts solution (also this is no diss on matt. hes super smart; software just isnt his expertise and thats ok)). Computer science gets the job done well and efficiently (the graph solution). I dont claim I could have gotten to the same solution, but figuring those types of stuff out is the fun bit for me lol
I was shocked that mentioned the vowels are being key but never used their importance as part of the algorithm.
If had put words into buckets that included each vowel and a bucket for y and another without vowels he could have greatly reduced comparison.
For example, if the first word included "a" there is no point testing words from the a bucket, if the second word included "e" you don't check the a and e buckets for the next word etc etc.
Such an obvious improvement.
@@v.sandrone4268 Even better, if he could verify that all the words need at least one vowel (y included) he could just discard any iteration that has at lease two words using multiple vowels (and technically cut out any individual words that use three) to skip a _ton_ of the processing
He's a *lot* faster than I could ever be!
@@v.sandrone4268 If he uses aggressive pruning, I suspect the gain is moderate, since repeated vowels are found immediately anyways. You do gain a bit because you don't need to check all words, but the time complexity is in the size of the expanded tree, and that doesn't improve.
Orange nostril's trick *does* prune the search tree, however.
Q is the 6th 5-letter word to complete the whole alphabet! The other 4 letters in Q are completely unnecessary anyway
Galaxy brain move right here!
The countdown music, the live "photos", the surprise twist at the end tying everything up in a neat bow - you knocked this video out of the Park(er)!
Parker is an interesting combo of a stand up artist and a mathematician. His shows are not for everyone, but they are interesting for those curious in math.
This is called "the Jotto problem". There were papers published in '68 and '96. I spent a bunch of time when Wordle came out doing the same thing, then I searched for the set I found and realized I could have just done a literature search.
You should play Wordle on Hard Mode
@@saar144 beside the point lol
Oh, that brings back memories. Had Jotto as a PBM game, wrote my own program (looked flashy, could be optimized probably to certainly) in Turbo Pascal. Only downside was there was no list of words to download at the time so a friend and I spent quite a lot of time on creating a word list. Only to realize it was too much for the array I defined, so we had to weed out "unused" words. Which would have probably killed this exercise. (Different language though)
How do you code a literature search?
@@shoo7130 Mechanical Turk
11:11 - can we talk about how apparently these notes were handwritten with such enormous pressure that you can almost decipher the contents from the backside of the paper?
No pens or pencils were available so he instead hammered the letters in with a metal stamping kit, I presume
Pen didn't have ink, had to go entirely off pressure, I think
@@coryman125 with a muntz stamp, you mean?
@@feedbackzaloop We've gone full circle!
He didn't have anything sturdy to lean on, so instead used a sheet of playdough
0:42 Lmao, this bit was really well done. Great recurring joke too
10:05 The ‘y’ in glyph is, in fact, a vowel. There are a few rules you can use to determine when ‘y’ is (or isn’t) a vowel, but in this case, it undoubtedly is a vowel.
That sounds so odd to me. In my language (Portuguese), it's so simple to know what a vowel is. If it's A, E, I, O or U, then it's a vowel, otherwise it's not. 😆
@@sergio_henrique ye in english 'Y' acting as a vowel is pretty uncommon, so quite a few people dont even know it does lmao
@@aaronl19 prett*y* common, actuall*y*
Y: the alphabet equivalent of gender fluid
@@sergio_henrique that's what happens when a language is mostly loan words like English is lmao
It would be really interesting hearing Matt giving a deeper explanation of how graph theory was used to solve this problem. It always amazes me how different fields can use different tools to solve the same problem, and that some tools obviously are much more effective than others.
Assuming you know some basic graph theory: If you imagine a graph, where each node is a different 5-letter word, we can connect two words with an edge if they do not share a letter (e.g. "fjord" and "gucks" are connected). The problem we want to solve is finding 5 words that all don't share letters pairwise or in the context of the graph, find 5 nodes that are all connected to each other. Such a collection of nodes is called a clique, and finding cliques of certain sizes is a well-studied problem. Now it is just a matter of going out an implementing some algorithm that solves this problem (Here's the first one I found, don't know if it is what was used: en.wikipedia.org/wiki/Bron-Kerbosch_algorithm)
Benjamin describes it in the GitHub readme - he generated a graph by giving each word a vertex and connecting them with an edge if they didn't share any letters. The groups of words we look for then correspond to vertex sets where each two vertices are connected by an edge. That structure is called a clique, and looking for maximally sized cliques is a well known problem. It's NP-complete in the general case, but this instance is small enough that the algorithms developed for the problem can deal with it just fine.
In this particular case, it isn't so much so that the graph solution is way more efficient. It's just so that Matt's brute force implementation was terribly inefficient 😉. My initial brute force did it in 67 seconds, and using some clever lookup techniques I've got it down to 7. I doubt that can be beaten by using a generic maximum clique algorithm from graph theory.
@@qaysed453 Technically we should already know the exact shape of the clique we're trying to find, so a regular subgraph isomorphism algorithm should suffice
@@kalecgos1 well, a clique is a complete graph, so we always know its shape, aside from the cardinality, so the max clique problem can always be solved by log n applications of a subgraph isomorphism algorithm (this is actually the common proof for subgraph isomorphism being NP complete). I don't know the actual algorithms well enough to tell whether a general isomorphic subgraph search or a clique search would be faster, but the latter is more specific, so presumably it at least wouldn't be slower.
11:32 Even after multiple NYT updates, the code still stores the word lists locally! You can check in the game assets js file. I won't link it here in case Matt filters links, but it's the third script in the source HTML.
Unfortunately, NYT have completely removed some definitely valid English words from the list, so the original is still better. All 4 lists are uploaded to the same github account, iirc
@@user-rv9vk8by5i profanity?
@@rngwrldngnr and offensive words
@@user-rv9vk8by5i To be clear, they removed them as ever being possible answers, but they are still accepted as guesses.
@@user-rv9vk8by5i NYT has only removed ['agora', 'pupal', 'lynch', 'fibre', 'slave', 'wench'] without adding any, so the list is functionally the same.
Including the Countdown music while the efficient code was running: an absolute masterstroke. Well played.
As a software developer this seemed like a wonderful little weekend challenge. So I wrote an initial version and realised I was going to get the kind of times you were initially getting. Then I did some optimisation and then some more and now my release mode software running on a laptop finds 538 results in 15.825 seconds. I'm running C# code and taking advantage of the parallel library but perhaps the biggest leap forward was realising we have 64bits and only 26 possible characters. Now I'm just wondering how I can shave off those pesky 15 seconds 🙂
Could you share the code? It would be awesome to learn from it :) thanks!
@@emorell96 Sorry, I have been caught up for weeks installing a new kitchen. I hope I can get some rather ugly code out there at some point. Meanwhile I should mention that while I'm now slightly below two seconds, I've seen somewhere that some other guy has managed to get significantly below 1 second.
@@NickAskew That's pretty cool, did you ever manage to improve eve further?Still in C# right?
@@jeremyzz Hi. Yes, I've managed to get it to around 2.3 seconds by using various techniques such as Parallel.For(...) and profiling the code to find the bottlenecks.
I should mention that others have managed to exceed this by a factor of about 25 times and I am impressed BUT I do not want to see how they did it because I'm looking to see if I can implement my own idea before seeing how they did it, so if you find out no spoiler 🙂
I'm looking at indexing as an option as my current code is a little brute force. I guess rewriting in assembler would help but that's a step too far, I'll stick with C# and framework net7.0.
So if Benjamiin's code had to run for approximately 1/30th of the day, and your code ran for approximately 30 days, it means that Matt's code was about 900 times slower than Benjamin's, which was running for 900 seconds. I like that.
15 minutes is 1/96th.
So does that mean for every 1 second of Ben's code, Matt's code ran for 15 min?
@@DIMOHA25 Ah, so 15 minutes = 1/30th of a day is a new Parker approximation!
@@DIMOHA25 For anyone who's curious (but not curious enough to do the calculations themselves...), 1/30 of a day is exactly 48 minutes, assuming a typical 24-hour day with no daylight saving time change or leap second.
More like a solution squared than a problem squared!
I just wanted to mention that formally this problem is searching for a maximum clique (subset of vertices s.t. there are edges between all pairs of vertices) in a graph. If we build a graph where every vertex is a word, and we have an edge between two vertices if they have different letters, then a maximum clique will be the answer you are looking for.
Edit: I should not write comments before finishing watching videos.
This sounds like a great topic for a follow up video!
I'd love to see a video on that - right now I don't understand it!
I would *love* to see a video about graph theory by Matt Parker. I will bet he has at least one pal who specializes in it.
Thanks for taking one for the team: I was reading the comments while watching the video to see if someone else mentioned this before posting it myself.
(At least we can feel vindicated that the theory worked out, all without having to actually code it up!)
Yo 🔥th-cam.com/video/rdJ9bsN7JAw/w-d-xo.html..
The "Matt from the future" part with improved code was a good addition. It's a nice demonstration how much extra perofrmance you can get with improved algorithm instead of just using better hardware. You could have improved the code or run the original code on 3000 computers in parallel to get the results in identical time.
Running code on 3000 computers doesn’t make it 3000x faster.
@@gonzalo_b762 It depends on algorithm. For "embarrassingly parallel" problems you can get totally linear scaling. For example, if you're brute forcing 64 bit encryption, you could just split the whole range to 3000 parts and use 1...2^64/3000-1 for the first computer, 2^64/3000..2*2^64/3000-1 for the second computer etc. If I understood the algorithm correctly, Matt was brute forcing the whole range so it would have been trivial to split into parts.
@@MikkoRantalainen Good point. I’m trying to figure out how you could separate it into equal parts given how the output is dependent on all the input though.
@@gonzalo_b762 For example, when you know that you have to evaluate a list of words, you only test words where the index of the word mod N is J, where N is the total number of machines running in parallel and J is the index for the machine running the algorithm. Some other machine will test all the skipped words. (Of course, any decent optimizing compiler should be able to avoid division and just add N for every loop.)
Someone got it down to a tenth of a second running on a 10yo laptop a couple days ago!
Completely off topic to the actual video, but I love the python library used for the progress bars in Benjamin's code. tqdm, just wrap whatever you're looping over (for X in tqdm(thing)) and bam, you get a progress bar! It even calculates iterations per second and time estimates. Very useful and easy to use.
Tip for mac and linux users: you can time commands using the "time" command. So, if you want to time how long it takes to run "python ./python-script.py", you run "time python ./python-script.py". I know you love spreadsheets, but this approach might save you some... time.
Depending on exactly what you want to time, this could give an inaccurate number since it times the entire process including spinning up the python interpreter, not just the algorithm. That said, yes, time is a wonderfully handy command
@@liorramati265 It includes spinning up the Python interpreter which, upon repeated uses, itself is inconsistent. As the first run might be from disk whereas subsequent runs are from cached memory. This is why when tech sites use time $command as a benchmark they reboot the system between runs.
If you're using Python, it's even better to just use the timeit module
@K.D.P. Ross optimized version is sub 1 second
This is actually an older question than you think. On the Netherlands, there is a magazine called Pythagoras, which asked exactly that question. I myself asked some of my friends from the Mathematical Olympiad whether they could come up with any combination. I concluded that is was probably impossible, after checking every word containing Q and X and Y (those are rare in Dutch)
Damn we Dutch are everywhere
What if you allow y for ij as in Old Dutch?
@@thibautsnoeijs but probably mostly in the Netherlands 🇳🇱
Op Nederland?
Yo 🔥th-cam.com/video/rdJ9bsN7JAw/w-d-xo.html..
I mean the topic was intresting and presented in an accesible way and all, but I loved the pictures of BeChill and the Countdown music for the code running. Just hillarious!
that photo joke - gold, now I MUST check it out. Also what a satisfying result with just the 1 set of 5 words using 25 letters, well done!!
What about the ten other sets that he overlooked?
The Countdown music when waiting for the code to finish "building neighborhoods" was a nice touch, Matt.
(Also, thank you, weird TH-cam algorithm, for introducing this American to Countdown during lockdown.)
I thought Suzie Dent was going to come on when you said you've got the ultimate authority on what is a word. But given the stated problem was about Wordle, it does feel like the Wordle list of acceptable words is correct.
He did include the Countdown theme, which I thought was pretty clever. I'm guessing Suzie was a tad beyond the budget.
In Matt's defence, the video did include (multiple photographs of) someone who has in fact sat in Dictionary Corner next to Susie Dent.
@@gregmark1688 It just wouldn't be optimizable.
5:47 Fun fact: If you take the 3,213,696 pairs of words with 10 unique letters and remove the anagram equivalents, the amount of double-words that you have to check goes down by a factor 5 to just 640,023. This could have made the runtime a factor 25 quicker, meaning it would have taken just about 30 hours in total instead of 32 days.
Actually, having 4 words with 20 unique letters is kinda useful on Quordle, Octordle, Sedecordle, and Duotrigordle, in order to practically guarantee that you get all of them right.
I concur. I most often play sedecordle. I usually start with three words that share no letters and cover all the vowels. The results from that usually give me an enjoyable challenge that is doable but not too easy.
You also want to prioritise the most common letters. Cracking the Cryptic loves to use SONIC TRADE LUMPY. SIREN OCTAL DUMPY is the same set of letters if you prefer base 8.
@@DeGuerre Indeed. I follow that same principle but rather make up my starters each day. My most recent set was PRUDE MINTY GOALS, which differs only by C/G. I’m sure and C is marginally better, but it’s not a bad set for something made up in the moment.
That's what I do.
Usually using WEIRD-FANCY-GHOST-PLUMB
CAMPY WOULD BIGHT FERNS
Bec's "photo" coming up from the bottom of the screen is amazing!!
"This appeared to the author as optimizable" is one of my new favorite lines of Academic Sass
I almost lived this. I once guessed:
GIVER
DWARF
JOCKS
EQUAL
BLITZ
and finally got the answer of the day NYMPH. I repeated E, I, L, R, and A once each so it isn't what Matt Parker is looking for, but it sure had me sweating looking at a sea of only grey squares by the end of guess 5.
that s insane
That must have been scary!
If I may, though, that's not necessarily a great approach in Wordle - since you can change your strategy based on the feedback from each submitted word, and positive responses almost always contain more information about the solution than negative ones, you want to front load the odds of getting any kind of positive result in the first word to narrow the search space as early as possible ^^ Frequent letters are good, and packing in vowels is great because it's a much smaller search space which in practice will always contain at least one positive result.
That's min-maxin to get the answer in as few hits as possible, though, which of course isn't the only way to play it or to have fun ^^
What the heck is a glent brick jumpy vozhd waqfs?
Dubious. If first guess GIVER gives no hits, who would then have an R in the next guess DWARF?
@@MartinInBC people aren't machines. sometimes u wanna live a little lmao
The sheer hubris of live editing in your podcast cohost is so wonderful
I am highly suspicious that the "photo" of Bec was just Bec going up and down trying to be stationary as possible lol. Such a Bec thing to do!
Also, at 16:49 "OK, I am Bec" - No, silly, you aren't Bec, you are Matt!
I'm thinking the same thing. I could swear I saw some movement other than the up and down.
You may be on to something here.
There are so many times in Matt Parker videos where I am just like, "did that really just happen?"
That's the gag
@@michael1 Ahh the obligatory comment of the person not getting the sarcasm and explaining to the sarcastic jokers they did not understand the joke, thereby ironically not understanding theirs. Classic
I like how you went to the effort of super imposing a shadow at 0:48..... its almost as if the photo wasn't a photo at all.
You must have done a full VFX 3d reconstruciton and reprojected the image as an image texture. Corridor ditgital would be proud. The attention to detail is immense!
Those were videos, though, not images.
@ "it's almost as if the photo wasn't a photo at all" 😉
Love the Countdown clock theme over that program bit. Good touch.
In addition to “building neighbours” there should also be “reticulating splines” “calibrating matrices” and “sidefumbling wainshafts”
"Calibrating matrices"? You can’t just add an engineering word to an algebra word and hope it means something. Oh wait, looks like something’s wrong with the manifold tesselator.
manifold tesselator sounds good for packing suitcases
I can hear the build music now
@@KyleJMitchell yes you can
Aren't we all?
I was surprised you didn’t start off with a “how many have none of the vowels”, since that eliminates any word with three or more vowels.
Unfortunately (as you may have seen by now) some "valid" English words don't have any vowels
@@Henrix1998 technically y is a vowel in those cases
@@thepardigon178 phonetically, yes. Orthographically, no.
Maybe filter instead by lack of vowels and semivowels (w and y in English). Basically every valid word without a vowel has a semivowel.
@@Henrix1998 yes, but I suspect that all ‘real’ words that don’t have a vowel have a y… hence being able to eliminate those with three (not just two) vowels.
I LOVE how we just had a video conversation that no one else I showed the video with understood. You are truly a great story teller for the programmer! Horray!
Thanks for making a video about this! I tweeted a related question to you a few months back, but this one seems more appropriate for your channel.
the optimized version is fast entirely due to algorithm, too - both versions are written in python and neither use a fast external library like numpy. If the optimized version were ported to something like optimized rust you could probably get the time down to the seconds range
I don't think seconds but maybe minute or two
once again, rust is inevitable
Or just do it with constexpr and consteval in C++ (assuming we don't time the compilation time, of course).
@@xarcaz bruh that's not IOI
🦀
The title alone makes me think this is about Wordle.
It’s Parker about wordle
Wordle inspired which is pretty close.
I've been learning Python recently, so it was fun reading through both sets of code and seeing how far my knowledge of Python has come in the last couple of weeks :)
Listen to the problem squared episode yesterday, excited we get the video as well. Love the podcast, only recently caught up having started at episode 1.
You have to love that, in a segment about Matt writing bad code, he uses excel to find the difference between two variables that he defines. At least do something like _now = time.time() ... print(now - time.time())_
yeah i cringed when he did that
Or just type "time" before the command.
I thought the same thing 🤣
start = … finish = … print(finish - start) is more usual. But hey, any excuse to use Microsoft’s bloatware, hey Matt?
see this is a huuuuge difference i keep telling people about. i did a computer science degree. i am a software engineer now. I stand by the fact that programming != computer science
and we see the difference here. programming gets the job done (matts solution (also this is no diss on matt. hes super smart; software just isnt his expertise and thats ok)). Computer science gets the job done well and efficiently (the graph solution). I dont claim I could have gotten to the same solution, but figuring those types of stuff out is the fun bit for me lol
"Vingt"... your pronunciation of this was beautiful, considering it's just "twenty" in French.
yeah... caught me off guard lol
10:56
And in true French fashion they use 3 times more letters than they need, considering how they pronounce it.
@@matthewwhiteside4619 The 'g' is pronounced. It's very subtle, but it's there. The 't' might also be pronounced, too, if you happened to have multiple "twenties", as in "les vingts". ;^)
@@gregmark1688 The 'g' is definitely not pronounced at all lmao, the 't' indeed might or might not be (depending on context and accent)
The first rule when running a program: The Cup of Coffee Rule. If it doesn't finish when you have finished your coffee, interrupt the program and find a better way! This is what I teach all my students. I am amazed that Matt had confidence that his program was going to give any useful result after so long. I would be expecting zero or infinity.
The exception to this rule is lots of scientific or mathematical problems, especially simulations, but can also be combinatorial problems of the type in this video (of course in this case it was optimizable but to be honest if you have other stuff going on sometimes it really is easier to just set the code running and come back to it when it’s done rather than spend Time making better code.)
@@interlooper83 but you almost always need to re-run it, or some one else will need to verify it. If you are a 'good' programmer then you won't need to spend time writing code that never finishes. You can think up a better approach while drinking your coffee. Especially with Python, which is used extensively in scientific problems now.
My expectation is that simple functions should finish quickly. I try to set similar expectations in the minds of my students. It's not hard to replace the shell sort with quicksort if you are competent you will know that quicksort exists. Even with simulations that may take hours (surely not days!) you can provide a progress log to monitor the state. Perhaps partition so that the time is divided by n times. It is easy to add in timers to see where the time is being taken. It is easy in python to import modules that are compiled code instead of reinventing the wheel using python. It is easy to isolate a function and optimise it with cython to get 100 times speed improvement.
Maybe the approach to a simulation is using the wrong variables that are not converging. Maybe you didn't realise that your system does not scale well. So you start with a sample and then release it on a large dataset. Well then, that is when the Cup of Coffee Rule kicks in: interrupt and think about what might have gone wrong or how you can shorten the time. Time is money and also your own valuable attention. Leaving a problem for a week seems to be a waste of both to me. If you are using the cloud a week's processing will cost a fortune.
I am still not impressed with any workflow that takes days to complete. It just makes you look amateur.
@@kimollivier He is amateur, he stated that multiple times -_-
@@interlooper83 when I'm on such a problem, I'll always try to spend some time producing a sample set. Need to calculate all the roundabouts in the world? Start with all roundabouts in Iceland. Must find how many days were warmer than average since jura? Start with last two months. Even if making the sample costs days, you'll eliminate the chance of having to rerun a computation that takes days.
@@kimollivier I think this philosophy might be fine to teach in any introductory programming class, but it is naïve in the real world. Many fields in computational science are limited by computing power, and the reason is because some things just take time. Do you think it simply never occurred to the people whose algorithms take hours or days to run (even on the most advanced supercomputing clusters) that they should try to optimize their code?
10:08 Ah! Something I learned in a K Klein video: apparently in the UK they teach that the vowels are aeiou, where here in the US we’re taught aeiou and sometimes y.
Dude!
Keep doing what you do
I love your videos. Sometimes i get it sometimes not, but always I'm entertained.
Your enthusiasm and passion for your subject is infectious.
😊🍻
"Vibex" sounds like an old-people medicine that will be marketed to GenZ one day.
Congratulations on 1 million followers!! I've been away from YT for a short while, and awesome to see you reaching that milestone
Matt: "Don't send me ways I could have improved it"
Also Matt: "This is the maths behind the way I could have improved it"
Given the purpose of the search, each word (or even each valid word combination) could be represented by single 32-bit (or rather 26-bit) integer with only bits corresponding to used letters set to 1. That alone can save quite a lot of time on checking for collisions and collecting valid results, including pretty much automatic pruning of anagrams.
I wonder if, using that method and written in C, it could be done in under one second given a powerful enough computer. I'd say probably.
I did this, and I get results really quickly
Yes, that's a great hashing algorithm for this purpose. You're just looking for 5 hashes with no bits in common.
I basically wrote a version of that back when wordle blew up. Depending on the word list, the whole search took anywhere between a few seconds and minutes. Getting a decent wordlist that isn't full of straight up junk words was the hard part, and in the end I could only come up with sensible combinations that had 24 unique letters.
@@nicholasvinen Average C user when python is mentioned.
/s
Did you check whether all the "worlde words" appear in your initial database? If the former isn't a subset of the latter, maybe some sneaky wordle words could give you another solution. I guess you could just run your original code on the wordle list and check whether you've missed a five-word set in the initial result?
'vozhd' and 'gymps' are in the wordle list, but not in the original wordlist, which leads to some extra worldle solutions
@@whyando What are those extra solutions?
@@stefanpochmann5205 I ran a search a few months ago and remember finding ~9 including waqfs. I only remember this one off the top of my head, but you could just run the script with the improved list and find the rest:
waqfs, vozhd, jumpy, glent, brick
Matt, I used visual basic for applications (VBA, comes with Excel) to find 10 combinations using a list of Wordle words from which I excluded anagrams and words with repeated letters.
The program uses a 26-bit bitmap of letters to quickly compare words to ensure no duplicates. At each point in the recursive search, I only consider the subset of wordle words not containing the letters used so far. This way, I spend my valuable computing power to make subsets, avoiding the need to do pairwise comparisons of words to see if they have letters in common. The program completes in well under a minute.
The program finds 10 combinations of 5 words:
1. glent, prick, waqfs, vozhd, jumby. Missing letter is x
2. glent, brick, waqfs, vozhd, jumpy. Missing letter is x
3. treck, pling, waqfs, vozhd, jumby. Missing letter is x
4. treck, bling, waqfs, vozhd, jumpy. Missing letter is x
5. kreng, clipt, waqfs, vozhd, jumby. Missing letter is x
6. kempt, waqfs, brung, cylix, vozhd. Missing letter is j
7. cimex, waqfs, blunk, grypt, vozhd. Missing letter is j
8. gucks, waltz, vibex, fjord, nymph. Missing letter is q
9. bemix, clunk, waqfs, grypt, vozhd. Missing letter is j
10. gymps, waltz, vibex, chunk, fjord. Missing letter is q
That said, Chrome doesn't think glent, jumby, treck, kreng, clipt, brung, grypt, or bemix are words, leaving number 8 as the only one Chrome would agree with, which is the same one you found.
It's not exactly fair to say "Wordle words" when waqfs and vozhd definitly would not be legal words in Wordle.
... wait, would they?
@@tomdekler9280 As a matter of fact, both "waqfs" and "vozhd" are valid guesses, even now that the NYT took it over. I just tested them to make sure they work.
You did that in visual basic? Bro who hurt you 😆
Great content. Loved your pruning and the graph theory was a slick bonus. Bec was funny.
Strongly suspect that that wasn't a photo of Bec Hill but an actual Bec Hill. Trying to save costs on the special effects?! /s
DisguisedToast was doing this strategy for speedrunning wordle like half a year ago in which he would put as many disjoint words in a row. He always put in "fjord waltz quick nymph gybes". There's a repeated Y in the last word though so I guess he found 4.
gvbes
I love how A Problem Squared is leading to more and more Standupmaths videos
This is the kind of crossover content I support through patreon for the podcast and this channel. :D
So delighted and impressed by your work as always, Matt - and super pleased that your interaction with Benjamin spawned a meme! "This appeared to the author as optimizable." Golden
I absolutely love the improved version of the code. I'm not a programmer myself, but the field fascinates me*.
Just seeing how clever and quick the solution is compared to brute force comparisons is just such a delight ♥️
*(I am trained in what one of my professors called being a translator between non-programmy clients and the programmers who make their products because the two groups can't communicate (the client doesn't know the difference between what they need and want. They don't know how to ask for either. Programmers don't understand their need or want or how to implement their ask in a way they understand. So I first suss out what the client actually needs, translate that to a graphic both parties can understand, and then give the programmers the parameters and requirements of the product)).
that's a chunk of my job too - but without a diagram usually :)
Matt's mattes have become very excellent! First of all, the key on the chroma screen is pulled very nicely and cleanly, and second, the edge shadow when elements are composited behind him is just... chef's kiss!
Hell yeah! Nice follow up to the problem squared pod episode :)
I'm not sure precisely why, but this video hit me right in the giggles. I haven't laughed this hard at a TH-cam video in a long time, so I just wanted to give a genuine thanks for this Wednesday silliness. Proud to be a Patreon supporter!
Thanks for making this mid-week silliness possible!
It’s always a good day when I get a video from stand up maths
Hahaha that reveal. Showmanship at its finest.
Those photos are amazing. So lifelike!
Matt! Thanks for giving all us programmers a momentary feeling of superiority! So nice! Literally every one of us were thinking, “Am I missing something?? It can’t possibly take that long...” and then nodding sagely at the end. (Even though most of us don’t know graph theory from our elbows.)
If I were you, I would pick some mind bending math for the next video and put us all back in our places as the bit jockeys we are.
Bec is an absolute treasure 😄
I took a coding class last semester and challenged myself to write wordle in my own code. I ended up doing it in about 850 lines. It also has a feature where the user is able to look up any word and it will tell you the day it is going to be used as a wordle puzzle. This just accesses the wordle database of answers and calculates the day. Pretty cool. I was proud of myself for doing it after only starting coding this year
The Wordle word list is created from the "web2" words list, found on most BSD-based Unix systems (e.g. macOS) at /usr/share/dict/words -- this list contains all words from the Webster's New International Dictionary, Second Edition.
The fact that you got any version of your idea to work is a win. I have a program I'm trying to write that's only 1/10 the size of the Parker Program and it's got some design flaw that I can't figure out. Eleven lines and I can't get it to work. Take your win Mr. Parker, you deserve it.
Maybe put it on stackoverflow?
.. Damn, That photo was almost life like 'o.O
There are definitely more solutions than this which work in Worldle. One example is BRICK GLENT JUMPY VOZHD WAQFS. I guess your dictionary is missing some words which are in the Wordle dictionary, or maybe some words that you have which are not in the Worldle dictionary have anagrams which are?
Yeah it would be best if the wordle list was put into the beginning steps of the process again. Perhaps even you or I could do it and find a few more solutions.
I've been sitting here this whole video thinking about how to structure the words list in order to trivialize the work of finding matches, so glad to hear somebody else already did it so I don't have to!
I loved this episode in the podcast and I'm loving this video. I find it really satisfying that there's just the one answer.
There are eleven answers.
There's another wordle-valid set:
GLENT, BRICK, JUMPY, VOZHD, WAQFS
The latter two words are loans from Russian and Arabic, respectively.
I assume whatever word search he used those two had to be excluded (they are missing in some online dictionaries)
This feels like that issue with traveling to another star, where the first people to leave Earth are likely to meet humans when they arrive. Because it takes less time to both invent faster space ships and travel there, than the initial travel time.
Just imagine the looking at each other like 😳😳
I just started running your code. I'll check back when it's done.
I love this! I was so invested the entire video, best topic for real
I did a janky version of this puzzle with wordle and got 19 letters in 4 words which i was pretty happy with
Thanks for explaining the graph theory optimization.
Bonus problem: how many solutions are there to the set cover problem of using six 5-letter words to cover the entire alphabet?
What a beautiful and satisfying solution and final answer!
What about the ten others that he overlooked?
This video really helped me. Thank you very much!
Uhm, Y is definitely a vowel in "glyph". :-)
Edit: And you can time a command from the command line by just typing "time" before it.
In England, Y is not considered a vowel for some reason, despite the fact that it is literally a vowel in that usage lmao.
Using the Linux time command would also report how long it took to spin up the python interpreter, not just how long it took his code to run. Timing it from inside the python code is going to give a way more accurate result in this case (even if doing print(time.time()) twice and then subtracting the results in excel isn't the optimal way to do that 😅)
@@liorramati265 Spinning up python, importing the libraries used and shutting it down takes between 0.05 seconds on my old laptop. It's not going to change the measurement outcome significantly of anything that takes over a few seconds.
So, I appreciate the method and the story behind the progress here.
But, once you had decided to use the wordle dictionary as your source of correctness, surely the best way to get the final solution would be to perform the original search on wordle's list. Rather than comparing the list to the one found by the original search.
But he would have to wait another month for it :D
That would be a more efficient way but it would still produce the same only solution
@@robertr7923 Nope: there's also:
jumby
clipt
waqfs
kreng
vozhd
in the original wordle list!
One of my favorite bits of trivia about words and letters...
20% of the words are used 80% of the time and, yes, 20% of letters are used 80% of the time [I believe] in any language.
The "photos" cracked me up. Nicely done. :D
Correction: There are more than just one by Wordle definitions, if you include words that are not in the original wordset provided by Matt. Among others, this includes vozhd, waqfs, and gymps. I found 11 sets of five, using my own code and the original wordle dataset (it took under 10 minutes). I think other people have already mentioned this elsewhere in the comments.
For example,
bemix, clunk, grypt, vozhd, waqfs
chunk, fjord, gymps, vibex, waltz
Out of the ones I've found, I still agree with Matt that the one he presented was the best.
You're right, all that has already been mentioned.
My first instinct when seeing this problem was that this could be solved as an exact cover problem using algorithm X. It's been a long long while since I used it, but guessing from the size of the problem it should be faster than finding complete graphs.
It's also a fun excercise to implement if you feel like spending an evening coding.
I'm not sure if you can call this an "exact cover problem", because english has 26 letters, not 25.
@@BenjaminGoldberg1 It is not exact cover problem, but you can use that algorithm anyway
I'm glad someone else optimised that code, it saved me going out and doing it myself.
Though I was going to use hashtables/dictionaries to do it - the graph theory bits are nice.
22 minutes is now down to 10 seconds.
Congratulations on reaching 2^20 subscribers!
Wouldn’t removing the anagrams limit your comparison to the wordle list? You could be throwing away ‘real’ words and keeping the ‘bad’ alternate
I thought the same, indeed.
But since he does use a reasonable trick to retain the most common one, it would only happen if Wordle contains an uncommon anagram of a more common word that it doesn't have.
Matt later checked that restricting it by anagrams gave the same number of solutions.
You can bring them back later by a relatively simple anagram search
Oh, a new hangman cheating set! Thanks!
So glad to see all those unique photos of Bec included
Those Bec Hill photos were so life-like. I could swear they were moving.
3:58 Now interesting enough, 5977 choose 5 different options isn't that bad provided you have a quantum computer. It only needs to check up to square root of that number, so if you can check a million per second, you'll end up spending 4.2 minutes instead of 2000 years.
So perhaps the first solution of simply a bigger computer in this case isn't such a bad idea!
"provided you have a quantum computer" is a bit of the problem there then, isn't it
That's a very interesting topic for me, could you please provide any link to an quantum algorithm which does that? What exactly do you mean by "check by the quantum computer" and why you think this problem can be managed that way in a quantum computer? My understanding - at least based on the description - a regular graph algorithm isn't a good fit for a quantum computer?
@@TaranovskiAlex en.wikipedia.org/wiki/Grover%27s_algorithm
Basically, you can do unstructured brute force search in O(sqrt(N)*check) time, where N is the number of possible solutions, and 'check' is the time required to verify a potential solution.
-but wouldn't you also need on the order of (5977 choose 5) amount of time to compile the oracle since its so irregular?- Actually, I guess you could incorporate the knowlege of the graph edges of valid pairs of words in just an order of (5977 choose 2) time, then maybe the instructions for confirming a K5 graph is very regular? And that sounds like you would get the speedup as it's much smaller.
-And wouldn't you need a quantum computer with a register of (5977 choose 5) many quantum bits?- oopsie
@@JNCressey Incorporate a preprocessed word table as part of the problem, so only q-bits for the word number are needed.
"Vingt" is pronounced /væ̃/ and means "twenty". Homophones include "vint" (came) and "vin" (wine).
If he didn't already know that, and deliberately mispronounced it as brutally as possible, I will eat my own legs.
And "vain"
While working on creating a decision tree for Wordle using SAT I used a similar problem as a stepping stone to learn how to work with SAT.
Instead of trying to find every set of 5 words without letters in common it just searched for the first valid set it could find.
The resulting CNF DIMACS file has 5202 literals and 17477630 clauses and when run results in the following 5 words:
chunk, fjord, gymps, vibex, waltz
Really interesting to see this exact problem on this channel, a really pleasant surprise.
Being left with just one could not have been more satisfying, nor more astonishing.
There are ten more, though.