Kolmogorov Complexity Meta Golfer

Question

• Mike Bufardeci (Pyth) - 175 bytes

• Leo (Retina) - 175 bytes

• devRicher (Lua) - 182 bytes

• Peter Taylor (CJam) - Waiting for clarification

• Lyth (C++11) - Waiting for clarification

---

Edit: Several changes made, should not affect any already submitted answers.

Edit #2: Very few people are taking advantage of the 1024 byte limit. The point of this challenge is to output code golf answers, not things like the example at the bottom of this post.

Edit #3: Here is the paragraph to test against: WASHINGTON - These are chaotic and anxious days inside the National Security Council, the traditional center of management for a president's dealings with an uncertain world. I will test the submissions myself later.

At PPCG, we pride ourselves in writing programs to solve problems. However, it's very time consuming to write the programs to solve problems. Instead we should write programs to write programs to solve problems!

In this case, the problem is Kolmogorov Complexity. You must write a program that golfs a program, that outputs piece of text.

Main program -> Generated program -> Text

You do not necessarily need to golf the main program. Your score is the length of the generated program.

---

You will not know the final text when writing the main program. Therefore, you will not be able to write the generated program by hand. The main program should take a string input and create the generated program, which correctly outputs the text.

---

On February 12th, the first paragraph of the headline of the New York Times will be used for scoring. I will post the article at 10 AM ESThttps://www.nytimes.com/

---

• You may use any language for the main program and generated program. They do not have to be the same.

• The final text will never contain these characters: ", ', \n, \r.

• The main program is limited to 1024 bytes (not characters). The generated program has no byte limit, as long as it outputs the text.

• Compression algorithms built in to your language are not allowed (both ways), unless you code it from scratch. This includes any type of text compression libraries, and base conversion. This does not include Regexes.

• Standard loopholes apply.

---

Example: (JavaScript)

f=(g)=>{console.log("console.log('" + g + "')")}

Answer 1

Retina, worst case (3+original length) bytes

EDIT: added support for newlines, in order to try this code in actual kolmogorov complexity challenges. Behaviour on strings without newlines remains unchanged.

Retina is great at substituting substrings, so that's what we're going to do!

This program looks for repeated sequences of characters and replaces them every time with a single character not appearing in the full string. The generated program then starts with the "compressed" string and applies all substitutions in reverse.

