2
\$\begingroup\$
  • 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 + "')")}
\$\endgroup\$
  • 9
    \$\begingroup\$ Compression algorithms built in to your language are not allowed That's fuzzy. What qualifies as compression algorithm? Things like run-length decoding are probably borderline \$\endgroup\$ – Luis Mendo Jan 29 '17 at 13:47
  • 2
    \$\begingroup\$ In order for this challenge to be objective you must lock in your choice of text right now, before revealing it, by posting a hash of it. Otherwise you have 100% free reign in choosing the winner by choosing a text that best matches your chosen answer. \$\endgroup\$ – orlp Jan 29 '17 at 14:10
  • 5
    \$\begingroup\$ @JulianLachniet Yes there is, if you publish the hash of the text you chose right now we know when you post the text later that it's the correct text that you chose now. \$\endgroup\$ – orlp Jan 29 '17 at 14:16
  • 3
    \$\begingroup\$ @JulianLachniet If you want an even stronger guarantee, you can instead post a function that generates a text given a number, and state that the number used to generate the scoring text will be the hash of the headline of a big publicly available newspaper at a certain date. This way no one knows the text ahead of time, including you. \$\endgroup\$ – orlp Jan 29 '17 at 14:23
  • 3
    \$\begingroup\$ Also, why is the main program restricted to 512 bytes? It makes any attempt of making your own compression algorithm (since pre-made ones are invalid) a lot harder in common languages. \$\endgroup\$ – devRicher Jan 29 '17 at 14:45
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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 ;.

\$\endgroup\$
  • \$\begingroup\$ This is not a valid answer: 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. \$\endgroup\$ – Julian Lachniet Feb 2 '17 at 21:29
  • \$\begingroup\$ @JulianLachniet, it's a perfectly valid answer. "unless you code it from scratch". \$\endgroup\$ – Peter Taylor Feb 2 '17 at 22:20
  • \$\begingroup\$ If you are coding it from scratch, that's fine. Your post does not make that clear. \$\endgroup\$ – Julian Lachniet Feb 2 '17 at 22:57
  • \$\begingroup\$ @JulianLachniet, I thought my other answer made it pretty clear, but as you insist I've copied across the relevant introduction. \$\endgroup\$ – Peter Taylor Feb 3 '17 at 8:19
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ As implemented this is actually an adaptives binary arithmetic coder because it doesn't track the partially coded byte (you would need 255 different probs to achieve byte order). This usally doesn't work very well at all for text (probably 1-2%). A byte oriented coder would give you around 1/3 reduction rate for english text. \$\endgroup\$ – Christoph Feb 13 '17 at 7:41
  • \$\begingroup\$ @Christoph you're right. I do not expect byte-oriented coder to fit into 1024 bytes with decoder, though. \$\endgroup\$ – Lyth Feb 13 '17 at 10:54
  • \$\begingroup\$ There are only a few minor changes which probably pay of quite fast: prob would have to be an array of 256 elements and used as prob[ctx] (problem maybe to init it all to 256 but changing math to use prob[ctx] as prob[ctx]+256 and init to 0 should do the trick). ctx would be set to 1 at the start of each byte and gets shifted in the coded bit ctx = (ctx << 1) |bit; after each bit. \$\endgroup\$ – Christoph Feb 13 '17 at 11:35
0
\$\begingroup\$

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)}.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.