Nicer Trees Spend Fewer Bytes: compressing 12947 Wordle words into 12155 bytes

What's the smallest javascript program you can write whose output is the Wordle wordlist? A lively "code golf" competition to answer that question is currently underway at the website golf.horse/. This video describes how one particular entry achieved an impressive amount of compression by using binary trees to divide the space of possible words.
Made in collaboration with ‪@jedgrabman‬ .
Submitted to Summer of Mathematical Exposition 2023: some.3b1b.co/
#SoME3
Interactive visualization: dwrensha.github.io/nicer-trees/
My code: github.com/dwrensha/nicer-trees
Jed's code: github.com/JedGrabman/WordleG...
Our current best solution.js: github.com/dwrensha/golf-hors...
00:00 - intro
01:04 - encoder/decoder
02:44 - Noiseless Coding Theorem
03:32 - a simpler two-letter version
04:32 - the binary entropy function is concave
05:35 - binary tree representation
06:39 - visualizing simple greedy search
07:39 - a more optimized tree
08:15 - some interesting clusters
09:02 - call to action

[@MT-nu8ox]

Very interesting! Only downside is that I am not smart enough to understand 90% of this haha

[@Fritz0id]

yet so interesting!

[@leosmi1]

you need to understand data structure first

[@MT-nu8ox]

@@leosmi1 Thanks, I'll try to learn that

[@parlor3115]

@@leosmi1 Half of the video is information theory. He's referenced entropy FFS.

[@leosmi1]

thank you @@parlor3115

[@brady6968]

This is surprisingly relevant for the Sebastian Lague chess competition where I've been trying to compress the weights of a neural network instead of wordle words.

[@pinruihuang8463]

You're writing an NNUE in the competition? God help us all...

[@gwentarinokripperinolkjdsf683]

@@pinruihuang8463 NNs compete separately no?

[@pinruihuang8463]

@@gwentarinokripperinolkjdsf683 tbh i have no idea man

[@macchiato_1881]

​@@pinruihuang8463NNs don't perform all that well in chess unless it has a shit ton of parameters. More traditional engines will outperform low-parameter models by a huge margin.

[@pinruihuang8463]

@@macchiato_1881 I was expecting an NNUE on top of a traditional engine, which would most likely require this kind of compression.

[@jedgrabman]

Great working with you David! This turned out to be a surprisingly deep problem combining math, stats, CS and linguistics!

[@proterotype]

I always love stumbling across a video where you know the channel is going to grow a ton, and you found it early on.

[@GigsVT]

I have to echo the other comments. I think something like this will be useful to me in an entirely different problem space. A truly useful idea that I'm surprised i never heard about before quite like this. It's like huffman rainbow tables.

[@nif4345]

I feel like it could be more efficient to sometimes hardcode words in very sparse areas to lower the cost further

[@dwrensha]

Quite possibly!

[@unflexian]

username w

[@SpencerTwiddy]

@@unflexianyo I can’t believe 3 seximal enthusiasts stumbled into the same comment section

[@SpencerTwiddy]

I was just musing that in a twelve team fantasy football league, you want to have RBs and WRs in the top nif for fantasy points each week

[@unflexian]

@@SpencerTwiddy im not american enough to understand that but it sounds really reasonable:) also seximal rocks

[@ArtificialDjDAGX]

hmm, could try using the rubik's cube short-path finding approach, where you start both top-down and bottom-up and try to find a convergence point where both methods meet, vastly reducing the scale of the problem.

[@undefined06855]

Is the word on the thumbnail "First"?

[@dwrensha]

Looks quite right. Bravo. Great solve.

[@alexismandelias]

This is beautifully obscure, unique, intriguing and satisfying at the same time

[@taranknutson175]

Awesome job!! I love how simple problems can have such deep answers in CS/cryptography

[@JediJess1]

Fascinating video. I love seeing mathematics becoming a part of the discussion with programming and Computer Science

[@commandblockguy]

Sweet video! I first tried this problem back in like February 2022 when I was writing a Wordle clone for a graphing calculator and needed to compress the word list to get it to fit in memory. The best I could do was around 14 KB for just the word list (never got around to writing a golfed decoder for that compression format, since handling bit streams is a pain in the assembly language the calculator uses). I effectively just applied a Huffman coding to convert each word into a bitstring, sorted the list of bitstrings, then encoded only the number of bits that changed and the bits after the first bit that changed between each pair of words. I was excited to see this video in my recommendations - I'm glad that there's still progress being made on it, and the algorithm is very impressive.