This code adds 3 bytes of boilerplate (a newline at the beginning, and a \` towards the end to suppress a trailing newline), so in the worst case (when there are no repeated sequences worth substituting) we have a length of 3 bytes more than the starting string. On average, this will shave a few bytes from the original length, not much but still a compression.

Here's the code with some comments:

First, we use a trick with transliteration ranges to change newlines into ¶, which is how newlines are printed in a Retina program

T`µ¶·`µ-·

then we start the main loop, duplicating the first line

{`^.+
$&¶$&

we only substitute when the sequence is repeated enough times (depending on its length)

^.*?((......+).*?\2|(.....?).*?\3.*?\3|(...).*?\4.*?\4.*?\4|(..).*?\5.*?\5.*?\5.*?\5.*?\5).*
"$2$3$4$5
^"(.+)|^.*
$+

to find a character not in the string, we append a list of candidates to the string, using " as separator, and then remove duplicates

^(.*)¶(.*)
$2" 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!#%&\'()*+,-./:;?@\^_`{|}~¶$2¶$1
D`(?<=^.*).
^.*"(.)?.*¶(.+)
$2¶$1

here the actual substitution in the text happens

+`^(.*)(.+)(.*¶(.)¶\2(¶|$))
$1$4$3

in case we couldn't find a repeated sequence or an unused character, we restore the string to the original state (which makes us break from the loop)

}`(.*)¶(¶.*|.*¶)(¶|$)
$1$3

at the end, we add the 3 bytes of boilerplate

^
¶
\-1=`.*¶
\`$&

Try it online!

In the linked example, the 292 bytes paragraph gets compressed to a 286 bytes Retina code.

NOTE: the substitutions made are not optimal, we just make every time the first suitable substitution we find; I don't know if an algorithm finding the optimal substitutions could run in a reasonable amount of time.

Answer 2

Pyth, worst case length(input) + 1 bytes

=kNJ++kzkV92Iq/zC+32N0 aYC+32N))V.:z7I>/JN2=J+++\::JNK.)Y+\\K++kNk))V.:z6I>/JN2=J+++\::JN=K.)Y+\\K++kNk))V.:z5I>/JN2=J+++\::JN=K.)Y+\\K++kNk))V.:z4I>/JN3=J+++\::JN=K.)Y+\\K++kNk))V.:z3I>/JN4=J+++\::JN=K.)Y+\\K++kNk))V.:z2I>/JN7=J+++\::JN=K.)Y+\\K++kNk))?qeJkPJJ

Test Suite Available Online
Generated Programs from Test Suite

Explanation

This program no longer abuses the fact that the article will be the first paragraph of a NY Times article and is now a general compressor of short strings. There are still some assumptions being made here, specifically that not all characters will appear in the text and that the text is at least seven characters long.

The high level explanation is that the program searches thorough the text for progressively shorter repeated strings, then replaces each repeated with a character not present in the text. Each string length has its own break even point where making a substitution is actually shorter than leaving the text alone. For strings of length 7 only 2 occurrences are needed but for strings of length 3 the break even point is 4 occurrences.

Main Program

The main program mostly consists of six loops: one each for strings of length seven down through strings of length 2. Each loop goes over all substrings of the input with that length, counts how often they appear in the article and determines if a replacement should be made. If a replacement is made then the string is wrapped with a replacement method to obtain the original string.

This breakdown is itself broken down into several parts for readability. This first part is setting up for the main loops.

=kNJ++kzkV95Iq/zC+32N0 aYC+32N))
  N                               N is initialized to " (the double quote character)
=kN                               assign " to k
       z                          z is initialized to the input
    ++kzk                         wrap z with double quotes
   J                              and assign that to J (J automatically assigns on first use)
          92     +32      +32     32-126 is the "printable" character range
          92     +32      +32     | causes issues so we stop before it (code point 124)
         V92                   )  for each printable character:
              /zC+32N              count occurrences of it in the input
            Iq       0        )    if there are 0 occurrences:  
                       aYC+32N      append that character to list Y (Y is initialized to an empty list)

The six main loops are nearly identical. I will breakdown a general loop for the sake of simplicity.

V.:z5I>/JN2=J+++\::JN=K.)Y+\\K++kNk))
   z                                   z is the input
 .:z5                                  get each substring of a certain length (here 5)
V                                   )  for each string:
       /JN                              count how many times it appears in the input
     I>   2                        )    if count > break even point: (here 2)
                       .)Y               pop a character off Y (unused characters list)
                     =K                  assign it to K (K automatically assigns the first time but must be manually assigned after that)
                  :JN K                  regex replacement:
                   J                      in the input
                    N                     replace current string
                      K                   with popped character
               +\:                       prepend : (the colon character)
              +           +\\K           append \ and popped character
             +                ++kNk      append current string wrapped in double quotes
           =J                            and assign to variable J

This last section only saves one byte on the generated program but also ensures that the worst case is as long as our trivial answer.

?qeJkPJJ
    k     k is still set to " (the double quote character)
   J  JJ  J is the string to be returned
?qeJk     if the last character of J is ":
     PJ    return J without the last character
          else:
       J   return J

Generated Program

If no substitutions are made the generated program will be in this format:

"(input)

This will have a length of length(input) + 1 bytes. This is the worst case, and I fear it may also be the average case. One paragraph does not have a lot of repeated strings, especially because professional writers try to vary their words.

If one substitution is made then the generated program will be in this format:

:"(input with replacements)"\(unused character)"(replacement string)

In Pyth, this is the format for replacement with regular expressions. Instances of the unused character in the input are replaced with the replacement string.

This adds a static 6 characters to the string, but in the worst case we are hitting the break even point mentioned earlier.

Here is the format for a generated program with two replacements:

::"(input with replacements)"\(char 1)"(str 1)"\(char 2)"(str 2)

As replacements stack up we simply add another colon to the front and add the substring and replacement character to the end.

I have not determined what the size reduction is in the best case. If anyone can determine the size of the generated program in the best case please let me know.

Answer 3

CJam, Burrows-Wheeler transform and run-length encoding

I think it's stupid to ban builtins for base-conversion as "compression", but I've implemented my own, as well as implementing run-length encoding and decoding manually rather than using the builtin.

q
e# Reduce range, add start-of-message marker
[0\:i_:e<(:If-+
e# Burrows-Wheeler transform
_,({_(+}*]$Wf=
e# RLE without e`, decrementing each runlength for compactness
0\{_2$={;\)}0?\}%\;2/
e# Pair [runlength-1 ch] to a single int
_1f=:e>):Paf{.*1b}
e# Base-convert to the minimal possible base
_:e>):B;W%{\B*+}*
e# Base-convert to base 256
[{256md\}h;]W%
e# Format as a string literal with as few special cases as possible
:c'"\'"/"\\\""*'"
e# Decoder base-converts to base 256, then base B, unpairs, run-length decodes, and
e# inverse Burrows-Wheeler transforms
":i{\256*+}*{"B"md"P"mda\)*\}h;]e_:A,Ma*_,{A\.+$}*0=(;"I"cf+"

• I is the increment which must be added to each decoded value
• P is the base used to combine run-length with char
• B is the base used to convert the whole thing

Answer 4

CJam, range reduction and base conversion

