100 prisoners GitHub issue #33

[Wtfsaitama]

https://claude.ai/share/62394fb1-217d-466e-afc6-4efd62679101

Stefan 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);
}

}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 AssistantJava implementation of ideal solution to the 100 Prisoners problemWillst du dir den Diff im Kontext der ganzen Datei ansehen oder geht's dir nur um diesen Ausschnitt?