[@unflexian]

wait what I wrote Wordle for desmos too didn't need any compression, one base-26 number per word fit just fine

[@commandblockguy]

@@unflexian This was for a physical graphing calculator (the TI-84 Plus CE), not Desmos. Those are more restrictive (150 KB total RAM + 4 MB flash, shared with OS, with 64 KB per program max)

[@unflexian]

@@commandblockguy that's great damn

[@campbellhutcheson5162]

Incredible video!

[@Marcox385]

Lately some real underrated gems such as this has been emerging in youtube. Truly a blessed time. I had never seen any of your videos but this is amazing David. Thank you for sharing.

[@TheDestroyer55e]

i think it has something to do with #SoME3

[@EchoErik]

Great video, look forward to seeing more videos from you!

[@khoda81]

Oh my god, this was such a fascinating video, really hope you make more of these :)

[@dwrensha]

Thank you for the words of encouragement!

[@iogamesplayer]

This is criminally underrated!

[@kitizz548]

Nice! I hadn’t considered the intersection between codegolf and maths before this 😄

[@michaelbauer8766]

Amazing to see KZbin suggesting this to me! Excellent, excellent video. Hope the view count keeps growing and growing!

[@claytonharting9899]

I was looking for an example to show how math and computer science can be applied in an interesting way to a magic system (on the author’s request). This is a perfect video to share. It’s short, well explained, and very interesting

[@kgleba4442]

Great job! Definitely worth watching and digging deeper Probably great choice of topic for the next video would be explaining the algorithm behind the visualization (clusterization particularly) from the computer science perspective

[@yaybaby7984]

Cool video!

[@smileyp4535]

I have no idea what like any of this is but it has very pretty pictures and your voice and enthusiasm is very nice ☺️

[@blank4305]

Thanks for the vid, it was super interesting!

[@kalei49]

i have never watched this video, but from the thumbnail in my recommended what i took away was that 'nicer' is a good word to open with in wordle. turns out that is not at all what the video is about but /is/ what i've been playing with for weeks now and having pretty decent success, so i just figured that the video was right. turns out i literally just made up that fact myself.

[@dwrensha]

I don't think "nicer" is a particularly bad word to start with! But yeah that's not what this video is about at all. I hope you found it interesting, even if it was not what you expected!

[@Belissimo-T]

The video was so good, I wish it would have been longer.

[@Tobiky]

Very cool video, thank you

[@Asterism_Desmos]

This is so cool!

[@ckq]

5:00 I've found this result in the context of win probability models. The entropy is initially maximal then after time passes, the expected entropy decreases until it finally reaches 0 when the game is over. The change in entropy between two points in time corresponds to the information/importance.

[@pseudolemon8272]

criminally underrated channel, glad to be in the first thousand

[@Vfulncchl]

Honest to god, one of the very best #SoME3 entries

[@willowytale]

Fantasic video. Completely nerdsniped me. I know what I’m doing this weekend

[@dwrensha]

Eagerly awaiting your submissions on the leaderboard. :)

[@sheepcommander_]

I love this!!

[@Dorumin]

Very fascinating. But it would've been nice to see more on the decoder front code too, ha

[@sdjhgfkshfswdfhskljh3360]

Wow, did not expected to find such video. I think it's a great idea to learn about programming in general and compression in particular by trying to make more and more optimized solutions. I created similar challenge with the goal of compressing specific image. I learned a lot while making solutions to it, but sadly, failed to find anyone else who want to participate in it.

[@claudiacarrasco908]

Fun fact: The wordle answer in the video's thumbnail is "first"

[@Finnnicus]

Great channel and presentation. Tom7 vibes to me

[@bihazards]

Bonus points for the wordle word in the thumbnail

[@DemonixTB]

