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 (
TorFfor each variable, in header order) and its probability. A query isX=vorX=v | Y=w,Z=u(evidence separated by commas). - Print each answer with four decimal places, or
undefinedif 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}")