Hide One Fish at a Time

With only a small labelled catch, the biologists do not want to lock part of it away as a test set. Instead they measure the nearest-neighbour rule by hiding one fish at a time: each fish is labelled by its nearest neighbour among all the other fish, and the fraction of fish labelled correctly is recorded.

Write loo_accuracy(X, y) that returns a tuple (train_accuracy, hidden_accuracy):

• train_accuracy: every fish is labelled by the nearest fish in the whole set, itself included;
• hidden_accuracy: every fish i is labelled by the nearest fish j with j != i.

"Nearest" means the smallest Euclidean distance; among equally near fish the one with the smallest index wins. Note that a fish can have an exact duplicate (the same measurements) with a different label.

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

Examples

Input:  X = [[0], [1], [5], [6], [3]], y = ["a", "a", "b", "b", "b"]
Output: (1.0, 0.8)
Explanation: in the whole set every fish is nearest to itself. Hidden, the fish at 3 is
equally near to the fish at 1 (label "a") and the fish at 5 (label "b"); index 1 is
smaller, so it is labelled "a", which is wrong. The other four are right.

Input:  X = [[2, 2], [2, 2], [0, 0]], y = ["x", "y", "y"]
Output: (0.6666666666666666, 0.0)
Explanation: fish 1 is at distance 0 from itself and from fish 0; index 0 wins, so even
in the whole set fish 1 is labelled "x".

Constraints

• 2 <= len(X) <= 400; the rows hold whole numbers and have the same length (1 to 5)

Goals

• See why the nearest-neighbour rule scores (almost) perfectly on its own training data
• Estimate accuracy on unseen data by predicting each example from all the others
• Handle duplicate examples and ties with a precise rule