Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The Setup


Here you can find the full text of The Tragedy of Macbeth. If you view the source, and save it as text, you will notice it comes out to 206,244 total characters (including the whitespace at the end of the html).

The Challenge


Write a program which compresses the text linked above into the smallest possible text file which can then reproduce the original text exactly (including the whitespace).

The Rules


Your program cannot have any prior knowledge of the text it is compressing. The goal however is still to compress this specific text, so don't worry if it sucks at other text as long as it does the best job possible on Macbeth.

The program must take either "compress" or "decompress" as the first parameter and the text file as the second command line parameter. The compressed output has to be a text file, and it has to be UTF16. The compressed output when decompressed must match exactly the original file in a character for character comparison.

The program needs to finish in a reasonable amount of time. If it takes longer than a few seconds, please list the average running time with your submission.

The Scoring


The only score is the number of characters in the compressed output. The score only counts if the decompress matches the original in a character for character comparison.

share|improve this question

closed as not a real question by Jeff Atwood Apr 14 '11 at 7:34

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
re: The compressed output has to be a text file, and it has to be UTF16., why? also, does that mean that the output must only contain valid UTF16 codepoints? –  Hasturkun Feb 8 '11 at 15:07
4  
0x0000~0xFFFF are valid UTF-16 right? –  YOU Feb 8 '11 at 15:16
5  
@NickLarsen, why on Earth would you want the compressed file to be "readable text"? It's not going to make sense anyway. –  Peter Taylor Feb 8 '11 at 18:37
3  
I'm also surprised how many try or assume golfing here. –  Joey Feb 8 '11 at 23:09
3  
It makes sense to count the length of the program plus the length of the output - then it becomes something approximating a competition to find the best bound on the Kolmogorov complexity. –  Peter Taylor Feb 9 '11 at 8:10

3 Answers 3

Pseudo-code, compresses Macbeth to 0 bytes

Counter-example (yeah, almost joke) submission intended to point out the flaws with the question. (the C# was a bit long both in source size and resulting output)

if argument is "compress"
  compare entire input file to the Tragedy of Macbeth
  if equal, then output empty file
  else if input is non-empty,
    then RLE-encode input stream on chr(127) only and output that
  else [if input is empty]
    then RLE-encode a string of zero times chr(127)
else if argument is "decompress"
  if input is empty
  then output the Tragedy of Macbeth
  else RLE-decode input file on chr(127) only and output back

With this approach, Macbeth is brought down to as short a file as possible. Other text input is usually passed untouched, at worst gains a byte per chr(127) which tend not to occur in actual text.

share|improve this answer
    
Zero bytes?! shaking fist Grr, +1. –  Justin Morgan Mar 22 '11 at 13:44
    
It can suck at other files, so why bother RLE-encoding?I'd just pass non-Macbeth though unchanged. –  Romain Jun 22 '12 at 13:23
    
@Romain what if the input file is empty? –  J B Jun 23 '12 at 14:54
    
@JB good point :) –  Romain Jun 25 '12 at 14:23

Python, compresses to 40,304 bytes.

Similar to Mark's answer, but uses bzip2 instead of zlib (usually better for plain text.)

import bz2 as z,sys;print getattr(z,sys.argv[2])(open(sys.argv[1]).read())

Call like so:

python macbeth.py macbeth.txt compress > macbeth-compressed.txt
python macbeth.py macbeth.txt uncompress > macbeth-uncompressed.txt

Results:

thomas@jupiter:~$ python macbeth.py macbeth.txt compress | wc -c
40304
share|improve this answer
    
Post the results in text format? –  Nick Larsen Feb 8 '11 at 18:03
    
@NickLarsen How do I do that? It's 44KB of binary data. –  Thomas O Feb 8 '11 at 18:09
    
The point is to encode the text into other text. –  Nick Larsen Feb 8 '11 at 18:13
3  
` as z` costs 5 strokes, but you only save 2 since you only use z once –  gnibbler Feb 9 '11 at 4:05
1  
@gnibbler: Since it isn't a code-golf, the discussion is off topic. –  user unknown Jun 22 '12 at 5:21

C#, 1 byte compressed

I've hardly ever used C#'s file manipulation capabilities, so I'll try not to screw this up too badly:

class Program
{
    //args[0]: "compress" = compress mode, anything else = extract mode
    //args[1]: filename of source
    //args[2]: filename of target
    static void Main(string[] args)
    {
        byte[] info;

        using (FileStream fs = File.Open(args[1], FileMode.Open))
        {
            //read the source file
            info = new byte[fs.Length];
            fs.Read(info, 0, (int)fs.Length);                  
        }

        byte[] macbeth;

        using (WebClient client = new WebClient())
        {
            //get the real MacBeth
            macbeth = client.DownloadData(@"http://shakespeare.mit.edu/macbeth/full.html");
        }

        if (args[0] == "compress")
        {
            //is this also MacBeth?
            if (Encoding.Default.GetString(macbeth).Equals(Encoding.Default.GetString(info), StringComparison.Ordinal))
            {
                //yep, write a dot
                using (FileStream fsOut = File.Create(args[2]))
                {
                    byte[] infoOut = new UTF8Encoding(true).GetBytes(".");
                    fsOut.Write(infoOut, 0, infoOut.Length);
                }
            }
            else
            {
                //nope, better just copy it
                File.Copy(args[1], args[2];
            }
        }
        else
        {
            //is it a dot?
            if (info.Length == 1 && info[0] == Convert.ToByte("."))
            {
                //yep, write MacBeth
                using (FileStream fsOut = File.Create(args[2]))
                {
                    fsOut.Write(macbeth, 0, macbeth.Length);
                }
            }
            else
            {
                //nope! just copy the file
                File.Copy(args[1], args[2]);
            }
        }
    }
}

Compresses MacBeth all the way down to a single byte. While admittedly cheesy, this is technically within the rules (I checked). If it's good enough for Jon Skeet, it's good enough for me.

Holy smoke, talk about a tiny file size, huh? And it's lossless! I'm going to make a million dollars.

share|improve this answer
    
+1 Beat me to it lol. –  mellamokb Mar 21 '11 at 21:34
    
Won't work on non-Macbeth documents, will it? I mean, it should still produce output, even if poorly compressed. –  Romain Jun 22 '12 at 13:23
    
@Romain I don't think so. It may be an overly-literal reading, but the task is to compress MacBeth, specifically, without any requirements for other input. Technically, I could use a completely empty input and claim I've compressed MacBeth to 0 bytes, but that would be silly. –  Justin Morgan Jun 22 '12 at 18:43
    
@Romain - Now that I think about it, though, you make a good point. Fixed now. –  Justin Morgan Jun 22 '12 at 18:44

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