9
\$\begingroup\$

I am working on a new challenge (sandbox link) that has something in common with my old challenge Paint Starry Night. In these challenges the goal is essentially to design a compression algorithm tailored to a particular input. (For the new challenge the input is text rather than an image.)

In Paint Starry Night the most competitive answers simply wrapped an existing image compression format such as FLIF or BPG. These answers are (to me) less interesting than some of the others, which did really clever things with genetic algorithms and deep neural networks. For the new challenge I would like to include a rule against such off-the-shelf implementations of compression algorithms, while still leaving a level playing field for all other approaches.

My question is on the right way to do this --- in short, where and how to draw the line between compression routines like bz2 or gzip, versus language features like Python's base conversion or Jelly's dictionary lookup feature, both of which I think should be allowed. The things I want to avoid are (i) that people come up with loopholes that allow them to produce trivial solutions that wrap existing algorithms, or (ii) I accidentally ban perfectly sensible language features that could be used to build a non-trivial solution.

The sandbox link above has (at the time of writing) a possible way to do this based on what Wikipedia's editors list as compression algorithms, but I am not really sure if this is a good idea. Hence I would like to ask for feedback on it, and/or other suggestions of how to define off-the-shelf compression algorithms for the purposes of this kind of challenge.

\$\endgroup\$
  • \$\begingroup\$ Since anyone can edit Wikipedia, you should specify "what Wikipedia said when the challenge got posted", IMO \$\endgroup\$ – NieDzejkob Dec 31 '17 at 9:28
  • \$\begingroup\$ @NieDzejkob the problem with that is that there might be an obscure-but-effective compression algorithm that isn't currently listed, in which case someone could just use that. The difficulty of preventing this is what makes me doubt that my Wikipedia idea is a good one. \$\endgroup\$ – Nathaniel Dec 31 '17 at 9:38
  • \$\begingroup\$ I decided to get around this problem for now with a different approach that doesn't require built-in compression to be banned. (See codegolf.meta.stackexchange.com/a/14546/21034). But visitors please note: the upvoted answer is based on a complete misunderstanding of my question! \$\endgroup\$ – Nathaniel Jan 8 '18 at 13:00
12
\$\begingroup\$

It's unrealistic to define this

You have summed up well the reasons that banning certain algorithms will cause problems (whether you ban too many or too few). I don't expect anyone to come up with a clean solution to this that won't cause other problems. If an existing compression algorithm happens to be better than any the contestants can come up with, then their striving towards the best approach will lead some of them to converge on their own implementations of those existing algorithms. Banning an algorithm that people will naturally converge on seems to create an unavoidable grey area.

Observable rules

As has been pointed out elsewhere in similar discussions, it's problematic to try to ban implementation approaches. To keep the rules objective, it's generally better to define them in terms of inputs and outputs, instead of in terms of the internal workings of the code. This has been described elsewhere as avoiding making rules about unobservable behaviour.

Seek the weaknesses of existing algorithms

So I recommend approaching this problem from a different direction. Instead of taking an input that is best compressed with existing algorithms, and trying to carefully ban those algorithms without banning too much, try to find an input or category of inputs that existing algorithms are not the best approach to. Then you don't need to ban them. Early answers may involve existing algorithms, which may not seem as innovative, but later answers will show custom algorithms that suit the specific input types better.

This will be a difficult task, as there are a variety of compression algorithms available that are suited to different input types, but I still think this will be more realistic than trying to find an objective way to ban only some algorithms.

\$\endgroup\$
  • \$\begingroup\$ "their striving towards the best approach will lead some of them to converge on their own implementations of those existing algorithms" --- but that's completely fine. My intention is only to prevent trivial solutions that wrap an existing implementation. \$\endgroup\$ – Nathaniel Dec 31 '17 at 13:07
  • 2
    \$\begingroup\$ Oh I see. So you're not looking for necessarily new approaches, just that whatever algorithm used is actually implemented, rather than just a builtin? If so the same problem applies to defining what counts as an unacceptable builtin, so this answer is still the best advice I can come up with at present \$\endgroup\$ – trichoplax Dec 31 '17 at 16:56
  • \$\begingroup\$ Yes, that's correct. I agree that the same problem applies to determining which builtins are allowed, but I think to a much lesser extent. In the Starry Night challenge there are answers that use an off-the-shelf implementation and there are answers that don't, with no grey area in between at all. Of course if you try to ban one approach then people might find a grey area, but I don't think it's very big in this case and I just want to find a good and precise place to draw the line. \$\endgroup\$ – Nathaniel Jan 1 '18 at 2:35
  • \$\begingroup\$ The point about choosing an input that won't be compressed by existing approaches is an interesting one, but I have a hard time working out how to make an interesting challenge out of it. For example: a file consisting of the first 1000000 binary digits of pi would be pretty much incompressible by all algorithms I know, but it would be too trivial as a target for this challenge. On the other hand I could encrypt that same data, and then it would be an impossible challenge for anyone who doesn't know the key. \$\endgroup\$ – Nathaniel Jan 1 '18 at 2:40
  • \$\begingroup\$ [contd] The nice thing about natural language is that it combines some patterns with some incompressible data, in a way that provides a lot of structure. This should make the challenge quite open-ended, in the sense that there's always that little bit more in the data that can be exploited, similarly to the Starry Night challenge. It's really hard to think of something that would have those properties while not being compressible by existing routines, or transformable into something that is. \$\endgroup\$ – Nathaniel Jan 1 '18 at 2:43
  • \$\begingroup\$ Anyway, just to be absolutely clear, I don't want to ban any builtins except those that are implementations of bzip, gzip and their ilk. I understand the point about unobservable behaviour, and I want to break that principle as minimally as possible, while avoiding answers where the compressor just runs bzip on its input and the decompressor just runs bunzip. \$\endgroup\$ – Nathaniel Jan 1 '18 at 2:48
  • \$\begingroup\$ @Nathaniel perhaps instead of banning bzip/gzip, you provide it for free for every submission. Aka, have them write a two-part submission, one that compresses, and another that decompresses. Their score is the size of the output of their compressor after it is bzipped/gzipped. \$\endgroup\$ – Nathan Merrill Jan 4 '18 at 16:06
  • \$\begingroup\$ @NathanMerrill That makes a different challenge, "output something that can be best bzipped"? \$\endgroup\$ – user202729 Jan 7 '18 at 6:55
  • \$\begingroup\$ @user202729 Right. You're trying to take the input, and identify what parts bzip isn't handling well, and compress those. \$\endgroup\$ – Nathan Merrill Jan 7 '18 at 13:22

You must log in to answer this question.

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