Remember Only the Fish That Teach Something

A nearest-neighbour model on a small sensor chip cannot store the whole labelled catch. Most fish in the middle of their species' group are never the nearest neighbour that matters, so the chip keeps a store: a subset of the training indices, built like this.

1. The store starts with example 0 only.
2. Make a pass over the examples i = 0, 1, ..., n - 1. Skip i if it is already in the store. Otherwise predict its label with the nearest-neighbour rule using only the stored examples (the smallest Euclidean distance; among equally near stored examples, the smallest index). If the prediction is wrong, add i to the store immediately, so the rest of this pass already uses it.
3. Repeat passes until a whole pass adds nothing.

Write condense(X, y) that returns the store as a sorted list of indices.

The tests use fish_catch(n, seed), which returns (X, y); it is available in your code.

Examples

Input:  X = [[0], [1], [2], [10], [11], [3], [9]], y = ["a", "a", "a", "b", "b", "a", "b"]
Output: [0, 3]
Explanation: 1 and 2 are labelled "a" by example 0. Example 3 (at 10) is labelled "a",
wrongly, and joins the store. From then on every example is right; a second pass adds nothing.

Input:  X = [[0], [3], [6], [2]], y = ["a", "a", "b", "b"]
Output: [0, 1, 2, 3]
Explanation: in the first pass example 1 is right (nearest stored is 0), 2 and 3 are wrong and
are added. In the second pass example 1 is nearest to the stored example 3 ("b"), so it is added.

Constraints

• 1 <= len(X) <= 800; rows hold whole numbers and have the same length (1 to 5)
• labels are strings or whole numbers

Goals

• Shrink a nearest-neighbour model while keeping its training predictions right
• Simulate a procedure whose state changes during a pass, exactly as specified
• See that most training examples are redundant for the nearest-neighbour rule