threePrisoners.jls

(import) => {

assert = import('assert');
console = import('console');

range = (n) => {
  res = [];
  i = 0;
  
  while (i < n) {
    res.pushBack(i);
    i++;
  }
  
  return res;
};

strategy = {responses, visibleHats, log} => {
  totalHats = responses.length + visibleHats.length + 2;
  assert(totalHats == 4);

  eliminatedHats = [...responses, ...visibleHats];
  possibilities = range(totalHats).filter(i => !eliminatedHats.contains(i));

  log['possibilities: ', possibilities];

  if (responses.length == 0) {
    log('I\'m the first prisoner');

    nextHat = visibleHats.(0);
    lastHat = visibleHats.(1);
    rotation = [nextHat, ...possibilities].sort();
    log['rotation is: ', rotation];

    nextHatIndex = rotation.indexOf(nextHat);

    [offset, lastHatParity, direction] = (lastHat % 2 == 1 ?
      [1, 'odd', 'up'] :
      [-1, 'even', 'down']
    );

    guess = rotation.((rotation.length + nextHatIndex + offset) % rotation.length);

    log[
      'lastHat(', lastHat, ') is ', lastHatParity, ', so I will guess *', direction, '* from ',
      'nextHat(', nextHat, ') to get ', guess
    ];

    return guess;
  } else if (responses.length == 1) {
    log['I\'m the middle prisoner'];

    lastHat = visibleHats.(0);
    rotation = [responses.(0), ...possibilities].sort();
    log['The first prisoner's rotation should have been: ', rotation];

    [offset, lastHatParity, direction] = (lastHat % 2 == 1 ?
      [-1, 'odd', 'down'] :
      [1, 'even', 'up']
    );

    firstResponseIndex = rotation.indexOf(responses.(0));

    guess = rotation.((rotation.length + firstResponseIndex + offset) % rotation.length);

    log[
      'Since lastHat is ', lastHatParity, ', I should go *', direction, '* from the first prisoner's ' +
      'guess ', responses.(0), ' to get ', guess
    ];

    return guess;
  } else if (responses.length == 2) {
    log['I\'m the middle prisoner'];

    log['My possibilties are ', possibilities];

    scenarios = possibilities.map(myHat => {
      myHat,
      rotation: range(totalHats).filter(i => i != myHat),
    });

    log['That means there are two scenarios: ', scenarios];

    middleHat = responses.(1);

    scenariosConsistent = scenarios.map({ myHat, rotation } => {
      log['Scenario with my hat being ', myHat];

      [offset, myHatParity, direction] = (myHat % 2 == 1 ?
        [1, 'odd', 'up'] :
        [-1, 'even', 'down']
      );

      middleHatIndex = rotation.indexOf(middleHat);

      simulatedFirstHat = rotation.(
        (rotation.length + middleHatIndex + offset) % rotation.length
      );

      log[
        '  My hat is ', myHatParity, ', so the first prisoner should have gone ', direction, ' from ' +
        middleHat, ' to get ', simulatedFirstHat
      ];

      if (simulatedFirstHat == responses.(0)) {
        log['  And that\'s what happened, so this scenario is consistent.'];
        return true;
      }

      log['  But that\'s not what happened, so this scenario is inconsistent.'];
      return false;
    });

    assert(scenariosConsistent.any(c => c));

    if (scenariosConsistent.all(c => c)) {
      log['Both scenarios work, so I\'ll arbitrarily pick ', scenarios.(0).myHat];
      return scenarios.(0).myHat;
    }

    correctScenario = (scenariosConsistent.(0) ? scenarios.(0) : scenarios.(1));
    log['So the only valid possibility is ', correctScenario.myHat];
    return correctScenario.myHat;
  }
};

perms = (arr) => (arr.length == 0 ? [[]] :
  range(arr.length).map(
    i => perms(arr.filter(x => x != arr.(i))).map(perm => [arr.(i), ...perm])
  ).reduce([a1, a2] => [...a1, ...a2])
));

assert((() => {
  visualPerm = (arr) => perms(arr).map(perm => perm.join('')).join(',');

  assert(visualPerm([]) == '');
  assert(visualPerm(['a', 'b']) == 'ab,ba');
  assert(visualPerm(['a', 'b', 'c']) == 'abc,acb,bac,bca,cab,cba');

  return true;
})());

simulate4 = [hats, log] => {
  assert(hats.length == 4);
  names = ['A', 'B', 'C'];

  prisoners = range(3).map(i => { name: names[i], hat: hats[i] });

  responses = [];

  log[
    'Prisoners ', names, ' have hats ', hats.slice(0, 3), ', ',
    '(hat ', hats.(3), ' was omitted)\n\n'
  ];

  correctCount = 0;

  range(3).forEach(i => {
    visibleHats = hats.slice(i + 1, 3);
    log[
      'Prisoner ', prisoners.(i).name, ' is wearing hat ', hats.(i), ', has heard ', responses, ', ',
      'and can see ', visibleHats
    ];

    response = strategy[responses, visibleHats, str => log['  ', str]];
    correct = (response == hats.(i));

    if (correct) {
      correctCount++;
    }

    log['The response was ', response, '. This prisoner ', correct ? 'lives' : 'dies', '.\n\n'];

    responses.pushBack(response);
  });

  log[correctCount, ' prisoner(s) lived.'];

  return correctCount;
};

results = perms(range(4)).map(hats => {
  logOutput = '';
  correctCount = simulate4(hats, str => { logOutput +~ str + '\n'; });

  return {
    hats,
    logOutput,
    correctCount,
  };
});

console.log['minimum survival:', results.map(r => r.correctCount).reduce([x, y] => min[x, y])];

console.log['mean survival:',
  results.map(x => x.correctCount).reduce([x, y] => x + y) / results.length
];

console.log['results', results];

console.log['\n\n', results.map(r => r.logOutput).join('\n\n\n\n\n')];

}