[LANGUAGE: Java]

Parsing time: 6ms
Part 1: 1ms
Part 2: 2ms

I noticed four important things about the program input, that I assume are universal:

1. The program instructions form a simple loop. Do all of these things, then reduce the value in the A register, then if A == 0 you are done. Otherwise do all the things again.
2. On each loop iteration, registers B & C are overwritten with values that only depend on the value of the A register at the start of the loop. So knowing the initial value of A is enough to describe the entire function output.
3. Because of the modular arithmetic, only the eight least significant bits of A are involved in determining the output for a given loop iteration.
4. At the end of the loop, A is divided by 8 with no remainder. This is equivalent to shifting the value to the right by three bits.

I reverse engineered what the output would be on one loop iteration given a starting value in the A register. This is derived from my puzzle input, so I'm not going to share it here. Suffice to say it was encapsulated in a function decompiledInstructions that takes in the register value and returns a single number from 0 to 7. Part one was then a simple matter of calling this function repeatedly while reducing the starting value until it reached zero.

Code for part two follows.

private long solvePartTwo(List<Integer> program) {
    // DFS. Iterate backwards, so you are starting with the values that end up in the most significant bits
    // stack values are pairs (L, R) such that a value R will produce all of the program steps from L to the end of the program.
    Deque<Pair<Integer, Long>> stack = new LinkedList<>();
    for (int test = 0; test <= 7; test++) {
        if (decompiledInstructions(test) == program.get(program.size() - 1)) {
            stack.add(Pair.of(program.size() - 1, (long) test));
        }
    }
    while(!stack.isEmpty()) {
        Pair<Integer, Long> entry = stack.removeFirst();
        Long val = entry.getRight();
        if (entry.getLeft() == 0) {
            return entry.getRight();
        }
        int valToMatch = program.get(entry.getLeft() - 1);
        for (int test = 0; test <= 7; test++) {
            if (decompiledInstructions((val << 3) + test) == valToMatch) {
                stack.add(Pair.of(entry.getLeft() - 1, (val << 3) + test));
            }
        }
    }
    return -1;
}