Paris Is to France as Rome Is to ...

In a good word embedding, the step from a country to its capital points in roughly the same direction for every country. That makes analogies computable: "a is to b as c is to ?" is answered by the word whose vector is closest to b - a + c.

Write analogy(vectors, a, b, c, k) that returns the k best answers as a list of (word, similarity) pairs, best first:

1. Normalise every vector to length 1 (divide it by its Euclidean length).
2. Compute the target t = b̂ - â + ĉ from the normalised vectors of the three question words.
3. Score every other word w (not a, b or c) by the cosine similarity of t and ŵ, t·ŵ / |t| (or 0.0 if t is all zeros), rounded to 9 decimal places.
4. Sort by score, highest first, breaking ties by the word in alphabetical order, and return the first k.

word_vectors(dim, seed) builds the test vocabularies (twelve countries with their capitals and languages, in dim dimensions); it is available in your code.

Examples

Input:  vectors = {"cat": [1, 0], "kitten": [1, 1], "dog": [0, 1], "puppy": [-1, 1], "car": [1, -1]},
        a = "cat", b = "kitten", c = "dog", k = 2
Output: [("puppy", 0.816496581), ("car", -0.816496581)]
Explanation: with unit vectors the target is [0.7071 - 1 + 0, 0.7071 - 0 + 1] = [-0.2929, 1.7071].

Input:  vectors = word_vectors(12, 1), a = "france", b = "paris", c = "italy", k = 3
Output: [("rome", 0.915419548), ("stockholm", 0.779619456), ("ankara", 0.766061459)]

Constraints

• 3 to 500 words, 2 to 50 dimensions, 1 <= k <= 10; a, b and c are different words
• no vector is all zeros

Goals

• Normalise embedding vectors so that only their directions count
• Answer an analogy by adding and subtracting embeddings
• Search the vocabulary for the nearest word to the result, excluding the question words