DEV Community

Hayden Mankin
Hayden Mankin

Posted on

Coins on a Chessboard

#javascript #algorithms #tutorial #computerscience

Introduction

Recently I've discovered the concept of error detecting/correcting codes and have been fascinated. Specifically I read an article here about the Luhn algorithm the other day.

divyajyotiuk

Credit card number check

Divyajyoti Ukirde ・ Jul 5 '20

#javascript #algorithms #tutorial

And even more fascinating to me was this video from 3blue1brown.

This problem is fascinating to me for so many reasons, especially how it can be rewritten as a graph theory problem. I won't be diving into the many different ways to write or solve this problem, but I encourage you to watch his video if you're interested.

The Chessboard Problem

In case you don't wanna watch the whole video, I'll summarize the problem posed.

  • There are 3 people involved in this scenario two prisoners and a warden.
  • The warden takes prisoner 1 to a room with a chessboard, the chessboard has a coin on every square.
  • The warden is able to flip any coins he wants over, and hide a key under one coin.
  • Prisoner 1, knowing where the key is, is allowed to flip over one coin in an attempt to relay the keys position to prisoner 2.
  • No other information or hints may be left by prisoner 1, he is escorted out of the room and prisoner 2 enters.
  • Prisoner 2 is allowed to pick up one coin to find the key, if he finds the key their freedom is assured, if not they are stuck in prison.
  • If the prisoners are allowed to strategize before attempting the puzzle, is it possible to relay the position of the key to the other prisoner?

The Solution

While it would be tricky to do by hand (entirely feasible, but tedious), writing a program to find a solution is fairly simple. I thought I would share my implementation and how I worked through it.

To solve this problem I'm going to start with an example of a 2x2 chessboard, every position on the checkerboard is going to be assigned a unique index.
0 1
2 3

The problem doesn't actually need a 2D grid to be solved, we can just as easily work it out if we flatten the above array:
0 1 2 3

For the sake of matching the original problem, I will mostly display the table in 2d format.

It's also important to note that all of these numbers can be written in binary.
00 01
10 11

Next we can represent the board state in terms of heads and tails, or true and false.
Heads Heads
Heads Tails

For our notation the above layout will match the following representation.
True True
True False

Before we can find a way to send information by flipping a coin, we need a way to turn our board state into a message for the other prisoner. If we look at all the spots on the board that are heads up, we get the positions {00, 01, 10} while {11} is tails. If we XOR all of the positions in the heads up positions we get 00 XOR 01 XOR 10 -> 11 meaning the message prisoner 2 would receive is position 11.

We now need a way to send a specific message, let's say the warden hides the key position 10. We need to flip one and only one coin to change the message from 11 to 10, to do this we find the differing bits 11 XOR 10 -> 01 and flip the resulting coin.

So our board state goes from:
True True
True False

To:
True False
True False

After flipping the coin prisoner 1 can leave and allow prisoner to decode the message using the previously described method.

  1. The heads up coins are in positions {00, 10}
  2. XOR all heads up coins: 00 XOR 10 -> 10
  3. Look under the resulting coin (10 -> 3) to find the key

This method extends to larger boards, with some caveats I will explain later.

We will expand to a 4x4 for another example. The positions are going to be assigned as follows:
0000 0001 0010 0011
0100 0101 0110 0111
1000 1001 1010 1011
1100 1101 1110 1111

The warden flips coins to give this board:
False False False True
False True False False
True False True False
True False False False

Then the warden hides the key in position 0010.

Prisoner 1 takes the following steps to flip a coin over:

  1. Find all positions that are heads up: {0011, 0101, 1000, 1010, 1100}
  2. XOR all positions: 0011 XOR 0101 XOR 1000 XOR 1010 XOR 1100 -> 1000
  3. Find different bits between the keys position and the current message: 0010 XOR 1000 -> 1010
  4. Flip the coin at position 1010

