Keep a belief about a hidden state up to date as observations arrive.
What to build
A program that filters a hidden Markov model and prints the belief after every observation.
Requirements
- The prior is the distribution one step before the first observation. Each observation: predict with the transition model, multiply by P(observation | state), normalize.
- Print
day T (OBS):followed bySTATE Ppairs (four decimal places) for each observation.
Input
Line 1: states. Line 2: observation symbols. Then n transition rows, then n sensor rows (one probability per symbol), then the prior, then the observations.
Output
One line per observation.
Constraints
At most 10 states, 10 symbols and 100 observations.
Example
Input:
Rain Dry
U N
0.7 0.3
0.3 0.7
0.9 0.1
0.2 0.8
0.5 0.5
U U
Output:
day 1 (U): Rain 0.8182 Dry 0.1818
day 2 (U): Rain 0.8834 Dry 0.1166
Why it works
Predicting accounts for how the state may have changed, and multiplying by the sensor model weighs each state by how well it explains what was seen.
Examples
Rain Dry U N 0.7 0.3 0.3 0.7 0.9 0.1 0.2 0.8 0.5 0.5 U U
day 1 (U): Rain 0.8182 Dry 0.1818 day 2 (U): Rain 0.8834 Dry 0.1166
Rain Dry U N 0.7 0.3 0.3 0.7 0.9 0.1 0.2 0.8 0.5 0.5 N
day 1 (N): Rain 0.1111 Dry 0.8889
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each observation: predict with the transition rows, multiply by the sensor probability of that observation, then divide by the total.
Hint 2
Start from the prior, which describes the state before the first observation's day.
Solution
Show one correct solution (try it yourself first)
states = input().split()
symbols = input().split()
n = len(states)
T = [list(map(float, input().split())) for _ in range(n)]
E = [dict(zip(symbols, map(float, input().split()))) for _ in range(n)]
belief = list(map(float, input().split()))
for t, obs in enumerate(input().split(), start=1):
predicted = [sum(belief[r] * T[r][s] for r in range(n)) for s in range(n)]
weights = [predicted[s] * E[s][obs] for s in range(n)]
total = sum(weights)
belief = [w / total for w in weights]
print(f"day {t} ({obs}): " + " ".join(f"{s} {b:.4f}" for s, b in zip(states, belief)))