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 Ywith 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 (orX: empty), thenremoved 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))