Source code in the jq programming language

export LC_ALL=C
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -MRcnr -f 100-prisoners.jq


def count(s): reduce s as $x (0; .+1);

# Output: a PRN in range(0;$n) where $n is .
def prn:
  if . == 1 then 0
  else . as $n
  | (($n-1)|tostring|length) as $w
  | [limit($w; inputs)] | join("") | tonumber
  | if . < $n then . else ($n | prn) end
  end;

def knuthShuffle:
  length as $n
  | if $n <= 1 then .
    else {i: $n, a: .}
    | until(.i ==  0;
        .i += -1
        | (.i + 1 | prn) as $j
        | .a[.i] as $t
        | .a[.i] = .a[$j]
        | .a[$j] = $t)
    | .a 
    end;

# Output: if all the prisoners succeed, emit true, otherwise false
def optimalStrategy($drawers; np):
  # Does prisoner $p succeed?
  def succeeds($p):
    first( foreach range(0; np/2) as $d ({prev: $p};
             .curr = ($drawers[.prev])
             | if .curr == $p
               then .success = true
               else .prev = .curr
               end;
             select(.success))) // false;
  
  all( range(0; np); succeeds(.) );
  
# Output: if all the prisoners succeed, emit true, otherwise false
def randomStrategy($drawers; np):
  (np/2) as $maxd
  # Does prisoner $p succeed?
  | def succeeds($p):
      {success: false }
      | first(.d = 0
              | .opened = []
              | until( (.d >= $maxd) or .success;
                  (np|prn) as $n
                  | if .opened[$n] then .
                    else .opened[$n] = true
                    | .d += 1
                    | .success = $drawers[$n] == $p
                    end )
              | select(.success) ) // false;

  all( range(0; np); succeeds(.) );


def run(strategy; trials; np):
  count(range(0; trials)
    | ([range(0;np)] | knuthShuffle) as $drawers
    | select (if strategy == "optimal"
              then optimalStrategy($drawers; np)
              else randomStrategy($drawers; np)
              end ) );

def task($trials):
  def percent: "\(10000 * . | round / 100)%";
  def summary(strategy):
    "With \(strategy) strategy: pardoned = \(.), relative frequency = \(./$trials | percent)";

  (10, 100) as $np
  | "Results from \($trials) trials with \($np) prisoners:",
    (run("random";  $trials; $np) | summary("random")),
    (run("optimal"; $trials; $np) | summary("optimal")),
    ""
;

task(100000)