ฝัง
- เผยแพร่เมื่อ 20 ก.ย. 2024
- This video was made for 3Blue1Brown's 2024 Summer of Math Exposition #SoMEπ #SoMEpi
Real-time Anagram Suggester: www.ikebot.dev...
The original episode of Taskmaster: • Series 13, Episode 4 -...
Matt Parker's Wordle video, which was used as inspiration: • Someone improved my co...
A showcase of the making of the real-time anagram solving software I wrote to aid in a speech-writing task in an episode of Taskmaster, and a look into the optimization I found to make it run super fast using bitwise operations. If you are interested in optimization algorithms or creative writing--or you're just a fan of Taskmaster--this video is for you.
In response to Javascript maybe not being the right tool: In the words of Matt Parker: You gave it a go, and that's what matters.
For something that isn't super important, I'd say that the best tools are the ones we can use.
The thoughtful approach to the problem is also a factor. A good algorithm in Javascript will do better than a naive attempt in C++.
Along the same line - just because JS is slow doesn't mean its bitwise operators are trash. They still map to cpu instructions under the hood so are going to wind up faster than doing the same equivalent math with loops and non-boolean operators.
Thank you! From looking online it was unclear to me to what extent the js binary operations directly map to cpu instructions, or if it's more abstracted. The binary operators definitely aren't worthless, they're in js for a reason. But I figured it was worth a disclaimer. Maybe someone who knows a faster language could rewrite the program and compare. And experiment with other optimizations while they're at it.
@@allaryin JavaScript engines will also JIT (Just In Time compilation) the functions/code so (except for the first few times it's called) will be nearly as fast as a statically compiled language. A lot of research has gone into making JavaScript fast when the input types are stable and the code is running in a hot (long running or frequently called) loop.
"I am OK; adding letter pairs on a whim that can use man-provided flag pieces is my kink."
Okay, I think you win this one. No other comment will ever beat this.
🏆 I love it! The first solution I've seen that uses every letter with no compromises (gramagrams, abbreviations, acronyms, etc). Unless you count "OK" but I think "OK" is an official spelling in some dictionaries.
@@Ikebot Surprisingly, OK is actually the original spelling! it came from a joke spelling of "oll korrect" (all correct) and people saying it out loud sounded like "okay".
@@Nerdy1729 That's a common misconception, but it's not actually true.
@@GoldenSandslash15 Nope! I did research into this a while ago, here's a quote:
"Origin disputed... of which the most widely accepted is that it is an abbreviation of oll/orl korrect, a comical spelling of all correct, which first appeared in print in The Boston Morning Post on March 23, 1839, as part of a fad for similar fanciful abbreviations in the United States during the late 1830s. The expression became popular through its use in the presidential campaign of Martin Van Buren in 1840, who was nicknamed Old Kinderhook, and then slowly acquired other meanings.
The Choctaw word oke, okeh (“it is so”), common in Choctaw translations of the Bible, could also explain OK's variety of affirmative definitions. Additionally, okeh was the most common etymology of okay in dictionaries until the 1960s, and linguistically predates Boston's O.K.. However, this theory suffers from the fact that the Choctaw language was relatively obscure and generally spoken (sometimes in a pidgin form) mainly with African-American slaves."
My favorite anagram is one I learned when my friend and I were playing with one of those anagram solvers. He typed in the name of his favorite band, "Infected Mushroom".
It spat out "Techno for Dummies".
Jack Lance has made some of my favorite anagrams. All of the letters in the following code anagram to "Fibonacci rabbits":
for(int i=0; i++
One of my favourite bands, Optimus Rhyme, have 2 albums that are anagrams. "School the indie rockers" and "He dies in rocket school"
that's incredible
Is that a joke? Because they are not anagrams of each other.
@lordofthe6string first one has 2 Rs and the second only has 1
The one thing I learned from taskmaster is that you always look under the table
If I was on Taskmaster I'd constantly be turning the room upside down before starting anything
Debajo de la mesa
I think Sarah Millican killed off that one :-)
But can program check under the table??
Yes it can
Check this out
console.table(jsonResponse);
if(jsonResponse.length > 0) {
//Do sth
}
Or combine two letters to produce a new letter?
My attempt at this task (gave myself only 20 minutes, but allowed myself to use your tool, and ended up using every letter):
"Once a piece of knowledge appears, it must say viral things. I'm adamant, kid. Drink him."
🏆 Complete sentences only and no compromises to the grammar or spelling. That's so impressive for just 20 minutes
Splendid! I love programming and Taskmaster, so a nice piece. My, I had fun with it.
(Couldn't get rid of the two 'a's, and 'k's, haha.)
🏆 Perfect! May I recommend the "ak" strategy?
the first optimisation that jumped out at me was to only do the one letter comparison for the letter the user added/removed (maybe with a bit of caching)
Me when copy-paste exists (I have forgotten to update the code to handle that and now everything is broken)
That's a great idea, when the user adds letters to their message, just remove words in the current suggested word list instead of building the entire thing from scratch every time. I'm not sure how it would work when the user removes letters from their message, I'm sure someone smarter than me could figure it out.
@@Ikebotcaching the words that you removed for each letter.
Let's say the user types an "o" and now you remove "dog" and house" as these are clearly(!) the only two words with an "o" in them ;).
Now if a letter is removed, you can add all the words back to the pool.
It’s interesting seeing people who share things I like (Taskmaster) combine it with things that are outside of my interests. Very cool!
hark! well made program, it messages machine of constant keypad input. dank vid, iiii
🏆 I love the Roman numeral strategy
Mm what a slick program you designed in this vid! And fleek animations. Epic, peak art.
🏆 Fantastic! And also thank you.
this is such a good video idk why it doesn't have more views ?? i guess the rest of the internet isn't thinking about taskmaster as much as i am
oh they have been as obsessed, they just haven't found this one yet
I think it's a great video but the title and thumbnail aren't exactly perfect clickbait
"I spake real lies; wham!" is truly inspired.
Man, I wanna see that cat one more time.
Thank you for the cat breaks. They really helped.
"I faked depth, keep a grip. To whom it may concern: a divined skill in anagrams is a must."
Oh my god this is the most niche combination of my hyper-specific interests I love this
I know the agenda for this: marked speed uptick mainly via minimal data processing.
🏆🏆🏆 Ok this one may be the all-time winner
Great video! Had fun with your program. My take:
"Dear taskmaster, in my opinion those red flags implied cheating. Kinda wack. Aim up! V."
With "V" left i had no more braincells to spare so let's say i managed to match taskmaster's tip. 😅
🏆 I love it! The first one I've seen to mention the red flags
Thank you for killing the sandman at the end
Nice cat, btw
Great video, the quality from new youtubers is amazing! I saw this episode the other day and this is just great! You got yourself a new subscriber.
What a great video! The editing is amazing; making those little cat breaks, the music, the animations, just perfect! Can't believe you're not famous yet... Keep going!
This reminds me of a leetcode problem find max value within window. Because we are only modifying the letter pool at the cursor, the rest of the letter pool is unchanged and recalculated over and over unnecessarily. You may want to look into the KMP algorithm as I believe it was the optimal (though not easily implementable) algo for this.
Insanely good video bruh keep it up
Is this correct? I think so, but feel free to check my counts:
A path awaits! Time is infinite.
Aim, rise, and take hold.
Keep moving.
Dare to inspire. Stand tall.
Strength is in you.
Make it happen.
Here's a quick attempt that kind of makes sense: "Look under the desk and make an anagram within limits of massive cryptidic pipage"
🏆🏆🏆 Wow this one is probably the best one I've seen yet, that's amazing! How much time did this take?
I'm imagining a contestant decodes the red flags, looks under the table and sees the Greg Davies video, and then just writes this speech anyway to show off
Oh yeah, definitely
I don't remember how long it took but I reckon it took well under 20 minutes, the hardest part is finding the last few words that fits with the rest
I love anagrams (even made a more primitive anagram helper tool myself once), and that is one of my favorite Taskmaster tasks, so I'm glad to see this in my recommended. :)
I feel like you made the bitwise operation more complicated than needed (though probably not slower). Instead of looking for failures, look for success. So you just do a bitwise AND between the two, and if the output equals the word bitfield, then you found a match.
That's a good idea, I didn't think to check for equality with the word bitfield. I only thought to check for equality with zero
My attempt: "And if i did Taskmaster, my language machine appropriates lives with one dim knock"
Excellent! Here's my attempt:
A key detail changes how environmental issues mark a damp format: "I'd nick pi digit"
(P.S. It explains why I wouldn't be able to participate in Matt's calculations as I would cause a tsunami of tears)
(P.P.S. That definitely wasn't written after I solved the anagram)
Commenting for the sake of the algorithm. This was a good watch and it deserves more recognition!
Another idea instead of bitfields could be to use vectors/matrices. That way you can easily encode the letter quantities, and instead of 26 comparisons you just subtract two vectors. Should be a lot faster than loops and ifs, even in JS.
My attempt: "I am king Ammu. Apply what visions I declare: Go, think, make it, proceed and end as first."
I love taskmaster (especially series 13)! And I love 3b1b! And I'm a CS major learning C++! It's like this video was made for me omg thank you ^_^
I absolutely love this! Taskmaster, math, and computer science. What could be better?
Im always down for these „I wrote a software for x“ videos but each and every time I am surprised the video maker actually explains the code and all that. I understand nothing, nodding happily along and stay for the results 😊 great idea and video 👍
wait why isn't this super popular yet wtf
because it was uploaded 4 days ago by a channel with only 400 subscribers
I did something like that in the 80's to quickly search a database -- on floppy disk. I actually used a 32x32 bit square noting letter combinations.
I note that if it's a *speech* , it doesn't have to be spelled entirely correctly.
The clip you showed at the beginning had upside-down flags. So, you need either-or letters, so the pair is removed if you use either of them.
Great vid! Meathod was genius. I press red channel notification pad
(Trying to say "Subscribed" with the letters provided was a nightmare)
Really cool video! As someone with no understanding of code whatsoever, I appreciate the cat breaks
Really nice video and explanations! I will try out your anagram solver to see if I can come up with some interesting anagrams. It seems very useful for creating some hard puzzles
Looking at the problem, I think a slightly faster algorithm would be:
* Create a list for each letter-number pair, for digits 1-9.
* Each word gets put into the lists for the count of each letter. For example, "Terrible" goes into the T1, E2, R2, I1, B1, and L1 lists.
* At the start, all words are available if the word list has sufficient letters to spell them (this first step can be done the slow way)
* Whenever the user types a letter, look at the word list for how many of that letter remain in the pool +1 (for example, if the user types an O, and there are 2 O's left in the pool, look at the O3 list), and remove all of those words from the pool.
If the list of available words is stored in a reasonably efficient data structure (for example, a binary tree), I would expect this to take less than 1ms per letter added. The downside is that it doesn't support backspace except for by recomputing everything from the start.
This sounds like a great idea, I think another commenter suggested caching which words are removed from the suggested word list as the user writes their message, so that if the user backspaces, the program can add suggested words back in by referencing the cache instead of recomputing everything.
My main concern with storing 5 or 6 copies of every word in the wordlist would be approaching memory limits. Although from my math and Googling it seems like it may only be an issue for particularly old browsers/devices. The new word list would use ~550 MB at most, but storing index references to the words instead of copies of the word itself would reduce that number.
That cat interlude gained you a subscriber today 💚
Awesome idea and execution!!
Why do they call it oven when you of in the cold food of out hot eat the food? ->
you! ten cent to vitally delete the food!
"food, of in food, ow ow ahhhh touchy"
you! ten cent to finally delete the food!
I!
"to food.. food! ow! ow! vahhhh! touchy"
Beautiful, I'm glad to know that rearranging the letters makes it no easier to understand
Such a good video!
The year is 2030, coding interviews have moved on from leetcode. The challenge? Solve Taskmaster tasks.
It would be so cool if the program could write sentences on its own and not just suggest words, but I don't know how to do it 😂
Someone smarter than me could probably get a large language model like ChatGPT to write a speech using these constraints somehow. Kind of like Tom 7's recent video where he gets an LLM to do a different kind of constrained writing (suckerpinch on TH-cam).
Otherwise the program could maybe rank words based on likelihood using the kind of predictive text algorithms that mobile keyboards use.
My program just ranks the words based on their frequency in English, so "the" will always be at the top of the list if it's spellable.
@@Ikebotwithout some form of encoding, like LLMs do, it will be about as good as 2005 Google translate.
If you only used words from a dictionary, it's a good helper tool for a real brain but it would lack forms of words, wouldn't it?
Let's say "it would lack form of word" (only base forms used) is possible with the pool of letters but there are less than 2 "s" left in the pool. The suggestion of the base form is suddenly pretty weak because it makes no sense, grammar-wise.
I reckon this is an even bigger problem if you tried it in another language where forms of words are often more complicated than adding an "s"
You have made me think I should watch Taskmaster.
I'm impressed you didn't go down the LLM route and have AI complete a sentence.
AI doesn't know how to do letters. It only stores whole words (whole tokens) in its memory. You ask it how many R's are in "strawberry" it will insist the answer is 2.
@@NixinovaMC right. But you could use the list of suggestions from the LLM and filter it by available words. Then repeat that until all the letters are used up.
task master AND matt parker?? like
I like frogs. we should make them participate in society, and parks, inn and div gamma.
Great vid! Awesome idea to use bitfields
4:44 spotted a mistake, a bitwise negation operator is ~, not !
I'm coming from python so my symbols might be a little different.
& is binary `and` with ! Being boolean not
He could have used ^ which is *i think* boolean xor and done it with one instruction rarher than two.
So instead of (a & b) !=== c
It would be a ^ b !=== 0
Thanks for catching this, I was confusing the binary not with the logical not in Javascript.
@@xxlarrytfvwxx9531 Unfortunately I don't think XOR would work because that would cause outputs of 1 in digit places where the letter pool has a letter that the word doesn't (as opposed to the other way around), which I think would cause the program to only suggest anagrams that use every letter (full anagrams) instead of any number of letters (sub-anagrams).
the video is most inte'esting, i used for cracked anagram, plainly, madam pikin; "ahkpw!"
I remember watching this episode and having the same idea, I paused the episode and wrote a program like this to try and figure out the answer before watching it in the episode: I came out with something about "I'm cavalry" :|
I was wondering if other people had the same idea. I'm curious to know how your program worked, do you still have the code?
@@Ikebot Yes, but not sure if I can post it all here. It's in Python by the way :)
Basically there's a function that finds a word that can be made with the letters inputted, it runs that on the letters and then removes the letters that word used from the original list.
It keeps doing that until there's only a few letters left (like a q and a z or something, that can't be made into a word on their own - my word list includes some words with an apostrophe but none with an exclamation mark so that's always left over) and returns the list of words and the remainder letters.
Then it runs that again a bunch of times (shuffling the letters) to see which collection of random words have the least remaining letters!
What it definitely doesn't do (but it would be cool if it did) is sort the words to make them grammatically correct 😅 ...🤔
Modern JS is actually decent for bitwise operations of 32 bit integers, at least if all the variables and members you use as 32 bit integers always remain 32 bit integers (so the VMs can make the assumption that it won't change type to speed things up).
Yeah, in the video I left out the detail that technically the bitfields are all 32 bits instead of 26 (the first 6 bits are just ignored by my program).
Man I love it when people use computer science to do pointless things. I once wrote a program to exchange the price of gold nuggets and chicken nuggets.
"Personally I disagree with our concept. Adapt, madam; invest in hags. Damn Mike!" Unused: fiikk
I got “Could information help me manage the system. A Kid died via writing Paprika snacks”
🏆 Possibly the most surreal one I've read so far
nice video
Wow this was great
How much faster was the code before and after the change to bit-wise comparisons?
Sidenote, but another reason that bit-wise encodings work well is that they're much smaller memory footprint compared to an integer per letter. Memory bandwidth is often a larger limiting factor for computation than FLOPS. This is especially true in this case, where you the computation you need to do is small (just a comparison) but the amount of data is very large.
Great video!
Thank you, I can give more detail here than I did in the video. With the letter frequency table system, the word suggestion time varies a lot because of an added feature that I didn't mention. If you're in the middle of typing a word, the word suggestion list will be filtered to only show words that contain the string you're typing. This filtering eliminates a lot of words before the letter frequency table is even used, so as your latest word in your message gets longer, the word suggestion time gets faster (from ~130ms to ~20ms on my computer). But with the bitwise method, it's consistently ~20ms no matter what. So the new system is at most ~6 times faster than the old system.
My attempt at the Task (in under 20 mins) using your website:
Did I speak an acid poem? Aging vinyl foes wrecked! I am triumphant on Taskmaster.
Letters remaining: H, i, L
edit: grammer lol
Great video!!
great video!! also, i love the cat. give it extra scratches pls
It would be trivial to extend this to more letters, symbols and digits.
That's true, a lot of it would be trivial. One non-trivial thing might be that some users might want certain characters to be interchangable with others, like À with A, or " with “ (standard vs curly double quotes). Very doable, just would require extra thought and work. My word list was the 2023 NASPA Scrabble Word List (NSWL), so it only used the 26-letter alphabet, so I prioritized just getting the user input to work with that.
wait this is really funny. Here's my silly go at it
"taskmaster, I have not seen, did hear its good. many a mind game lack prickin. flip wupi!"
🏆 This is so good! I agree, something has to be done about the Water Utility Performance Index
"Canvas-fueled parents dare erect painting shop! I dig silk, okay? Hmm- into wiki, madam!"
Uses all the letters, makes none of the sense.
Ikebot: "there are no rules"
The Taskmaster hiding in his walls: 👁👄👁 🔪
Should I be worried 😨
@@Ikebot All of the information is in the card.
cool vid!
Nice! Sorry if I missed it, but is this open source? I had the idea of making the suggested words clickable to directly add that word to the textbox. I'd have a go at a pull request if it was open source.
That would be great! I considered making the words clickable. I ultimately didn't have enough time. The code is in a folder in the Github Repo for my whole personal website: github.com/IkeB108/home/tree/main/description/anagram-constructor
Thank You
very cool :^)
like and supscripe for more pi content and shit i make, and i always might give a dam, k!
🏆 Perfect, and I like that the K is right at the end
i train no more fad maps, the way i- akk! Damn deeds in great value. Click things, i pop sim.
Maybe possible to make it a bit faster by using webassembly
Shocked to see only 400 likes
You can try the program right now and leave a comment with your solution to the Taskmaster task: www.ikebot.dev/description/anagram-constructor/anagram-constructor.html
If you'd like to see the code, it's in this folder in the Github repo for my whole personal website. Changes, additions, and suggestions are welcome
github.com/IkeB108/home/tree/main/description/anagram-constructor
I am here for 2:48 and 5:45 ᓚ₍ ^. .^₎
woah cool
An anagram of title usiπ ikebot
Womens rite to vote is hot (mrsssssss kw)
🏆 I love it, you even used the π. Looks like it was written by Mrsssssss Knows-Words, the hissing snake who's an expert at wordplay.
(or maybe Mrsssssss Keep-Waiting, the Python that convinced Matt Parker to wait 30 days for his Wordle code to run)
After the end of the video, you could have done better than "Thank you for watching my video, I hope you enjoyed it, ack!", because that includes letters not in Taskmaster's bunting.
What you need to do, since you were inspired by Matt Parker, is mention that MP's videos, much like your own, are very impactful in the education side of TH-cam, and therefore are less likely to get likes, so you need more likes for them. Something like this will suffice:
"Thank you for watching. Learned it's said impacting videos need likes. MP & I map karma."
And there you go... you've used all the letters in the Taskmaster bunting (though the ampersand does kinda ruin it, this was the best that I could do).
🏆 That is so perfect! I think the punctuation in the episode was two apostrophes, two periods, and an exclamation point. Maybe you could remove your third period, then fudge an ampersand by combining the remaining exclamation point and comma. (If an ! can count as an x then I think nothing is off the table)
Cat appears
2:50
5:50
nice cat
Some would call this a TASmaster.
(I hope this joke isn’t made in the video)
I spake real lies, wham!
I'll second what I've seen others say: I'm surprised this doesn't have more views! I had fun trying my hand at it. My attempt is spoken by someone with the name Ace Dims. Maybe came out as more of a threat than anything inspiring, but ah well.
"Ace Dims: If you don't make grampa king, I will take his ice heart and end it. Ransoms. PVP."
Akk!
track id at 5:15 ?
The song? The song is I Don't Need Your Love by Adi Goldstein
@@Ikebot ay thanks! the vocals in the song reminded me of the vocals in eery - her. just wanted to see if i could find the sample.
Great video by the way! i really enjoyed it
This seems too complicated. What we need is to spend six months writing an even more complicated program that will create a program that can quantify how to turn any task into a formula that can be programmed.
"I spake" but not "I speak" why?
spake comes first alphabetically
Shakespeare has been dead for a little while, so the past form "spake" is more appropriate than the present tense "speak".
Also, "spake" makes it sound appropriately Shakespearean old English.
Oik
cat
6:06 "Oh he is about to upgrade the binary string to a unique number for each letters combination and then use it as key for an hashtable"
6:08 "nevermind"
For real tho, you could have just used a single number instead of 9 and used it as key in an hashmap.
Way faster than doing bitwise operations for every single word
what would that number be, and what would you store in the map? if you use the bitfield representing whether the word contains a letter or not, you have collisions and need to store multiple values in one map slot and disambiguate after lookup. this is a lot of work and complexity.
and then what to store: if you intend to store the counts of every letter, thats an array of 26 integers, all of which need to be compared against the available counts. thats even more work.
hashmaps are also not free in the slightest. they tend to have decent amortized performance, but they will be more expensive than a couple extra bitwise comparisons. hashmaps are not the play here, at least not without some major restructuring of how this program operates.
@@jotch_7627TLDR:
Just imagine the bit strings are written base 10 and add all the 9 strings up. Use the number as key to a list of all the words with the same amount of letters. Congrats, you just saved 5 200 000 checks per word
#ENDTLDR
What do you store? The words themselves obviously? You need to return a list of all the words with a certain amount of certain letters.
The number is a 26 digits number base 10. 26 is the amount of letters in the alphabet. 10 is the different amounts of letters you can have (from 0 to 9). This is ofc an example, there are many different ways one could do this.
Words with the same amounts of letters will have the same unique number obviously. You use this number as key to a list of words in the hashmap.
Also yeah bitwise operations are fast, but not 5 200 000 times faster than a search in an hashmap ffs. And this is not counting the 9 fields each word has
Major refactor? Can you even code?
If I understand correctly, your idea to generate a single 26-digit number for each word, where the digits represents the occurrences of each letter. Conveniently, my word list happens to have no words with more than 9 occurrences of a single letter, so only single-digit numbers would be needed.
Then, words with the same 26-digit number would be grouped together into arrays. The word list would be replaced with a hashmap, where the keys are the 26-digit numbers and the values are the arrays of words that fit those numbers.
So to find word suggestions, the program could just generate a 26-digit number for the letter pool and look up that number in the hashmap to find matching words.
This would be a good system for finding standard anagrams (words that use every letter in the letter pool), but the program needs to find sub-anagrams (words that use any amount of letters in the letter pool, like Scrabble Word Finder), so it can't just search for identical letter counts. That's why my original system (with letter frequency tables) needs to compare the letter frequencies one at a time with ≤ operators instead of all at once with an = operator.
That's the crux of the problem, which I think is the point @jotch_7627 was making.
In the same vein, with the bitfield system, it needs to compare the bitfields with bitwise operations instead of just checking if they're equal.
The more I think about it, I wonder if you could use a hashmap like this, then have each array in the hashmap also store references to all other arrays that are subsets (less than or equal letter counts). Hmm
@@Ikebot 26-digit integers require 87 bits of precision, so that rules out any kind of fast number type. you also cannot discount the time it takes to construct this map. if it only contained words with equal letter requirements, maybe it could be decent. but equal-or-less-than? i have my doubts
"w. a cool video guy. i like it thanks mn. math mind transfer, same page. n rapid pick ideas"
Here's my attempt. I've substituted sounds for words with "m[a]n" and "[a]n[d]" and had to completely drop the "[we are on the] same page" to express it's cool how we're on the same wavelength.