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
Project Euler: Problem 4, Palindromic numbers
300 Solvers
96 Solvers
59 Solvers
Calculate compression ratio of engine
88 Solvers
Vector of numbers divisible by 3
132 Solvers
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!