Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

alexanderpruss.blogspot.com

Post reply on HN
Print view View original

161–170 of 170 posts

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

#161

Post by jepler »

quicktwo wrote: post #155
jepler wrote: post #145

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…

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'…

Nice!

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

#162

Post by jepler »

quicktwo wrote: post #155
jepler wrote: post #145

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…

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'…

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

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

#163

Post by quicktwo »

jepler wrote: post #162
quicktwo wrote: post #155

Earlier quoted context omitted.

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'…

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.

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

#164

Post by quicktwo »

lucb1e wrote: post #128

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... $ 2000 bytes smaller without any optimizations (this even includes the newlines), though now I guess the question is what the size of the xz decompres…

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!

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

#165

Post by quicktwo »

davidjohnstone wrote: post #17
jagged-chisel wrote: post #3

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.

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…

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

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

#166

Post by quicktwo »

bbbbbr wrote: post #136
zackboe wrote: post #41

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…

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.

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

#167

Post by quicktwo »

tragomaskhalos wrote: post #107

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.

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

#168

Post by quicktwo »

bbbbbr wrote: post #136
zackboe wrote: post #41

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…

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.

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

#169

Post by lifthrasiir »

quicktwo wrote: post #160
lifthrasiir wrote: post #82

Earlier quoted context omitted.

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 s…

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 painful…

> 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 ;-)

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

#170

Post by ecf »

_dujt wrote: post #126

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

Post reply on HN