// Return the Manhattan distance between two points.
private static int getDistance(Point a, Point b) {
    return Math.abs(a.x-b.x) + Math.abs(a.y-b.y);
}

// Given a source and destination point, return one of '<', 'v', '^', or '>' characters to indicate
// the direction needed to travel to get from the source to destination point.
private static Character getDirection(Point source, Point dest) {
    if (source.x != dest.x) {
        if (source.x > dest.x) return '^';
        return 'v';
    } else if (source.y != dest.y) {
        if (source.y > dest.y) return '<';
        return '>';
    }

    return '\0';
}

// Given a list of sequences, return a list only containing the sequences with the shortest length.
private static List<String> shortestSequences(List<String> cumulativeSequences) {
    List<String> shortestSequences = new ArrayList<>();

    int min = Integer.MAX_VALUE;

    for (String s : cumulativeSequences) {
        min = Math.min(s.length(), min);
    }

    for (String s : cumulativeSequences) {
        if (s.length() == min)
            shortestSequences.add(s);
    }

    return shortestSequences;
}

// This is a general solver that takes:
// - a given sequence to type
// - a map between a point on a keypad grid and its neighbors
// - a map between a character on a keypad grid and its point
// and generates all possible sequences of directions and button presses it would take to achieve that.
private static List<String> getAllValidButtonPresses(String sequence,
                                                        Map<Point, List<Point>> keypadNeighbors,
                                                        Map<Character, Point> keypadPositions) {
    List<String> cumulativeSequences = new ArrayList<>();

    Point source = keypadPositions.get('A');

    // For each character in the sequence
    for (int i = 0; i < sequence.length(); i++) {
        // Stores each intermediate sequence
        List<String> sequencesFromSourceToDest = new ArrayList<>();

        Point destination = keypadPositions.get(sequence.charAt(i)); // Find where am I trying to go
        int distance = getDistance(source, destination); // The length of the optimal sequence

        Queue<KeypadState> queue = new LinkedList<>();
        Set<Point> visited = new HashSet<>();
        queue.add(new KeypadState(source, ""));

        // We run a BFS through the grid where each state is a point on the grid and the sequence of button presses
        // it would take to get there.
        while (!queue.isEmpty()) {
            KeypadState keypadState = queue.poll();
            Point currPoint = keypadState.point();

            // If we've found our destination, add that as a possible sequence and keep searching.
            // (not forgetting to actually push the button too)
            if (currPoint.equals(destination)) {
                sequencesFromSourceToDest.add(keypadState.sequence() + 'A');
                continue;
            }

            visited.add(currPoint);

            List<Point> neighbors = keypadNeighbors.get(currPoint);

            for (Point neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    // The new sequence is how we got here so far plus the direction it takes to get to this neighbor.
                    String updatedSequence = keypadState.sequence() + getDirection(currPoint, neighbor);

                    // We don't want to consider sequences longer than necessary
                    if (updatedSequence.length() <= distance) {
                        queue.add(new KeypadState(neighbor, updatedSequence));
                    }
                }
            }
        }

        // At this point, the BFS has finished so we want to accumulate our intermediate sequences
        // into a cumulative sequence.
        List<String> newCumulativeSequences = new ArrayList<>();
        if (cumulativeSequences.isEmpty()) {
            // For the first character, we've just found the starting sequences.
            cumulativeSequences.addAll(sequencesFromSourceToDest);
        } else {
            // For getting to subsequent characters, we need to append the
            // intermediate sequence found with each sequence generated so far.
            for (String sequenceSoFar : cumulativeSequences) {
                for (String intermediate : sequencesFromSourceToDest) {
                    String combined = sequenceSoFar + intermediate;
                    newCumulativeSequences.add(combined);
                }
            }
            cumulativeSequences = newCumulativeSequences;
        }

        // Don't forget to update our new starting point
        source = destination;
    }

    // Only keep the sequences that are the shortest.
    return shortestSequences(cumulativeSequences);
}

// Part 1: Iterate through each door pad code and work backwards, finding all the sequences it would take
// the first robot to type on the number pad and from that, all the sequences it would take the second robot
// to type on the directional pad, and so on. Filter down to only the shortest sequences
// and return the complexity sum.
private static int part1() {
    int sum = 0;

    // Iterate through each code.
    for (String code : codes) {
        // Get all the possible sequences for the first robot to type on the number pad.
        List<String> firstLevelAbstraction = getAllValidButtonPresses(code, numpadMap, numpadPositions);

        List<String> secondLevelAbstraction = new ArrayList<>();

        // For each possible sequence that the first robot generated, get all the possible sequences
        // for the second robot to type on the directional pad.
        for (String first : firstLevelAbstraction) {
            secondLevelAbstraction.addAll(getAllValidButtonPresses(first, dirpadMap, dirpadPositions));
        }

        // Only keep the shortest sequences.
        secondLevelAbstraction = shortestSequences(secondLevelAbstraction);

        List<String> thirdLevelAbstraction = new ArrayList<>();

        // For each possible sequence that the second robot generated, get all the possible sequences
        // for the third robot to type on the directional pad.
        for (String second : secondLevelAbstraction) {
            thirdLevelAbstraction.addAll(getAllValidButtonPresses(second, dirpadMap, dirpadPositions));
        }

        // Only keep the shortest sequences.
        thirdLevelAbstraction = shortestSequences(thirdLevelAbstraction);

        // Calculate complexity
        int numeric = Integer.parseInt(code.substring(0, code.length()-1));
        int shortestLength = thirdLevelAbstraction.get(0).length();

        sum += numeric * shortestLength;
    }

    return sum;
}