The new board state is:
False False False True
False True False False
True False False False
True False False False

Prisoner 2 takes the following steps to decode the message:

  1. Find all positions that are heads up: {0011, 0101, 1000, 1100}
  2. XOR all positions: 0011 XOR 0101 XOR 1000 XOR 1100 -> 0010
  3. Look under the coin in position 0010

The Implementation

To implement, there are 5 individual functions we will implement:

  • randomBoard(n)
    • returns randomized n x n board of coins
  • randomPosition(board)
    • returns random position on board in the format {i: int, j: int}
  • decodeBoard(board, target=0)
    • returns result of XOR operations on all true values on board as well as the target parameter
  • whatCoinToFlip(board, target)
    • returns position of coin to flip to encode target on the board in the form {i: int, j: int}
  • flipCoin(board, target)
    • return a deep copy of board where the coin at target is flipped
  • findKey(board)
    • return position in the form {i: int, j: int} of key given a board that has the proper message encoded.

randomBoard(n) 

function randomBoard(n) {
    let board = [];
    for (let i = 0; i < n; i++) {
        board.push([]);
        for(let j = 0; j < n; j++) {
            board[i].push(Math.random() > .5);
        }
    }
    return board;
}
Enter fullscreen mode Exit fullscreen mode

All this function does is initialize an array, push n arrays into it then push n random boolean values into all of those.

We can also test it using console.table(board) which will allow us to view our board in a very attractive way.

let board = randomBoard(4);
console.table(board);
Enter fullscreen mode Exit fullscreen mode 
┌─────────┬──────┬───────┬───────┬───────┐
│ (index) │  0   │   1   │   2   │   3   │
├─────────┼──────┼───────┼───────┼───────┤
│    0    │ true │ false │ true  │ true  │
│    1    │ true │ true  │ false │ true  │
│    2    │ true │ true  │ true  │ false │
│    3    │ true │ true  │ false │ false │
└─────────┴──────┴───────┴───────┴───────┘
Enter fullscreen mode Exit fullscreen mode

randomPosition(board) 

function randomPosition({length}) {
    return {
        i: random(length),
        j: random(length)
    };
    function random(max) {
        return  Math.floor(Math.random() * max);
    }
}
Enter fullscreen mode Exit fullscreen mode

Javascript doesn't have a built in random function that takes a range, so I just wrote a small random function to make it more readable to me. Our indexes i and j line up with the boards row and column respectively. Simply returning two random numbers constrained to the boards length is enough.

Also, rather than calling board.length, it's easier to destructure the object and just get length in the function parameters.

let board = randomBoard(4);
let keyLocation = randomPosition(board);
console.log(keyLocation);
Enter fullscreen mode Exit fullscreen mode 
key:  { i: 3, j: 2 }
Enter fullscreen mode Exit fullscreen mode

decodeBoard(board, target=0); 

function decodeBoard(board, target=0) {
    return board.flat().reduce((cum, val, idx) => cum ^ (val * idx), target);
}
Enter fullscreen mode Exit fullscreen mode

First I'm going to flatten the array because 1D arrays are easier to iterate over, from here we can proceed with reduce. Using javascript reduce to XOR all elements of an array is pretty trivial, the trick here is val * idx will be 0 whenever val is false. Because when it tries to do multiplication the True value will act is if it is 1 and False will act as if it is a 0. I can see how this might be viewed as bad practice, however I think it makes the code look pretty nice in this case.

I'm also using target as the starting point of our accumulator, since target is 0 by default it will decode the board normally if not given anything. However, if we give it a value it will also XOR that value, this allows us to pass an extra parameter to get the coin we need to flip to get a specific value encoded.

