import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

class Gamestate {
    // P1: current score of P1
    // P2: current score of P2
    // lastTaken: amount of coins taken during last move
    // P1touched: boolean list, which stacks has P1 interacted with
    // P2touched: boolean list, which stacks has P2 interacted with
    // coins: integer list of coins left on stacks
    // turn: either "P1" or "P2"
    // next: list of Gamestates

    private int P1;
    private int P2;
    private int lastTaken;
    private LinkedList<Boolean> P1touched; // we can't use primitive types like "boolean" in LinkedList
    private LinkedList<Boolean> P2touched;
    private LinkedList<Integer> coins;
    private String turn;
    private LinkedList<Gamestate> next;

    // creates initial game start node
    // it was makeInitState
    Gamestate(LinkedList<Integer> coins) {
        this.P1 = 0;
        this.P2 = 0;
        this.lastTaken = 0;
        this.P1touched = new LinkedList<>();
        this.P2touched = new LinkedList<>();
        this.coins = coins;
        this.turn = "P1";
        this.next = new LinkedList<>();

        for (int i = 0; i < coins.size(); i++) {
            P1touched.add(Boolean.FALSE);
            P2touched.add(Boolean.FALSE);
        }
    }

    // i removed parent since you weren't using it
    public Gamestate(int P1, int P2, String turn, int lastTaken, LinkedList<Boolean> P1touched, LinkedList<Boolean> P2touched, LinkedList<Integer> coins) {
        this.P1 = P1;
        this.P2 = P2;
        this.lastTaken = lastTaken;
        this.P1touched = P1touched;
        this.P2touched = P2touched;
        this.coins = coins;
        this.turn = turn;
        this.next = new LinkedList<>();
    }

    static Gamestate minmaxTree(Gamestate tree) {
        // if leaf, return self
        if (tree.next.size() == 0) {
            return tree;
        }
        // if not leaf, agregate minmaxTree results from all possible moves
        LinkedList<Gamestate> choices = new LinkedList<>();
        for (Gamestate move : tree.next) {
            choices.add(minmaxTree(move));
        }

        // if P1 choose best minmax for P1 from choices
        Gamestate result;
        if (tree.turn.equals("P1")) {
            result = Collections.max(choices, Comparator.comparing(g -> (g.P1 - g.P2)));
        }
        // if P2 choose worst minmax for P1 from choices
        else {
            result = Collections.min(choices, Comparator.comparing(g -> (g.P1 - g.P2)));
        }
        return result;
    }

    // it overrides toString method in Object (parent of every object)
    public String toString() {
        return "P1:" + P1 + ", P2:" + P2 + ", coins" + coins.toString();
    }

    // turns whole tree into string with indents
    static String strFromTree(Gamestate tree, int depth) {
        // StringBuilder is faster than String when object is frequently modified
        // Strings are immutable which means that whenever we're adding some new letters to existing String, program will have to create new object and delete existing one
        StringBuilder s = new StringBuilder();

        for (int i=0; i<depth; i++){
            s.append(" ");
        }

        s.append(tree.toString()).append("\n");
        for (Gamestate subtree : tree.next) {
            s.append(strFromTree(subtree, depth + 1));
        }
        return s.toString();
    }

    String nextTurn() {
        if (turn.equals("P1")) // == is for checking address comparison, .equals(...) is for content comparison
        {
            return "P2";
        } else {
            return "P1";
        }
    }

    // return list with possible amounts of coins to take from given stack
    LinkedList<Integer> possibleTakes(int stack_num) {
        LinkedList<Integer> result = new LinkedList<>();
        if (coins.get(stack_num) == 0) {
            return result;
        }
        if (lastTaken == 0 && coins.get(stack_num) >= 1) {
            result.add(1);
            return result;
        }
        int j = 1;
        while (j <= coins.get(stack_num) && j <= lastTaken * 2) {
            result.add(j);
            j++;
        }
        return result;
    }

    void addSubstates(LinkedList<Gamestate> substates) {
        next.addAll(substates);
    }

