AI: Where is the robot?

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

Example 1 · Input
GRRGG
0.8
1
sense R
Expected output
0.0909 0.3636 0.3636 0.0909 0.0909
most likely cell: 1
Example 2 · Input
GRRGG
0.8
2
sense R
move 1
Expected output
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)))

Lesson: Probability and Bayes' rule →