AI: Answer questions from a joint distribution

Compute marginal and conditional probabilities by summing a joint table.

What to build

A program that answers probability queries from a full joint distribution of true/false variables.

Requirements

  • The table has one row per combination of values (T or F for each variable, in header order) and its probability. A query is X=v or X=v | Y=w,Z=u (evidence separated by commas).
  • Print each answer with four decimal places, or undefined if the evidence has probability 0.

Input

Line 1: the variable names. Then 2ⁿ rows: values and probability. Then q and q queries.

Output

q lines.

Constraints

At most 4 variables.

Example

Input:

Rain Traffic
T T 0.2
T F 0.1
F T 0.2
F F 0.5
3
Rain=T
Rain=T | Traffic=T
Traffic=F | Rain=F

Output:

0.3000
0.5000
0.7143

Why it works

The joint distribution assigns probability to every complete situation, so any question is a ratio of sums over the matching situations.

Examples

Example 1 · Input
Rain Traffic
T T 0.2
T F 0.1
F T 0.2
F F 0.5
3
Rain=T
Rain=T | Traffic=T
Traffic=F | Rain=F
Expected output
0.3000
0.5000
0.7143
Example 2 · Input
A B C
T T T 0.10
T T F 0.05
T F T 0.15
T F F 0.10
F T T 0.05
F T F 0.20
F F T 0.05
F F F 0.30
4
A=T
A=T | B=T
C=T | A=F,B=F
B=T,C=T
Expected output
0.4000
0.3750
0.1429
0.1500

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Store each row as a dictionary from variable name to True or False, with its probability.

Hint 2

P(query | evidence) = (sum over rows matching both) / (sum over rows matching the evidence).

Solution

Show one correct solution (try it yourself first)
names = input().split()
rows = []
for _ in range(2 ** len(names)):
    *values, p = input().split()
    rows.append(({n: v == "T" for n, v in zip(names, values)}, float(p)))


def parse(text):
    out = {}
    for item in text.split(","):
        if item.strip():
            name, value = item.strip().split("=")
            out[name] = value == "T"
    return out


def total(condition):
    return sum(p for row, p in rows if all(row[k] == v for k, v in condition.items()))


for _ in range(int(input())):
    query, _, evidence = input().partition("|")
    q, e = parse(query), parse(evidence)
    denominator = total(e)
    print("undefined" if denominator == 0 else f"{total({**e, **q}) / denominator:.4f}")

Lesson: Probability and Bayes' rule →