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

81–90 of 170 posts

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

#81

Post by hinkley »

microtonal wrote: post #77
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 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 autom…

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.

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

#82

Post by lifthrasiir »

quicktwo wrote: post #56

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.

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)

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

#83

Post by iforgotpassword »

justinlloyd wrote: post #71

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

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

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

#84

Post by phire »

lifthrasiir wrote: post #70
phire wrote: post #50

Earlier quoted context omitted.

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

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.

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

#85

Post by operator-name »

dietrichepp wrote: post #43

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

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

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

#86

Post by londons_explore »

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

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

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

#87

Post by ant6n »

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

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

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

#88

Post by ant6n »

coumbaya wrote: post #68

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.

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

#89

Post by slim109ya »

iforgotpassword wrote: post #83
justinlloyd wrote: post #71

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

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.

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

#90

Post by jhgb »

Someone wrote: post #60

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

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

Post reply on HN