Computer vision: Classify by the nearest image

The simplest image classifier copies the label of the most similar known image.

What to build

A program that classifies images with the 1-nearest-neighbour rule and the L1 distance.

Requirements

  • Each image is a line of D values. For each test image, find the training image with the smallest L1 distance; on ties, the earliest one.
  • Print LABEL (distance D) for each test image.

Input

Line 1: N and D. Then N lines label v1 … vD. Then M and M lines v1 … vD.

Output

M lines.

Constraints

N, M ≤ 200; D ≤ 400.

Example

Input:

2 4
dark 0 0 10 10
light 200 200 255 255
2
5 5 20 0
190 210 250 255

Output:

dark (distance 30)
light (distance 25)

Why it works

The training image that differs least from the test image, pixel by pixel, is the most similar one, so its label is the best single guess.

Examples

Example 1 · Input
2 4
dark 0 0 10 10
light 200 200 255 255
2
5 5 20 0
190 210 250 255
Expected output
dark (distance 30)
light (distance 25)
Example 2 · Input
3 3
a 1 0 0
b 0 1 0
c 0 0 1
1
0 1 1
Expected output
b (distance 1)

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

Hints

Hint 1

The L1 distance is the sum of |a − b| over matching positions.

Hint 2

Keep the first training image with the smallest distance (use `<`, not `<=`, when comparing).

Solution

Show one correct solution (try it yourself first)
n, d = map(int, input().split())
train = []
for _ in range(n):
    parts = input().split()
    train.append((parts[0], list(map(int, parts[1:]))))
for _ in range(int(input())):
    x = list(map(int, input().split()))
    best = None
    for label, v in train:
        dist = sum(abs(a - b) for a, b in zip(x, v))
        if best is None or dist < best[0]:
            best = (dist, label)
    print(f"{best[1]} (distance {best[0]})")

Lesson: Classifying images with features and nearest neighbours →