puzzle.cc

// See Puzzle 1 from https://blog.tanyakhovanova.com/2024/03/two-lovely-puzzles/

#include <algorithm>
#include <iostream>

const int ROUNDS = 1000;

// To make the puzzle at least somewhat amenable to dynamic
// programming, we introduce a new parameter: the fraction of all
// possible binary sequences for the leader to choose their stone
// sequences from. In the original version, that parameter is always
// 100%.

// The entry fractions[s] is the maximum number x with the following
// property. As long as the dealer is restricted to choose their stone
// sequence from at from a fraction x of all binary sequences, there
// is an algorithm that guarantees that the non-dealer players score
// at least s wins.
double fractions[ROUNDS+1];

// The version of the puzzle referenced above does not let player 2
// distinguish the between which stone was produced by player 1 and
// which stone was produced by the dealer. We call this version
// "anonymous" (ANON == true). There's another version, where player 2
// can make that distinction (ANON == false).
// https://puzzling.stackexchange.com/questions/30214/strategy-to-beat-the-casino
const bool ANON = true;

#define out(x) << " "#x":"<< x << " "

int main() {
  fractions[0] = 1.0;
  for (int r = 1; r <= ROUNDS; ++r) {
    // We iterate backwards in order to have access to the old
    // fractions[s-1] while computing fractions[s].
    for (int s = ROUNDS; s >= 0; --s) {
      // This is the core of the computation. When player 2 makes a
      // guess, say 0, there are the following cases:
      // 1. Both the dealer and player 1 also chose 0. This is a win.
      // 2. The dealer or player 1 or both chose 1. This is a loss.
      double case1 = fractions[std::max(0, s-1)];
      double case2 = fractions[s];
      if (ANON) {
        // In the anonymous case, there are only two distinguishable
        // ways case2 can happen (the stones of dealer and player 1
        // have the same color or not).
        fractions[s] = std::min(2.0, case1 + 2 * case2) / 2.0;
      } else {
        // In the non-anonymous case, the are three distinguishable
        // ways case2 can happen (if the dealer and player 1 cast
        // stones of different colors, player 2 can't tell who cast
        // which).
        fractions[s] = (std::min(1.0, case1 + case2) + std::min(1.0, 2 * case2)) / 2.0;
      }
    }
    for (int s = ROUNDS; s >= 0; --s)
      // We don't worry too much floating point accuracy here because
      // all the operations we perform are near-exact in IEEE
      // representations (additions and divisions by 2).
      if (fractions[s] == 1.0) {
        // s is the maximum score that can be guaranteed for d rounds.
        std::cout out(ANON) out(r) out(s) << std::endl;
        break;
      }
    // for (int s = 0; s <= r; ++s)
    //   std::cout out(r) out(s) out(fractions[s]) << std::endl;
    // std::cout << std::endl;
  }
  return 0;
}