import junit.framework.TestCase;

import java.util.*;

public class kabaleo_gk_Test extends TestCase {
    final kabaleo_gk_ok_cases solution = new kabaleo_gk_ok_cases();
    final Random random = new Random(3248418023124914124L);
    final int[] LOOSE = a();

    public void testOne() {
        assertGame(1, a(1), a(1), a(0));
        assertGame(1, a(1), a(0), LOOSE);
        assertGame(1, a(1), a(0, 1), a(0));
        assertGame(1, a(1), a(1, 0), LOOSE);

        assertGame(1, a(0), a(1), a(0));
        assertGame(1, a(0), a(0), LOOSE);
        assertGame(1, a(0), a(0, 1), a(0));
        assertGame(1, a(0), a(1, 0), LOOSE);
    }

    public void testTwo() {
        assertGame(1, a(1, 1), a(1), a(0, 1));
        assertGame(1, a(1, 0), a(1), a(1));
        assertGame(1, a(0, 0), a(1), LOOSE);
        assertGame(1, a(1, 1), a(1, 1, 1), a(0, 1));
        assertGame(1, a(0, 1), a(1, 1, 1), a(0));
        assertGame(1, a(0, 0), a(1, 1, 1), LOOSE);
        assertGame(1, a(1, 1), a(1, 0, 1), LOOSE);
        assertGame(1, a(1, 1), a(0), LOOSE);
        assertGame(1, a(1, 1), a(0, 1, 1), LOOSE);
    }

    public void testThree() {
        assertGame(1, a(1, 1, 1), a(1), a(0, 1, 2));
        assertGame(1, a(1, 0, 1), a(1), a(0, 1, 2));
        assertGame(1, a(0, 0, 1), a(1), a(0, 1));
        assertGame(1, a(0, 0, 0), a(1), LOOSE);

        assertGame(1, a(1, 1, 1), a(1, 1, 1), a(0, 1, 2));
        assertGame(1, a(1, 0, 1), a(1, 1, 1), a(0, 1, 2));
        assertGame(1, a(0, 0, 1), a(1, 1, 1), a(0, 1));
        assertGame(1, a(0, 0, 0), a(1, 1, 1), LOOSE);

        assertGame(1, a(1, 1, 1), a(1, 0), a(0, 1, 2));
        assertGame(1, a(1, 0, 1), a(1, 0), a(1));
        assertGame(1, a(0, 0, 1), a(1, 0), LOOSE);

        assertGame(1, a(1, 1, 1), a(0, 1, 1), a(0, 1, 2));
        assertGame(1, a(1, 0, 1), a(0, 1, 1), a(1));
        assertGame(1, a(0, 0, 1), a(0, 1, 1), LOOSE);

        assertGame(1, a(1, 1, 1), a(0, 0), LOOSE);
    }

