Write a function to solve the problem mentioned below. The chessboard 8x8 matrix will be filled with coins randomly and given to you. Also the index key chosen by the warden will be given. All you need to find is the flipping index. (In testing boards 1 refers to heads whereas 0's are tails)
Standard setup: A prison warden is bored, so gives two prisoners the chance to escape, but only if they can solve a puzzle. They have 30 minutes to discuss a solution, but thereafter they will be placed in solitary confinement.
The problem: One prisoner is going to be put in front of a chessboard, with a coins on each square (such that there are 64 coins). The coins will be tossed and placed randomly, such that heads or tails can be showing on any given square. The warden is then going to point to a single coin and state 'This is the magic key'. The prisoner can then flip one, and only one, coin (doesn't have to be the one the warden pointed at). The first prisoner will be escorted away, and the second prisoner brought to the chessboard. The second prisoner must then point to a single square, and state 'This is the magic key'. The prisoner has only one chance - if correct, they go free. Can the prisoners find a strategy to guess the magic key correctly? If so how?
It suffices to convey 6 bits of information to determine the magic key on a 8*8 chessboard. However, different bit mapping/coding schemes require different coins to be flipped. Under different coding schemes, it is possible to identify the magic key by flipping a coin different from the one specified in your test suite. Thus, it is not a good idea to check the index of the flipped coin.
Peng, there is one and onyly one index for the flipping coin given the chessboard and the magic key. Therefore the problem is valid. Cheers.
Hi, Omer, thanks for submitting this interesting problem to Cody, which makes Cody an interesting game. But I am sure you are missing some important thing here, i.e., the coding/decoding rule to convey the 6 bits of information is not unique, and consequently, the flipping coin which is determined by the coding rule is not unique either. To elaborate on this, let’s consider the simplest 1*2 chessboard example. There are a total of 4 possible initial coin states on the 1*2 chessboard: HH, HT, TT, TH, where H stands for “head” and T stands for “tail”. The warden may choose either coin as the magic key. Now here comes the first possible coding/decoding rule which is predetermined and agreed by the two prisoners. If the 1st coin is the magic key, the first prisoner always flips one coin such that the 1st coin shows H. If the 2nd coin is the magic key, the first prisoner always flips one coin such that the 1st coin shows T. This is the coding rule applied by the first prisoner. The decoding rule applied by the second prisoner is like this: whenever the second prisoner sees H on the 1st coin, he declares the 1st coin as the magic key; whenever he sees T on the 1st coin, he declares the 2nd coin as the magic key. For simplicity of explanation, suppose that the first coin is chosen by the warden as the magic key. Then under the above coding rule, the flipping coins corresponding to the 4 initial states HH, HT, TH, TT are 2, 2, 1, 1, respectively. Now, let’s consider a different coding/decoding rule predetermined by the prisoners. The coding procedure works as follows: If the 1st coin is the magic key, the first prisoner always flips one coin such that the 1st coin shows T (not H). If the 2nd coin is the magic key, the first prisoner always flips one coin such that the 1st coin shows H (not T). The decoding rule also needs to be updated: whenever the second prisoner sees T (not H) on the 1st coin, he declares the 1st coin as the magic key; whenever he sees H (not T) on the 1st coin, he declares the 2nd coin as the magic key. Under this set of rule, again consider that the first coin is chosen as the magic key. Then the flipping coins corresponding to the 4 initial states HH, HT, TH, TT are 1, 1, 2, 2, respectively. Obviously, we see different flipping coins corresponding to the above two different coding/decoding methods. The 8*8 chessboard is just a generalization of the above simple 1*2 example; thus, it has many more different coding/decoding rules which correspond to different flipping coins.
Hi Peng thanks for the descriptive comments you are right i have to change the question. Cheers
Hi Omer, any progress in modifying this interesting problem? Cheers.
Hi, Omer. This is a very interesting problem. Yet there are many possible correct strategies for the prisoners to follow and your testsuite only checks one particular strategy. Perhaps you could ask players to create a function that can be asked to act as the first prisoner or as the second prisoner and simply check that the second prisoner response correctly guesses the magic key?
example of possible strategy (among many)
and by "many" I mean at least "~10^90 many"...
just seen your code, must say you did very well. will consider your recommendations to correct the question. Cheers
Number of 1s in the Binary Representation of a Number
322 Solvers
Sum all integers from 1 to 2^n
6663 Solvers
73 Solvers
Greed is good - Simple partition P[n].
22 Solvers
54 Solvers