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 →