Non-optimal solution for LeetCode Cat and Mouse problem

Solution.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Stack;
import java.util.stream.IntStream;

class Solution {

    static boolean DEBUG = false;

    static final int POSITION_HOLE = 0;
    static final int POSITION_MOUSE_START = 1;
    static final int POSITION_CAT_START = 2;

    static final int MOUSE_WIN = 1;
    static final int CAT_WIN = 2;
    static final int DRAW = 0;

    int catMouseGame(int[][] graph) {
        // check graph validity
        // (mostly to validate our assumptions about the graph that are left un-clarified)
        for (int[] moves: graph) {
            // each node must have a path out
            assert moves.length > 0;
            // there may not be any duplicate values
            final HashSet<Integer> options = IntStream.of(moves)
                    .collect(HashSet::new, HashSet::add, HashSet::addAll);
            assert options.size() == moves.length;

        }
        return getResult(
                new State(true, POSITION_MOUSE_START, POSITION_CAT_START),
                new Stack<>(),
                graph,
                new HashMap<>()
        );
    }

    /**
     * Caches known win results for getResultHelper().
     * We cannot cache DRAW results because the DRAW test depends on the
     * ancestors when a given state is seen, which can be different each time we see the same
     * state.
     */
    static int getResult(
            final State state,
            final Stack<State> previousStates,
            final int[][] graph,
            final Map<State, Integer> resultsCache
    ) {
        final Integer cachedResult = resultsCache.get(state);
        if (cachedResult != null) {
            print(previousStates.size(), "[cache] %s => %d", state, cachedResult);
            return cachedResult;
        }
        print(previousStates.size(), "[compute] %s", state);
        final int result = getResultHelper(state, previousStates, graph, resultsCache);
        print(previousStates.size() + 1, "=> %d", result);
        // NOTE: If we allow caching of DRAW results (which would be incorrect)
        // we get 44/49 test cases. The remaining 5 test cases most likely trigger the condition where
        // it would incorrrectly report a DRAW where the ancestors for a given state are different than the
        // ancestors when state which resulted in the cached DRAW.
        // I've verified not caching DRAW results in the correct solution for at least 1 of those
        // test cases, so I'm fairly certain this solution is now correct, just inefficient.
        if (result != DRAW) {
            resultsCache.put(state, result);
        }
        return result;
    }

    /**
     * Recursively checks each possible move path from the given state, determining the 
     * result for each possible sub-path (DRAW, MOUSE_WIN, or CAT_WIN), and rolling the
     * result back up the tree.
     */
    static int getResultHelper(
            final State state,
            final Stack<State> previousStates,
            final int[][] graph,
            final Map<State, Integer> resultsCache
    ) {
        // check base cases
        if (state.isMouseAtHole()) {
            return MOUSE_WIN;
        } else if (state.isMouseCaughtByCat()) {
            return CAT_WIN;
        } else if (state.isDraw(previousStates)) {
            return DRAW;
        }
        
        previousStates.push(state);
        
        // graph[i] gives a list of nodes it's connected to, therefore the list of potential moves
        final int[] potentialMoves = graph[state.currentPlayerPos()];
        
        // Assume that the current player loses this path if we don't see a DRAW or a win for
        // the current player on a child path.
        int result = state.mouseTurn ? CAT_WIN : MOUSE_WIN;
        
        for (final int move: potentialMoves) {

            // cat cannot enter hole
            if (!state.mouseTurn && move == POSITION_HOLE) {
                // it would be invalid for the cat to be able to reach a point where
                // the only option is the hole
                assert potentialMoves.length > 1;
                continue;
            }

            // recursively find the result if we choose this path
            final int moveResult = getResult(
                    state.moveTo(move),
                    previousStates,
                    graph,
                    resultsCache
            );

            // If any child path results in a DRAW we're at least guarenteed not to lose,
            // but must continue to check to see if we win.
            if (moveResult == DRAW) {
                result = DRAW;
            }
            // If a child path results in a win for the current player, this path is
            // guarenteed to win, and we can stop checking other children.
            else if (state.mouseTurn && moveResult == MOUSE_WIN) {
                result = MOUSE_WIN;
                break;
            } else if (!state.mouseTurn && moveResult == CAT_WIN) {
                result = CAT_WIN;
                break;
            }
        }
        previousStates.pop();
        return result;
    }

    static class State {

        final boolean mouseTurn;
        final int mousePos;
        final int catPos;

        State(
                final boolean mouseTurn,
                final int mousePos,
                final int catPos
        ) {
            this.mouseTurn = mouseTurn;
            this.mousePos = mousePos;
            this.catPos = catPos;
        }

        boolean isMouseAtHole() {
            return mousePos == POSITION_HOLE;
        }

        boolean isMouseCaughtByCat() {
            return catPos == mousePos;
        }

        boolean isDraw(final Iterable<State> previousStates) {
            // A path is considered a DRAW when the current state has previously been seen
            // in this same path, i.e. a cycle has been encountered.
            for (final State state: previousStates) {
                if (equals(state)) {
                    return true;
                }
            }
            return false;
        }

        @Override
        public boolean equals(final Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            final State state = (State) o;
            return mouseTurn == state.mouseTurn &&
                    mousePos == state.mousePos &&
                    catPos == state.catPos;
        }

        @Override
        public int hashCode() {
            return Objects.hash(mouseTurn, mousePos, catPos);
        }

        int currentPlayerPos() {
            if (mouseTurn) {
                return mousePos;
            } else {
                return catPos;
            }
        }

        State moveTo(final int newPos) {
            if (mouseTurn) {
                return new State(false, newPos, catPos);
            } else {
                return new State(true, mousePos, newPos);
            }
        }

        @Override
        public String toString() {
            return "(" + (mouseTurn ? "mouse, ": "cat, ") + mousePos + ", " + catPos + ")";
        }
    }

    static void print(int depth, String str, Object... args) {
        if (!DEBUG) {
            return;
        }
        final StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("|  ");
        }
        sb.append(String.format(str, args));
        System.out.println(sb.toString());
    }
}