Alex Rivera | Logout

Write a program that takes text as input and produces a program that reproduces that text

Asked 2011-06-29T19:32:26.547
35

Recently I came across one nice problem, which turned up as simple to understand as hard to find any way to solve. The problem is:

Write a program, that reads a text from input and prints some other program on output. If we compile and run the printed program, it must output the original text.

The input text is supposed to be rather large (more than 10000 characters).

The only (and very strong) requirement is that the size of the archive (i.e. the program printed) must be strictly less than the size of the original text. This makes impossible obvious solutions like 

std::string s;
/* read the text into s */
std::cout << "#include<iostream> int main () { std::cout<<\"" << s << "\"; }";

I believe some archiving techniques are to be used here.

c++ algorithm compression lossless-compression
Edit
Report

1 Answer

0

  1. Assuming "character" means "byte" and assuming the input text may contains at least as many valid characters as the programming language, its impossible to do this for all inputs, since as templatetypedef explained, for any given length of input text all "strictly smaller" programs are themselves possible inputs with smaller length, which means there are more possible inputs than there can ever be outputs. (It's possible to arrange for the output to be at most one bit longer than the input by using an encoding scheme that starts with a "if this is 1, the following is just the unencoded input because it couldn't be compressed further" bit)

  2. Assuming its sufficient to have this work for most inputs (eg. inputs that consist mainly of ASCII characters and not the full range of possible byte values), then the answer readily exists: use gzip. That's what its good at. Nothing is going to be much better. You can either create self-extracting archives, or treat the gzip format as the "language" output. In some circumstances you may be more efficient by having a complete programming language or executable as your output, but often, reducing the overhead by having a format designed for this problem, ie. gzip, will be more efficient.

answered 2011-07-05T15:14:42.947

Your Answer