The Roll That Would Run Off the Track
A token sits on square 1 of a track of n squares, numbered 1 to n. Some
squares are the start of a jump: landing on square a moves the token straight
to square b, which may be ahead of it or behind it.
The token is moved by a list of k rolls, taken in order. For each roll r:
if the current square plus r is GREATER than n:
the roll is WASTED. The token does not move at all.
otherwise:
the token moves to that square, and then, if that square starts a jump,
it moves once more to the jump's destination and stops there, even if
the destination also starts a jump.
A jump is taken AT MOST ONCE per roll. Chaining is the subject of #2149 and
is deliberately forbidden here. Reaching square n is not special: the token
stays in play, and since every roll is at least 1 every later roll from square
n is wasted.
Print the final square and how many rolls were wasted.
``` n = 10, no jumps, rolls 2 3 4 -> 10 0 1 -> 3 -> 6 -> 10 n = 10, jump 3 -> 8, rolls 2 3 4 -> 8 2
the first roll lands on 3 and jumps to 8; 8 + 3 is 11 and 8 + 4 is 12, so both later rolls are wasted ```
## What most people try first
Moving the token and then pushing it back if it has gone past n. The position
comes out right and the wasted count comes out wrong, because a move that was
undone and a move that never happened are indistinguishable once the move has
been made, and the obvious place to increment the counter is reached in both
cases. Test the destination BEFORE moving, and the two outcomes stay apart.
The other common slip is applying the jump before the bounds test. The bounds test is about the square the roll points at, not about the jump's destination: a jump may legally send the token backwards, and that does not make an overshooting roll legal.
## The rule, as code
for each roll r:
target = pos + r
if target > n:
wasted = wasted + 1
else:
pos = (target starts a jump) ? jumpDestination(target) : target
Holding the jumps as an array dest of n + 1 entries, with dest[s] = s
when s starts no jump, collapses the branch to pos = dest[target] and makes
each roll one array read. That is the second implementation used to verify this
problem; the first keeps the jumps in a hash map and consults it per move.
## Why it is correct
The specification is a sequence of independent single-roll rules, so all that has to hold is that each roll is handled by exactly the stated rule with the state the specification names.
The loop reads pos as it stands before the roll, which is the state after all
earlier rolls and no later ones, so the rules are applied in the listed order.
Within one roll, the overshoot test is evaluated on pos + r before anything
is written, so the wasted case cannot be contaminated by a move. In the moving
case, exactly one jump lookup happens, so the "at most once" clause holds by
construction rather than by a loop that must be stopped.
## The boundary that breaks a careless implementation
pos + r equal to n exactly is a legal move, not an overshoot. The test is
strictly greater than. Writing >= loses the last square entirely, which is
invisible on a track where nothing ever reaches the end and wrong on every
input where something does.
A jump may start at square n itself, so landing on the last square can send
the token back toward the start. One declared test does exactly that.
## Cost
O(n + m) to build the destination array and O(1) per roll, so
O(n + m + k) in total, with O(n) memory.