Which Bird Is Singing?

A garden app records a bird call, measures two numbers, and names the bird. It keeps a library of labelled calls: X_train[i] = [pitch, length] with the species y_train[i].

Write knn_vote(X_train, y_train, queries, k) that returns a list with one species per row of queries, found like this:

1. Order the training calls by their Euclidean distance to the query, nearest first; calls at the same distance are ordered by their index (smaller first). The first k calls in this order are the neighbours (all of them if k is larger than the library).
2. Each neighbour votes for its species. The species with the most votes wins.
3. If several species share the most votes, the winner is the tied species whose first neighbour comes earliest in the order of step 1.

The tests draw calls from bird_calls(n, seed), which returns (X, y) with whole-number rows [pitch in tens of hertz, length in tenths of a second] and species "wren", "robin" or "finch". It is available in your code, so you can look at a library with Run.

Examples

Input:  X_train = [[0, 0], [2, 0], [0, 2], [5, 5], [6, 5]]
        y_train = ["a", "b", "b", "c", "c"]
        queries = [[1, 1], [3, 3]], k = 3
Output: ["b", "b"]
Explanation: [1, 1] is at the same distance from the first three calls, so they are the
neighbours (indices 0, 1, 2) and "b" wins 2 votes to 1. For [3, 3] the order is index 3
(squared distance 8), 1 (10), 2 (10), 4 (13); the first three give "c", "b", "b", so "b" wins.

Input:  the same library, queries = [[3, 3]], k = 4
Output: ["c"]
Explanation: the votes are "c" 2, "b" 2. The first "c" neighbour (index 3) comes before the
first "b" neighbour (index 1), so "c" wins.

Constraints

• 1 <= len(X_train) <= 500, 0 <= len(queries) <= 300, 1 <= k <= 1000
• all rows have the same length (1 to 5) and hold whole numbers

Goals

• Predict a label from a vote among the k most similar training examples
• Order neighbours by distance with a stated tie-break on the index
• Break a tied vote deliberately instead of by accident