interesting, I am currently solving a similar problem, regarding a specific 1bit/pixel video (yes, you guessed it, it's Bad apple) that I am trying to fit into the lowest space possible (at a significantly reduced resolution and fps, all to fit the code and data under 60kb, so far i have not found a technique that could do it, but this seems like a promising avenue to explore, though I doubt it will help since this "only" cuts about 90% where as I need to compress ~10M bytes, = 99.3% savings

[@ahumanintheory4114]

Have you considered only encoding the changed pixels? A significant portion of bad apple is either a black screen that stays black or a white screen that stays white. The GIF specification includes an optional system like this that allows for updating any sub-rectangle of the larger image, which with some optimization could potentially yield high compression ratio given the nature of bad apple.

[@DemonixTB]

​ @ahumanintheory4114 of course I have, gifs are notoriously large and inefficient, it only got to around 2MB, far far too much. I've also tried RLE, I've tried bzip2, several voxel compression algos, contour mapping, cubemarching, k-trees, octrees, huffmann coding, I now have several files that technically fit, though at reduced visual fidelity, or reduced resolution and framerate, with, surprisingly the now old-ish h264 codec at rfc 48 being the best quality result I've found so far (still only 40x30 resolution at 8fps) although h265 got a far far better quality result (my target 64*48 at 15fps), but at 90kb, sadly I also need a method that has a small and fast enough decoder. to fit within the previously mentioned 64K so h265 can't be used. currently I think my best bet is a 3D representation of the contour edges with some good enough 3D object simplification , together with some custom compression algorithm, since most stock 3D asset compression focuses on things that are not the verticies themselves.

[@FinetalPies]

I'm trying to figure out why you would need a 60kb Bad Apple and I have no idea so I'll just assume you're trying to make Bad Apple run on Doom

[@DemonixTB]

@@FinetalPies close enough look up "poom"

[@disketa25]

@@FinetalPies Given 60k limit, I expect the port for some 8bit/64K machine.

[@boysosleepy]

Go Jed!

[@Nylspider]

Took me a surprisingly long time to figure out that the thumbnail puzzle’s solution was “First”

[@Stonehawk]

Was "FIRST' the solution to the thumbnail?

[@ckq]

9:15, yeah generally speaking bottom up is optimal for minimizing the number of bits used since you can combine the two smallest, and repeat

[@technicalgaming4936]

I’m only half way through but I have thought of an idea if you can turn the world list of 0’s 1’s into a 2D array then send the positions of each correct word we could maybe cut but the array would be so long that we might have to cut it up and have another number but cut it up as many times to find the most efficient one then decide it by doing the opposite but I don’t know if it would work

[@NonTwinBrothers]

I was amazed I recognized the profile picture "Wait, is that the Acronymy guy?"

[@fireyblackdragon]

about the thumbnail: is the solution word "first"? it was the only one I could think of given the colors. Most wordle-esque designs like that tend to be impossible, just using random coloring.

[@msclrhd]

I wonder if it would make sense to encode the data as a trie first. That way, you can take advantage of the sparsity of the data. Another trick could be to pack the branches of the trie into a 26bit integer, with one bit per letter -- i.e. each bit indicates whether the letter is used. Using your 7bits per byte from the base 125 encoding, that gives 4 bytes per trie node with 2 bits for additional information. Because all words are 5 letters, you don't need to store an "end of string" marker. Note: I haven't calculated how many bytes this encoding/approach will need for the complete trie data structure. You then just need to order them in a way that makes it easy to walk the trie in a compact decoder algorithm that prints out the words.

[@dwrensha]

some of this sounds similar to what Luke G is doing in the currently-first-place submission: www.luke-g.com/modeling-5-letter-english-words/

[@yash1152]

3:33 3:42 to 4:10 woaohwww!! plots and plots.

[@unflexian]

how would you go about implementing this for arbitrary length strings, or just a general byte sequence? ~it's for an advanced research project involving~ i'm trying to make bad apple in shenzhen i/o

[@dwrensha]

Haha, now that's a demo I want to see! I'm not sure exactly how to translate the specific ideas from this video, but the general strategy of "find some model where your data has low entropy" should be a good guiding principle.

[@unflexian]

​@@dwrenshaI've compressed the pixel data to 19kb, and after two days of fiddling I can't get it any lower without implementing rar or some ridiculously complicated file format. Luckily, there's a mod that lets you resize the working grid. it only works for 2x which is not enough to store 19kb, but it's open source so... see you in a bit.

[@trex2537]

I am new to Javascript and programming. I can't understand a thing can someone please explain? What kind of programming is this and Where is this used ?

[@empty5013]

it's interesting that theres a bias towards the bottom right of each node, is that coming from the algorithm itself?

[@dwrensha]

That's coming from the layout algorithm used by `d3.treemap()`. Positioning and shape are chosen in way that's supposed to be balanced and nice to look at. The only geometric thing that's significant is the area, which is proportional to the number of strings represented by the node.

[@Z0DI4C]

Seems you could encode tokens in a Huffman tree taking advantage of the knowledge the output would be 5 characters, allowing you to optimally encode with the assumption that the decoder could truncate all bytes past 5. For example, a node in the tree expanding to a token of "aste" could also be used as the last token in everything ending in "ast" ("ast ", "as ", and "a "). "[ide][aste]" would truncate/decode into "ideas" while sharing tokens with both "[p][aste]" ("paste") and "[ovo][ide]" ("ovoid").

[@dwrensha]

Interesting! How would you choose your set of tokens?

[@Z0DI4C]

​@@dwrensha That's the hard part, I think :) -- you could brute force it, partly by searching for the most common 3- and 4-character strings (previewable with Notepad++'s Count functionality) and adding weight to them by the count of the valid strings which (in terms of regex) match "....", "... ", ".. ", and ". ". I'm not sure if I would expect the resulting tree to be mostly for 3-character-long tokens (e.g. "are", "ang", "ear", "one", "ast", "ide", "der"), resulting in an output which mostly truncates just one trailing character, or a mixture of 1-2 character plus 4-character tokens. There are a lot of possibilities there.

