This is demonstrating a solution to the "hiding a key in a chessboard" problem detailed here: https://www.youtube.com/watch?v=as7Gkm7Y7h4

chessboardproblem.py

"""
This is demonstrating a solution to the "hiding a key in a chessboard" problem detailed here:
https://www.youtube.com/watch?v=as7Gkm7Y7h4
"""

"""This function cribbed from wikipedia.  Yes I know it's impossibly slow."""
def crc_remainder(input_bitstring, polynomial_bitstring, initial_filler):
    """Calculate the CRC remainder of a string of bits using a chosen polynomial.
    initial_filler should be '1' or '0'.
    """
    polynomial_bitstring = polynomial_bitstring.lstrip('0')
    len_input = len(input_bitstring)
    initial_padding = initial_filler * (len(polynomial_bitstring) - 1)
    input_padded_array = list(input_bitstring + initial_padding)
    while '1' in input_padded_array[:len_input]:
        cur_shift = input_padded_array.index('1')
        for i in range(len(polynomial_bitstring)):
            input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))
    return int(''.join(input_padded_array)[len_input:], 2)

def as_bitstring(k):
    return "{0:b}".format(k)

# Number of squares
problem_size = 64
max_board_val = (2**problem_size) - 1
# Number of bits required to uniquely address a square
n_addr_bits = 1
while 2**n_addr_bits < problem_size: n_addr_bits += 1

# Number of bits in the CRC polynomial
n_poly_bits = n_addr_bits + 1

# For a given board layout, what key address is being indicated?
def getKeyAddrFor(board_val):
    poly = '1000011'
    return crc_remainder(as_bitstring(board_val), poly, '0')

# For a given board and key position, what address should you flip to indicate the correct key position?
def genMoveFor(board_val, key_pos):
    flip_map = {}
    # No-flip is actually not allowed... oops
    flip_map[-1] = getKeyAddrFor(board_val)
    for j in range(problem_size):
        other_bv = board_val ^ (1 << j)
        flip_map[j] = getKeyAddrFor(other_bv)
    available_moves = []
    for flip_pos, shown_val in flip_map.items():
        if shown_val != key_pos:
            continue
        # We have iterated to a single flip which will display the correct key position
        available_moves.append(flip_pos)
        if flip_pos == -1:
            print("Using no-flip will work.")
        else:
            print("Flipping the coin at location %d will work."%flip_pos)
        return available_moves
    print("NO SOLUTION FOUND FOR BOARD %X KEY POS %d"%(board_val, key_pos))
    assert(0)

# Using the solution from the video, what key address is being indicated by a particular board layout?
def officialGetKeyAddrFor(board_val):
    key_addr = 0
    for i in range(64):
        if (1<<i) & board_val: key_addr ^= i
    return key_addr

# Using the solution from the video and given a particular board value and key location, what coin should we flip?
def officialGenMoveFor(board_val, key_pos):
    return officialGetKeyAddrFor(board_val) ^ key_pos

from random import randint

for i in range(100):
    print("Run %d"%i)
    chosen_key_pos = randint(0,63)
    board_val = randint(0,max_board_val)
    # Switched off: test my solution vs. official solution
    if 0:
        my_move = genMoveFor(board_val, chosen_key_pos)
        official_move = officialGenMoveFor(board_val, chosen_key_pos)
        print("My move vs official move: %d  vs %d"%(my_move[0], official_move))
        test_board = board_val ^ (1<<official_move)
        indicated_key_pos = officialGetKeyAddrFor(test_board)
        print("Official chosen vs. indicated: %d vs %d"%(chosen_key_pos, indicated_key_pos))
    # For a random board and key location, figure out the coin to flip, then verify that the new board shows the correct address
    if 1:
        print("board %X key pos %d" % (board_val, chosen_key_pos))
        available_moves = genMoveFor(board_val, chosen_key_pos)

        # Check returned moves
        for move in available_moves:
            flipped_bv = board_val
            if move != -1:
                flipped_bv ^= (1<<move)
            indicated_key_pos = getKeyAddrFor(flipped_bv)
            if indicated_key_pos == chosen_key_pos:
                print("Successfully indicated key position %d"%chosen_key_pos)
            else:
                print("Failed to indicate key pos %d, got %d"%(chosen_key_pos, indicated_key_pos))