Hey everyone I hope you enjoyed the video. I’m still figuring out how the format can be improved, especially the code portions (03:57 to 05:38) which I find a bit dull and “tutorial-y”. I’m open to suggestions and ideas to make them more engaging. Here’s my list of ideas so far: - Fart noises - ?
From what I've seen, it's done in two ways: 1. The one you did, writing slowly and talking over it, telling what each part does. 2. Sped up footage of code being written, which I think makes it more appealing to non-technical audience. But maybe somewhere in between would be better. Which you don't go over each line, but talk about the code in general and what each part does. I think, having an overview of what your approach to solving is going to be (pseudocode maybe), talking over that, then replacing it with your implementation would be nice. I hope I'm clear. If not, tell me.
Good point. I see Sebastian Lague displays the entire finished result and then films himself highlighting the line he's currently talking about. But I feel it's a lot to take in at once
@@uselessgamedev I don't know if this is the right place to ask, but I'm currently in the process of starting my own UA-cam channel. I'm truly inspired by the content you make and would greatly appreciate your guidance and advice. Could you please provide me with some assistance? It would mean a lot to me. If possible, could you kindly share any contact information or suggest a way for me to reach out to you directly? I have a few questions that I think you could help me with. Thanks in advance.
@@uselessgamedev sebastian lague might be a good inspiration as well actually, instead of explaining using the code you could explain using visuals and then show the code for those who are interested/have it displayed in a corner or sth
You can improve the speed another 100x or so by encoding the letters into a bitmask and getting the entry from a hash lookup. Matt Parker did a video about that algorithm recently: ua-cam.com/video/c33AZBnRHks/v-deo.html To adapt it to this problem, you could just use more than 1 bit per letter for duplicate letters. Not that you need the speed or anything haha, but just another elegant algorithm.
Assuming you mean to use the bitmask to hash into the optimal word for that mask, we may run into memory concerns. A letters game requires 3 vowels and 4 consonants, with the other 2 belonging to either set. This means there can be at most 5 vowels and 6 consonants in any given game. log2(5) = log2(6) = 3 (with rounding), so minimal bits required would be 3 per letter. 3 * 26 = 78 = 5 bytes per game representation with optimal (byte-aligned) packing. One could reduce this by yielding the wasted 2 bits by clever shifting but I doubt it would be worth it. Assuming C-style char arrays we would have 9 bytes for the optimal word (using null characters for words < 9 letters and repeated best words). Again this could be made more dense by using pointers to strings for optimal words, but this would still at an absolute minimum use 4 bytes on a x32 machine plus the cost of storing the strings somewhere. For a near-optimally stored hash pair we therefore have 9+5 = 14 bytes per game representation with its best word. I am unsure how the author of this video calculated the number of games but I reached a very different figure. As per the above rules, letters games can have 4, 5, or 6 consonants and 5, 4, or 3 vowels respectively. Using combination with repetitions (named multichoose) as (n + k - 1) choose k (for n = number of letters in consonants/vowels and k = number of consonants/vowels) for each of the 3 cases of letters game, we get a total of 13,116,026 different games. Do note that this figure is a bit larger than the 9,719,199 quoted on the countdown wiki, but they make references to letter frequencies and counts that I've not included in my calculations. Putting these 2 numbers together and assuming a perfectly packed hash table, we would have 13,116,026 * 14 bytes which is approximately 175MiB. While this is possible, it seems a bit large to load into ram just to keep the optimal games known! The trie solution avoids this large use of memory as the strings abcde and abcdd differ by only 1 node, both pointing to the abcd path. If you have a question or think I'm wrong, let me know, and thanks to the creator of the video! Edit: Whoops! Just realised it does not need to be this memory intensive at all, at the cost of some (but not even close to all!) of the speed. If we instead create a hash map of the above 5 bytes of letter usage to each valid word (NOT each valid game!) we will use far less memory of around 2MiB. Now when we want to find the word we check in decreasing length order the combinations of the letters. For each of the 512 (2^9) sub-combinations of the game letters we create the 5 byte identifier and check its existence in the hash map. With early stopping we are very unlikely to see more than 256 checks of the hash map. Granted this is of course 255 more than the 1 in the previous solution, but at an 80th of the memory cost, so I'd say it's a far better solution.
This was really cool, you are definitely not a dollar store Sebastian Lague you're a high quality UGD! Good luck with your speech inpedement of "being French" 😂
Nice, someone noticed The first draft of the script said "unless it already is a word!" but I removed it as to not confuse people who haven't seen the show
@@uselessgamedev when I watched that episode, I came up with "BATTEN", but I don't know what happens in the event of a tie, because we don't get Countdown in my country.
"You budget Sebastian Lague", I laughed so hard. In any case, I just wanted to mention theres a much better way to do the naive algorithm. This certainly won't be faster than the average solve for batch data with a precomputed tree, but for single games it will be much faster. function( letters, words, depth ): * Remember the longest word you've seen (longest) * For each available letter: * Get the sublist of your available words that match the letter at "depth" * If that list is empty, return an empty string * Perform a recursive call to this function with the available letters except for this one, the sublist of words, and depth + 1 * If the result of the recursive call is longer than "longest" overwrite it
@@uselessgamedev haha, indeed, i do my best. i knew that the second scramble of letters had to be something, but it made more sense when you solved it for me :P or should i say, when your code solved it for me
at the start i was clawing at the walls hoping you would implement a trie and felt satisfied when you did :) also i really like your humor it adds a lot to the videos
hello its me again great vid by the way just wondering what video editor do you use im thinking of posting a ASCII video that uses compute shader to get it which should get a nice and high framerate thanks Gc edit - i mean shader graph then turn it into compute maybe in a diffrent vid
Super interesting video! I have a few suggestions considering (even more) optimization. What about sorting all the words by letter (since order is not important)? This way you can stop the tree search prematurely. For example "FRENCH" would be stored as "CEFHNR". This would also mean a smaller tree with less nodes. You should of course store the real word in the leaf to retrieve it. (En tout cas super vidéo, comme d'hab, j'avais même pas remarqué que t'étais français avant que tu le mentionnes !)
I was thinking that as well, and you would only need one valid word per set of letters (like spacer and scrape would both be aceprs) so there is even less to store
I'm about half that age myself, but preparing this video I watched some countdown on Channel4 and the ads they run are "at home gp health check for the elderly" so clearly the target audience is quite old haha
i wonder if any word culling could be performed by making a list of numbers for each word that has a bit for each character and sets whether it’s on, either way that’s where my mind went first, hadn’t thought of a trie but it seems like a great option for this.
actually an optimization could be figuring out which letter should go first in the checks to have a higher chance of finding words, instead of in order or random
That’s amazing that you made the actual device lmaoo. I have a question - could you make this even faster if you could skip the array copy by using an integer to mark each letter in the array as used or remaining, where the nth bit corresponds to the nth letter? I don’t know the speed of an array copy vs passing an integer so idk if it actually would improve performance, but the array copy set off the 🚨 in my brain. Thanks for making great videos!
Thank you for your message :) I guess your suggestion makes sense, I was wondering as well while coding, I was thinking to myself that I should somehow pool the arrays or something because memory allocation is always the worst thing to do. It would probably not be a game changer, but I think your approach would be faster indeed
Did you sort the letters of the word before inserting them? It will help prune duplicates and should reduce the depth of the trie. Coat and taco for example would both map to the path 'acot'. You'd have to keep the words in the last leaf instead of a flag for done, though.
I would have just made a separate list of words for each number of letters for example a list of just 1 letter words, a list of just 2 letter words, etc then look trough them and see if you can make a 9 letter word, 8 letter word, 7 letter word, etc but your way of doing it seems much better
This is awesome!! Wouldn't two rings be enough though? Since morse code is based on how long the signal is held for. Would that be harder to implement?
Wouldn't be a lot harder to implement but certainly a lot harder to use: without any visual/sound feedback to confirm whether you've entered a dot or a dash, it's hard to know you didn't make a mistake
I don't know who that is, so... no haha Red hoodie is the titular series, Useless Game Dev Black hoodie is Game Dev's Revenge And then there may or may not be other colors/series in the future 🤫
Tought it was about cheating with timers in video games, could have put a little reference to "Des chiffres et des lettres" in the thumbnail for your fellow french afflicted viewers 😅
Very cool video! I feel like you could optimize this even further by removing all words from your dictionary that are less than, say, 7 or 8 letters long. I’ve never seen this show so I have no idea, but I feel like the makers of the puzzle always intend it to have a 9 letter solution. If they don’t you can just put 7 or 8 letter words in as a security measure. Then you have the program search downwards from 9 letter words (so if it doesn’t find any 9 letter words go to 8, then 7). No idea if it’s compatible with trie, but I feel like that would make your dataset much smaller and make it even faster.
It is indeed random, the candidates draw the letters themselves, so sometimes the word specialist on set doesn't find a 9 letter word. Your suggestion is correct though, for the "naive" approach it does speed things up (although as I said not by much) For the trie it makes barely a difference, which I guess is expected since you still have to traverse the trie to find leaf words
Couldn’t you do a very quick early out of each branch? I.e. if you had no A’s, you could ignore the A branch straight away? Worst case scenario, only 9 branches to check? Put each branch into an high level array, and then only check each based on a quick array lookup based on each letter. If that makes sense? Now I want to take your code and optimize it for this.. lol.. but I have work to do…
Yes the trie exploration does it by design. With other dfs/bfs approaches you definitely could (and should) prune branches as soon as you can but it'd still be a lot slower
> raving on about how optimization is important for code that needs to deploy on a rPi > porting the code into javascript Yep, that's a work of a platypus :D
Hah. I knew I was going to get that comment haha Truth is JavaScript is the only language I know at a reasonable level, but yeah I bet it would be even faster un rust or go or whatever is hip these days
Really cool. But use 3 wires for the morse code? I mean, it was designed with single contact in mind, you'd need a little practice but the result would be even more discreet.
Indeed, especially since I'm not really a "lots of rings" guy. However with the absence of feedback (can't have the usual beep beeeeep sound) I deemed it safer to know exactly if I was using a dash or a dot. Could take inspiration from the world of chess with a vibrating device I guess
I would try to sort every dictionary word's by the letters, then sort those "words". Sort scrambled input. search n choose k of input letters; starting from choosing 9 out of 9. max 511 combnations to lookup. and best score comes up first.
Graphviz, specifically, dot. It's a graph description language and it's very easy to write code that generates it. If you type "graphviz online" you'll get website to play with it in your browser
Hey everyone I hope you enjoyed the video. I’m still figuring out how the format can be improved, especially the code portions (03:57 to 05:38) which I find a bit dull and “tutorial-y”.
I’m open to suggestions and ideas to make them more engaging. Here’s my list of ideas so far:
- Fart noises
- ?
look up dani for inspiration lol
From what I've seen, it's done in two ways:
1. The one you did, writing slowly and talking over it, telling what each part does.
2. Sped up footage of code being written, which I think makes it more appealing to non-technical audience.
But maybe somewhere in between would be better.
Which you don't go over each line, but talk about the code in general and what each part does.
I think, having an overview of what your approach to solving is going to be (pseudocode maybe), talking over that, then replacing it with your implementation would be nice.
I hope I'm clear. If not, tell me.
Good point. I see Sebastian Lague displays the entire finished result and then films himself highlighting the line he's currently talking about. But I feel it's a lot to take in at once
@@uselessgamedev I don't know if this is the right place to ask, but I'm currently in the process of starting my own UA-cam channel. I'm truly inspired by the content you make and would greatly appreciate your guidance and advice. Could you please provide me with some assistance? It would mean a lot to me.
If possible, could you kindly share any contact information or suggest a way for me to reach out to you directly? I have a few questions that I think you could help me with.
Thanks in advance.
@@uselessgamedev sebastian lague might be a good inspiration as well actually, instead of explaining using the code you could explain using visuals and then show the code for those who are interested/have it displayed in a corner or sth
You can improve the speed another 100x or so by encoding the letters into a bitmask and getting the entry from a hash lookup. Matt Parker did a video about that algorithm recently: ua-cam.com/video/c33AZBnRHks/v-deo.html To adapt it to this problem, you could just use more than 1 bit per letter for duplicate letters. Not that you need the speed or anything haha, but just another elegant algorithm.
Assuming you mean to use the bitmask to hash into the optimal word for that mask, we may run into memory concerns.
A letters game requires 3 vowels and 4 consonants, with the other 2 belonging to either set. This means there can be at most 5 vowels and 6 consonants in any given game. log2(5) = log2(6) = 3 (with rounding), so minimal bits required would be 3 per letter. 3 * 26 = 78 = 5 bytes per game representation with optimal (byte-aligned) packing. One could reduce this by yielding the wasted 2 bits by clever shifting but I doubt it would be worth it. Assuming C-style char arrays we would have 9 bytes for the optimal word (using null characters for words < 9 letters and repeated best words). Again this could be made more dense by using pointers to strings for optimal words, but this would still at an absolute minimum use 4 bytes on a x32 machine plus the cost of storing the strings somewhere. For a near-optimally stored hash pair we therefore have 9+5 = 14 bytes per game representation with its best word.
I am unsure how the author of this video calculated the number of games but I reached a very different figure. As per the above rules, letters games can have 4, 5, or 6 consonants and 5, 4, or 3 vowels respectively. Using combination with repetitions (named multichoose) as (n + k - 1) choose k (for n = number of letters in consonants/vowels and k = number of consonants/vowels) for each of the 3 cases of letters game, we get a total of 13,116,026 different games. Do note that this figure is a bit larger than the 9,719,199 quoted on the countdown wiki, but they make references to letter frequencies and counts that I've not included in my calculations.
Putting these 2 numbers together and assuming a perfectly packed hash table, we would have 13,116,026 * 14 bytes which is approximately 175MiB. While this is possible, it seems a bit large to load into ram just to keep the optimal games known! The trie solution avoids this large use of memory as the strings abcde and abcdd differ by only 1 node, both pointing to the abcd path.
If you have a question or think I'm wrong, let me know, and thanks to the creator of the video!
Edit: Whoops! Just realised it does not need to be this memory intensive at all, at the cost of some (but not even close to all!) of the speed.
If we instead create a hash map of the above 5 bytes of letter usage to each valid word (NOT each valid game!) we will use far less memory of around 2MiB. Now when we want to find the word we check in decreasing length order the combinations of the letters. For each of the 512 (2^9) sub-combinations of the game letters we create the 5 byte identifier and check its existence in the hash map. With early stopping we are very unlikely to see more than 256 checks of the hash map. Granted this is of course 255 more than the 1 in the previous solution, but at an 80th of the memory cost, so I'd say it's a far better solution.
That, or just rewriting this in plain C
im so sorry for your condition, being french
I inherited it from my parents. It seems there's nothing that can be done about it
@@uselessgamedev I have it too, this is really sad...
@@uselessgamedev Well on the bright side, you legally own the moon
I hear it's chronic, and eventually terminal...
@@mrlucky974 I've seen it worse, some of us are half french, half catalonian 🤮
This was really cool, you are definitely not a dollar store Sebastian Lague you're a high quality UGD! Good luck with your speech inpedement of "being French" 😂
Loved the abdicates inside joke
lol thought of the IT Crowd bit as tnettenba was being put on screen then looked up and was surprised
Nice, someone noticed
The first draft of the script said "unless it already is a word!" but I removed it as to not confuse people who haven't seen the show
@@uselessgamedev when I watched that episode, I came up with "BATTEN", but I don't know what happens in the event of a tie, because we don't get Countdown in my country.
@@uselessgamedev I was definitely expecting that.
Gotta love the IT Crowd reference at the start. "Umm it actually already is a word"
"You budget Sebastian Lague", I laughed so hard.
In any case, I just wanted to mention theres a much better way to do the naive algorithm.
This certainly won't be faster than the average solve for batch data with a precomputed tree, but for single games it will be much faster.
function( letters, words, depth ):
* Remember the longest word you've seen (longest)
* For each available letter:
* Get the sublist of your available words that match the letter at "depth"
* If that list is empty, return an empty string
* Perform a recursive call to this function with the available letters except for this one, the sublist of words, and depth + 1
* If the result of the recursive call is longer than "longest" overwrite it
Excellent IT Crowd reference
I don't know any other youtuber whose video ideas are this creative and interesting.
Missed an opportunities to make the word at the end 'subscribe'
😱
ayy i dont understand what i watch but i enjoy it
Love the subtle IT crowd reference
All the references had me in stitches. Keep it up! Big fan of your work!
This was really interesting, never knew about tries.
Also I know for certain that you were watching the 8oo10c version because of 'abdicates'
I rewatched the episode while preparing this video, and this opening line "to be honest Jimmy, I don't think that's any of your business" is just gold
Nice references with tnetennba and abdicates XD
OMG someone found the second easter egg. Congrats! I see you're a man of culture as well
@@uselessgamedev haha, indeed, i do my best. i knew that the second scramble of letters had to be something, but it made more sense when you solved it for me :P or should i say, when your code solved it for me
never heard of a trie before and I've been doing comp sci for 7 years now! awesome video!
at the start i was clawing at the walls hoping you would implement a trie and felt satisfied when you did :) also i really like your humor it adds a lot to the videos
Love 8 out of 9 cats does countdown and your content as well. What a combination I didn't know I needed!
Your favorite data structure is also a Trie? Let's go!
I'll never forget the interview I busted that out on, it felt really good
WTH I just learned about and implemented my own Trie structure 😮 if only this video was available then 😢
Loved the "Abdicates" reference in the end!! Great vid as usual! Good luck on countdown!!!
Wow, that was really interesting to watch. Impressive work!
Are these explosions.mp4 at the start specially made?
I just thought it would be funny to have a "broken link" picture where people can absolutely imagine what the image is supposed to be
awesome stuff on this channel, very rewatchable too
0:38
Awfully convenient when the letters fall in place like that.
"you dollar store Sebastian Lague" omg I love you (from a fellow french citizen)
Love the video, and the easter eggs for the 8/10 Cats does CD people. Abdicates FTW
hello its me again great vid by the way just wondering what video editor do you use im thinking of posting a ASCII video that uses compute shader to get it which should get a nice and high framerate thanks Gc edit - i mean shader graph then turn it into compute maybe in a diffrent vid
I like how you edited your logo onto your jumper
Man i love this channel, I'm so glad it blew up recently
Fantastic, really love the solution for the input, and your beeps and boops.
Thanks! Since Moebius every SFX is hand made. Or rather mouth made I should say
Love the IT Crowd reference in there - Bravo!
I love the Abdicates easter egg!
knew right away this was going to be a video about tries
I'm very sorry but the best Countdown player is and always will be Maurice Moss.
But it's very impressive and fun what you did there :D
Super interesting video! I have a few suggestions considering (even more) optimization.
What about sorting all the words by letter (since order is not important)? This way you can stop the tree search prematurely.
For example "FRENCH" would be stored as "CEFHNR". This would also mean a smaller tree with less nodes.
You should of course store the real word in the leaf to retrieve it.
(En tout cas super vidéo, comme d'hab, j'avais même pas remarqué que t'étais français avant que tu le mentionnes !)
Hmmm that's a very good idea. It would probably ~double the size in ram but it might improve speed!
I was thinking that as well, and you would only need one valid word per set of letters (like spacer and scrape would both be aceprs) so there is even less to store
@@uselessgamedev How would the memory double? I think it could actually even reduce the size as anagrams would no longer be duplicated.
I just threw that together in Python and got 98ms to build the lookup table after which it took 14us per game.
"is quite slow" - literally a fourth of a second
I am so early omg! This is so cool
An awesome video, thank you for sharing it! And i hope your frenchness gets better soon 🙏
I constantly crave croissants :( alas the doctors say there's nothing to do.
I keep going "oui oui hon hon oui mon petit chéri"
I've used this data structure before for a couple things but never knew its name, very cool video
I honestly liked the code portion of the video, I would personally rather see it, too many youtubers skip it
the second you mentioned the 8oo10c version i subbed !
You are the genius that makes all my useless uses for technology come to life! I love 8 out of 10 cats version and I'm 28!
You're the best english speaking french-man I've ever heard ;)
Gracias
@@uselessgamedev Bittechön
And I know what I'm talking about, I live on the french border
Another awesome video! Sorry for your condition, being french should be hard.
That’s a nice Tnetennba
"For those of you who are under 60"
I feel offended and at the same time you're entirely correct.
I'm about half that age myself, but preparing this video I watched some countdown on Channel4 and the ads they run are "at home gp health check for the elderly" so clearly the target audience is quite old haha
@@uselessgamedev thankfully we have 8oo10cdc for us slightly younger folk.
i wonder if any word culling could be performed by making a list of numbers for each word that has a bit for each character and sets whether it’s on, either way that’s where my mind went first, hadn’t thought of a trie but it seems like a great option for this.
actually an optimization could be figuring out which letter should go first in the checks to have a higher chance of finding words, instead of in order or random
That’s amazing that you made the actual device lmaoo. I have a question - could you make this even faster if you could skip the array copy by using an integer to mark each letter in the array as used or remaining, where the nth bit corresponds to the nth letter? I don’t know the speed of an array copy vs passing an integer so idk if it actually would improve performance, but the array copy set off the 🚨 in my brain. Thanks for making great videos!
Thank you for your message :) I guess your suggestion makes sense, I was wondering as well while coding, I was thinking to myself that I should somehow pool the arrays or something because memory allocation is always the worst thing to do. It would probably not be a game changer, but I think your approach would be faster indeed
Did you sort the letters of the word before inserting them? It will help prune duplicates and should reduce the depth of the trie. Coat and taco for example would both map to the path 'acot'. You'd have to keep the words in the last leaf instead of a flag for done, though.
I didn't but it would certainly improve speed (at the cost of ram because you'd indeed need to store every word twice)
most underrated youtuber
Very cool, always a pleasure to watch your video
That's a nice Tenetennba.
Ah c'est de là que ça vient des chiffres et des lettres !
L'inverse ! Le jeu français a été copié au royaume-uni (et en Australie). Mais je crois que le concept a mieux marché au UK
love your channel! keep up the good work!
Great video!
Great video!
...for a frenchman
I would have just made a separate list of words for each number of letters for example a list of just 1 letter words, a list of just 2 letter words, etc then look trough them and see if you can make a 9 letter word, 8 letter word, 7 letter word, etc but your way of doing it seems much better
Omg l’écriture
Yes you wrote definitely better than me (we call my writing hieroglyphs )
This is awesome!! Wouldn't two rings be enough though? Since morse code is based on how long the signal is held for. Would that be harder to implement?
Wouldn't be a lot harder to implement but certainly a lot harder to use: without any visual/sound feedback to confirm whether you've entered a dot or a dash, it's hard to know you didn't make a mistake
alternatively, you could have haptic feedback using a small vibration motor to tell you what you inputted and what the output word is, in Morse
Ahh that makes sense. I didn't consider that you don't really get good feedback. Any sound it makes would make it more obvious you're cheating anyway
I love your style of content! Keep it up!
Some cool stuffs
nice !!
Great vid!
Wait, is the black hoodie a reference to giorno giovanna's outfit? (Since giorno's outfit change color from purple/pink to black like your hoodie)
I don't know who that is, so... no haha
Red hoodie is the titular series, Useless Game Dev
Black hoodie is Game Dev's Revenge
And then there may or may not be other colors/series in the future 🤫
Nice touch with the tnetennba. Moss's 9 letter word!
I think this can be made a lot faster by sorting the letters in the dictionary words, as well as the clue. i.e. store "abdicates" as "aabcdeist".
Thank you for the amazing video. Impressive.
1:54 programmers when their 99GB code doesn't run in -1ms
Tnetennba .. okay, that got a laugh
I am ashamed at how quickly I would order a hoodie with your avatar embroidered on it
We're not quite there yet but it is an eventuality 😉
Tought it was about cheating with timers in video games, could have put a little reference to "Des chiffres et des lettres" in the thumbnail for your fellow french afflicted viewers 😅
Yes.
Dollar store Sebastian Lague xD
You too can gladly coexist. I enjoy all the videos I can get
I come from the discord. I like optimization.
I'd say you write far better than an 8 year old. At least from personal experience.
Awesome video!
Very cool video! I feel like you could optimize this even further by removing all words from your dictionary that are less than, say, 7 or 8 letters long. I’ve never seen this show so I have no idea, but I feel like the makers of the puzzle always intend it to have a 9 letter solution. If they don’t you can just put 7 or 8 letter words in as a security measure. Then you have the program search downwards from 9 letter words (so if it doesn’t find any 9 letter words go to 8, then 7). No idea if it’s compatible with trie, but I feel like that would make your dataset much smaller and make it even faster.
It is indeed random, the candidates draw the letters themselves, so sometimes the word specialist on set doesn't find a 9 letter word.
Your suggestion is correct though, for the "naive" approach it does speed things up (although as I said not by much)
For the trie it makes barely a difference, which I guess is expected since you still have to traverse the trie to find leaf words
@@uselessgamedev gotcha. I guess the biggest benefit would be a smaller dataset means the trie initializes faster?
@@ozzi9816 I guess.
The trie really is useful when reusing it multiple times. Like looking up phone numbers for instance
This would be hilarious to try out on a friend group 😂
Couldn’t you do a very quick early out of each branch? I.e. if you had no A’s, you could ignore the A branch straight away? Worst case scenario, only 9 branches to check?
Put each branch into an high level array, and then only check each based on a quick array lookup based on each letter. If that makes sense?
Now I want to take your code and optimize it for this.. lol.. but I have work to do…
Yes the trie exploration does it by design. With other dfs/bfs approaches you definitely could (and should) prune branches as soon as you can but it'd still be a lot slower
Trop fan de ce canard bleu
Anyone notice the 9 letter word at 0:38?
Good morning, that's a nice TNETENNBA
> raving on about how optimization is important for code that needs to deploy on a rPi
> porting the code into javascript
Yep, that's a work of a platypus :D
Hah. I knew I was going to get that comment haha
Truth is JavaScript is the only language I know at a reasonable level, but yeah I bet it would be even faster un rust or go or whatever is hip these days
Really cool. But use 3 wires for the morse code? I mean, it was designed with single contact in mind, you'd need a little practice but the result would be even more discreet.
Indeed, especially since I'm not really a "lots of rings" guy. However with the absence of feedback (can't have the usual beep beeeeep sound) I deemed it safer to know exactly if I was using a dash or a dot.
Could take inspiration from the world of chess with a vibrating device I guess
Isn't TNETENNBA already a word? 🤔🤣
I would try to sort every dictionary word's by the letters, then sort those "words". Sort scrambled input. search n choose k of input letters; starting from choosing 9 out of 9. max 511 combnations to lookup. and best score comes up first.
What did you use to visualise the trie?
Graphviz, specifically, dot.
It's a graph description language and it's very easy to write code that generates it.
If you type "graphviz online" you'll get website to play with it in your browser
I like this
That’s a nice tnetennba
Consider your avatar matching that classic beard you have.
Yeah the beard wasn't supposed to be visible, it usually isn't that long. But a bearded version of the avatar, I say why not
Dentroyer. Very clever 🙄😂
I wonder if Rust trie is a good idea.
Vidéo très intéressante! Je n’aurais pas deviné que tu étais français… quelle condition horrible 😨
Hello, that's a nice tnetennba :)
yes
There are going to be a lot of french jokes in this comment section.
Oui oui, hon hon.
Neato
You french 🥖?
Damm, hope you get better 🙏😢
/J
But why Javascript?
It's the only language I know enough beside C# to implement this. Certainly suboptimal but still faster than learning rust or go or cpp
yippeeee
ABDICATES