AI: Forward chaining

Derive everything a set of rules and facts implies.

What to build

A program that runs forward chaining and reports each new fact.

Requirements

  • A rule A B -> C means "if A and B are known, C is known". Make passes over the rules in order, firing every rule whose premises are known and whose conclusion is not; facts derived earlier in a pass can be used later in the same pass.
  • Print derived C for each new fact, then known: and all known facts in alphabetical order (or known: none).

Input

Line 1: r. Then r rules. Last line: the starting facts (possibly empty).

Output

The derived facts, then the known line.

Constraints

r ≤ 100.

Example

Input:

3
A B -> C
C -> D
D E -> F
A B

Output:

derived C
derived D
known: A B C D

Why it works

Each firing adds a fact that must be true, and repeating until nothing changes reaches every fact the rules can produce.

Examples

Example 1 · Input
3
A B -> C
C -> D
D E -> F
A B
Expected output
derived C
derived D
known: A B C D
Example 2 · Input
2
X -> Y
Y -> X

Expected output
known: none

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

Hints

Hint 1

Keep a set of known facts; in each pass, go through the rules in order and fire any rule whose premises are all known and whose conclusion is new.

Hint 2

Stop when a whole pass adds nothing.

Solution

Show one correct solution (try it yourself first)
rules = []
for _ in range(int(input())):
    left, right = input().split("->")
    rules.append((left.split(), right.strip()))
known = set(input().split())
changed = True
while changed:
    changed = False
    for premises, conclusion in rules:
        if conclusion not in known and all(p in known for p in premises):
            known.add(conclusion)
            changed = True
            print("derived", conclusion)
print("known: " + (" ".join(sorted(known)) or "none"))

Lesson: Inference: chaining, resolution and unification →