Use the defining formula of a Bayesian network.
What to build
A program that computes the probability of a full assignment in a Bayesian network.
Requirements
- Each node line is
NAME PARENTS… : P1 P2 …, giving P(NAME = true) for each combination of parent values, with the first parent changing slowest and true before false. A node with no parents has one probability. - Print
factors:and each node's factor in node order (written with Python'sgformat), thenP = Xwith six decimal places.
Input
Line 1: n. Then n node lines (parents before children). Last line: NAME=T or NAME=F for every node, in any order.
Output
Two lines.
Constraints
n ≤ 10; each node has at most 3 parents.
Example
Input:
4
Cloudy : 0.5
Sprinkler Cloudy : 0.1 0.4
Rain Cloudy : 0.7 0.2
Wet Sprinkler Rain : 0.95 0.9 0.8 0.05
Cloudy=T Sprinkler=F Rain=T Wet=T
Output:
factors: 0.5 0.9 0.7 0.8
P = 0.252000
Why it works
The network says each variable depends only on its parents, so the joint probability is the product of one table entry per node.
Examples
Example 1 · Input
4 Cloudy : 0.5 Sprinkler Cloudy : 0.1 0.4 Rain Cloudy : 0.7 0.2 Wet Sprinkler Rain : 0.95 0.9 0.8 0.05 Cloudy=T Sprinkler=F Rain=T Wet=T
Expected output
factors: 0.5 0.9 0.7 0.8 P = 0.252000
Example 2 · Input
1 Coin : 0.5 Coin=F
Expected output
factors: 0.5 P = 0.500000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each node, find the row of its table for its parents' values; use p if the node is true and 1 − p if false.
Hint 2
Multiply the factors of all nodes in the order the network lists them.
Solution
Show one correct solution (try it yourself first)
import itertools
nodes = []
for _ in range(int(input())):
left, right = input().split(":")
name, *parents = left.split()
probs = list(map(float, right.split()))
combos = list(itertools.product([True, False], repeat=len(parents)))
nodes.append((name, parents, dict(zip(combos, probs))))
world = {k: v == "T" for k, v in (item.split("=") for item in input().split())}
factors = []
for name, parents, table in nodes:
p_true = table[tuple(world[q] for q in parents)]
factors.append(p_true if world[name] else 1 - p_true)
total = 1.0
for f in factors:
total *= f
print("factors: " + " ".join(f"{f:g}" for f in factors))
print(f"P = {total:.6f}")