let board = randomBoard(4);
console.table(board);
let val = decodeBoard(board);
console.log(val);
Enter fullscreen mode Exit fullscreen mode 
┌─────────┬──────┬───────┬───────┬───────┐
│ (index) │  0   │   1   │   2   │   3   │
├─────────┼──────┼───────┼───────┼───────┤
│    0    │ true │ false │ true  │ true  │
│    1    │ true │ false │ false │ true  │
│    2    │ true │ true  │ true  │ false │
│    3    │ true │ true  │ false │ false │
└─────────┴──────┴───────┴───────┴───────┘
8
Enter fullscreen mode Exit fullscreen mode

whatCoinToFlip(board, target) 

function whatCoinToFlip(board, {i, j}) {
    let target = i * board.length + j
    let pos = decodeBoard(board, target);

    return {
        i: Math.floor(pos / board.length),
        j: pos % board.length
    };
}
Enter fullscreen mode Exit fullscreen mode

I'm using the same destructuring trick as earlier (in randomPosition) to just get i and j from the target passed in. Then we need to convert the row column indexes to our mapping we laid out in the solution part of the post. It will be the same as an index in the flattened array, so we can use i * board.length + j

We can then decode the board, passing in the extra parameter to get the specific coin we need to flip.

We can then convert the index on a 1D array to a position on a 2D array and return it.

let board = randomBoard(4);
console.table(board);
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);
Enter fullscreen mode Exit fullscreen mode 
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ true  │ false │ true  │ false │
│    1    │ false │ false │ false │ true  │
│    2    │ true  │ false │ true  │ false │
│    3    │ true  │ true  │ true  │ false │
└─────────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 3, j: 1 }
flip over the coin at { i: 1, j: 1 }
Enter fullscreen mode Exit fullscreen mode

flipCoin(board, target) 

function flipCoin(board, {i, j}) {
    let newBoard = board.map((arr) => arr.slice());
    newBoard[i][j] = !newBoard[i][j];
    return newBoard;
}
Enter fullscreen mode Exit fullscreen mode

While this may be a somewhat unnecessary addition as I can always just change board itself, I wanted to avoid mutations as much as possible, so I'm returning a new array. The array is also always going to be 2D, so the copy can be made by using map, where every array in the board is mapped to a copy.

Then, we make the change at position [i][j] and return the newBoard.

let board = randomBoard(4);
console.table(board);
let locationToFlip = randomPosition(board);
console.log("Flipping coin at", locationToFlip);
board = flipCoin(board, locationToFlip);
console.table(board);
Enter fullscreen mode Exit fullscreen mode 
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ false │ false │
│    1    │ true  │ false │ false │ true  │
│    2    │ true  │ true  │ false │ true  │
│    3    │ false │ false │ false │ false │
└─────────┴───────┴───────┴───────┴───────┘
Flipping coin at { i: 2, j: 3 }
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ false │ false │
│    1    │ true  │ false │ false │ true  │
│    2    │ true  │ true  │ false │ false │
│    3    │ false │ false │ false │ false │
└─────────┴───────┴───────┴───────┴───────┘
Enter fullscreen mode Exit fullscreen mode

findKey(board) 

function findKey(board) {
    let pos = decodeBoard(board);

    return {
        i: Math.floor(pos / board.length),
        j: pos % board.length
    };
}
Enter fullscreen mode Exit fullscreen mode

This function is very simple as we only need to decode the board, and then convert the 1D index to a 2D index and return it.

let board = randomBoard(4);
console.table(board);
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);
board = flipCoin(board, flipLocation);
console.table(board);
let decodedKeyLocation = findKey(board);
console.log("The key is at", decodedKeyLocation);
Enter fullscreen mode Exit fullscreen mode 
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ true  │ false │
│    1    │ true  │ false │ true  │ false │
│    2    │ false │ true  │ false │ false │
│    3    │ true  │ false │ true  │ true  │
└─────────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 1, j: 0 }
flip over the coin at { i: 0, j: 0 }
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ true  │ false │ true  │ false │
│    1    │ true  │ false │ true  │ false │
│    2    │ false │ true  │ false │ false │
│    3    │ true  │ false │ true  │ true  │
└─────────┴───────┴───────┴───────┴───────┘
The key is at { i: 1, j: 0 }
Enter fullscreen mode Exit fullscreen mode

