Ready to run the jave code

[Wtfsaitama]

https://github.com/Wtfsaitama/100-prisoners/tree/main

Use the optimal cycle-following strategy: each prisoner starts at the box with their own number and follows the permutation inside boxes up to 50 steps. Below is a compact, production-ready Java implementation plus a Monte Carlo simulator to estimate the success probability.

import java.util.Random;

public class PrisonersProblem {
    // Generate random permutation of 1..n (perm[i] is value in box i+1)
    public static int[] randomPermutation(int n, Random rnd) {
        int[] perm = new int[n];
        for (int i = 0; i < n; i++) perm[i] = i + 1;
        for (int i = n - 1; i > 0; i--) {
            int j = rnd.nextInt(i + 1);
            int tmp = perm[i];
            perm[i] = perm[j];
            perm[j] = tmp;
        }
        return perm;
    }

    // Run one trial using cycle-following strategy.
    // Returns true if every prisoner finds their number within maxLookups (= n/2).
    public static boolean trialCycleStrategy(int[] perm) {
        int n = perm.length;
        int maxLookups = n / 2;
        for (int prisoner = 1; prisoner <= n; prisoner++) {
            int box = prisoner; // start at box with own number
            boolean found = false;
            for (int step = 0; step < maxLookups; step++) {
                int value = perm[box - 1];
                if (value == prisoner) { found = true; break; }
                box = value; // follow the permutation cycle
            }
            if (!found) return false; // this prisoner failed => whole trial fails
        }
        return true; // all prisoners found their number
    }

    // Run many trials and return fraction of successful trials
    public static double estimateSuccessProbability(int n, long trials, long seed) {
        Random rnd = (seed >= 0) ? new Random(seed) : new Random();
        long successes = 0;
        for (long t = 0; t < trials; t++) {
            int[] perm = randomPermutation(n, rnd);
            if (trialCycleStrategy(perm)) successes++;
        }
        return (double) successes / (double) trials;
    }

    public static void main(String[] args) {
        int n = 100;
        long trials = 100_000;
        long seed = -1; // negative means random seed

        if (args.length >= 1) n = Integer.parseInt(args[0]);
        if (args.length >= 2) trials = Long.parseLong(args[1]);
        if (args.length >= 3) seed = Long.parseLong(args[2]);

        long start = System.currentTimeMillis();
        double prob = estimateSuccessProbability(n, trials, seed);
        long elapsed = System.currentTimeMillis() - start;

        System.out.printf("n=%d, trials=%d -> success rate = %.6f (time: %d ms)%n",
                          n, trials, prob, elapsed);
    }
}

Notes:

• This implements the standard optimal strategy (follow cycles) and a fast Fisher–Yates shuffle for random permutations.
• For n = 100 the theoretical success probability ≈ 0.3118 (≈ 31.18%). With 100,000 trials you'll converge close to that.
• Usage: compile and run, e.g. javac PrisonersProblem.java && java PrisonersProblem 100 100000.

Do you want me to add this file to your repository (Wtfsaitama/100-prisoners) and commit it? If so, tell me the exact path/filename to create (default suggestion: src/PrisonersProblem.java) and the commit message to use.

GitHub Copilot Chat Assistant