AI: Probability of a complete situation

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's g format), then P = X with 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}")

Lesson: Bayesian networks →