The ancient Finnish predictor data compressor. Smallest compressor ever? | Hacker News Reader

The ancient Finnish predictor data compressor. Smallest compressor ever?

bugfix-66.com

35 pointsbugfix-6631 comments

Just do a proper Show HN post if you want to push your thing on HN

The site is not finished yet, but each algorithm is interesting on its own.

Look at my submission history:

https://news.ycombinator.com/submitted?id=bugfix-66

Really remarkable tiny algorithms like Martin Rem's almost-forgotten Union-Find, the tiny bitwise linear string search from approximate-grep, hash treaps, Quicksearch (the fastest sublinear string search in practice), a simple state-of-the-art arithmetic coder/decoder, space-filling curves, the Shortest Path Faster algorithm, etc.

Next week I'll publish a fantastic generalization of bytewise integer encoding (like Varint or git's VLQ but better).

I'll do a Show HN for the site itself some time next year.

Now do a real tiny, robust encryption algorithm.

This was on the todo list: https://en.m.wikipedia.org/wiki/XXTEA

From one of the minds that brought you the Burrows-Wheeler transform. The problem is that the chosen plaintext attack is too cheap, so it's not interesting.

But XXTEA is a historical curiosity like the Finnish predictor compressor, so maybe!

This is a good suggestion. The title makes it sound like an article about some lesser-known but interesting compression algorithm. Turns out it's a Go puzzle bank. Nothing wrong with that, but it would be less confusing to make that a bit more clear.

And the corresponding decompressor:

https://bugfix-66.com/d548f3abf6faa823a829e4c770a8babca648a5...

Does a simpler compressor/decompressor exist with comparable bits-per-byte performance?

Is there some more info on this algorithm, who designed it, when, where?

Or, considering the web site title, is there a bug in this algorithm? Thanks!

This is a folk algorithm of unknown origin.

All I know is the original author was probably a hacker from Finland and it was originally written in x86 assembly. This is my modernized implementation of his algorithm.

As for solving the BUGFIX-66 puzzles, to fix the bug in the compressor, add

  to = append(to, 0)

on the line after

  loc = len(to)

The original code was not inserting a placeholder for every control byte.

To fix the decompressor, add

  at++

on the line after

  ctrl := int(from[at])

The original code was not stepping past a control byte after loading it.

Thank you!

Doe it literally check for the specific solution?

Writing

    to = append(to, ctrl)

which is functionally equivalent and, in my personal opinion, with clearer intent (ctrl = 0 at that point in the code), returns "incorrect".

In fact, it seems that any placeholder value should work - as it is always overwritten by the final value of ctrl for a given set of bytes at the end; however, the checker rejects this.

Your fix is wrong, so the site rejects it.

Go doesn't do integer type conversions implicitly, to avoid the implicit-type-casting bugs endemic to C. Go (thankfully) doesn't allow an implicit conversion from int to byte. You must do the cast explicitly.

So you would have to say

  to = append(to, byte(ctrl))

and that's correct.

The site builds and executes the code you submit, and any correct solution is accepted.

Seems like something that might have been written as an evolutionary step towards LZ77.

Fixing a bug in code like this isn’t the kind of problem that anyone should work on without tests. I guess you’re supposed to copy the code into your own environment and write tests?

No, a programmer should be able to read a small piece of code, understand the algorithm (especially given a summary in English), and understand what's wrong (a small, simple mistake).

Some people will be better at this than others. Programming (algorithms, etc.) is not something everyone is equally good at. I wrote this puzzle after reading the x86 assembly original, which I believe was written in the 1980's. I never executed the original code, except in my mind, but I know how it works.

This is like saying you should be able multiply 4-digit numbers without a calculator. Is it possible? Yes. Is it something anybody uses outside of school? No. In practice it's a skill that's pretty much useless because using a calculator (or debugger in the case of OP) is both faster and easier. I myself got very good at mental arithmetic during math competitions, but 20 years later I find that I've forgotten most of the tricks because I never use it.

You don't read code to understand it?

You can't understand a small block of code without running it in a debugger?

When you read code in a book, how do you understand it?

Hey friend, Humans are giving you feedback on your project. If your goal is for people to enjoy your cool thing, maybe listen?

He's not trying to sell something, so why should he pretend all feedback is equally valuable? A hobbyist can afford to forego the "customer is always right" mentality.

It's a good idea to set expectations about what you want to achieve. If you're publishing puzzles that you expect people to solve in their head and you know it's uncommon, you'll avoid lots of criticism / confusion by stating that upfront. ("Some of you may be surprised with the format, but the trick here is to solve the puzzle in your head without external tools.") Other services with programming challenges normally give you sample input/output, so that's a popular expectation in this area. People usually don't stare at the code until they see a solution (as you can see from the comments), since it's not an everyday development scenario.

