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 -> Cmeans "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 Cfor each new fact, thenknown:and all known facts in alphabetical order (orknown: 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"))