16
5
Recently at Puzzling.SE, there was a problem that I wrote about determining which two bottles out of a larger number are poisoned when the poison only activates if both components are drunk. It ended up being quite the ordeal, with most people managing to get it down to 18 or 19 prisoners using completely different algorithms.
The original problem statement is as follows:
You are the ruler of a medieval kingdom who loves throwing parties. The courtier who tried to poison one of your wine bottles last time was furious to learn that you managed to identify which bottle he had poisoned out of 1,000 with just ten prisoners.
This time he's a bit craftier. He's developed a composite poison
P
: a binary liquid that's only deadly when two individually harmless components mix; this is similar to how epoxy works. He's sent you another crate of 1,000 wine bottles. One bottle has componentC_a
and another one has componentC_b
. (P = C_a + C_b
)Anyone who drinks both components will die on the stroke of midnight on the night they drank the final component, regardless of when in the day they imbibed the liquid. Each poison component stays in the body until the second component activates, so if you drink one component one day and another component the next, you will die on midnight at the end of the second day.
You have two days before your next party. What is the minimum number of prisoners you need to use for testing in order to identify which two bottles are tainted, and what algorithm do you need to follow with that number of prisoners?
Bonus
Additionally, suppose that you had a fixed limit of 20 prisoners at your disposal, what's the maximum number of bottles you could theoretically test and come to an accurate conclusion about which bottles were affected?
Your task is to build a program to solve the bonus problem. Given n
prisoners, your program will devise a testing schedule that will be able to detect the two poisoned bottles among m
bottles, where m
is as large as possible.
Your program will initially take as input the number N
, the number of prisoners. It will then output:
M
, the number of bottles you will attempt to test. These bottles will be labelled from1
toM
.N
lines, containing the labels of the bottles each prisoner will drink.
Your program will then take as input which prisoners died on the first day, with the prisoner on the first line being 1
, the next line being 2
, etc. Then, it will output:
N
more lines, containing the labels of the bottles each prisoner will drink. Dead prisoners will have blank lines.
Your program will then take as input which prisoners died on the second day, and output two numbers, A
and B
, representing which two bottles your program thinks contains the poison.
An example input for two prisoners and four bottles might go as such, if bottles 1
and 3
are poisoned:
> 2 // INPUT: 2 prisoners
4 // OUTPUT: 4 bottles
1 2 3 // OUTPUT: prisoner 1 will drink 1, 2, 3
1 4 // OUTPUT: prisoner 2 will drink 1, 4
> 1 // INPUT: only the first prisoner died
// OUTPUT: prisoner 1 is dead, he can't drink any more bottles
3 // OUTPUT: prisoner 2 drinks bottle 3
> 2 // INPUT: prisoner 2 died
1 3 // OUTPUT: therefore, the poisoned bottles are 1 and 3.
The above algorithm may not actually work in all
cases; it's just an example of input and output.
Your program's testing schedule must successfully determine each possible pair of poisoned bottles in order for it to be a valid submission.
Your program will be scored on the following criteria, in order:
The maximum number of bottles it can discern for the case
N = 20
.The number of bottles for the case
N = 21
, and successively higher cases after that.The length of code. (Shorter code wins.)
How will the input look if more than one prisoner dies on a single day? Neither of your examples covers that case, and the specification is ambiguous to me. – ESultanik – 2015-07-16T11:34:03.690
Is it a single line with a space-separated list of prisoners that died? – ESultanik – 2015-07-16T11:35:29.813
Does shorter code matter more than number of bottles? Is it productive to increase the length of the code to make it handle one more bottle, as i did in my recent edit? – pppery – 2015-10-12T00:33:03.090
Number of bottles takes priority. If you make your code longer and more complex to squeeze more bottles in, that is productive. – Joe Z. – 2015-10-12T05:26:20.990
In the original problem there are only 2 days to solve the problem. Is that also the rule for the challenge? (it severly limits possible solutions, however an unlimited amount of days would be to easy) – LukStorms – 2015-11-02T22:43:10.657
The problem statement says, "You have two days before your next party." – Joe Z. – 2015-11-02T23:55:45.490