Decide independence without a single number, just by reading the graph.
What to build
A program that decides whether two variables are d-separated by a set of observed variables.
Requirements
- The network is given by its arrows. A path between X and Y is active if every node on it is either a non-collider that is not observed, or a collider (both arrows point into it) that is observed or has an observed descendant. X and Y are independent given the evidence exactly when no path is active.
- Print
independentordependent.
Input
Line 1: e. Then e arrows A B (A → B). Last line: X Y or X Y | Z….
Output
One line.
Constraints
At most 30 nodes; the graph has no cycles; X and Y are not observed.
Example
Input:
4
C S
C R
S W
R W
S R
Output:
dependent
Why it works
Information flows along a path through causes and effects unless an observed middle node blocks it, while a common effect connects its causes only once it, or something it causes, is observed.
Examples
4 C S C R S W R W S R
dependent
4 C S C R S W R W S R | C
independent
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Search over (node, direction) pairs: arriving from a child (going up) or from a parent (going down), as in the Bayes-ball algorithm.
Hint 2
A collider passes the search only if it or one of its descendants is observed; any other node passes only if it is not observed.
Solution
Show one correct solution (try it yourself first)
from collections import deque
parents, children = {}, {}
for _ in range(int(input())):
a, b = input().split()
children.setdefault(a, []).append(b)
parents.setdefault(b, []).append(a)
children.setdefault(b, [])
parents.setdefault(a, [])
pair, _, rest = input().partition("|")
x, y = pair.split()
observed = set(rest.split())
# nodes that are observed or have an observed descendant
opens_collider = set()
todo = list(observed)
while todo:
node = todo.pop()
if node not in opens_collider:
opens_collider.add(node)
todo.extend(parents.get(node, []))
seen = set()
queue = deque([(x, "up")])
reached = set()
while queue:
node, direction = queue.popleft()
if (node, direction) in seen:
continue
seen.add((node, direction))
if node not in observed:
reached.add(node)
if direction == "up" and node not in observed:
queue.extend((p, "up") for p in parents.get(node, []))
queue.extend((c, "down") for c in children.get(node, []))
elif direction == "down":
if node not in observed:
queue.extend((c, "down") for c in children.get(node, []))
if node in opens_collider:
queue.extend((p, "up") for p in parents.get(node, []))
print("dependent" if y in reached else "independent")