AI: Check a map colouring

Write the constraint checker that every CSP solver relies on.

What to build

A program that checks whether a colouring of a map breaks any border constraint.

Requirements

  • Each border joins two regions that must have different colours.
  • Print conflict: X and Y are both COLOUR for each border whose two regions share a colour, in the order given, or valid if there are none.

Input

Line 1: b. Then b lines X Y. Last line: the colouring, as REGION=COLOUR items separated by spaces.

Output

The conflicts, or valid.

Constraints

b ≤ 200; every region on a border is coloured.

Example

Input:

3
A B
B C
A C
A=red B=green C=red

Output:

conflict: A and C are both red

Why it works

A solution must satisfy every constraint, so checking each border once tells you whether the colouring is a solution.

Examples

Example 1 · Input
3
A B
B C
A C
A=red B=green C=red
Expected output
conflict: A and C are both red
Example 2 · Input
3
A B
B C
A C
A=red B=green C=blue
Expected output
valid

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

Hints

Hint 1

Store the colours in a dictionary, then look at every border once.

Hint 2

Report the borders in the order they are given.

Solution

Show one correct solution (try it yourself first)
borders = [input().split() for _ in range(int(input()))]
colour = dict(item.split("=") for item in input().split())
conflicts = [f"conflict: {x} and {y} are both {colour[x]}" for x, y in borders if colour[x] == colour[y]]
print("\n".join(conflicts) if conflicts else "valid")

Lesson: Constraint satisfaction problems →