Memorizer against a simple rule

Reproduce the lesson's experiment on any data: a model that memorizes against a one-number rule, on training and on test data.

What to build

A program that trains both models on the training data and reports their accuracy on both sets.

Requirements

  • Memorizer: the label of the training example whose value is closest; ties go to the one listed first.
  • Rule: predict 1 when value ≥ C, with C learned on the training data (most training examples right; ties go to the smallest C).
  • Print memorizer: train A, test B and rule (value >= C): train D, test E, accuracies with 3 decimal places.

Input

Line 1: training values (integers). Line 2: their labels (0 or 1). Line 3: test values (numbers). Line 4: their labels.

Output

Two lines.

Constraints

Each set has 1 to 500 examples.

Example

Input:

1 2 3 4 5 6
0 0 1 0 1 1
2.6 3.4 4.6 1
0 0 1 0

Output:

memorizer: train 1.000, test 0.500
rule (value >= 3): train 0.833, test 0.750

Why it works

The memorizer scores perfectly on distinct training values because each one is its own nearest neighbour, which says nothing about new data; the rule must generalize, so its test score is the honest comparison.

Examples

Example 1 · Input
1 2 3 4 5 6
0 0 1 0 1 1
2.6 3.4 4.6 1
0 0 1 0
Expected output
memorizer: train 1.000, test 0.500
rule (value >= 3): train 0.833, test 0.750
Example 2 · Input
1 10
0 1
4 6
0 1
Expected output
memorizer: train 1.000, test 1.000
rule (value >= 10): train 1.000, test 0.500

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

Hints

Hint 1

The memorizer predicts the label of the nearest training value; on equal distances, the earlier training example wins.

Hint 2

Train the rule as in "Learn the best cut-off": candidates are the different training values in increasing order, then the largest plus 1; keep the smallest best one.

Hint 3

Accuracy is the number right divided by the number of examples, printed with 3 decimals.

Solution

Show one correct solution (try it yourself first)
train_x = list(map(int, input().split()))
train_y = list(map(int, input().split()))
test_x = list(map(float, input().split()))
test_y = list(map(int, input().split()))


def memorizer(v):
    best = 0
    for i in range(len(train_x)):
        if abs(train_x[i] - v) < abs(train_x[best] - v):
            best = i
    return train_y[best]


best_cutoff, best_correct = None, -1
for cutoff in sorted(set(train_x)) + [max(train_x) + 1]:
    correct = sum(1 for v, y in zip(train_x, train_y) if (v >= cutoff) == (y == 1))
    if correct > best_correct:
        best_cutoff, best_correct = cutoff, correct


def rule(v):
    return 1 if v >= best_cutoff else 0


def accuracy(model, xs, ys):
    return sum(1 for v, y in zip(xs, ys) if model(v) == y) / len(xs)


print(f"memorizer: train {accuracy(memorizer, train_x, train_y):.3f}, test {accuracy(memorizer, test_x, test_y):.3f}")
print(f"rule (value >= {best_cutoff}): train {accuracy(rule, train_x, train_y):.3f}, test {accuracy(rule, test_x, test_y):.3f}")

Lesson: Training, testing and overfitting →