    public void testFour() {
        assertGame(1, a(1, 1, 1, 1), a(1), a(0, 1, 2, 3));

        assertGame(1, a(1, 1, 1, 2), a(1), a(0, 1, 2, 3));
        assertGame(1, a(1, 2, 1, 2), a(1), a(1, 3));
        assertGame(1, a(2, 2, 1, 2), a(1), LOOSE);
        assertGame(1, a(2, 3, 1, 4), a(1), a(0, 1, 3));
        assertGame(1, a(2, 2, 1, 4), a(1), a(0, 1));
        assertGame(1, a(2, 2, 1, 2), a(1), LOOSE);

        assertGame(1, a(1, 1, 1, 2), a(1, 0), a(0, 1, 2, 3));
        assertGame(1, a(1, 2, 1, 2), a(1, 2), LOOSE);
        assertGame(1, a(2, 3, 1, 4), a(1, 1), a(0, 1, 3));
        assertGame(1, a(2, 4, 1, 2), a(1, 1), a(0, 3));
        assertGame(1, a(2, 4, 1, 2), a(1, 0), LOOSE);
        assertGame(1, a(1, 1, 2, 3), a(1, 0), a(2, 3));
        assertGame(1, a(1, 1, 2, 3), a(1, 2), a(2));
        assertGame(1, a(1, 1, 2, 2), a(1, 2), LOOSE);

        assertGame(1, a(1, 1, 1, 1), a(1, 0, 1), a(0, 1, 2, 3));
        assertGame(1, a(1, 1, 1, 1), a(1, 0, 2), a(0, 1, 2, 3));
        assertGame(1, a(1, 1, 1, 1), a(1, 0, 0), LOOSE);

        assertGame(1, a(1, 1, 1, 2), a(1, 0, 1), a(0, 1, 2, 3));
        assertGame(1, a(1, 1, 1, 0), a(1, 0, 1), a(3));
        assertGame(1, a(1, 1, 1, 2), a(1, 0, 3), a(3));
        assertGame(1, a(1, 1, 1, 2), a(1, 0, 0), LOOSE);

        assertGame(1, a(1, 1, 2, 3), a(1, 0, 1), a(2, 3));
        assertGame(1, a(1, 1, 2, 3), a(1, 2, 1), a(2));
        assertGame(1, a(1, 1, 2, 2), a(1, 0, 1), a(2, 3));
        assertGame(1, a(1, 1, 2, 2), a(1, 2, 1), LOOSE);

        assertGame(1, a(1, 2, 3, 4), a(1, 1, 1), a(1, 2, 3));
        assertGame(1, a(2, 1, 3, 4), a(1, 0, 1), LOOSE);
        assertGame(1, a(1, 2, 2, 4), a(1, 1, 1), a(1, 2));
        assertGame(1, a(1, 2, 2, 4), a(1, 1, 1), a(1, 2));
        assertGame(1, a(1, 2, 2, 4), a(1, 1, 3), LOOSE);
        assertGame(1, a(1, 2, 2, 2), a(1, 1, 1), LOOSE);

        assertGame(1, a(1, 2, 1, 1), a(0), a(0, 1, 2, 3));
        assertGame(1, a(1, 0, 1, 1), a(0), a(1));
        assertGame(1, a(1, 0, 1, 1), a(0, 0), LOOSE);
        assertGame(1, a(1, 0, 2, 1), a(0), a(1));
        assertGame(1, a(1, 0, 2, 3), a(1), a(1, 2, 3));
        assertGame(1, a(1, 0, 2, 3), a(4), LOOSE);

        assertGame(1, a(1, 1, 1, 2, 3), a(2, 3), LOOSE);
    }

    public void assertGame(int h, int[] board, int[] players, int[] expected) {
        String d = String.format(
                "%d stacks, %d stacks of your color, you have %s, %s",
                board.length,
                count(h, board),
                h == players[0] ? "your color" : "color of " + count(players[0], board) + " other stacks",
                players.length == 1 ? "you last" : count(h, players) == players.length ? "all tail your color" : ""
        );
        int c = Math.max(h, Math.max(Collections.max(toList(board)), Collections.max(toList(players)))) + 1;

        System.out.println(d);
        List<Integer> result = solution.solve(c, h, board, players);
        assertEquals(d + ": ", toList(expected), result);

        for (int t = 0; t < 10000; t++) {
            int[] colorPermutation = permutation(c);
            h = colorPermutation[h];
            permuteValues(board, colorPermutation);
            permuteValues(players, colorPermutation);

            int[] boardPermutation = permutation(board.length);
            int[] newBoard = new int[board.length];
            for (int i = 0; i < board.length; i++) {
                newBoard[boardPermutation[i]] = board[i];
            }
            board = newBoard;

            int[] newExpected = new int[expected.length];
            for (int i = 0; i < expected.length; i++) {
                newExpected[i] = boardPermutation[expected[i]];
            }
            Arrays.sort(newExpected);
            expected = newExpected;

            result = solution.solve(c, h, board, players);
            assertEquals(d + ": ", toList(expected), result);
        }
    }

    private void permuteValues(int[] array, int[] permutation) {
        for (int i = 0; i < array.length; i++) {
            array[i] = permutation[array[i]];
        }
    }

    private int[] permutation(int n) {
        int[] permutation = new int[n];
        for (int i = 0; i < n; i++) {
            int j = random.nextInt(i + 1);
            permutation[i] = permutation[j];
            permutation[j] = i;
        }
        return permutation;
    }

    private int count(int color, int[] board) {
        int yourColor = 0;
        for (int i : board) {
            if (i == color) {
                yourColor++;
            }
        }
        return yourColor;
    }

    List<Integer> toList(int[] values) {
        List<Integer> result = new ArrayList<>();
        for (int value : values) {
            result.add(value);
        }
        return result;
    }
    
    int[] a(int... values) {
        return values.clone();
    }
}