    // creates all valid moves
    void genPossibleSubstates() {
        LinkedList<Gamestate> result = new LinkedList<>();
        int n = coins.size();

        String currMove = turn;
        String nextMove = nextTurn();

        // consider which stacks can current player interact with
        LinkedList<Boolean> consideredTouches;
        if (currMove.equals("P1")) {
            consideredTouches = new LinkedList<>(P1touched); // this constructor will copy list
        } else {
            consideredTouches = new LinkedList<>(P2touched);
        }

        boolean madeMove = false;
        for (int i = 0; i < n; i++) {
            // if stack touched, skip
            if (consideredTouches.get(i) == Boolean.TRUE) {
                continue;
            }

            LinkedList<Integer> takes = possibleTakes(i);

            // many lines were duplicated and i have removed them
            // for each stack player can interact with, generate branch for each possible amount taken
            for (Integer takevalue : takes) {
                LinkedList<Boolean> newTouchP1 = new LinkedList<>(P1touched);
                LinkedList<Boolean> newTouchP2 = new LinkedList<>(P2touched);
                LinkedList<Integer> newCoin = new LinkedList<>(coins);
                newCoin.set(i, newCoin.get(i) - takevalue);
                int newP1 = P1;
                int newP2 = P2;
                madeMove = true;

                if (currMove.equals("P1")) {
                    newTouchP1.set(i, Boolean.TRUE);
                    newP1 += takevalue;
                } else {
                    newTouchP2.set(i, Boolean.TRUE);
                    newP2 += takevalue;
                }
                result.add(new Gamestate(newP1, newP2, nextMove, takevalue, newTouchP1, newTouchP2, newCoin));
            }
        }

        // if moves couldn't be generated for current player, check if there exist any valid moves
        if (!madeMove) {
            boolean gameOver = true;
            for (int i = 0; i < coins.size(); i++) {
                if (coins.get(i) != 0 && (!P1touched.get(i) || !P2touched.get(i))) {
                    gameOver = false;
                    break;
                }
            }
            if (!gameOver) {
                result.add(new Gamestate(P1, P2, nextMove, lastTaken,
                        new LinkedList<>(P1touched), new LinkedList<>(P2touched), new LinkedList<>(coins)));
            }
        }
        addSubstates(result);
    }

    void makeTree() {
        genPossibleSubstates();
        for (Gamestate gamestate : next) {
            gamestate.makeTree();
        }
    }
}

// there can be only one public class in java file and it has to match filename
//public class Coins {
//    public static void main(String[] args) {
//        LinkedList<Integer> coins;
//        Gamestate gameTree;
//        Gamestate result;
//
//        // ========================
//        coins = new LinkedList<>();
//        coins.add(2);
//        coins.add(2);
//        coins.add(2); // it would look better as an array instead of list but in Python everything is list so i made it that way
//        gameTree = new Gamestate(coins);
//        gameTree.makeTree();
//        result = Gamestate.minmaxTree(gameTree);
//
//        System.out.println(Gamestate.strFromTree(gameTree, 0));
//
//        System.out.println("===========");
//        System.out.println("game: " + coins.toString());
//        System.out.println("minmax game outcome:");
//        System.out.println(result.toString());
//        System.out.println("----------");
//
//        // ========================
//        coins = new LinkedList<>();
//        coins.add(3);
//        coins.add(3);
//        coins.add(3);
//        gameTree = new Gamestate(coins);
//        gameTree.makeTree();
//
//        result = Gamestate.minmaxTree(gameTree);
//
//        System.out.println("===========");
//        System.out.println("game: " + coins.toString());
//        System.out.println("minmax game outcome:");
//        System.out.println(result.toString());
//        System.out.println("----------");
//
//        // ========================
//        coins = new LinkedList<>();
//        coins.add(1);
//        coins.add(2);
//        coins.add(6);
//        gameTree = new Gamestate(coins);
//        gameTree.makeTree();
//
//        result = Gamestate.minmaxTree(gameTree);
//
//        System.out.println("===========");
//        System.out.println("game: " + coins.toString());
//        System.out.println("minmax game outcome:");
//        System.out.println(result.toString());
//        System.out.println("----------");
//    }
//}