AI: Revise one arc

Perform the basic step of constraint propagation.

What to build

A program that revises the arc (X, Y) for one constraint.

Requirements

  • The constraint is X OP Y with OP one of <, >, =, !=. Remove every value of X that has no value in Y making the constraint true.
  • Print X: and the remaining values in the given order (or X: empty), then removed K.

Input

Line 1: the values of X. Line 2: OP. Line 3: the values of Y.

Output

Two lines.

Constraints

At most 50 values each; whole numbers.

Example

Input:

1 2 3 4
<
2 3

Output:

X: 1 2
removed 2

Why it works

A value of X with no partner in Y can never appear in any solution, so removing it loses nothing.

Examples

Example 1 · Input
1 2 3 4
<
2 3
Expected output
X: 1 2
removed 2
Example 2 · Input
1 2 3
!=
1 2 3
Expected output
X: 1 2 3
removed 0

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

Hints

Hint 1

Keep a value of X if at least one value of Y satisfies the relation with it.

Hint 2

The relation is read as `x OP y`, with x from X and y from Y.

Solution

Show one correct solution (try it yourself first)
xs = list(map(int, input().split()))
op = input().strip()
ys = list(map(int, input().split()))
tests = {"<": lambda a, b: a < b, ">": lambda a, b: a > b, "=": lambda a, b: a == b, "!=": lambda a, b: a != b}
kept = [x for x in xs if any(tests[op](x, y) for y in ys)]
print("X:", " ".join(map(str, kept)) if kept else "empty")
print("removed", len(xs) - len(kept))

Lesson: Constraint propagation and AC-3 →