7.13

Idea. After each throw you may pick any value 1–6, then—if the square reached is the mouth of a chute or the foot of a ladder—you are forced to its other end. Hence a move is a directed edge     i → g(i+k)  for every k∈{1…6}, where g(x) returns the square at the bottom/top of a chute/ladder whose entry is x (or x itself if none). With all edges having equal cost (1 throw) the problem is the single-source shortest-path problem on an unweighted graph; breadth-first search (BFS) yields the answer in O(n) time and O(n) space. Pseudocode (0-based squares for brevity, so finish is n-1):

function min_throws(n, jump): # jump[i] = destination of chute/ladder starting at i, or i dist = array(n, ∞) dist[0] = 0 Q = queue() Q.push(0) while not Q.empty(): v = Q.pop() if v == n-1: return dist[v] # reached last cell for k in 1..6: w = v + k if w < n: w = jump[w] # forced ride on chute/ladder if dist[w] == ∞: dist[w] = dist[v] + 1 Q.push(w) return -1 # unreachable (never happens in a legal board)

Explanation. 1. Pre-compute jump in O(n). 2. BFS scans each square once and inspects up to 6 edges, so total time O(6n)=O(n); the queue and distance array need O(n) memory. 3. When the exit square n-1 is popped, its distance is the minimal number of throws because BFS explores states in increasing throw count. Optional Python snippet (straightforward translation):

from collections import deque def min_throws(n, chutes_ladders): jump = list(range(n)) for a, b in chutes_ladders: # pairs (mouth/base, destination) jump[a-1] = b-1 # convert to 0-based inf = n+1 dist = [inf]*n dist[0] = 0 q = deque([0]) while q: v = q.popleft() if v == n-1: return dist[v] for k in range(1,7): w = v+k if w < n: w = jump[w] if dist[w] == inf: dist[w] = dist[v]+1 q.append(w) return -1

This algorithm outputs the minimum possible number of rigged dice throws required to reach square n.

Back to Chapter 7