I think it's stupid to ban builtins for base-conversion as "compression", but I've implemented my own.

q
e# Reduce range by offsetting towards 0 as far as possible
:i_:e<:If-
e# Base-convert to the minimal possible base
_:e>):B;W%{\B*+}*
e# Base-convert to base 256
[{256md\}h;]W%
e# Format as a string literal with as few special cases as possible
:c'"\'"/"\\\""*'"
e# Decoder base-converts to base 256 and then base B, adding the offset
":i{\256*+}*{"B"md"I"c+\}h;"

The text is too small to benefit greatly from techniques which require a lot of decoding, but if we can subtract 32 from each byte and base-convert then we get an asymptotic improvement of at least 2.4%, and with luck the input source will be pure ASCII and we get an asymptotic improvement of about 18.7%. With an overhead of about 26 bytes we stand a decent chance of getting compression.

If the output is allowed to have a trailing NUL byte, one byte can be saved by removing that final ;.

Answer 5

Pyth, length(input) + 1 bytes

+Nz

Online interpreter available here.

This will return a generated program of the form "(input). Put another way, the main program prepends a double quote to the input text.

Main Program Explanation

+      Concatenate
 N     " (the variable N defaults to a double quote mark)
  z    and the input

Generated Program Explanation

"                start of a string
 (input)         the input text 
        (eof)    strings are closed automatically at the end of file

This is the shortest of the "input length plus a constant" answers. I'm posting this mostly to set a bar for the non-trivial answers. It's unclear if a non-trivial answer can exist within the rules as they are currently worded, but I am setting this bar nonetheless.

Answer 6

C++11, arithmetic coding, overhead >= 382 bytes

Compression algorithm is shamelessly copied from Simple byte-aligned binary arithmetic coder by Fabian 'ryg' Giesen

#include <iostream>
using std::cout;
void pu(char c){c=='\r'?cout.write(")OMG\" \"\\r\" R\"OMG(",17):cout.put(c);}

int main() {
    uint32_t lo{0},hi{~0u},x,i,prob{256};
    char ch;

    cout<<R"!*(#include <iostream>
void operator ""_p(const char* q,size_t z){uint32_t d{0},l{0},h{~0u},p{256},x,t;size_t r{0},i;for(i=4;i-->0;)d=(d<<8)|q[r++];while(r<=z){char y{0};for(i=8;i-->0;){x=l+((uint64_t(h-l)*p)>>9);t=(d<=x);t?(h=x):(l=x+1);while((l^h)<(1u<<24)){d=(d<<8)|q[r++];l<<=8;h=(h<<8)|0xff;}p+=t?((512-p)>>5):-(p>>5);y+=y+t;}std::cout.put(y);}}int main(){R"OMG()!*";

    while (std::cin.get(ch)) {
        for (size_t b=8; b-->0;) {
            int bit{ch&(1<<b)};
            x = lo+((uint64_t(hi-lo)*prob)>>9);
            bit ? (hi=x) : (lo=x+1);
            while ((lo^hi)<(1u<<24)) {pu(lo>>24);lo<<=8;hi=(hi<<8)|0xff;}
            prob += bit?((512-prob)>>5):-(prob>>5);
        }
    }
    for (i=4;i-->0;) {pu(lo>>24);lo<<=8;}
    cout<<")OMG\"_p;return 0;}";

    return 0;
}

Explanation

1. Main program reads the input and uses BinShiftModel to generate an encoded bitstream.
2. The bitstream is then included into a C++11 user-defined raw literal in the output program.
3. The literal is being processed by the user-defined function, operator ""_p(const char* string, size_t size), printing out the decoded stream.

Some extra care was necessary due to all newline values being converted to \n.

Improvement

The code does not look for different compression paths (there were, but some optimal value was chosen instead).

It is possible to improve the compression ratio, either by limiting input to 7 bits (did not do that because "em-dash" in the sample became corrupted) or by storing MSB from all input bytes first, which will likely be roughly same for 1/4 of the text.

Either way, algorithm overhead is huge on small texts.

Usage

g++ -std=c++11 -o golf golf.cpp && ./golf < sample.txt > degolf.cpp && g++ -std=c++11 -o degolf degolf.cpp && ./degolf

Answer 7

Lua

print('print"'..io.read()..'"')

Try it here.

Will always be string length + 7 bytes long.

C#

using System;
namespace H {
    class K {
        static string P;
        static void Main(string text)
        {
            P = text;
            Console.WriteLine("()=>{Console.WriteLine(H.K.P);}");
        }
    }
}

Works if the program itself is added as a dependency where you run the resulting output program. If you would to run the resulting code in a OutputText.exe, you will have to add OutputCodeThatOutputsText.exe as a dependency.

Resulting code is always ()=>{Console.WriteLine(H.K.P)}.