A warehouse robot drives along a dead-end aisle cut into n cells, numbered 0 (the left end) to n - 1 (the right end). Both ends are solid walls. Its belief belief is a list of n probabilities that add up to 1: belief[i] is the probability that it is in cell i.
The robot is told to move, and its motion is described by outcomes, a list of pairs (d, p): with probability p it actually moves d cells (positive to the right, negative to the left, 0 means it stays where it is). The displacements d are all different and the p add up to 1.
The aisle does not wrap round: a move that would take the robot past an end stops it at that end cell, against the wall. So from cell i a displacement d lands in cell i + d, but in cell 0 if i + d < 0 and in cell n - 1 if i + d > n - 1.
Write move_in_aisle(belief, outcomes) that returns the belief after the move, in cell order.
Examples
Input: belief = [0.25, 0.25, 0.25, 0.25, 0, 0], outcomes = [(1, 0.1), (2, 0.8), (3, 0.1)]
Output: [0.0, 0.025, 0.225, 0.25, 0.25, 0.25]
Explanation: from cell 3, a move of 3 would reach cell 6, past the end, so it stops in
cell 5. Cell 5 collects 0.025 + 0.2 + 0.025 = 0.25.
Input: belief = [0.5, 0.5, 0, 0], outcomes = [(-1, 1.0)]
Output: [1.0, 0.0, 0.0, 0.0]
Explanation: backing up one cell from cell 0 leaves the robot against the left wall.
Constraints
- answers are compared with a tolerance of
1e-6; do not round
Goals
- Apply a motion model given as a table of displacements and their probabilities
- Clamp moves that would leave the corridor to the end cell
- See probability pile up against a wall