A cleaning robot rides the lift and gets out on one of several floors, but it does not know which. On every floor the corridor is a ring of cells (after the last cell comes cell 0 again) with a "door" or a "wall" beside each cell; floors[f] is the map of floor f, and floors can have different lengths. Each floor is equally likely before the robot starts, and on whichever floor it is, every cell is equally likely.
The robot then makes the steps, each a pair (u, reading). In each step, in this order:
- Move. The robot is commanded
ucells forward. It actually ends upu - 1,uoru + 1cells further on with probabilitiesp_under,p_exactandp_over(they add up to 1), wrapping round the ring. - Sense. Its sensor reports
reading,"door"or"wall": the true side of its cell with probabilityp_correct, the other one otherwise.
Write which_floor(floors, steps, p_under, p_exact, p_over, p_correct) that returns the list of the probabilities that the robot is on each floor, given all the readings, in the order of floors.
Examples
Input: floors = [["door", "wall", "wall", "wall"], ["door", "wall", "door", "wall"]],
steps = [(1, "door"), (2, "door")],
p_under = 0.1, p_exact = 0.8, p_over = 0.1, p_correct = 0.9
Output: [0.12626263, 0.87373737]
Explanation: before the first reading, "door" has probability
0.25 * 0.9 + 0.75 * 0.1 = 0.3 on floor 0 and 0.5 * 0.9 + 0.5 * 0.1 = 0.5 on floor 1.
After one step the floors stand at 0.3 / 0.8 = 0.375 and 0.625; the second "door"
favours floor 1 even more.
Input: the same floors, steps = [(1, "wall"), (1, "wall"), (1, "wall")], same probabilities
Output: [0.82548309, 0.17451691]
Explanation: three walls in a row fit floor 0's long blank stretch.
Constraints
- answers are compared with a tolerance of
1e-6; do not round
Goals
- Predict the probability of the next reading before it arrives
- Multiply those predictions into the probability of a whole run of readings
- Compare several maps with Bayes' rule, using that probability as their likelihood