A board game as a graph
Model a dice-and-ladders board as places and moves, then find the fewest rolls to reach the end. About 13 minutes.
Squares and rolls
A dice board is a straight line of squares. From square x, one roll takes you to x + 1 up to x + 6. Some squares have a ladder or a snake: land there and you are moved to a different square straight away.
That's a graph with six roads leaving each square. A road leads either to the square you landed on, or to wherever the ladder or snake sends you. Count each roll as one road, and ladders as free.
for roll in range(1, 7):
nxt = cur + roll- rolls
- 0
Start on square 0. Rolls of 1 to 6 reach squares 1 to 6.
Careful with the rules
Two small things catch people out. A ladder moves you once. If the square it sends you to is itself a ladder, you stay there, because the move only triggers when you land by rolling.
And a roll that would go past the last square is not allowed here, so skip it. Once the search has finished, the answer is the distance of the final square, or -1 if it was never reached.
You roll onto a square holding a ladder, and the ladder's top square holds another ladder. How many ladders do you climb?
- AOne. You only use the ladder at the square you landed on
- BTwo, you keep climbing
- CNone, ladders only work from the start
Show the answer
One. You only use the ladder at the square you landed on. Moves trigger when you land by a roll, not when a ladder drops you.
Fewest rolls
A board has n squares in a line, numbered 0 to n − 1. You start on square 0 and want to reach square n − 1. Each turn you roll a die and move forward 1 to 6 squares (you may choose any roll, and a roll that would go beyond square n − 1 is not allowed). jumps[i] is -1 for an ordinary square. Otherwise landing on square i moves you at once to square jumps[i], and you do not follow a second jump from there. Return the fewest rolls needed to land on the last square, or -1 if it can't be reached. Squares 0 and n − 1 never have a jump.
jumps = [-1, -1, 6, -1, -1, -1, -1, -1, 3, -1] → 2
2 ≤ n ≤ 400 · each jump is -1 or a square number