Conclusion

Now after putting everything together we are left with a fairly concise program that can simulate and solve the puzzle.

function randomBoard(n) {
    let board = [];
    for (let i = 0; i < n; i++) {
        board.push([]);
        for(let j = 0; j < n; j++) {
            board[i].push(Math.random() > .5);
        }
    }
    return board;
}

function randomPosition({length}) {
    return {
        i: random(length),
        j: random(length)
    };

    function random(max) {
        return  Math.floor(Math.random() * max);
    }
}

function whatCoinToFlip(board, {i, j}) {
    let target = i * board.length + j
    let pos = decodeBoard(board, target);

    return {
        i: Math.floor(pos / board.length),
        j: pos % board.length
    };
}

function flipCoin(board, {i, j}) {
    let newBoard = board.map((arr) => arr.slice());
    newBoard[i][j] = !newBoard[i][j];
    return newBoard;
}

function findKey(board) {
    let pos = decodeBoard(board);

    return {
        i: Math.floor(pos / board.length),
        j: pos % board.length
    };
}

function decodeBoard(board, target=0) {
    return board.flat().reduce((cum, val, index) => cum ^ (val * index), target);
}

// generate new board
let board = randomBoard(4);
console.table(board);

// generate random position for the key
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);

// get the coin prisoner 1 should flip
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);

// flip the specified coin over
board = flipCoin(board, flipLocation);
console.table(board);

// have prisoner 2 decode the board and find key.
let decodedKeyLocation = findKey(board);
console.log("The key is at", decodedKeyLocation);
Enter fullscreen mode Exit fullscreen mode 
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ true  │ false │ true  │ false │
│    1    │ true  │ false │ false │ false │
│    2    │ false │ true  │ false │ false │
│    3    │ true  │ true  │ true  │ true  │
└─────────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 0, j: 0 }
flip over the coin at { i: 3, j: 3 }
┌─────────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │
├─────────┼───────┼───────┼───────┼───────┤
│    0    │ true  │ false │ true  │ false │
│    1    │ true  │ false │ false │ false │
│    2    │ false │ true  │ false │ false │
│    3    │ true  │ true  │ true  │ false │
└─────────┴───────┴───────┴───────┴───────┘
The key is at { i: 0, j: 0 }
Enter fullscreen mode Exit fullscreen mode

Pretty cool right? the program also changes pretty easily to larger boards, lets try it with n=8 since the original problem wanted a chessboard.

// generate new board
let board = randomBoard(8);
console.table(board);

// generate random position for the key
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);

// get the coin prisoner 1 should flip
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);

// flip the specified coin over
board = flipCoin(board, flipLocation);
console.table(board);

// have prisoner 2 decode the board and find key.
let decodedKeyLocation = findKey(board);
console.log("The key is at", decodedKeyLocation);
Enter fullscreen mode Exit fullscreen mode 
┌─────────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │   4   │   5   │   6   │   7   │
├─────────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ true  │ true  │ false │ true  │ true  │ false │
│    1    │ false │ true  │ false │ false │ true  │ false │ false │ false │
│    2    │ false │ true  │ true  │ false │ true  │ true  │ true  │ true  │
│    3    │ true  │ false │ true  │ false │ false │ true  │ false │ true  │
│    4    │ true  │ false │ true  │ true  │ true  │ false │ true  │ true  │
│    5    │ false │ true  │ false │ false │ true  │ false │ true  │ false │
│    6    │ false │ true  │ false │ false │ false │ true  │ false │ false │
│    7    │ false │ false │ true  │ false │ false │ true  │ true  │ false │
└─────────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 5, j: 5 }
flip over the coin at { i: 7, j: 3 }
┌─────────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │   4   │   5   │   6   │   7   │
├─────────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│    0    │ false │ false │ true  │ true  │ false │ true  │ true  │ false │
│    1    │ false │ true  │ false │ false │ true  │ false │ false │ false │
│    2    │ false │ true  │ true  │ false │ true  │ true  │ true  │ true  │
│    3    │ true  │ false │ true  │ false │ false │ true  │ false │ true  │
│    4    │ true  │ false │ true  │ true  │ true  │ false │ true  │ true  │
│    5    │ false │ true  │ false │ false │ true  │ false │ true  │ false │
│    6    │ false │ true  │ false │ false │ false │ true  │ false │ false │
│    7    │ false │ false │ true  │ true  │ false │ true  │ true  │ false │
└─────────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘
The key is at { i: 5, j: 5 }
Enter fullscreen mode Exit fullscreen mode

