10
\$\begingroup\$

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?

\$\endgroup\$
10
  • 17
    \$\begingroup\$ 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. \$\endgroup\$
    – DJMcMayhem
    Commented Aug 11, 2016 at 17:52
  • \$\begingroup\$ @DJMcMayhem plz put as answer, will upvote \$\endgroup\$
    – Maltysen
    Commented Aug 11, 2016 at 18:00
  • \$\begingroup\$ What would general compression schemes that we implement ourselves without a built-in (e.g. base compression) count as? \$\endgroup\$
    – Maltysen
    Commented Aug 11, 2016 at 18:04
  • \$\begingroup\$ @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. \$\endgroup\$
    – DJMcMayhem
    Commented Aug 11, 2016 at 18:19
  • 2
    \$\begingroup\$ 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? \$\endgroup\$
    – Peter Taylor
    Commented Aug 11, 2016 at 21:31
  • \$\begingroup\$ @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. \$\endgroup\$
    – billpg
    Commented Aug 12, 2016 at 8:41
  • \$\begingroup\$ @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? \$\endgroup\$
    – billpg
    Commented Aug 12, 2016 at 8:50
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Maltysen
    Commented Aug 12, 2016 at 11:17
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – trichoplax is on Codidact now
    Commented Aug 22, 2016 at 10:52
  • \$\begingroup\$ 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. \$\endgroup\$
    – Shaun Wild
    Commented Aug 25, 2016 at 15:01

1 Answer 1

Reset to default
20
\$\begingroup\$

If your goal is to have hand-implemented compression, you can disallow built-in compression methods in your challenge (not retroactively, after answers are posted).

But by default Kolmogorov complexity is just the shortest string in a certain language that produces the intended output. This includes compression builtins, if that language contains them.

\$\endgroup\$
3
  • 13
    \$\begingroup\$ Although if you decide to ban built-in compression methods (or, more to the point, decompression methods) you need a good definition of what qualifies because it's a rather fuzzy term. \$\endgroup\$
    – Peter Taylor
    Commented Aug 12, 2016 at 10:06
  • 1
    \$\begingroup\$ Are function using specific external library like zlib libraries part of the language ? If the library is not installed the language cannot use it. \$\endgroup\$
    – Emmanuel
    Commented Aug 18, 2016 at 13:30
  • \$\begingroup\$ What you are doing by writing a specific program P is giving an upper bound, not the complexity itself, and that bound looks like \exists d\inN: K(x) <= length(P) + d. That is, by using complex built-ins, you are increasing d and decreasing length(P) for no significant effect in total. It seems pointless. \$\endgroup\$
    – Nobody
    Commented Dec 15, 2016 at 11:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .