1
\$\begingroup\$

how about adapting the rules of Code Golf to replace less code-characters are better rules (=> code minifiers) with: the smaller BZIP2(sourcecode) the better?

I claim the true intent of character counting is to drive shorter, compacter source code creation which implies to some degree optimal en-coding of the algorithms used. Bzip(source code) provides an entropy measure of the source which as well could be used to measure the efficiency of the en-coding...

What do you think?

\$\endgroup\$

migrated from codegolf.stackexchange.com Feb 25 '12 at 16:14

This question came from our site for programming puzzle enthusiasts and code golfers.

5
\$\begingroup\$

In contradiction to @dmckee, I'm not sure that this would easily meet the requirement of an objective primary winning criterion. The common compression formats are really rules for how to uncompress, and there aren't canonical levels of CPU effort to expend in compression. So even GNU zip with the same options may give slightly different results for the same input in different versions. In fact, some zip/gzip implementations are non-deterministic and may give sizes differing in a few bytes according to the contents of your entropy pool.

If you try specifying versions as "GNU zip 3.0.2 with options -9" then it's possible that a lot of people would have to find the source and compile it themselves. Technically that doesn't make it subjective, but it does make it a lot harder to check.

Also, bearing in mind that most archive formats include the original filename, you're going to have to either specify single-character names or penalise people whose languages use long filename extensions.

If you require people to submit the compressed versions of the file then it is objective, but there are some serious disadvantages. All the submissions will be base-64 encoded and opaque, and it gives an advantage to people who are able to run non-deterministic compressors on lots of high-powered computers.

\$\endgroup\$
  • \$\begingroup\$ well, i suggested compression as a way to find out the entropy of the code submitted. maybe there are deterministic tools/ways to measure entropy of a text? the main idea is to spare people (if they are not interested in that => seperate compr-golf) the code-minification step of solution \$\endgroup\$ – pointernil Feb 26 '12 at 12:48
  • \$\begingroup\$ @pointernil, the Kolmogorov complexity of a text is undecidable. And since compression aims to restore the text exactly, people would still have to remove whitespace and use single-character names, so it's not really achieving your intention. \$\endgroup\$ – Peter Taylor Feb 26 '12 at 14:10
  • \$\begingroup\$ These are good points...Can we rescue the idea by requiring a deterministic compression algorithm? And does someone have a list of algorithms that says which are which? And is it worth it: in other words will people care enough to try? \$\endgroup\$ – dmckee Feb 26 '12 at 18:58
  • \$\begingroup\$ well, i see there are theoretical issues preventing such a "entropy" based scoring to be scientifically sound. Still, after checking out many golf submissions my claim would be that not forcing ppl to minify they code the solutions would provide much more insight into the main idea of the solutions. a simple deterministic compression run would provide a good enough estimate which could be easily calculated. \$\endgroup\$ – pointernil Feb 26 '12 at 23:18
1
\$\begingroup\$

I think that "compressed size" represents "An objective primary winning criterion" as demanded by our FAQ, and as such would certainly be acceptable as a different class of challenge (i.e. not replacing ).

One thing I'm not sure of would be how different the results would be vis-a-vis normal code golf. I suppose some highly repetitive code could do much better after compression than before, but such code seems to be rare in actually answer to in the site.


That leaves a couple of followup questions:

  1. What compression: should we try to standardize on a single algorithm or leave it up to the challenge authors?
  2. Tagging. Just or something more specific? Maybe ? In principle we could have , , etc, but I am not sure that we would be well served by such a proliferation of tags.

My answers would be (1) author's choice and (2) .

\$\endgroup\$
  • 1
    \$\begingroup\$ I've written some self-decompressing answers (e.g. this one) to golf challenges, and can say that it does have a significantly different feel than normal code golf. In particular, maximizing repetition and using as few distinct characters as possible become much more important. One issue I find potentially problematic is that it's hard to predict just which version of a program will compress best, requiring some trial and error. E.g. for the answer I linked to, I used a brute force exhaustive search to choose some variable names and delimiters. \$\endgroup\$ – Ilmari Karonen Feb 29 '12 at 18:57
  • \$\begingroup\$ Thanks, @IlmariKaronen. Real experience is always valuable. \$\endgroup\$ – dmckee Feb 29 '12 at 20:38

You must log in to answer this question.

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