Hats – Java

public class Hats
{
    private static List stringsList = new ArrayList();

    private static final String reference = "0123456789";

    private static Random random = new Random();

    private static List copy = new ArrayList();

    public static void main(String args[])
    {
        int numberOfGuests = 10;
        for (int i = 0; i < 10; i++) {
            stringsList.add("" + i);
        }
        System.err.println("Strings: " + stringsList);
        int m = 0;
        int n = 100000000; // 000000;
        System.err.println("Going to run " + n + " tests.");
        for (int i = 0; i < n; i++) {
            String s = generateOnePermutation(numberOfGuests);
            if (noDigitInPosition(s)) {
                m++;
            }
            if (i % (n / 100) == 0) {
                System.err.println("Finished test number: " + i);
            }
        }
        System.err.println("Results:\nTotal Cases tested: " + n);
        System.err.println("Cases in which no guest got their hat back: " + m);
    }

    /**
     * @param stringSize
     * @return
     */
    private static String generateOnePermutation(int stringSize)
    {
        if (copy.size() > 0) {
            System.err.println("Serious problem: copy not empty");
        }
        copy.addAll(stringsList);
        StringBuilder output = new StringBuilder();
        while (output.length() < stringSize) {
            int index = random.nextInt(copy.size());
            output.append(copy.get(index));
            copy.remove(index);
        }
        // System.err.println("One permutation: " + output);
        return output.toString();
    }

    /**
     * @param s
     * @return
     */
    private static boolean noDigitInPosition(String s)
    {
        // System.err.println("s: " + s);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == reference.charAt(i)) {
                // System.err.println(i + ": " + s.charAt(i));
                return false;
            }
        }
        // System.err.println("No digit is in correct position");
        return true;
    }
}

Leave a Reply