Forked from anonymous/gist:79aca4248b09cf436846
Last active
February 14, 2016 01:03
-
-
Save heiner/274bf8a6285d2551cb4c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15| | |
----------------------------------------------| | |
0 0 0 0 | 0 | |
1 1 1 1 | 0 | |
2 2 2 2 | 1 | |
3 3 3 3 | 1 | |
4 4 4 4 | 2 | |
5 5 5 5 | 2 | |
6 6 6 6 | 3 | |
7 7 7 7| 3 | |
8 8 8 8 | 3 | |
9 9 9 9 | 3 | |
10 10 10 10 | 2 | |
11 11 11 11| 2 | |
12 12 12 12 | 1 | |
13 13 13 13| 1 | |
14 14 14 14| 0 | |
15 15 15 15 | 0 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Implementing chessboard prisoner puzzle | |
# generate_table() below generates pictures | |
# beware: these quickly become big | |
import math | |
import sys | |
import random | |
length = 8 | |
board_size = length**2 | |
def generate_chessboard(): | |
return random.getrandbits(board_size) | |
def generate_magic_square(): | |
return random.getrandbits(math.frexp(board_size-1)[1]) | |
def print_chessboard(board): | |
for line in [format(board, '0' + str(board_size) + 'b')[j:j+length] | |
for j in range(0, board_size, length)]: | |
print '-' * (length*4 + 1) | |
print '| ' + ' | '.join(list(line)) + ' |' | |
print '-' * (length*4 + 1) | |
def h(board): | |
result = 0 | |
for j in range(board_size): | |
if (1 << j) & board: | |
result ^= j | |
return result | |
def flip_coin(board, coin): | |
return board ^ (1 << coin) | |
def first_prisoner(board, magic_square): | |
return h(board) ^ magic_square | |
def second_prisoner(board): | |
return h(board) | |
def generate_table(x_cutoff=32, y_cutoff=512): | |
if board_size > 2**4: | |
raise Exception("That's gonna become too big") | |
size = 2**board_size | |
x_cutoff_size = min(x_cutoff, size) | |
for j in range(x_cutoff_size): | |
sys.stdout.write(format(j, '3')) | |
sys.stdout.write("|\n") | |
sys.stdout.write('-'*3*x_cutoff_size + "|\n") | |
for k in range(min(size, y_cutoff)): | |
flips = [flip_coin(k, coin) for coin in range(size)] | |
for j in range(x_cutoff_size): | |
if j in flips: | |
sys.stdout.write(format(k, '3')) | |
else: | |
sys.stdout.write(' ') | |
sys.stdout.write("|") | |
guess = h(flips[-1]) | |
sys.stdout.write(" "*2*guess + format(guess, '2') + "\n") | |
def run(): | |
#generate_table() | |
#return | |
board = generate_chessboard() | |
print ("""First prisoner sees board {0} | |
(in binary: {0:0{board_size}b})""").format(board, board_size=board_size) | |
print_chessboard(board) | |
print "h(board) =", h(board) | |
magic_square = generate_magic_square() | |
print "Magic square is {0}".format(magic_square) | |
coin = first_prisoner(board, magic_square) | |
print "First prisoner chooses coin", coin | |
print "\n * * * \n" | |
new_board = flip_coin(board, coin) | |
print ("""First prisoner sees board {0} | |
(in binary: {0:0{board_size}b})""").format(new_board, board_size=board_size) | |
print_chessboard(new_board) | |
print "Second prisioner guesses magic square", second_prisoner(new_board) | |
if magic_square == second_prisoner(new_board): | |
print "And they survive!" | |
else: | |
print "And both die." | |
if __name__ == '__main__': | |
run() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Oliver Nash about this problem: http://olivernash.org/2009/10/31/yet-another-prisoner-puzzle/ (includes rings and modules! <3)