[@DerMatheman]

Instead of a tree one can use a graph that has directional paths. And every path hast to start at root and only contains 5 letters one could easily cut those bytes to half

[@Exilum]

Surprised no one commented First. Good thumbnail.

[@k.umquat8604]

Very interesting video. Unfortunately I can only understand the gist of it

[@coffeefish4743]

making trees sounds lkike a good task for a nureral network.

[@dwrensha]

Please try it and let me know how well it works!

[@aze4308]

woahhhh

[@Preinstallable]

Only 500 subs? Wow

[@joshuachan6317]

So... what's the word on the thumbnail

[@kinglysandus]

I just clicked on the video to say that I think the answer is "First" in the Wordle puzzle in the thumbnail.

[@dwrensha]

bingo

[@EHMM]

the answer to the wordle in the thumbnail might be fires

[@dillon8124]

it's first S can't be the last letter

[@taraskuzyk8985]

how many hours did you spend on the title?

[@dwrensha]

I was stuck on the title for weeks! I hit upon the "use five-letter words" idea first thing in the morning the day before the SoME3 deadline. After that, it took less than an hour to select the words in a satisfactory way.

[@Omena0]

Me when i make a request to a server to get the wordle words 💀💀💀

[@dwrensha]

oh no please don't die we just wanted to send you as small of a payload as possible

[@helper_bot]

oh no i clicked this from reccommendation

[@GameJam230]

The irony is, anybody who commented "first" on this video was finally right for once...

[@BlastinRope]

FRITS

[@stevemelons]

Good video but why didn't you implement it...

[@adsan7787]

Why is grrrl a word?

[@dwrensha]

I think you're going to have to ask Josh Wardle that one.

[@dwrensha]

en.wiktionary.org/wiki/grrrl

[@adrianover]

First

[@zyxwv]

horrible wordle start. did not get the word.

[@dwrensha]

Sorry about those inept ploys.

[@zyxwv]

@@dwrensha with that, you could figure out the word, but it'd be difficult

[@PipStuart]

@@dwrensha You're quite adept along these words. Bravo! ;) Great video makes Pippi happy. Super enjoy! Peace.

[@dwrensha]

Witty reply, there. Props!

[@zyxwv]

@@dwrensha didn't get today's wordle with that :(

[@buttonasas]

first

[@TheOobo]

The thumbnail beat you, sorry

[@Green24152]

did anyone else figure out the wordle on thumbnail

[@nanopi]

FIRST

[@vepply]

Ong you sound like shounic and yall both make coding content lol

[@Cyberian_Khatru]

8:55 "maybe if we stare at these things long enough..." we will inevitably realize how dumb the english language is lol That's what I was thinking, at least.

[@NiGHTcapD]

I think that the way the wordlist is compressed is similar to the way pokemon sprites were originally compressed? I have to assume, because you did not explain.

[@myrusEW]

First…

[@nbecnbec]

First

[@mydearaniryx7829]

FIRST

[@durellnelson2641]

First

[@MrArbaras]

First

[@F1e308]

First