1
\$\begingroup\$

Challenge:

Write a lossless encoder/decoder that is able to compress its own source code.

Usage:

progname encode

Encodes data provided on the standard input, writes the encoded representation of the data to the standard output.

progname decode

Decodes data produced by progname encode. Reads the encoded data from the standard input, writes the decoded data to standard output. Must perfectly restore the original data.

Example:

$ progname encode < /usr/include/stdlib.h > encoded
$ progname decode < encoded > decoded
$ diff -qs /usr/include/stdlib.h decoded
Files /usr/include/stdlib.h and decoded are identical

Requirements:

  1. It must be a real lossless encoder/decoder for all inputs - encoding any data and then decoding it must produce the original data.

  2. If the input is identical to the program's source code, the size of encoded output must be less than the size of the input.

Score:

Size of the program's source code + the size of its encoded source code

Clarification:

The program doesn't need to be a general purpose compressor/decompressor. That's why its commands are called encode/decode. It may also use existing tools predating this question.

\$\endgroup\$
  • 3
    \$\begingroup\$ The problem I see is that it doesn't necessarily have to be good compression. You could simply map the program input to a single byte and all other inputs to themselves, and get a crazy good score. Basically like lenpeg but recognizing it's own source code instead \$\endgroup\$ – James Nov 11 '16 at 20:57
  • \$\begingroup\$ @DrMcMoylex That's OK. I intentionally didn't add restrictions preventing such an implementation. \$\endgroup\$ – Leon Nov 12 '16 at 5:41
  • \$\begingroup\$ It has been put on hold while I was writing my answer. I think this is a perfectly valid and interesting challenge. \$\endgroup\$ – lovasoa Nov 12 '16 at 13:15
  • \$\begingroup\$ NodeJS, 330 bytes: b=";c=require('fs').readFileSync('/dev/stdin','ascii');p=process.argv[2][0];s='b='+JSON.stringify(b)+b;process.stdout.write(p=='e'?((c==s)?'':'0'+c):(c?c.slice(1):s))";c=require('fs').readFileSync('/dev/stdin','ascii');p=process.argv[2][0];s='b='+JSON.stringify(b)+b;process.stdout.write(p=='e'?((c==s)?'':'0'+c):(c?c.slice(1):s)) \$\endgroup\$ – lovasoa Nov 12 '16 at 13:16