You and your fellow revolutionaries have been captured by the evil archduke, and now you’re all waiting for execution in the archduke’s dungeons. Fortunately, a thousand year old tradition states that all prisoners must be given a last chance to go free if they can solve a logic puzzle.
The warden explains what will happen:
Every prisoner will receive a red or blue hat. The prisoners will be seated so that they can see everyone else’s hat, but not their own hat. The prisoners must stay completely silent.
When the warden shouts “Now!”, all prisoners must immediately and simultaneously choose whether to raise their hand or not. Everyone will see everyone else, but they must still stay silent.
The warden will (privately) ask every prisoner what is the color of their own hat. If all prisoners answer correctly, the archduke has to let them go. If anyone makes a mistake, they will all be executed.
In both subproblems, there are N = 13 prisoners. In the easy subproblem H1, the hats are of C = 2 different colors (red and blue). In the hard subproblem H2, there are C = 4000 available hat colors.
Write a program that describes the prisoners’ strategy.
This problem is special. Usually, you can write a program in any programming language, and you only submit the computed output data, not your source code. This task is the exact opposite. You only submit source code – specifically, a program written in the Lua 5.3 language. (See below for an introduction.)
We will run N copies of your program and allow them to communicate according to the rules. If all N programs answer correctly, you win.
Your program can use these variables:
N: the number of prisoners.C: the number of different colors.myself: your own ID – a number between 1 and N, inclusive.colors: an array of visible hat colors. For every i between 1 and N, colors[i] will be a number between 1 and C, inclusive, except for colors[myself] which will be nil.raise: a function which takes a single boolean argument (whether you raise your hand or not), and returns an array of N booleans (for each prisoner, whether they raised their hand). You must call raise exactly once.answer: initially unset. You must set it to a number between 1 and C, inclusive – the number you want to announce as the color of your hat.These functions won’t exist: debug.debug, io.*, loadfile, math.random, math.randomseed, os.*, package.*, print, require.
We will run 300 test cases. (In total, your program will run 300 × N times.) The memory limit is 256 MB (for the sum of your N programs). The time limit is 10 seconds (for the sum of your 300 × N runs).
If you’d like, you can test your solution with our testing program: lua h-test.lua solution.lua .
If you don’t know the Lua language, here’s a quick introduction:
foo_bar = a + bnil, true, false, 123, 0xFF, "a string"1+2 == 3, 1-2 == -1, 2*3 == 6, 3/2 == 1.5, 3//2 == 1, 7%5 == 2, 2^3 == 8a == b, a ~= b, a < b, a <= b, a > b, a >= ba and b, a or b, not a (note that nil and false count as false, and everything else counts as true, including 0 and "")math.abs(x), math.floor(x), math.max(a, b, c, d), math.pi, etc.a & b (AND), a | b (OR), a ~ b (XOR), a >> b (right shift), a << b (left shift), ~a (NOT)if ??? then ... elseif ??? then ... else ... endwhile ??? do ... endfor i = 1, 128 do ... endfunction some_name(a, b, c) local d = 7; return a + d; endlocal l = 123arr[idx] (indexed from 1), { 1, 2, 3 } (new array), #arr (array length)--[[ multiple lines ]], -- until end of linea = 1 b = 2 + 3 c = 4 * 5For more details, refer to the Lua manual and the language grammar, or other on-line resources – though you probably won’t need most parts.
my_bool = colors[1] == 1 or myself > 6
hands = raise(my_bool)
if hands[1] or not hands[2] then
answer = 1
else
answer = C
end