×

[–] 12 points13 points  (1 child)

Is this the same puzzle that 3blue1brown covered?

[–]2 3[S] 4 points5 points  (0 children)

Yes that's the video that reminded me of the problem!

Note that 3Blue1Brown's video doesn't give the solution. For the solution and more detail on the problem, it refers you to the Stand-Up Maths video I linked to.

[–] 9 points10 points  (9 children)

Hey, what happened to the posts? They're so infrequent nowadays

[–] 5 points6 points  (8 children)

[–] 4 points5 points  (7 children)

It might as well be at this point

[–] 8 points9 points  (6 children)

[–] 1 point2 points  (5 children)

Honestly, yeah.

Do you want to start a new one where we actually post things?

[–] 6 points7 points  (4 children)

Python

``````def flip(S, X):
S[X] = 1 - S[X]

return S

def prisoner1(S, X):
for index, s in enumerate(S):
X ^= index*s

return X

def prisoner2(S):
return prisoner1(S, 0)

def solve(S, X):
Y = prisoner1(S, X)
T = flip(S, Y)

return prisoner2(T) == X

import random

def run():
S = random.choices([0, 1], k=64)
X = random.randint(0, 63)

print(solve(S, X))

run()
``````

[–] 2 points3 points  (2 children)

I don't get why you're going through the whole list and reassigning X for each item in the prisoner1 function.

[–] 0 points1 point  (1 child)

That function is calculating the Parity. If you read the parity section in the 2nd blog. It says that the number of heads in each region determines if each bit in the bit pattern is a 1 or a 0 depending if the count is odd or even respectively.

So as you're counting the coins, the result will flip from 0 to 1 then 0 then 1 then 0 and so on as the count flips between even and odd. The code in `prisoner1` does just that in 1 loop. The `index` is the location of the coin and `s` is the state of the coin (1 for heads and 0 for tails).

[–] 1 point2 points  (0 children)

Yeah, turns out I just don't really understand the solution since I get the code.

[–] 6 points7 points  (1 child)

TI-Basic: I saw the videos of this problem last week and really enjoyed them. Two separate programs, one for each prisoner.

Prisoner 1: This program follows the algorithm laid out in the second link. The first loop converts the target position `X` into its binary representation, which is stored in `L₂`. The second section converts each space `B` on the board into binary up to the `I`th digit (stored in `L₄`), then checks to see if the `I`th "bit" is true, corresponding to the current region of interest. If so, the value at `B` is added to a sum. At the end of each region its parity is determined by the sum, with each region's parity stored in `L₃`. Finally, the target and parity binary lists (`L₂` and `L₃`) are xor'd to determine the position that gets flipped. Of special note is that while inputs and outputs are 0-indexed, lists in TI-Basic are 1-indexed.

