A different kind of programming contest, Kolmogorov style )

Revision en4, by tzador, 2021-01-24 11:59:06

Hello fellow coders.

I was reading a book about Kolmogorov Complexity the other day and while talking to a friend about it we thought of a different kind of programming contest that can be built around it.

You see, in classical contests, participants are asked to write a program, which when given some valid input produces a correct output, like so: [input] -> [program] -> [output].

What if we didn't have any input, and would just ask participants to write as short program as they can, that would produce the correct output, like so: [program] -> [output].

Would it be fun?

The coders are just given the desired output, possibly with some hints. They need to find structure in the desired output, and come up with as short program as they can, to generate that output. The shorter the submitted problem, the better.

Instead of using just strings as outputs (like in classical Kolmogorov theory), one could allow any JSON value.

Here are a few examples of such challenges (spoiler, the name of the challenge hints to its solution):

I would propose to allow only programs written in JavaScript for the following reasons:

  • It is more fare to compare solution programs written in the same language.
  • We can minify and gzip the program before judging its length (same settings for everyone).
  • Online IDE can be implemented, which could run the programs locally in the browser before submission. WebWorkers could be used to run the program in secure isolated environment without access to DOM.
  • When a solution is submitted, it is also run on the server just to check that it is correct and judge its length.

Do you think it would be fun to solve such challenges? If you think this is a stupid idea, could you provide some reasoning on why?

Could you come up with your own such problems (just paste json in comments, with an optional solution program and some hints/description).


  Rev. Lang. By When Δ Comment
en4 English tzador 2021-01-24 11:59:06 2 Tiny change: 'ure.json) [a solutio' -> 'ure.json) <-[a solutio'
en3 English tzador 2021-01-24 10:45:22 97 Tiny change: 'u see, in the classical' -> 'u see, in classical' (published)
en2 English tzador 2021-01-24 10:38:00 3557
en1 English tzador 2021-01-24 09:48:53 309 Initial revision (saved to drafts)