The second exercise in this document describes a graph visiting problem combined with dice rolling.

It’s a not very complicated problem, and we could solve it using Breadth First search. The gotcha here is how to identify visited nodes so that we could terminate with great confidence that continuing would be in vain. Attaching an boolean flag to each node is obviously wrong, for it’s possible that reaching the node with a different dice index could probably open the window to a totally different world.

One (straightforward) solution is to combine the dice index with the node to form a new state, then we could do graph visiting on this artificial state space using the ordinary BFS.

Another solution, which I read from other’s code, is less obvious to see its correctness, which makes it more interesting to discuss and ponder. The gist of this algorithm goes like: maintaining the frontier of BFS and visited nodes on each dice roll (iteration), but don’t do any filtering. On reaching the end of the dice list, check if the fixpoint of visited nodes has reached to decide if we should terminate or go on another around of dice roll list.

The algorithm is surely correctly if final node is reachable, for it’s doing BFS. However, why the -1 case works as well is not so obvious (at least to me). Is it possible that next iteration would reach the final node, but the program return -1 prematurely? The key to understand it lies on the cyclic dice list. One property of BFS is that the nodes on the final layer is determined by the sum of steps instead of the order of each step. In other words, starting from the same node, the final nodes are the same regardless the dice roll is [1,2] or [2,1]. If we focus on the last two rounds of dice list before returning -1:

1
2
3
4
5
6
7
8
9
10
11
------------------------- 0
------------------------- 1
...
------------------------- L-1

------------------------- 0
------------------------- 1    <-
...
------------------------- L-1

????????????????????????? 0

where L is the length of dice roll. All nodes in the second part have been visited in previous rounds. Now, we need to prove the ? line doesn’t introduce any new nodes, and this property holds for all future layers. Nodes on ? line are reached from nodes on line <- by going through a whole period of dice roll. We could find the exact same node in previous rounds, apply a whole period (regardless of the starting point in the dice roll), and end up with the nodes that are visited, as assumed that no new nodes are encountered. The same reasoning would go on for all other nodes on line <-, so the line marked as ? introduces no new nodes, so are all future layers, using the same logic.