Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes | Hacker News Reader

Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

alexanderpruss.blogspot.com

332 pointscubefox152 comments

I love little compression hacks like the one given in the article.

I created a word search game way back in late 1978/early 1979 4KB of RAM. I had about 2KB for storing the word database. And I recall I had about 2,500 words. Which I had to type in by hand.

I used the 26 tables of words trick too, to drop the first letter. I also treated each word being made up of 32 symbols. I called them letters, but they didn't represent individual letters necessarily.

Edit 36 minutes after writing my original comment: Having just checked my notes from December 24th 1978, I need to correct myself and say it was 38 symbols. Though I seem to recall I actually got it down to 32 symbols. I need to keep looking through my notes to refresh my brain on the solution.

A word might end in "ING" so that was considered a single letter/symbol. Words were between four and seven letters long.

Most words took up two bytes, some only took up a single byte, only a few took up three bytes, maybe a few dozen took up four bytes. And I judiciously pruned the database to minimize the words that took up three or four bytes so that I didn't have too many of them. I also packed the bits, so that there was no gaps between words.

And it was all written in 6502 assembly, originally for the CBM PET, and later for the Acorn Atom.

I was 11 years old and so proud of myself for such cleverness. I still have my notes and scribblings, including the digitised versions from all those years back.

Later, when I wrote a much more complex Bookworm type of game I had to take a word list that was about 8MB long, uncompressed, which would just barely fit on the hard drive, and turned it into a trie, which brought it down to just a few dozen kilobytes, which handily fit on a SS/SD 100KB 5+1/4" floppy.

Man, at 11 my programs mainly consisted of INPUT, PRINT and GOTO, which I wrote on my uncle's brand new IBM XT.

Yeah, me too. Mainly D&D character generators.

D&D character generators were fun to write. And remember those name generators? And you could make planet name & planet environment generators, and then solar system generators for Traveller. I threw together a really bad dungeon map designer thing when I bought once of the earliest mice you could get, with the roller ball inside the mouse that you had to take out and clean.

It doesn't matter how we all started, or how fast we got here, we're here now, in the same place, the adventure only stops, when you don't want to learn new things.

My programs at 11 were just Visual Basic 6 for an IE scrapper/clicker and making HTML websites in Dreamweaver 6.

Not sure why the 6 was so popular for many programs then. It was for sure Photoshop 7 era.

My guess is that it was the last version of Visual Basic before they moved over to VB.net -- it was easy and simple, and didn't aim for industrial strength.

I don’t know what amazes me more: your engineering solution or the fact you was able to find notes dated December 24th 1978

I got nerd sniped and compressed it to under 28K, which was good enough for the goal of fitting it in a 32K NROM cartridge for the NES. On the NES, you don’t need to do better than that, because you get a separate 8K for graphics, and 4K is plenty of space to fit the code for your Wordle clone.

https://www.moria.us/blog/2022/01/dictionary-compression

The annoying part is that the NES only gives you four background palettes, and you are constrained to use all four of those to color your words.

Both of these ideas remind me of tries and radix trees.

Nice! Do you have a repo somewhere?

I’ll put one sometime relatively soon, got some other stuff on my plate. The Wordle clone is currently “mostly functional”—no pretty graphics or anything, but gameplay checks. I have a limited stamina for NES programming, but I had fun with the proof of concept.

And far better than gzip compression. Nice work. My takeaway is that context matters - this is not General Purpose Compression, but compression made specifically for this case. Good Stuff.

Even though it's domain specific, it's a pretty clever idea that could carry over to other things. I wonder if you couldn't cleverly reorder any text document in chunks and get the maximum word differences per chunk, keep a map of word order and compress it this way. With a 2 bit minimum per word, maybe you could take all replica words in two bits.

If you have enough space to store the fully decompressed list, then you could in transpose the list of words - so instead of 5 by 12972 make them 12972 by 5, and get enormously long repeated runs of first, letters, second letters, etc. Any lz77 based compression will compress pretty well after that

That would be only effective for initial letters though. Implicit delta coding, where you strip a common prefix from the lexicographically previous word and mark word boundary somehow (e.g. capitalization), would be better suited if there are many short runs of words sharing a longer prefix; it seems to be the case for the Wordle list as well (about 10% smaller for zlib -9).

It would be, but it would also be really effective on those initial letters: a near-perfect use case for RLE compression on the first two characters should already result in something close to a 40% size reduction before Huffman encoding. But I suppose implicit delta coding also basically achieves that.

Anyway, thinking about the transposing idea some more: this would effectively split the word in to 26² = 625 "buckets" of three-letter suffixes. What we could do to make those still compress decently after transposing is look for shared suffixes in multiple buckets, and ensure they get grouped together in the same order before transposing. This would result in short runs in those suffixes, squeezing some more compression out of it.

... which should also work really well for implicit delta coding.

Hmm... you know, the basic concept here shouldn't be too difficult to implement and try out out, thanks for the ideas! :)

A trie will already run-length encode all the first letters into 26*5=130 bits pre-Huffman coding. I doubt RLE will beat that. A trie will in essence RLE every level but without needing to track the length of the run, so I suspect it'll outperform RLE at every level.

If you have a means of doing RLE that performs otherwise, I'd love to understand how it works.