I'd say that when we read code we read it in a similar way as text. I know what you mean, even if you make tiny mistakes / typos. And that's especially true in the book, where the code is normally prefixed by explanation of what it should do and is there for an extra illustration of the idea, not to be actually executed. Even more: the code in the book can omit required parts or be broken and still serve a purpose. Example:

    foo = some text
    for h in (itearte over foo indexes]:
      foo(h] is now (uppercase foo*h*)

That's totally broken, with typos, and not written in any real language, but we both have the same expectation of what it's supposed to do.

But that works against solving this puzzle in my head. I'm not reading the code to understand it anymore. You explained what it should do and presented the code. I understand it. Instead I need to play the role of "spot the typo" symbolic executor / debugger in my head, which is very different.

I agree about multiplying 4-digit numbers (though I suspect ability to do that correlates a lot with good working memory and concentration, which are useful for other things too). But the ability to dive into an unfamiliar body of code that isn't perfectly documented and exhaustively unit-tested, and figure out what it's trying to do even in the presence of minor errors, is useful, because there is lots of code out there that isn't perfectly documented and exhaustively unit-tested. And this sort of challenge exercises (and maybe improves?) that ability.

If you're chasing a bug, then yes, using a debugger will likely get you there quicker than staring at the code hoping for enlightenment. But you might instead be wanting to understand the code, and while running it in a debugger might be useful for that I think being able to read it and grasp what's going on is a genuinely valuable skill. (Maybe the code you're reading runs on some embedded system that doesn't have a good debugger. Maybe it's deep in the source code for your OS and there's no plausible way to hook a debugger into there. Maybe you're reading it on a webpage and it would be a nuisance to get all the code needed to run it onto your computer at all. These are all situations I have come across fairly recently.)

Disclaimer: this is a thing I am (I think) unusually good at, and there is a near-universal human tendency to overvalue one's own strengths.

It's a bit like doing chess tactics puzzles. When you're actually playing a game, usually there isn't a startling tactic available, and when there is you don't have the advantage of knowing there is, and winning slowly and mundanely may be a better approach than looking for a tactical brilliancy. But if you want to get better at chess, doing tactics puzzles should be part of what you do, because it helps make you better at spotting tactics when they do appear and at analysing them accurately. Also, if you enjoy playing chess, solving them can be fun in the same way as playing chess is; similarly, if you enjoy the small-scale work of designing and implementing algorithms and finding algorithmic bugs, solving puzzles like the one we're discussing can be fun in the same way as programming and debugging can.

No, a good programmer knows that the likelihood of someone as competent as them doing the next change to the module is very low and leaves behind some automated tests to help the next one not break what's there.

Competent good also implies "good" good, willing to help reduce the suffering of others.

Yeah, it's literally not good programming if the other people who will maintain it can't work with it. Even if you think they are all idiots. You're not working with some imaginary team of geniuses.

There's not enough of the very smartest to keep the modern world going by themselves, working with your team in the real world is part of the job.

Sure. But then the “idiots” can write the tests themselves. ;)

They almost literally cannot, or rather cannot write good tests.

I have seen If (testPassed) assert(true);

Nothing happens if the test should have failed...

Then you need smarter “idiots”. This idea that literal idiots can build or even maintain complex software systems is… simply untenable.

I wholeheartedly agree. It’s refreshing to see somebody state it so openly.

So you don’t know if it works, then. Maybe there’s more than one bug?

It works. As my Bostonian aunt would say, it's wikkid cleva.

FWIW, I did manage to spot the bug without executing it, but go isn't a language I've used before so I fired up godbolt to try it out before submitting my solution. This isn't a skill that I'd expect of juniors (that is, most programmers). Sounds like you're quite the skilled programmer, enough so that you're taking your experience for granted. I'd encourage you to be a bit kinder about your expectations -- especially with an unfamiliar algorithm, people have multiple unknowns to resolve -- when we read and comprehend code, we're emulating a program in our heads, and that's a hard thing to do!

And, for crap's sake, don't spoil the puzzle on a post about the puzzle!

That said, as an a collection of advanced puzzles, I'm delighted. You're digging out some really awesome algorithms that I've never seen, and I love it. This algorithm is ridiculously clever and surprisingly effective given its simplicity, speed, and memory efficiency. Keep up the good work; I look forward to more of these.

edit: heh, I just did the radix sort one. Made the same stupid mistake last time I wrote a counting sort, so I knew just what to expect... good times.

Cheers!

Definitely interesting as a puzzle, but personally I'd prefer a write-up on each of these novel algorithms, including what it is and how it works, with complete code.

To each their own.

Reply on news.ycombinator.com