November 04 2019, 16:38

Today, I was challenged with a very cool task (below), I found a solution, will you find one? They say there are multiple solutions, but I can’t see any others besides my own.

So, there is an 8×8 board scattered with stones randomly. Each cell can contain as many stones as it fits, from zero to whatever number fits. The host thinks of a cell. He calls it to character A. Character A, let’s call him Vasya, decides to either remove or add exactly one stone to any cell of his choice or to do nothing. Then he leaves. Next, a second character comes in, let’s call him Petya, looks at the board, thinks, and names the secret cell. Of course, Petya and Vasya had pre-arranged a strategy on what Vasya needs to do so that Petya can guess the cell correctly. The question is – what is this strategy?

UPDATE: Solution:

Essentially, two functions need to be written, encode (cell, origboard), which returns newboard and decode (newboard), which returns cell. The difference between newboard and origboard is one set bit.

static long encode(long board, int cell) {

int change = getHash(board) ^ cell;

return board ^ (1L << change);

}

static int decode(long board) {

return getHash(board);

}

static private int getHash(long board) {

int hash = 0;

for (int i = 0; i < 64; i++) {

if ((board & 0x1) != 0) {

hash ^= i;

}

board >>>= 1;

}

return hash;

}