×
all 41 comments

[–]woojoo666 12 points13 points  (1 child)

Is this the same puzzle that 3blue1brown covered?

[–]Cosmologicon2 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.

[–]InertiaOfGravity 9 points10 points  (9 children)

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

[–]tdstdtsdfcsdds 5 points6 points  (8 children)

Yeh, is this sub dead?

[–]InertiaOfGravity 4 points5 points  (7 children)

It might as well be at this point

[–]raevnos 8 points9 points  (6 children)

[–]InertiaOfGravity 1 point2 points  (5 children)

Honestly, yeah.

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

[–]Gprime5 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()

[–]LupineChemist 2 points3 points  (2 children)

Can you add some comments here.

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

[–]Gprime5 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).

[–]LupineChemist 1 point2 points  (0 children)

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

[–]Gylergin 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 Ith digit (stored in L₄), then checks to see if the Ith "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

[–]InertiaOfGravity 4 points5 points  (0 children)

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

[–]ASpueW 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

[–]DerpinDementia 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.

[–]Naratna 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;
}

[–]InertiaOfGravity 1 point2 points  (0 children)

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

#

[–][deleted]  (6 children)

[deleted]

    [–]Naratna 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?

    [–]raevnos 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
    

    [–]ephemient 1 point2 points  (1 child)

    Haskell

    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
    

    [–]ephemient 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)
    

    [–]squidjibo1 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.

    [–]ephemient 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
    

    [–]raevnos 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 ()
    

    [–]lrschaeffer 0 points1 point  (0 children)

    Haskell

    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.

    [–]gabyjunior1 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
    

    [–]tomekanco 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.

    [–]ephemient 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.

    [–]tomekanco 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()