Use Bayes' rule over and over to track a robot's position.
What to build
A robot on a ring of coloured cells that keeps a probability for every cell, updating it as it senses colours and moves.
Requirements
- The robot starts equally likely to be in any cell.
sense C: the sensor reports C correctly with probability p_hit, so each cell's belief is multiplied by p_hit if the cell's colour is C and by 1 − p_hit otherwise, then normalized.move K: the robot moves exactly K cells to the right, wrapping around. - After all steps, print the beliefs with four decimal places separated by spaces, then
most likely cell: I(from 0; the first of equal maxima).
Input
Line 1: the colours of the cells. Line 2: p_hit. Line 3: k. Then k steps.
Output
Two lines.
Constraints
At most 50 cells and 100 steps; the readings never rule out every cell.
Example
Input:
GRRGG
0.8
1
sense R
Output:
0.0909 0.3636 0.3636 0.0909 0.0909
most likely cell: 1
Why it works
Each reading is evidence weighed by Bayes' rule, and each move shifts the belief with the robot, so after a few steps only the positions that agree with every reading keep much probability.
Examples
GRRGG 0.8 1 sense R
0.0909 0.3636 0.3636 0.0909 0.0909 most likely cell: 1
GRRGG 0.8 2 sense R move 1
0.0909 0.0909 0.3636 0.3636 0.0909 most likely cell: 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sensing: multiply each cell's belief by p_hit if its colour matches the reading, else by 1 − p_hit, then divide by the total.
Hint 2
Moving K cells to the right on a ring: the new belief of cell i is the old belief of cell (i − K) mod n.
Solution
Show one correct solution (try it yourself first)
world = input().strip()
p_hit = float(input())
n = len(world)
belief = [1 / n] * n
for _ in range(int(input())):
action, arg = input().split()
if action == "sense":
belief = [b * (p_hit if world[i] == arg else 1 - p_hit) for i, b in enumerate(belief)]
total = sum(belief)
belief = [b / total for b in belief]
else:
k = int(arg)
belief = [belief[(i - k) % n] for i in range(n)]
print(" ".join(f"{b:.4f}" for b in belief))
print("most likely cell:", belief.index(max(belief)))