Lastly I wanted to jump back to something I mentioned briefly, there are some caveats to this scaling up, I was very intentional in using n=2, n=4 and n=8. these can all be written in the form of n=2k, since our algorithm is relies on flipping over a specific coin derived from repeated XOR operations there needs to actually be a coin for every possible value using 2k bits. So its impossible to solve a 9 x 9 board as we need 7 bits to represent numbers n > 63, however there is no coin for any n > 81 such as 93 -> 1011101

We can even try this odd board size and see an error occur as the index it tries to find is out of bounds

┌─────────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ (index) │   0   │   1   │   2   │   3   │   4   │   5   │   6   │   7   │   8   │
├─────────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│    0    │ false │ true  │ false │ false │ false │ false │ true  │ false │ false │
│    1    │ false │ true  │ true  │ true  │ false │ false │ false │ false │ false │
│    2    │ true  │ true  │ true  │ true  │ false │ false │ false │ true  │ true  │
│    3    │ false │ true  │ false │ false │ false │ true  │ false │ true  │ false │
│    4    │ true  │ false │ false │ false │ false │ false │ true  │ true  │ false │
│    5    │ true  │ true  │ false │ false │ true  │ false │ false │ false │ true  │
│    6    │ true  │ false │ false │ false │ false │ true  │ false │ false │ false │
│    7    │ false │ true  │ false │ true  │ false │ true  │ false │ true  │ true  │
│    8    │ true  │ false │ false │ true  │ true  │ true  │ true  │ false │ true  │
└─────────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘
The key is hidden at { i: 1, j: 3 }
flip over the coin at { i: 12, j: 3 }
TypeError: Cannot read property '3' of undefined
    at flipCoin (/home/runner/ChessBoardProblem/index.js:35:32)
    at /home/runner/ChessBoardProblem/index.js:65:9
    at Script.runInContext (vm.js:131:20)
    at Object.<anonymous> (/run_dir/interp.js:156:20)
    at Module._compile (internal/modules/cjs/loader.js:1133:30)    at Object.Module._extensions..js (internal/modules/cjs/loader.js:1153:10)
    at Module.load (internal/modules/cjs/loader.js:977:32)
    at Function.Module._load (internal/modules/cjs/loader.js:877:14)
    at Function.executeUserEntryPoint [as runMain] (internal/modules/run_main
.js:74:12)
Enter fullscreen mode Exit fullscreen mode

It is entirely possible however, for some non-square boards, such as a 2 x 32 which will use all 5 bit numbers or an 8 x 16 board using all 7 bit numbers. As long as the total number of coins can be written in the form n=2^k

Rewriting some code we can generalize it for n x m boards.

function randomBoard(n, m) {
    let board = [];
    for (let i = 0; i < n; i++) {
        board.push([]);
        for(let j = 0; j < m; j++) {
            board[i].push(Math.random() > .5);
        }
    }
    return board;
}

function randomPosition({length, [0]: {length: width}}) {
    return {
        i: random(length),
        j: random(width)
    };

    function random(max) {
        return  Math.floor(Math.random() * max);
    }
}