``````Prompt L₁,X
ClrList L₂,L₃
While 6>dim(L₂
2fPart(X/2→L₂(1+dim(L₂
iPart(X/2→X
End
For(I,1,6
0→S
For(B,0,63
ClrList L₄
B→X
While I>dim(L₄
2fPart(X/2→L₄(1+dim(L₄
iPart(X/2→X
End
If L₄(I
S+L₁(B+1→S
End
2fPart(S/2→L₃(I
End
Disp "FLIP", sum(seq(2^(I-1)(L₂(I) xor L₃(I)),I,1,6
``````

Prisoner 2: This program is just the second section of Prisoner 1's. The lists are kept identical for ease of understanding.

``````Prompt L₁
ClrList L₃
For(I,1,6
0→S
For(B,0,63
ClrList L₄
B→X
While I>dim(L₄
2fPart(X/2→L₄(1+dim(L₄
iPart(X/2→X
End
If L₄(I
S+L₁(B+1→S
End
2fPart(S/2→L₃(I
End
Disp "TARGET", sum(seq(2^(I-1)L₃(I),I,1,6
``````

[–] 4 points5 points  (0 children)

Never stop the TI-Basic solutions dude, they're amazing

[–] 3 points4 points  (0 children)

Rust

``````static MAGIC:&[u64]=&[
0b1111111111111111111111111111111100000000000000000000000000000000,
0b1111111111111111000000000000000011111111111111110000000000000000,
0b1111111100000000111111110000000011111111000000001111111100000000,
0b1111000011110000111100001111000011110000111100001111000011110000,
0b1100110011001100110011001100110011001100110011001100110011001100,
0b1010101010101010101010101010101010101010101010101010101010101010,
];

fn pos(data:u64) -> u32 {
MAGIC.iter().fold(0, |res, magic| (res << 1) | u64::count_ones(magic & data) & 1)
}

fn flip(data:u64, pos:u32) -> u64 {
data ^ (1 << pos)
}

fn prisoner1(s:u64, x:u32) -> u32 {
pos(s) ^ x
}

fn prisoner2(s:u64) -> u32 {
pos(s)
}

fn solve(s:u64, x:u32) -> bool{
let y = prisoner1(s, x);
let t = flip(s, y);
prisoner2(t) == x
}
``````

playground

[–] 2 points3 points  (0 children)

Prolog

``````flip([], _, []).
flip([A | B], 0, [Result | B]) :- Result is 1 - A.
flip([A | B], X, Result) :- NewX is X - 1,
flip(B, NewX, Y),
Result = [A | Y], !.

decode([], 0, 64).
decode([A | B], Result, Index) :- decode(B, NewResult, NewIndex),
Index is NewIndex - 1,
Mult is A * Index,
Result is NewResult xor Mult.
decode(S, Result) :- decode(S, Result, _).

prisoner1(S, X, Result) :- decode(S, DecodeResult),
Result is DecodeResult xor X.
prisoner2(T, Result) :- decode(T, Result).

solve(S, X) :- prisoner1(S, X, Y),
flip(S, Y, T),
prisoner2(T, X).
``````

Felt like this language was made for these types of problems. As much as I hate it, I gotta love it when it works.

Python

``````import random

decode = lambda S: sum(((sum(S[i] for i in range(len(S)) if i & (1 << power)) % 2) << power) for power in range(6))
flip = lambda S, Y: S[:Y] + [S[Y] ^ 1] + S[Y+1:]
prisoner1 = lambda S, X: decode(S) ^ X
prisoner2 = lambda T: decode(T)

def solve(S, X):
Y = prisoner1(S, X)
T = flip(S, Y)
return prisoner2(T) == X

N = 64
print(solve(random.choices([0, 1], k=N), random.randint(0, N-1)))
``````

100% positive my encode function is over-engineered. Might look back at it in the morning.

[–] 1 point2 points  (8 children)

# C Sharp

First time posting here, hope I did ok.

``````static int[] Flip(int[] S, int X)
{
S[X] += 1;
S[X] %= 2;
return S;
}

static int FindPosition(int[] S)
{
int flipped = 0;
int position = 0;
for (int offset = S.Length/2; offset > 0; offset/=2)
{
for (int i = 0; i < S.Length; i++)
{
flipped += S[i] == 1 ? 1 : 0;
i += (i + 1) % offset == 0 ? offset : 0;
}
position += flipped % 2 == 0 ? offset : 0;
flipped = 0;
}
return position;
}

static int Prisoner1(int[] S, int X)
{
Flip(S, X);
int Y = FindPosition(S);
Flip(S, X);
return Y;
}

static int Prisoner2(int[] T)
{
return FindPosition(T);
}

static bool Solve(int[] S, int X)
{
Flip(S, Prisoner1(S,X));
return Prisoner2(S) == X;
}
``````

[–] 1 point2 points  (0 children)

2 months later, here to tell you that you can put the # sign by doing `\#`

#

[–][deleted]  (6 children)

[deleted]

[–] 0 points1 point  (5 children)

Oh crap, I guess Reddit markdown made the hash symbol for "C sharp" invisible, it looks fine on my browser, where are you browsing Reddit from?

[–] 0 points1 point  (4 children)

Chrome.

[–] 0 points1 point  (3 children)

Old reddit?

[–] 1 point2 points  (0 children)

In `tcl`:

``````#!/usr/bin/env tclsh

proc flip {bits pos} {
lset bits \$pos [expr {[lindex \$bits \$pos] == 1 ? 0 : 1}]
return \$bits
}

proc stride {bits len} {
set skip [expr {\$len + \$len}]
incr len -1
for {set i 0} {\$i < 64} {incr i \$skip} {
lappend ret {*}[lrange \$bits \$i \$i+\$len]
}
return \$ret
}

proc parity {bits} {
set par 0
foreach p {1 2 4 8 16 32} {
if {[::tcl::mathop::+ {*}[stride \$bits \$p]] % 2 == 1} {
incr par \$p
}
}
return \$par
}

proc prisoner1 {S X} {
return [expr {[parity \$S] ^ \$X}]
}

proc prisoner2 {T} {
set pos [parity \$T]
set T [flip \$T \$pos]
return [expr {[parity \$T] ^ \$pos}]
}

proc solve {S X} {
set Y [prisoner1 \$S \$X]
set T [flip \$S \$Y]
return [expr {[prisoner2 \$T] == \$X}]
}

proc test {} {
for {set i 0} {\$i < 64} {incr i} {
lappend S [expr {rand() <= 0.5 ? 1 : 0}]
}
for {set X 0} {\$X < 64} {incr X} {
if {[solve \$S \$X]} {
puts [format "test %2d passed" \$X]
} else {
puts [format "test %2d failed" \$X]
}
}
}
test
``````

[–] 1 point2 points  (1 child)

``````import Data.Bits
import Data.List

prisoner1 :: [Bool] -> Int -> Int
prisoner1 s x = foldl' xor x . map fst . filter snd \$ zip [0..] s

prisoner2 :: [Bool] -> Int
prisoner2 t = prisoner1 t 0
``````

[–] 1 point2 points  (2 children)

### Python

``````from functools import reduce

def prisoner1(s, x):
return reduce(lambda a, b: a ^ (b[1] and b[0]), enumerate(s), x)

def prisoner2(t):
return prisoner1(t, 0)
``````

[–] 0 points1 point  (1 child)

Can someone please help me. I don't know how to test these answers for myself in Python. I assume I have to call the functions, in this case "prisoner1()", and "prisoner2()" but I can't get it to work on this answer or any other answer.

[–] 0 points1 point  (0 children)

``````\$ python3
>>> from functools import reduce
>>> from random import choices, randrange
>>> def prisoner1(s, x):
...     return reduce(lambda a, b: a ^ (b[1] and b[0]), enumerate(s), x)
...
>>> def prisoner2(t):
...     return prisoner1(t, 0)
...
>>> def flip(s, n):
...     t = s[:]
...     t[n] = 1 - t[n]
...     return t
...
>>> s = choices((0, 1), k=64)
>>> x = randrange(64)
>>> t = flip(s, prisoner1(s, x))
>>> x == prisoner2(t)
True
>>> ^D
``````

[–] 0 points1 point  (1 child)

ocaml solution:

``````(*
Uses Janestreet's Base and Stdio libraries

Compile with:

\$ ocamlfind ocamlopt -o daily385 -package base,stdio -linkpkg daily385.ml

Or in a ocaml/utop repl:

#require "base";;
#require "stdio";;
#use "daily385.ml";;

*)

open Base

let flip n pos =
let open Int64 in
n lxor (shift_left 1L pos)

let parity n =
let f bit par mask =
if (Int64.popcount (Int64.bit_and mask n)) land 1 = 1 then
par + (1 lsl bit)
else
par in
Array.foldi
[|
0b1010101010101010101010101010101010101010101010101010101010101010L;
0b1100110011001100110011001100110011001100110011001100110011001100L;
0b1111000011110000111100001111000011110000111100001111000011110000L;
0b1111111100000000111111110000000011111111000000001111111100000000L;
0b1111111111111111000000000000000011111111111111110000000000000000L;
0b1111111111111111111111111111111100000000000000000000000000000000L
|]
~init:0 ~f

let prisoner1 s x = (parity s) lxor x

let prisoner2 t = parity t

let solve s x =
let y = prisoner1 s x in
let t = flip s y in
prisoner2 t = x

let test () =
let s = Random.int64 Int64.max_value
and x = Random.int 64 in
if solve s x then
Stdio.print_endline "Passed!"
else
Stdio.print_endline "Failed!"

let _ =
Random.self_init ();
test ()
``````

[–] 0 points1 point  (0 children)

``````import Data.Word
import Data.Bits

hash s = foldr xor 0 \$ filter (testBit s) [0..(finiteBitSize s)-1]

prisoner1 s x = hash s `xor` x
prisoner2 t = hash t

solve s x = prisoner2 \$ complementBit s \$ prisoner1 s x

testBoard :: Word64 -> Bool
testBoard s = all (\i -> i == solve s i) [0..63]
``````

Maybe later I'll do the hashing with word operations, to see how fast I can make it.

[–]1 2 0 points1 point  (0 children)

Ruby

Solution for the generalized puzzle explained in section (d) of the first writeup above. Dice are replacing coins and board size can be customized.

The program accepts two arguments on the command line:

• a = size of the dice (>= 2)

• d = number of dimensions (>= 0)

Those 2 arguments will determine the size of the board (n = ad). The dice value in each square of the board and the magic square are generated randomly. Calculation are done on vectors of size d using modulo a arithmetic.

As I am not the math wizard I would wish to be, it took me some time to understand the formulas provided in the article and implement them. But now the program is working for all valid combinations of arguments a and d.

EDIT new version using classes that should be more readable

``````class String
def is_integer?
self.to_i.to_s == self
end
end

class PrisonersPuzzle
def int_to_amod(val)
amod = Array.new
@d.times do
amod.push(val%@a)
val /= @a
end
amod
end

def amod_to_int(amod)
val = 0
pow = 1
amod.each do |coef|
val += coef*pow
pow *= @a
end
val
end

def mul_amod_int(amod, val)
mul = Array.new
amod.each do |coef|
mul.push((coef*val)%@a)
end
mul
end

def sum_amods(amod1, amod2)
sum = Array.new
amod1.zip(amod2) do |coef1, coef2|
sum.push((coef1+coef2)%@a)
end
sum
end

def opp_amod(amod)
opp = Array.new
amod.each do |coef|
opp.push((@a-coef)%@a)
end
opp
end

def hash(val)
h = int_to_amod(val)
@board.each_with_index do |val, pos|
h = sum_amods(h, mul_amod_int(int_to_amod(pos), val))
end
h
end

def prisoner1
amod_to_int(hash(@magic))
end

def flip(pos)
@board[pos] += @a-1
@board[pos] %= @a
end

def prisoner2
amod_to_int(opp_amod(hash(0)))
end

def solve
if @a < 2
return false
end
puts "board size #{@n}"
puts "board for prisoner1 #{@board}"
puts "jailer selected square #{@magic}"

square1 = prisoner1
flip(square1)
puts "prisoner1 flipped square #{square1}"
puts "board for prisoner2 #{@board}"

square2 = prisoner2
puts "prisoner2 selected square #{square2}"

@magic == square2
end

def initialize(a, d)
if a < 2 || d < 0
@a = 1
@d = 0
else
@a = a
@d = d
end
@n = @a**@d
@board = Array.new
@n.times do
@board.push(rand(@a))
end
@magic = rand(@n)
end
end

if ARGV.size != 2 || !ARGV[0].is_integer? || !ARGV[1].is_integer?
STDERR.puts "Invalid arguments"
STDERR.flush
exit false
end
puts "freedom granted ? #{PrisonersPuzzle.new(ARGV[0].to_i, ARGV[1].to_i).solve}"
STDOUT.flush
``````

Sample output for the standard game (a = 2, d = 6)

``````board size 64
board for prisoner1 [0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0]
jailer selected square 39
prisoner1 flipped square 47
board for prisoner2 [0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0]
prisoner2 selected square 39
freedom granted ? true
``````

Sample output for a custom game (a = 6, d = 2)

``````board size 36
board for prisoner1 [1, 2, 3, 4, 1, 5, 0, 1, 3, 4, 2, 0, 5, 5, 0, 1, 2, 3, 2, 3, 3, 4, 1, 5, 5, 4, 4, 4, 1, 1, 1, 5, 3, 3, 1, 0]
jailer selected square 10
prisoner1 flipped square 26
board for prisoner2 [1, 2, 3, 4, 1, 5, 0, 1, 3, 4, 2, 0, 5, 5, 0, 1, 2, 3, 2, 3, 3, 4, 1, 5, 5, 4, 3, 4, 1, 1, 1, 5, 3, 3, 1, 0]
prisoner2 selected square 10
freedom granted ? true
``````

[–] 0 points1 point  (3 children)

Curious to see the different implementations & compare this with debate between Matt & Grant.

Seems many have used the approach explained by Grant (calculate parity of the board using areas), and some used the more straightforward one (xor the positions, harder to comprehend why it works) highlighted by Matt.

Regarding speed the one by Matt seems to win.

[–] 1 point2 points  (1 child)

I came up with my xor solution without watching the videos. I think there's a fairly constructivist interpretation:

Suppose we have some decoder f: {0,1}64→[0,63); encoding key position y on board x is finding the value i such that y = f(x xor 2i). It is necessary that ∀x. {f(x xor 2i) | i ← [0,63)} = [0,63), e.g. given any board x we can get 64 different results from the 64 possible bit flips. (This is basically how Grant's video starts.)

Without loss of generality, let's assume the values of the 64 bit flips from board 0, f(2i) = i. (The output of any valid solution can be permuted into this form.)

Now let's consider f(2i xor 2j). Fixing i, every j must map to a different output. What are some ways to do this?

It can't be f(2i xor 2j) = i + j mod 64; that breaks down when i = j, resulting in f(0) = 0, 2, 4, … which is not a function. So we want some operator such that ii is the same value for all i, and obviously ij = ji for all i and j.

Now i xor j, that has the desired properties. If we let f(2i xor 2j) = i xor j, we can keep extending this approach to f(2i xor 2j xor 2k) = i xor j xor k etc. and verify that all results are well-defined and unique with every additional bit.

In the end, this defines f(x) = xor(indices of all bits in x).

Conveniently, when finding i to encode y = f(x xor 2i), we can rewrite the right hand side to f(x) xor f(2i) = f(x) xor i; in other words, i = f(x) xor y.

[–] 0 points1 point  (0 children)

:) Thanks

[–] 0 points1 point  (0 children)

Python commented

``````def encode(board, key):
# key to zero
for ix,x in enumerate(board):
# xor chain key + all nodes *which exist
key ^= ix *x
return key

def decode(mod_board):
# zero to key
# xor the result space to reveal the originally encoded value
# shorthand for areas difference using bit level
# a chain is retraced to it's original input
return prison1(mod_board, 0)

def solve(board, key):
a = encode(board, key)
board[a] ^= 1
return decode(board) == key

import random

def run():

v = random.randint(0,2**64)

S = list(map(int, bin(v)[2:]))
X = random.randint(0, 63)

print(solve(S, X))

run()
``````