There’s a special odometer with N (eg 5) digits. Each digit can increment (never decrement, to keep the problem simpler) independently and cyclically, like 8->9->0->1. You can think of them as 5 independent mini-odometers. The starting sequence is input (perhaps something like 07748). Ending sequence can be any other value.
Each increment on any mini-odometer has cost of $1. Find the cheapest way to go from start to end. One simple solution (from me) –increment each digit cyclically to the target value. So a “8” will increment to 9 -> 0 -> 1. Other mini-odometers are not affected by this mini-odometer.
However, 18021 is one of many illegal sequences — barriers.
Key insight — When N==2, this becomes a 2D matrix Tom-n-Jerry problem with barriers. We can simplify the problem to a 3×3 matrix i.e. 2-digit odometer from 00 to 22. Nine possible sequences.
We need to build a graph of nine nodes, which helps answer
- Q: feasible? [2,2] would be unreachable if [1,2] and [2,1] are blocked.
- Q: which path is shortest path
Once we build the graph, shortest path btw 2 graph nodes #binary matrix as illutration will solve it.