One commenter had an intuition that the optimal solution will be to compress the shakespeare.txt file and output it deterministically, so that this ends up just being a kolmogorov-complexity challenge. I'm fairly certain that isn't the case, for information-theoretic reasons. However, I will test it before I post the challenge: if I can't write a submission that beats the obvious bzip-based solution then I will not post the challenge.

I'm unsure about the rule banning built-in compression algorithms. It seems more elegant to leave it out, but in Paint Starry Night, objectively, in 1kB of code they spoiled the fun a bit, and I'm worried that with this scoring system the same could happen here. I'm happy to hear any thoughts about that.

Finally, a very specific query: the ban on word tables seems like it would rule out some golfing languages. I don't want to rule them out but don't want to open the floodgates either, so if someone can think of a good middle ground it would be helpful.

A note about the scoring system

In the sandbox, several people had an intuition that the optimal answers to this challenge will take the form of compressing the shakespeare.txt file and outputting it deterministically. However, the scoring system has been carefully chosen so that this strategy will not be optimal. If you have a stochastic solution then in theory you can turn it into a perfect deterministic solution, at the cost of adding -log2(p(program outputs shakespeare)) bits of code into your program. This extra code decreases p(monkey outputs program) by exactly the same factor that it increases p(program outputs shakespeare), resulting in zero change to the overall score.

But this is the absolute best you can do. Any real encoding will be less than perfect, so in reality the net result of such a strategy will be to slightly decrease the score. Because of this, it's likely that the most competitive answers will be stochastic. However, deterministic, compression-based answers are permitted and are welcome to complete, as long as they meet the spec.

On the off chance that I'm wrong about the properties of the scoring system, I intend to battle-test this challenge before I post it. To do this I will implement (i) the obvious illegal solution using bzip2 to compress the whole text, and (ii) the not-quite-so-obvious illegal solution using bzip2 to stochastically predict the next character from the ones already received, without including a compressed version of the text in the code. I expect solution (ii) to beat solution (i), for the reasons described in the last section of the question. If it doesn't I will either give up on the challenge or add a fudge factor into the scoring system to give slightly more reward to stochastic solutions.

I'll also post a sample answer (legal but not very competitive), in order to address the point about the spec being a bit daunting to understand.

I'm unsure about the rule banning built-in compression algorithms. It seems more elegant to leave it out, and it would still be a meaningful challenge without that rule. But in Paint Starry Night, objectively, in 1kB of code off-the-shelf compression spoiled the fun a bit, and I'm worried that with this scoring system the same could happen here. I'm happy to hear any thoughts about that.

Finally, a very specific query: the ban on word tables seems like it would rule out some golfing languages. I don't want to rule out any languages but don't want to open the floodgates either, so if someone can think of a good middle ground it would be helpful.

You may not use any libraries or functions designed for text compression. It's fine to use algorithms like bzip etc., but you have to implement them yourself (and hence include the implementation in your byte count).

You may not use any libraries or functions designed for compressing or decompressing data. It's fine to use algorithms like bzip etc., but you have to implement them yourself (and hence include the implementation in your byte count).

The score that this program calculates is the logarithm of the probability that the monkey outputs your program and your program then outputs Shakespeare, assuming that we always feed the program's output back in as input. We calculate the logarithm to avoid floating point errors, as the final probability will be extremely small. Note that the logarithm is to base 2.

• the code used to calculate its score, implementing the pseudocode above (this doesn't need to be in the same language as your submission)
• any code that was used to generate your submission (e.g. to create any data files that you included)
• an explanation of how your submission works.

You may not use any libraries or functions designed for text compression. It's fine to use algorithms like bzip etc., but you have to implement them yourself (and hence include the implementation in your byte count).

Your submission should include the code used to calculate its score. (This doesn't count towards the byte count.)

The score that this program calculates is the logarithm of the probability that the monkey outputs your program and your program then outputs Shakespeare, assuming that we always feed the program's output back in as input. We calculate the logarithm to avoid floating point errors, as the final probability will be extremely small. 

Note that the logarithm is to base 2. If your language doesn't provide the log2 function you should use log(correct_prob)/log(2).

• the code used to calculate its score, implementing the pseudocode above (this doesn't need to be in the same language as your submission). Please don't golf this.
• any code that was used to generate your submission (e.g. to create any data files that you included)
• an explanation of how your submission works.

You may not use any libraries or functions designed for text compression. It's fine to use algorithms like bzip etc., but you have to implement them yourself (and hence include the implementation in your byte count).