function whatCoinToFlip(board, {i, j}) {
    let target = i * board[0].length + j
    let pos = decodeBoard(board, target);

    return {
        i: Math.floor(pos / board[0].length),
        j: pos % board[0].length
    };
}

function flipCoin(board, {i, j}) {
    let newBoard = board.map((arr) => arr.slice());
    newBoard[i][j] = !newBoard[i][j];
    return newBoard;
}

function findKey(board) {
    let pos = decodeBoard(board);

    return {
        i: Math.floor(pos / board[0].length),
        j: pos % board[0].length
    };
}

function decodeBoard(board, target=0) {
    return board.flat().reduce((cum, val, index) => cum ^ (val * index), target);
}

// generate new board
let board = randomBoard(2,8);
console.table(board);

// generate random position for the key
let keyLocation = randomPosition(board);
console.log("The key is hidden at", keyLocation);

// get the coin prisoner 1 should flip
let flipLocation = whatCoinToFlip(board, keyLocation);
console.log("flip over the coin at", flipLocation);

// flip the specified coin over
board = flipCoin(board, flipLocation);
console.table(board);

// have prisoner 2 decode the board and find key.
let decodedKeyLocation = findKey(board);
console.log("The key is at", decodedKeyLocation);
Enter fullscreen mode Exit fullscreen mode 
┌─────────┬───────┬───────┬──────┬──────┬───────┬───────┬───────┬──────┐
│ (index) │   0   │   1   │  2   │  3   │   4   │   5   │   6   │  7   │
├─────────┼───────┼───────┼──────┼──────┼───────┼───────┼───────┼──────┤
│    0    │ false │ true  │ true │ true │ false │ true  │ false │ true │
│    1    │ false │ false │ true │ true │ true  │ false │ true  │ true │
└─────────┴───────┴───────┴──────┴──────┴───────┴───────┴───────┴──────┘
The key is hidden at { i: 1, j: 4 }
flip over the coin at { i: 0, j: 2 }
┌─────────┬───────┬───────┬───────┬──────┬───────┬───────┬───────┬──────┐
│ (index) │   0   │   1   │   2   │  3   │   4   │   5   │   6   │  7   │
├─────────┼───────┼───────┼───────┼──────┼───────┼───────┼───────┼──────┤
│    0    │ false │ true  │ false │ true │ false │ true  │ false │ true │
│    1    │ false │ false │ true  │ true │ true  │ false │ true  │ true │
└─────────┴───────┴───────┴───────┴──────┴───────┴───────┴───────┴──────┘
The key is at { i: 1, j: 4 }
Enter fullscreen mode Exit fullscreen mode

I'll leave it you to read through and find the changes on that one :)

This was my first post here, I hope you learned something, I thought this was a really cool and wanted to share. If anyone else knows any similar puzzles/algorithms I'd love to dive more into this subject. I know my university offers a course on error correcting codes but it's only offered in the spring semesters so I have a bit until I can take it, so I'd love some resources to dive into the subject on my own.

Thanks!

Top comments (3)

Collapse
 
mxldevs profile image
MxL Devs •

I stopped at the 2x2 as I don't understand lol. What happens if all of them are heads? Or all tails? Or half heads half tails?

Given any configuration of coins, does there exist a 1 to 1 mapping of squares regardless of how the coins appear?

Collapse
 
dry profile image
Hayden Mankin •

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.
youtube.com/watch?v=as7Gkm7Y7h4

Collapse
 
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.

Read next

ricardocaselati profile image

Types: char and boolean

Ricardo Caselati -

williamsdev profile image

Horóscopo com IA: Uma Experiência com Next.js e Gemini

Frank William -

thisweekinjavascript profile image

JavaScript vs. Deno, Vite 6, Astro 5, and more

James -

rivea0 profile image

LeetCode Meditations: Merge Intervals

Eda -