Hacker News new | past | comments | ask | show | jobs | submit login

Amazing post.

This part is a little funny (spoiler - this is from the end):

>So, our computer (with the Tetris ROM) has a bounding box of 1,436 x 5,082. Of the 7,297,752 cells in that box, 6,075,811 are empty space, leaving an actual population count of 1,221,941. Each of those cells needs to be translated into an OTCA metapixel, which has a bounding box of 2048x2048 and a population of either 64,691 (for an ON metapixel) or 23,920 (for an OFF metapixel). That means the final product will have a bounding box of 2,940,928 x 10,407,936 (plus a few thousand extra for the borders of the metapixels), with a population between 29,228,828,720 and 79,048,585,231. With 1 bit per live cell, that's between 27 and 74 GiB needed to represent the entire computer and ROM.

>I included those calculations here because I neglected to run them before starting the script, and very quickly ran out of memory on my computer. After a panicked kill command, I made a modification to the metafier script. Every 10 lines of metapixels, the pattern is saved to disk (as a gzipped RLE file), and the grid is flushed. This adds extra runtime to the translation and uses more disk space, but keeps memory usage within acceptable limits. Because Golly uses an extended RLE format that includes the location of the pattern, this doesn't add any more complexity to the loading of the pattern - just open all of the pattern files on the same layer.

>K Zhang built off of this work, and created a more efficient metafier script that utilizes the MacroCell file format, which is loads more efficient than RLE for large patterns. This script runs considerably faster (a few seconds, compared to multiple hours for the original metafier script), creates vastly smaller output (121 KB versus 1.7 GB), and can metafy the entire computer and ROM in one fell swoop without using a massive amount of memory. It takes advantage of the fact that MacroCell files encode trees that describe the patterns. By using a custom template file, the metapixels are pre-loaded into the tree, and after some computations and modifications for neighbor detection, the Varlife pattern can simply be appended.

What's really funny about this is that in the end, they are compressing the image. But we know what it compresses to! It compresses to this:

>The final Tetris program was written in Cogol,

which links to https://github.com/QuestForTetris/Cogol/blob/master/tetris.c... and is... 4.71 KB.

While it didn't get far enough to compress that well, in the end this a journey up and down and then a little up (because they went down too much and ran out of memory) various levels of abstraction.

Very cool - and a little funny.




Hey, that's me!

Yes, the size of the Cogol program is a decent estimate of the Kolmogorov complexity of the Tetris program. However, you also have to account for the size of the computer (including the massive RAM bank) - the Cogol program just encodes the Tetris program.

Naturally, no general-purpose compression scheme (or even a somewhat-specific-purpose scheme like MacroCell) is going to come close to the Kolmogorov complexity. We could come up with a custom compression scheme and write a compressor and decompressor, but give us a break - we built a computer! :P


:D Thanks for the reply. And great work!




Applications are open for YC Winter 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: