I'm not sure I understand, you can still test all the separate steps and parts of the puzzle with this approach. Decomposing calculation of both parts would just mean removing the transitions that modify related values (depth and score for part 1, garbageCount for part 2) from the list of transitions and excluding them from the initial state, to me that is decomposed enough so that the whole thing is not excessively over-engineered beyond the scope of requirements. Both parts depend on the same elements of state: the current character and whether it's in garbage; no point in running two FSM in parallel if their computations overlap that much.

But forgive me if I am speaking above my pay-grade, as this month has proved I seem to do that quite often.