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

61–70 of 170 posts

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

#61

Post by quicktwo »

willis936 wrote: post #14

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

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.

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

#62

Post by hinkley »

corruptio wrote: post #51

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. ed…

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.

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

#63

Post by voussoir »

anyfactor wrote: post #25
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.

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".

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

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

#64

Post by habibur »

hinkley wrote: post #34
retrac wrote: post #32

Earlier quoted context omitted.

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

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.

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

#65

Post by hinkley »

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?

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

#66

Post by ProjectBarks »

hinkley wrote: post #65

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

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

#67

Post by hinkley »

ProjectBarks wrote: post #66
hinkley wrote: post #65

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.

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

#69

Post by hombre_fatal »

hinkley wrote: post #65

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?

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

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

#70

Post by lifthrasiir »

phire wrote: post #50
hinkley wrote: post #40

Earlier quoted context omitted.

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…

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

Post reply on HN