DEV Community

Discussion on: Coins on a Chessboard

dry profile image
Hayden Mankin Author

Sorry about the confusion, I was trying to be very thorough in explaining this.

I'm not exactly sure what you're asking, but I can try to explain the 2 x 2 grid again and how you decode it. The premise is that given any board configuration we can find some function that maps it to a specific spot on the board.

We do this by looking at all of the spots that are heads up, and then xor their indices.

If they are all heads we can xor all of the indices together: 00 xor 01 xor 10 xor 11 -> 11 which is 3 in binary so that board corresponds to the 3rd spot on the board.

if they are all tails then their are no elements to xor together so it is just 00 which is 0 in binary so that board corresponds to the 0th spot on the board.

something like the following where half are heads and half are tails:

Heads Tails
Heads Tails

positions 00 and 10 are heads, so we do 00 xor 10 -> 10 which is 2 in binary so this board corresponds to the 2nd spot on the board.

It is actually many to 1, as there are more configurations of coins than there are spots on the board we are mapping them to. with a 2 x 2 board there are 24 coin configurations while there are only 4 spaces on the board to map them to.

After we know we can encode a specific position on the board based on the coins configuration, we can move on to how to choose which coin to flip.

Did that help? again, I'm sorry for the confusion.

This is another video that goes into detail if you're interested.

mxldevs profile image
MxL Devs

I think I understand the two-step process. The goal is to find two squares A and B such that A XOR B will give you the position of the key, so the trick is to treat the initial configuration as A and the final configuration as B.

It's an interesting trick.