FYI, turning it into 12972 by 5 and Brotli compressing achieves 15,093 bytes, which is less than if you first turn the data into an ASCII trie then Brotli compress that (14,180 bytes) (Source: https://github.com/adamcw/wordle-trie-packing#all-words).

This is neat. 1st letter, 2nd, then 3rd as simple lengths of runs; If you compressed a whole dictionary this way, it's possible you could then compress a document against that dictionary even further.

My only claim in this post is that anything can be pre-sorted if you want to achieve some better DS compression but of course, that means you have to have some map to undo the sorting after you decompress it (and obviously the utility only exceeds the computation time if the documents are longer than the associated dictionaries). The person who wrote the gameboy wordle compression did it by necessity, which is beautiful, and the way people used to do things when you had to fit them into tiny structures like that, so, huzzah! to that person.

But yeah, the observation that you could handle 40% reduction on the first two characters is a good clue.

So much has been missed in lossless image compression, along the same creative lines. We humans can look at an image of a red-black-yellow Cardinal bird sitting on a green-gray stem in the middle of a forest, and basically compress it in our mind in a way you'd have to throw thousands of CPU hours against. If you knew you only had to consider a red bird on a green background, you would have a whole different domain-specific strategy for compression; the amazing thing about our minds is that we can devise that compression strategy from the inputs, remember the strategy for that specific set, and then recall our own compression strategy well enough to decompress the data later.

There was, actually, an attempt in the 90s to do something they labeled "fractal compression" which was more or less an attempt to come up with a lambda function for a particular image; extremely CPU expensive to compress, and might or might not be lossy depending on the goal, but the salient thing was that the compression strategy was unique for each image. That didn't really work out as a commercial concept for a whole host of reasons. But it's one of those corners of extremely clever pre-modern code that might be worth a bundle to revisit now.

So if you wanna code something really, really fun -- consider a fully adaptive compressor that comes up with a specific strategy for each general sub-batch of use cases.

If you want to start a company doing that, let me know because I literally just came up with this idea 12 seconds ago.

To improve compression of a sorted list of words you can replace the (initial) letters repeated from the word above with spaces before compression and add them back as an extra step after decompression. For example, if the previous word was "apple", the next entry will be " y" ("apply", edit: HN removes extra spaces, so this should be four spaces + "y") ("apple" will probably already be entered as " le" (three spaces + "le")). In theory a compression algorithm could handle this automatically, but in practice this gives better compression.

This is conceptually similar to what OP does by storing the (numerical) difference between the words. Also, if you have a list of numbers that aren't random, they generally compress better if you turn it into a list of the differences between the numbers.

A simple compression algorithm (miniLZO is apparently 6KB compiled) might be small enough and save enough bytes with compression to make it worth it for OP.

You might want to look at locatedb and frcode - https://manpages.ubuntu.com/manpages/bionic/man5/locatedb.5....

If you want to skim, check out the EXAMPLE section toward the bottom.

Because all the words are five letters here, you should be fine to elide leading spaces in this case.

How would that work? If I want to store "apple", "apply", "apron" the bytes in memory would be "appleyron". How would I know where the second word ends?

One newline is probably better than 1-4 spaces.

Testing this with zstd -19

29.44% - Original sorted list just compressed with zstd

22.45% - Matching prefix characters from previous word replaced with space

19.38% - Matching prefix characters from previous word removed

In the more general sense, there is an almost universally overlooked property of compressed data that some of the data is unordered, and you are free to rearrange it any way you want in order to improve the compression ratio.

Years ago I worked on a J2ME (Java2 Mobile Edition) application that had no business being attempted given the very small archive files allowed. We did it anyway and it actually worked pretty well. We very quickly hit the max file size however, and every feature request meant first shrinking the existing code base to make space. First we had an intern fixing bugs in the code minifier we were using, especially around deleting unused (usually debug) methods. For some reason they rejected on archive size, not payload size, so while I started out doing 'honest' work with shrinking the binary, I had spent a lot of time in college noodling with compression algorithms so my eye was eventually drawn there.

Those were in the days when I could still read JVM assembly code, and shortly after I started thinking about the compression, I realized that the constant pool entries start with the type and then the size of the entry. So while our minifier made the reasonable assumption of sorting the constant pool by type and then alphabetically within it, because most of the constant pool was strings, and strings are variable length, it was hit or miss whether the header would be treated as a run or just Huffman encoded (the fallback). If I suffix sorted, then all but the last string in the pool would be followed immediately by the header for the next string, increasing the average run length.

This ended up knocking almost a kilobyte off of the archive size. Depending on your perspective that sounds like a little or a lot, but in our case each feature cost about 500 bytes, so that change pushed the cliff I was walking toward out almost a month (and slowing the growth rate), just by changing a sort algorithm.

I filed a ticket with Sun about this, but as it turns out they already had the dense archive format in flight, and within a couple months my observation was moot because the dense format can compress constant pools across and entire archive, not just a singe file. That was at least an order of magnitude better than what I had.

It's quite likely a lot of the files we use have similar problems in them. Off the top of my head, JSON compression probably would be much higher if we treated it as unordered, and did more aggressive minification particularly for JSON-at-rest. Sorting sibling keys by value instead of by name for instance.

Is this just a trie, but you reverse all the words first?

It's similar to the compression techniques you might use in column store

Is task specific compression a thing in real life practical software engineering? As far as reducing data loads go I only came across the keyword "SQL optimization".

One example that comes to mind is some work nvidia has done compressing “video” streams. They do so by capturing your facial movements and reconstructing them on the other side, resulting and massively less bandwidth.

https://developer.nvidia.com/ai-video-compression

Depends how specific you want "specific" to be I guess? I.e. we have loads of compression algorithms for different kinds of data. Whereas here we are looking at almost dataset-specific compression (i.e. the only benchmark is how it works for one specific set of data to compress), and there's a sliding scale between the two ends.

Similarly, having to contain the decompression code in the measured result size and it being a relevant contribution is something that only applies in some use cases of compression.

Scarcity breeds innovation. Why hand tune a compression scheme for a specific dataset when it is less storage efficient than LZ? You opt to not use LZ when all the memory and compute you have can barely run prefix codes.

That's why people still write for the Z80: it's a fun toy.

I have designed task specific data structures/compression oriented around memory efficiency. In my experience this starts to crop up when datasets get big enough to trigger cost for performance sensitivity. This is especially true for SaaS offerings, where e.g. an ability to stay under the next RAM doubling can result in serious hosting savings.

I'm echoing a couple of replies before me, but I'll give concrete examples - MP3, JPEG, and H.264 are all lossy task-specific compressions. Lossless compression includes FLAC and TIFF.

For genetic data, HapZipper beats general-purpose compression. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3488212/

So, yes, actively researched, but you've got to pick a specific task that makes sense. Even small niches are viable; I made a task-specific compressor to strip the essential numbers out of a remote sensor report to make it small enough to squirt to a satellite.

Video compression algorithms are fascinating. Choosing the correct color space and reducing bit count because the human eye doesn't see color as well, using discrete cosine transform to "group together" the important parts of an image, using diffs from previous and future frames, using diffs from movement in the image. There are so many techniques.

It used to be just best practice to shrink down anything over the wire as much as possible. When I started building websites around 1996, every byte counted and you would "optimize" every GIF image carefully to the smallest size you could, taking it down to 256 or 16 or even custom colors - like 6 colors in the VGA spectrum that looked good enough with dithering.

It kinda didn't matter from 2010 on. But one area I've written my own specific "compression" methods in, for the last few years, has been in shipping data in and out of webworkers (in-browser or in Node). This is where there's still enough of a performance penalty on a lot of devices for sending 1MB that in use cases where you're spawning lots of workers to run long tasks, it makes sense to trade time to compression for a smaller transfer size.

Here's another example from a constrained environment: in Andy Gavin's interview with Ars Technica, he talks about a domain-specific compressor they made for storing Crash Bandicoot's animations, because storing each coordinate of each vertex for each frame would have been too large.

https://www.youtube.com/watch?v=izxXGuVL21o&t=21m12s

Yep, in video games, especially on older systems, we did an awful lot of that. Storing vector deltas for bone animations rather than the full vector3. Compiled graphics on old PC games I worked on, which both helped in size, but also in speed of blitting to the display. Vector3 are made up of three 32-bit floats, but frequently stored as four 32-bit floats so that everything aligns on word boundaries, but you don't need to do that for data you aren't currently using, so you can save 25% of memory right there. Also, interleaving vector3's for packing and alignment on 3d models. Lots of bitmask manipulations and interleaved SIN/COS and DIV/MUL look-up tables. These last couple of techniques go all the way back to the original Atari Asteroids game from the arcades in the 1970's.

Anything that has limited memory or limited bandwidth, or where the data is much larger than the available memory or bandwidth, e.g. neural compute models at the edge in a IoT device, word databases on limited memory systems, and foveated compression in VR/AR on super high bandwidth connections that still cannot keep up with the 16K video stream given modern video protocols.

Anytime you're trying to squeeze more performance out of old/underpowered embedded hardware you'll come across stuff like this...

Eg. You work for a doorbell company and the boss says "yo, can we make our doorbell have 6 tunes instead of one, because our competitors are doing that. No, we don't want to change microcontroller".

At transit app, we built a domain specific compression for transit schedules. So instead of a city like New York taking 100mb, it takes like 5mb or so. This was a couple years back when data was still more expensive, so one of the things it allowed is simply always downloading schedules for offline availability, instead of having to ask the user when and what to download. Here's a write up (sorry for the cheery tone) with some details

https://blog.transitapp.com/how-we-shrank-our-trip-planner-t...

Yes! Not only is it a real thing, but with Moore’s Law slowing down, data/compute appetites going up, and the gap between processing speed and memory speed still large and growing, the need for task specific compression is currently going up.

Working on GPUs, I see many, and work on some task specific compression ideas as part of my job. The compiler has it’s own ways of compressing code & debug info. The hardware has it’s own ways of compressing textures. A recent feature we built on my team is a compressed encoding for adaptively subdividing curves. All of these things have the primary goal of reducing memory bandwidth, which in turn increases the speed of computation because memory is so frequently the main bottleneck.

Of course. For instance when you have an embedded controller with limited ROM size and you run out of space, compressing the message strings that are sent to a till roll printer or display might be the only way you can get enough space to add a feature.

I had to do this in the early '80s. The alternative was scrapping the boards and redesigning them to allow double the EPROM size but that would have been a lot more costly than writing the decompression routine and manually compressing the strings. It would also have delayed delivery.

Related but not the same: does anyone have information on how the old T9 pre-smartphone system stored its compressed and fast dictionaries? I remember reading about it a long time ago but can't find it now.

That system used some sort of lossy compression that created artifacts like fake words that don't exist but look enough like real words from the dictionary's point of view that they can be generated.

I find it fascinating.

Over on http://golf.horse/ there are leaderboards for finding the smallest Javascript programs that output various word lists, including the Wordle list. I've found it to be a fun and educational challenge. I would be excited to see more submissions!

Hasegawa Sayuri wrote up some notes about their submissions at http://sayuri.tx0.org/golfhorse/, including an extremely elegant and compact encoding of huffman trees.

Interesting that page suggests that the wordle dictionary is 'at most 11.11 bits per word', which works out to 18015 bytes, slightly higher than was achieved here.

Golf.horse is measuring the payload plus the compressor, which I don't believe the author is doing, and is important when trying to be objective about the relative strength of solutions. Otherwise you can store the entire file out of band in the compressor, emit 1 bit in the output file, and then the compressor just returns the expected value on 1 and throws an error on 0 saying the file was corrupt.

The other major difference is that golf.horse requires the payload to be valid uft8 javascript, which means your binary blobs are essentially limited to base64 encoded strings. You might manage slightly better, but I suspect the limit is somewhere around 6.5bits per byte.

On the gameboy, you have the advantage of being able to use the full 8 bits per byte.

The possible number of x-byte-long valid UTF-8 strings is defined with the following recurrence relation:

    f(-x) = 0
    f(0) = 1
    f(x) = 0x80 * f(x-1) + 0x780 * f(x-2) + 0xf400 * f(x-3) + 0x100000 * f(x-4)

(Replace 0x80 with 0x7c to account for ES6 template literals.) The characteristic polynomial for this recurrence has a positive root of 144.61 (or 141.12 for literals). This means that you can actually put quite more than 7 bits per byte in a valid JS code, provided that your decoder is negligibly small enough. Indeed, there exists an encoding that allows exactly 7 bits per byte by using two-byte-long UTF-8 sequence as an escape code [1].

[1] http://blog.kevinalbs.com/base122

Huh. Javascript is significantly more accepting of non-printing characters in it's strings than I was expecting. I guess I should have known better.

There's definitely apocryphal stories of someone winning a compression contest with this very approach :)

You can get down to 15,559 bytes by combining a trie with Huffman coding: https://github.com/adamcw/wordle-trie-packing

However, this doesn't beat general Brotli encoding of a ASCII trie representation, which gets down to 14,180 bytes (but needs an experience decoder), but goes to show general purpose compression is still really really good these days.

brotli on the raw word list gives 17194 bytes. gzip gives 32352.

A lot can be done in 3014 bytes, but what's the difference in code size for the ascii trie vs. a flat list/gzip/brotli?

A trie representation physically removes letters from the dataset. Leaving it in ASCII means that it still leaves enough information behind that can be compressed well (a trie only exploits shared prefixes, not suffixes).

Roadroller [1] is probably a borderline general purpose compression algorithm, and with some automatic parameter tuning it results in 12,170 bytes estimated, at the expense of a lot of memory. "Estimated" because the algorithm was originally meant to be recompresssed in a ZIP file, so it doesn't bother to generate the smallest JS file in terms of uncompressed size (yet). But that estimation does include the decoder size so it is a good estimate for the Kolmogorov complexity of the generated code though.

[1] https://lifthrasiir.github.io/roadroller/ (the exact parameters: golf.horse dataset; input mode text; action write to document; # contexts 12 with 12,15,49,50,70,79,96,97,131,154,292,353; pollute the global scope; max memory usage 150 MB; precision 16; learning rate 1333; model max count 11; model base divisor 14; dynamic model flags -1; # abbreviations 64)

I tried this out and got 12,231 bytes Brotli encoded, and 12,493 bytes gzipped, with 16,311 bytes raw -- so the estimate is very close.

It compresses better with new lines than if you remove them all (given you could just split on every 5 characters later), which is an odd quirk of compression algorithms that my brain will never quite grasp.

My best algorithm attempt + Brotli achieved 12,773 bytes, which is a painfully close 542 bytes away. It is 13,181 bytes raw though, and can technically be used in-memory, which is definitely a perk.

> It compresses better with new lines than if you remove them all (given you could just split on every 5 characters later), which is an odd quirk of compression algorithms that my brain will never quite grasp.

New lines give a usable context (namely the word boundary) to compression algorithms. If I give you an arbitrary unsorted list of 5-letter-long words with no delimiters you need to think harder to figure out that it is indeed a list of 5-letter-long words. Same for the compression algorithm.

> My best algorithm attempt + Brotli achieved 12,773 bytes, which is a painfully close 542 bytes away. It is 13,181 bytes raw though, and can technically be used in-memory, which is definitely a perk.

Yeah, the best solution depends on what you want to do with that. Your estimation is not too far from my experience: Roadroller tends to be on par with or slightly smaller than Brotli. Of course, Roadroller exists because web browsers generally don't provide a way to use Brotli in JS ;-)

Huffman coding was the first thing that jumped into my mind, too. Reminds me of the time we implemented a subset of bzip2 on a CS class in highschool.

Arithmetic coding is a drop-in replacement for Huffman coding that saves binary roundoff. It's less known because it was patented, and the (short) code to implement requires optimizing a tricky 1.0000 versus 0.9999 issue (in binary).

The usual application involves letter frequencies without context. Rather than a trie for deterministic context, one could in far less space compute a hidden Markov chain of small but effective dimension, to generate the probabilities for arithmetic coding.

Thanks, I'll look into it. This case is interesting though, because the Gameboy doesn't even have native mul/div operators, so I suspect that Huffman coding is as fancy as you're going to get while still having a small and efficient decoder that isn't taking up more space than its saving.

>The Answers could be stored as a bitmap of length 12972, which would be 1622 bytes. But this would make the code for generating a random word more complicated and slower.

You could run RLE on that as well for a decent storage savings.

Another thought: you could order the list of words such that the first 1622 words are answers. That way you don't need to store the answer list and checking is as fast as comparing the value of a memory address. This would probably hurt the differential coding performance though.

I was thinking that it's probably not quite sparse enough to benefit from RLE as-is, since the number of bits you'd need for your lengths would outstrip the length of your run. If any run can be more than 128 words, then you'd need at least 8 bits for the run, making it only beneficial for runs of longer than that.

An alternative would be to make 0 mean five zeros (or some other N) and then if you hit a 1, it means the next 5 bits are to be interpreted as-is. This reduces all 5 length 0s to 1 bit, while only adding 1 bit whenever there is a bit. At worst this introduces 1 extra bit per answer. The answer to non-answer ratio is about 5 to 1, so this should definitely save space while also having a trivial decoding algorithm.

Probably not suitable for direct RLE as you say, but if you looked over the data I suspect you might find that a stepped RLE, where you interleave two or more RLEs could provide a savings. You do of course need a cache to decompress parts of the intervleaved RLE'd data into.

I've noticed in the past (trying to optimize traffic for a game with delta compression, variable-length integers, ...) that it's really hard to beat good compression with manual tricks.

Original word list: https://raw.githubusercontent.com/arpruss/gb-fiver/main/comp...

    $ <full.txt wc  # "word count"
    #lines, words,  bytes
    12973   12972   77833

    $ calc 77833-12973  # bytes minus newlines
    64860  # matches the article, to confirm I got the right input data

    $ <full.txt xz -9 | wc -c
    15412

2000 bytes smaller without any optimizations (this even includes the newlines), though now I guess the question is what the size of the xz decompressor is since a few KB actually matter (not like on a regular computer).

For some reason bzip2 gets it only to 36K, even worse than gzip (32K) and zstd (29K).

Update: Counter-intuitively, stripping the newlines (... | tr -d \\n | ...) results in a higher compressed size with xz. It's surprisingly hard to find a minimal xz decompressor, it doesn't seem as though anyone bothers with this stuff. The Hutter Prize includes the decompressor so that was my first stop, but none of the contestants submitted that (I assume they predate xz).

Update#2: Found at least one measurement of xz decompressor at 36K, but it seems to me like this is the general-purpose utility and includes the compressor, help output, etc. http://mattmahoney.net/dc/text.html

You can beat 15,412 bytes with a much simpler decompression algorithm than xz. Using variable length encoding on a tail-sorted delta-offset array gets down to 13,180 bytes.

Neither competes with RoadRoller (which gets down to around 12,200 and includes the code for decoding), but that takes forever to decompress and uses a ton of memory so certainly not applicable for this application.

See my other comments in this thread if you have interest!

My first thought would be “DAWG”. That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one.

https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l... compresses a 780k word list into 175k. That’s about 22% of the size. This accomplishes 27%.

This list is a lot shorter, so there will be fewer opportunities for savings. On the other hand, all words are five letters, so the ‘is a word’ bit can be taken out.

> That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one.

That sounds like a DAG-shaped FSM to me...? At least I can't spot the difference.

Yeah, tries are special cases of FSMs, and so are DAWGs.

Ah, apparently I didn't manage to connect the sentence I quoted with the preceding sentence. Now I get it.

That’s correct. https://en.wikipedia.org/wiki/Directed_acyclic_word_graph links it to Deterministic acyclic finite state automaton (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...)

I guess a strategy for compressing a word set could be to compile a regular expression recognizing it using a good regex engine and to then construct a compact representation of the resulting automaton.

I tried this method today, but a huge shortcoming here is that a DAWG needs these large pointers between nodes.

I based my approach on http://www.wutka.com/dawg.html and http://stevehanov.ca/blog/?id=115.

I generated a DAWG with 12,822 nodes, which means you need 14 bits for each pointer. A trie representation can be packed much smaller because you don't need to randomly jump around the graph, you can just read it out sequentially.

With huffman coded labels and offsets, I got the size down to approximately:

- 94,761 bits for offsets. - 56,900 bits for labels. - 12,822 bits for indicating when you're at the end of a next chain.

= 164,483 bits + Size of Huffman Table = ~20,560 bytes

I assumed I didn't need any bits for indicating end of word, because all Wordle words are length 5.

Meanwhile, bitpacked trie can get down to 15,599 bytes.

https://github.com/adamcw/wordle-trie-packing#all-words

It's not clear to me a path that will compress the DAWG so much that it could cut another 5000 bytes and whatever the Huffman table size is.

I feared that (“This list is a lot shorter, so there will be fewer opportunities for savings”)

However, I think you can layout the tree so that no pointers point backwards. If so, can you make those offsets smaller by making them relative to the current point in the tree?

Also, since the list only has five-letter words, for the last letter, you don’t even need the letters themselves, just 26 bits for what letters can complete a word. That might be a saving.

Also, the crab source code is available (DEC: http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt, Mac: http://www.gtoal.com/wordgames/jacobson+appel/mac/Crab_sourc.... Both via http://www.gtoal.com/wordgames/scrabble.html)

Both are nice examples of C the way it is intended to be written, or rather, was intended to be written decades ago.

I don’t remember how that stores the data, but it might do a trick you didn’t think of.

And finally, I just realize that, for fairness, you need to look at (data size + decompressor size). Did you do that?

Ah, I replied to myself with more information while you were also replying.

I also surmise that the short length of the words makes a DAWG just very heavy.

It's not clear to me that relative offsets would be notably smaller to the extent that would be needed. Even a hypothetical and cheated DAWG I came up with is ~33% bigger than alternatives. I've generally explored enough (see the paper in my other comment) that I don't feel that further investigations into a DAWG are likely to outperform other methods.

I can't see anything immediately that jumps out that the Crab game is doing that's special to save space, I think it just achieves better compression because you can compress larger files easier, and the words are longer with more overlapping sections.

I agree that you need to compare including the decompressor size, so I'm not sure which approach is better the Huffman trie or the one in the original article. I'm not familiar enough with GB programming to be able to suggest how much program memory would be needed to decode the Huffman Trie, it looks like it would be somewhat similar in complexity.

Thanks for all the informational replies.

I ended up doing some math on a theoretical DAWG, based on: https://www.cs.put.poznan.pl/dweiss/site/publications/downlo...

With 12,822 nodes, you need 57,387 bits for the labels and the Huffman table (I'm sure you could make the Huffman table more efficient, but it's only 50 bytes, so that's not helping much).

Then, to mimic their edge reordering technique but without having to actually implement all the logic, I ordered the edges by frequency and used variable length integer encoding of size 3 (this performed the best on the data set) which required 95,988 bits.

Variable length integer encoding breaks the number into 3 bit chunks, each prefixed by 1 bit to indicate if there is another 4 bit chunk to read for that number. Since the distribution of offsets is heavily skewed, optimizing the most frequent offsets into a small package is better even if rarer ones suffer from multiple prefix bits.

This is 19,171 bytes total, or substantially worse than both the original article and Huffman tries do. This isn't even counting the flag bits needed for actually traversing the graph. So even cheating, it's not clear I can get a DAWG to be within striking distance of either other approach.

I hypothesize that the reason tries and other methods perform so well here is the relatively shallow depth. All words are only length 5, so the trie doesn't ever get really deep. This also means that suffixes generally don't actually take up that much space given common ones will also pack small with Huffman coding. The size of offsets appears to be just too great relative to how much you can save by removing shared suffixes from 5 letter words.

Would love to know if there is some trick to DAWG that I'm missing that would let me get it even smaller.

I haven't done any noodling with compression in some time and I'm tempted to sit down and try this. But I think he must be using a different list than I can find because the numbers don't quite add up.

Any time you are tasks with crushing the living daylights out of an unordered list, always, always look at suffix sorting as an option. It might not work out as useful, but it's frequently worth the cost of checking.

I will say that given that a delta encoding was settled on, bitpacking the words first is probably a mistake, and multiplication should have been used instead. For instance using multiplication you can store the words in 24 bits without chopping off the first character and using pointers to them. That may seem a small difference but it makes the deltas he's looking at narrower. So instead of choosing 8 words in 8 bytes versus 10 words in 8 bytes, it could be 8 vs 11, possibly 12.

It looks like the reliance on 5 bits per character versus using 26*5 is that a lot more of his deltas get an extra character.

He is encoding 7 bits per byte, so there are about 172 words that spill over into the next byte due to this.

With 5 bits per letter, if the second to last character shifts by more than 4, then it automatically spills over. With 26, it also depends on how much the last letter also varies.

My flashcart's GB emulator doesn't have a color palette that matched perfectly, but works well enough! https://i.imgur.com/ePtY5Jf.jpg

Found a GBC implementation as well: https://github.com/bbbbbr/gb-wordle

The linked GBC version is my fork with some improvements (and more in the works).

The current published release uses a similar compression approach by zeta_two, but in current builds I've switched to the compression by arpruss since total data + decompression code size is now a couple hundred bytes smaller.

I did some profiling and code size measurements before switching over. https://github.com/bbbbbr/gb-wordle/blob/compress_arpruss/wo...

Speed (and code size somewhat) have improved more since then.

Not sure what technique you're using for the answers list, but the compress5.py suggests it's doing a basic bitmap.

Base bitmap is 12972 bits, or 1622 bytes (your file lists 1619, not sure why it's 3 bytes smaller, but all the same). You can "skip encode" (I don't know the formal name for this technique) into 1232 bytes by encoding runs of three [0, 0, 0] as [0], and anything else as [1, X, X, X], saving another 390 bytes.

I tried all combinations of runs between 1 and 7, and 3 is optimal.

Not sure how big the word dict is in your latest version, but you can do much better simply by reordering how you create your index.

With alphabet in order, assembling letters ABCDE: 17345.00 bytes With alphabet in order, assembling letters EDCBA: 16949.00 bytes With alphabet order tweaked, assembling letters EDCBA: 16309.00 bytes

Where tweaked means you build your offset as if each position was ordered like this ([::-1] means reverse if you're unfamiliar with Python).

``` alpha1 = "abcdestfghijklmnopqruvwxyz"[::-1] alpha2 = "eaioustrbcdfghjklmnpqvwxyz" alpha3 = "aeioustrbcdfghjklmnpqvwxyz" alpha4 = "eaiousthrbcdfgjklmnpqvwxyz" alpha5 = "aeioustryhkbcdfgjlmnpqvwxz" ```

You can also use a prefix rather than variable length encoding, this means you can use 2 bits to represent a number bigger than 2^14, rather than 3. This might hurt your ability to decode though, as you'll have bits that cross byte boundaries.

  breaksv = [2**7, 2**14, 2**21]
  prefixesv = [[0], [1, 0], [1, 1]]

You can get much smaller using length 3 varints rather than 7 (13,110 bytes), but I presume that would perform worse on GB hardware than staying byte aligned.

There's a technique whose name I can't remember, where you take a bunch of words and you produce a much shorter string that has all of the input words in it but overlapping, where the beginning of one word is the end of the previous. Functionally it's like a 1 dimensional word search, and you store pointers into it for all of the individual words.

Anybody know what I'm thinking of?

I think you are thinking of a trie

No, not a trie.

After throwing more words at the Google Wall, it finally allowed that what I'm thinking of is the Shortest Superstring Problem.

Nerd sniping indeed.

This morning without putting a whole lot of effort into this, I was able to winnow it down to 27.32 bits per word without any other trickery like 5bit packing. You need at most 1 bit per word to identify the real words, so that's 27.32+1 bits without the bitpacking. Doing 6 bits per letter drops that by 25%.

Now having put too much effort in, I'm around 21.6 + 1 bits per word, (17 bit packed) just by using SSP.

You can see a trie in action used to build a better regex expression: https://www.npmjs.com/package/trie-regex

You can probably get better compression by storing the words in a minimized acyclic finite state automaton, since then e.g. shared prefixes and suffixes between words are compressed. Finite state automata can be stored as compact contiguous tables and you can use some of the same tricks as in the article to compress characters on transitions.

The linked post reaches 3.6 bits per byte. E.g. [1] uses finite state automata to reach 1.1 bits per byte for a Scrabble word list and 1.5 bits per byte for an English word list. Both word lists are probably more difficult, since they contain words of varying lengths and long words have less sharing in their pre/suffixes.

[1] https://www.cs.put.poznan.pl/dweiss/site/publications/downlo...

5.5 bits per word is pretty good. 18 bits per word leaves room to be undercut by a lucky break with a Bloom Filter.

But not for Wordle, since a Bloom filter cannot enumerate items? (So, you can't tell which letters were correct.)

What you'd need is a Bloom filter with no false positives in the 26^5 keyspace, and then you'd have to guess random words on startup until you got a hit, which on average would take you 917 guesses.

Which is terrible but still probably faster than the algorithm that the linked article is using, since finding the offset of the kth worth takes O(k) time, and there are 12948 (I still haven't found the mythical 12972 word list).

The 12972 are in the old source: https://web.archive.org//web/20220201010250js_/https://www.p...

NYT source: https://www.nytimes.com/games/wordle/main.4d41d2be.js

NYT removed 6 words from the solutions

agora pupal lynch fibre slave wench

and 19 words from the guessable list

bitch chink coons darky dyked dykes dykey faggy fagot gooks homos kikes lesbo pussy sluts spick spics spiks whore

so that's 12972 - 25 = 12947

What in the actual fuck.

I am glad they did that, but I'm not sure I wanted to know that those used to be in the dictionary.

(also you are probably on a list now, but we appreciate your sacrifice)

I think you might have miscalculated bits per bytes here?

8 * 17,763/64,860 = 2.19

Also, I attempted to implement this as described in this paper (variable length encoding the letters and the offsets, utilized L, and dropped F entirely because all words are the same length, N didn't make a big difference).

I achieved a naive size of 20,560 bytes, which I didn't have confidence implementing more advanced techniques outlined in the paper would get the size down sufficiently to compete with using a trie+Huffman representation (15,599 bytes, https://github.com/adamcw/wordle-trie-packing#all-words).

8 * 15,599/64,860 = 1.92 bits per byte.

https://en.wikipedia.org/wiki/De_Bruijn_sequence

Interesting. Here we don’t care about duplicates though, except that they may indicate we had yet to arrive at the optimal solution.

But it’s possible that you could accidentally make duplicates of one word by pairing others. For a single copy you can omit that word. But if it appears multiple times that represents a compression opportunity that a shuffle to avoid it might destroy.

See tom7's portmontout

http://tom7.org/portmantout/

an extension of portmanteau:

https://en.m.wikipedia.org/wiki/Portmanteau

De Bruijn sequence is more restricted: a cyclic portmontout over a "complete" lexicon of fixed sized words, where every possible string is a valid word.

Strictly speaking, treating the word list as a ring buffer might actually make it a little smaller. Perhaps more importantly, the cycle makes the problem almost exactly analogous to the Traveling Salesman Problem (Although there is an acyclic TSP, it is somewhat lacking in interesting properties like isomorphism)

There’s a similar algorithm for indexing words in text collections (I know it from the ‘Managing Gigabytes’ book).

Say you want to store the information that the word ‘algorithm’ occurs in documents 42, 2718 and 3141. That’s a sorted list, so as the author notes, you can just store the differences (42, 2676, 423). Those differences can still be arbitrarily large, but if there are many documents, you can expect most differences to be small.

The trick is to store the numbers not as fixed-bit-size integers, but using a variable-length encoding. The algorithm stipulates using a Golomb code with the parameter b = ceil(N / n * ln(2)), where N is the number of documents in total, n is the number of documents containing our word, and ln is the natural logarithm.

For our example, assuming 5000 documents in total, this gives N = 5000, n = 3, b = 1156, and our index entry is 10000101010001010110110010110100111, for a total of 35 bits.

> I don’t have a good feel for how fast the Game Boy runs, so I did a bit of speed optimization.

This sounds like a very wrong approach to optimization. I mean, if you don't know exactly what and how to optimize, or if there's a need for optimization at all, then what are you doing?

I read it as "I don't know how fast a Game Boy runs, so I optimized for speed rather than minimal size"

The idea of 'don't optimize if you don't have to' probably doesn't apply as much when developing a game for a 8-bit processor that runs at 4mhz with 8kb of working RAM, and when you are building a program which is inherently aiming to push the capabilities of the hardware with clever coding tricks (I mean the whole project is basically an exercise in optimization).

I think OP was saying they weren't sure if the original algorithm would be too slow to run under these conditions, and didn't have the ability to test it at the time, so they wrote it in a way which increased the chances of it running quickly considering the system limitations.

Once you have the delta encoding scheme, do you actually gain anything by splitting into 26 lists by first letter? It seems like the wrapping delta from a->b, b->c, etc would take similar space as the 2 byte pointer in the table, but simplify the code.

Saves you the CPU cycles of having to step through the entire list when the word is zebra.

Does anybody know how much words the Lingo/Motus GB game had ? Can't find the info online. Might be interesting toncompare to the original 1994 version (if it can be decompiled ?!).

In '94, it was possible to have multi-MB cartridges. They used bank switching to access all the data.

There was as similar discussion about Barclay's bank, and a list of 74,000 numbers:

https://shkspr.mobi/blog/2021/05/the-74000-numbers-of-barcla...

I tried a similar scheme of sorting the list and storing the delta of the previous number:

https://news.ycombinator.com/item?id=28348965

The colors are misleading in my opinion.

Green usually signifies something is correct. You should have used yellow for misplaced letters instead.

I had CRAN? in the second row, but I lost the game, because it was RANCH.

lol yes, I played it and was so confused, the colors are literally backwards!

  $ grep '^[a-z]\{5\}$' /usr/share/dict/words | python -c '
  > from sys import stdin
  > from os import write
  > N = 26 ** 5
  > data = bytearray((N+7)//8)
  > for l in stdin:
  >     b = 0
  >     for c in l.strip():
  >         b *= 26
  >         b += ord(c)-ord("a")
  >     data[b//8] |= 1<<(b%8)
  > write(1, data)
  > ' | gzip | wc -c
  12126

decompression code costs extra. Though I imagine someone has a small gunzip implementation somewhere.

Zlib's implementation, at least, requires more working RAM (~40 KB) than the Game Boy has (8 KB). https://github.com/madler/zlib/blob/master/zconf.h

        The memory requirements for inflate are (in bytes) 1 << windowBits
      that is, 32K for windowBits=15 (default value) plus about 7 kilobytes
      for small objects.

This example above is the entire dict file, not the wordle file, so it might be worth looking at this.

I'd have to check the version history, but while 15 bits is the default it's also the maximum, and you can go down to 8. Hardware has gotten a lot faster.

> This example above is the entire dict file, not the wordle fil

only 5 letter words from the dict, not the entire one. check the grep command at the beginning.

Right, but it's still many times larger and compresses better.

I think you'll find if you use the real dict that your compression numbers are much worse. I got around 25k using a list I hunted up.

There is also a NES port in the works: https://twitter.com/FG_Software/status/1495400042722897925

And a C64 port: https://twitter.com/roysterini/status/1493540659352985602

A brief quote about compression in the NES port:

https://twitter.com/FG_Software/status/1491044035884371971 "Official #Wordle dictionary implemented, and the game can now select a solution from all those found in the original for the cost of 1 extra bit per word! Uncompressed size (Raw text files): 76060 bytes Compressed size: 26256 bytes"

https://twitter.com/FG_Software/status/1495298243668099073 "Words are stored in 2 bytes: 15 bits data, 1 bit to check if it's a solution. They're all sorted alphabetically, so I can algorithmically determine the first 2 letters with a lookup table, and stick the last 3 letters in 15 bits. Bit more to it but you can't fit it all in a Tweet"

I've been working on a Game Boy Color (and regular GB) fork that in current builds uses the compression by arpruss. https://github.com/bbbbbr/gb-wordle

oo oo, idea... trying to implement it now:

With 5 bits per letter, you have 6 symbols left over. We can use those to represent alternate pairs like "A or E", so you can encode BANDS and BENDS at the same time. Looks like if you pick the 6 highest frequency replacements for each starting letter, you can reduce the full word list size by ~2k words.

A naive lookup table for the replacements is 26 * 2 * 6 = 312 bytes.

edit: oops double counted the reduction

Since delta encoding is applied after this step, it's probably better to just use 26^5 instead of trying to pack extra things into those bits.

oook did some experiments... just counting the size of the delta streams: 17346B for 26^4 and 16852B for 32^4 (as described above)

interestingly, the sweet spot is a mix at 30^4 at 16797B

I've been using the cleaned up list, so it's possible that changes the behavior a little bit.

But more likely one of us has a bug in their logic.

Hmmm... sounds familiar https://justinlloyd.li/blog/word-search-game-part-two/

Many times you don't even need to store the individual letters, just the pairings, and if you are permitted to prune out troublesome words from your dictionary, all the better.

Are there general purpose compression tools that preserve the data, but not the ordering?

[One of] the reasons gzip does worse is it also preserves the order of input.

That's what I was thinking, too. Are compression algorithms for Sets a thing? Might be useful for compressing JSON, because the key-value pairs are a Set.

Did you compare this to compression with a trie?

See step 1; the first level is stored as a trie. Then, see Notes, where it's stated that trie-ifying level 2 requires more space.

I imagine only having to store 5 bits for the differences accounts for a large swath of the savings. With the first letter bucketing the rest of the words in a sort of trie-like behaviour, I wonder if there's enough duplication of successive characters for a full trie to be worth it. After all, there would need to be extra bits used to store leaf/node identity, as well as whether there are _more_ nodes past the current leaf. I suppose instead of using markers to denote ends, the parent node could store a count, but that might be wasteful for buckets at the fourth character.

I'm very curious about this.

I wonder why the first letter is used on its own. Getting the first letter in 5 bits + 3 bits out of the second should make the first array much more densely populated. Maybe making the further lists more sparse offsets the gains?

Like y'all, I wanted to see how I could do. Of course, I didn't get all the way to tested code on a gameboy. But it does compress & decompress in Python.

I took the central idea of encoding deltas (or actually delta less 1, since the delta is always at least one; I'll just say delta below), but did it on the full five letter word. The largest delta was still less than 2*18 but bigger than 2*17. (I'm not sure why the blog mentions 20 bits as the biggest delta; I used the dataset from https://github.com/alex1770/wordle/commit/62520406365ca58a1a...)

I decided I wanted a variable length code in bits. Manually, I found the best break-points that I could:

    breaks = [16, 128, 512, 2**12, 2**18] 
    bitprefixes = ['0', '10', '110', '1110', '1111']

So deltas 0..15 are encoded as '0' plus a 4-bit number, deltas 16..271(=16+256-1) as '10' plus a 7-bit number, etc.

Compressed like that, my dictionary runs to 14840 bytes.

    1111000000000001010110 // aahed   4839 =    4839-      0
    1110100001101100       // aalii   2813 =    7652-   4839
    1110110100010010       // aargh   4003 =   11655-   7652
    110011000010           // aarti    339 =   11994-  11655
    1111000000001101110001 // abaca   5634 =   17628-  11994
    00111                  // abaci      8 =   17636-  17628
    00001                  // aback      2 =   17638-  17636
    00111                  // abacs      8 =   17646-  17638
    100111110              // abaft     79 =   17725-  17646
    ...

However, a non byte aligned code isn't ideal, especially on the gameboy's CPU which doesn't have variable bit shifts as far as I recall. Still, over 3000 bytes beckoning to be re-used for some other purpose. Did they put in a soundtrack yet?

Compressor & decompressor: https://gist.github.com/jepler/d502965b57fd52df0838a6def2d32...

I like your trick of subtracting the prior node size if it's too small, it gets a number of offsets into the lower bucket to save some bits.

I took this technique and made a few changes.

Firstly, I effectively did variable length integer encoding in chunks of 3, this mildly outperformed your hand crafted prefixes.

    self.breaksv = [2**3, 2**6, 2**9, 2**12, 2**15, 2**18, 2**21]
    self.prefixesv = [
       ['0'],
       ['1', '0'], 
       ['1', '1', '0'], 
       ['1', '1', '1', '0'], 
       ['1', '1', '1', '1', '0'], 
       ['1', '1', '1', '1', '1', '0'], 
       ['1', '1', '1', '1', '1', '1', '0']]

Secondly, I made my offsets relative to the overall solution space of 26*5, ordering the words sorting from their ends, and with a little bit of twiddling the order of the alphabet to put common letters near the start:

  alpha1 = "aeioustrbcdfghjklmnpqvwxyz"
  alpha2 = "aeioustrbcdfghjklmnpqvwxyz"
  alpha3 = "aeioustrbcdfghjklmnpqvwxyz"
  alpha4 = "aeioustrbcdfghjklmnpqvwxyz"
  alpha5 = "aeioustrybcdfghjklmnpqvwxz"

  bitmap = []
  for ia, a in enumerate(alpha1):
    for ib, b in enumerate(alpha2):
      for ic, c in enumerate(alpha3):
        for id, d in enumerate(alpha4):
          for ie, e in enumerate(alpha5):
            bitmap.append(e+d+c+b+a in words)

Doing this, and then doing the variable length encoding I got the file down to 13,181 bytes (it was 13,180 bytes, but I needed to add a 7 bit termination string so that you can properly decode the file after you write it to disk, otherwise when the file rounds to the nearest byte you have random 0s that get decoded).

I'm sure with some twiddling of the alphabets some more you could save a few more bytes, but this does better than both Brotli on a ASCII trie and the Huffman Trie by almost 1KB (https://github.com/adamcw/wordle-trie-packing#all-words), so I'm very happy.

Nice!

Can't you just pack the last byte with 1s, rather than having a whole extra byte?

A good idea, saves a couple bits depending on alignment.

Looks like you can try it out on this webassembly Gameboy emulator https://wasmboy.app/

For anyone playing, the dark green letters are correct and the lighter green letters are in the wrong spot. Took me 4 tries before I figured that out.

I once came across a calculator-like device that had some version of a Bible stored in it. But not very well. It clearly had a dictionary with the text stored by word number, because some of the longer words were off by one word in the dictionary. This produced some strange texts.

I think that in this case, the original text is rather strange to start with.

When I was a kid my parents had some bible (plus other books) software for their PC XT that came on dozens of 360K floppies and filled most of the 20MB hdd. What impressed me most was the search feature, and I've never seen anything like it since. You could search for a word within N words or N verses of another word, for example. I always wondered what indexing structures allowed that on an 8MHz 8088.

There was a pretty decent Scrabble available for the ZX Spectrum - around 41k for vocab + code. I always imagined that must have used a fairly ingenious compression mechanism for its dictionary, especially given the types of fairly open searching it would need to do.

May have been a DAWG like this: https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l...

These days GADDAG are used which are faster, but usually much less space efficient: https://en.wikipedia.org/wiki/GADDAG

Neither seem to work well in my attempts on this data as the words all being short and the same length work against it in these schemes.

Good job!

Works perfectly on the 3DS (mine is a New 3DS XL) with the NSUI! https://i.imgur.com/TjGYsKC.jpeg

Zero suppressed binary decision diagrams are the best

i wonder if the letter frequencies across the corpora could justify variable length character encoding.

Can we compresses further by optimizing for only testing set membership?

There is probably a bloom filter that covers all 26*5 possibilities with no false positives but that's somewhere over 10 bits per element or 16215 bytes not counting the encoder.

Might be a perfect hash waiting in there somewhere.

Why use one byte for each character? Why not 3 bytes per word?

Please see step 2.

> Step 2: Each four letter “word” (or tail of a word) can be stored with 5 bits per letter, thereby yielding a 20 bit unsigned integer.

Does anyone know of a HN client that supports keyboard blocking? I really don’t understand HN’s obsession with this game.

Go downvote someone else, this is something people want.

https://news.ycombinator.com/item?id=30440491

Bug? See screenshot. My 5th guess shouldn’t have gone down like that for a conventional Wordle clone.

https://ibb.co/93CdVWv

Looks like maybe a bug in highlighting multiple occurrences of a letter in the same word, yeah.

Black is right letter right spot. Green is right letter wrong spot.

Ahh thanks for this. Found it super confusing!

Oh my fault.. assumed the color scheme was the same:

Reply on news.ycombinator.com