# Ban zip-style decompression for kolmogorov-complexity?

A little while ago, I wrote a PPCG challenge under the tag, which frankly bombed.

Briefly, the challenge was to output a series of names. The first half of names were fixed but entrants could choose their own set of names for the second half under fairly loose restrictions.

When I wrote the challenge, I had imagined that entries would use encoding tricks like looking for every other capital letter as a separator with a special rule for names starting "Mc", or maybe the second half of names would all be rearrangements of the names used in the first half.

What I got, which should have been obvious in hindsight, is one answer that was essentially a bunch of bytes piped into a decompression function. No effort was made to find names with patterns that could be expanded by code, just a quick decompression and we're done.

I can't blame the author of that entry for doing it this way, but I got the feeling that this entry kinda sucked the fun out of the challenge. It was like we're taking part in a sprinting race and one entrant noticed that the rules allow you to use a motorcycle.

Thinking about kolmogorov-complexity in general, that style of piping bytes into a decompression function would work for a lot of these challenges, which would take away the fun of the challenge. So, what if we made a general rule, that use of zip-esque decompression functions go against the spirit of kolmogorov-complexity?

Thoughts?

• I disagree that we should ban them, but I will say those are the most boring of the answers. I don't generally upvote them. I think answers that take advantage of the patterns are far more interesting. Also, If a straightforward compression is one of the shortest answers, generally that means it's a boring challenge. – James Aug 11 '16 at 17:52
• @DJMcMayhem plz put as answer, will upvote – Maltysen Aug 11 '16 at 18:00
• What would general compression schemes that we implement ourselves without a built-in (e.g. base compression) count as? – Maltysen Aug 11 '16 at 18:04
• @maltysen Depends. Do you mean implemented as a feature of the language, or hand implemented as part of your submission? If it's the first, I don't see that as any different. If it's the second and you can still manage to make it competitive, I would consider that very impressive. Obviously there's somewhat of a gray line. – James Aug 11 '16 at 18:19
• What qualifies as "zip-style"? Just Lempel-Ziv-based schemes? Any grammar-based compression? Any method which allows you to get the full 8 bits out of each byte? – Peter Taylor Aug 11 '16 at 21:31
• @Maltysen - Right, I was thinking only of built in decompression functions. If someone implements LZW in code and still makes a good golf score, that would be impressive. – billpg Aug 12 '16 at 8:41
• @PeterTaylor - That's up for discussion if we can first reach a consensus on the general principle. Should encoding a block of bytes using base64 to produce the output count? – billpg Aug 12 '16 at 8:50
• @billpg if you're fine with general compression schemes but not built-ins, then this is just another instance of are built-ins allowed or not, which has been argued plenty. Btw, base-compression, while much shorter than LZW, is as general, and one of the most common techniques in kolmogrov-complexities. – Maltysen Aug 12 '16 at 11:17
• Sticking with your sprint race analogy, you can either ban motorcycles, or you can include stairs, sharp turns, fences and crossing a deep river. I'd much rather see a challenge that allows built in decompression functions but has a structure that favours imaginative new approaches. – trichoplax Aug 22 '16 at 10:52
• I personally think it's up to you to decide what you want banned for your challenge. Not to change the actual fundamentals of Kolmogorov Complexity. – Shaun Wild Aug 25 '16 at 15:01

• Are function using specific external library like zlib libraries part of the language ? If the library is not installed the language cannot use it. – Emmanuel Aug 18 '16 at 13:30