Solve an analogy with vectors

"Man is to king as woman is to ...?" Embeddings can answer with arithmetic: king − man + woman.

What to build

A program that answers an analogy by vector arithmetic and nearest-neighbour search.

Requirements

  • For the query a b c, the target is vector(a) − vector(b) + vector(c).
  • Print vector followed by the target's numbers with 2 decimal places.
  • Then print the word (other than a, b and c) with the highest cosine similarity to the target, and that similarity with 3 decimal places; on a tie, the alphabetically first word.

Input

Line 1: n. Then n lines word x1 x2 .... Then a line with the three query words.

Output

Two lines.

Constraints

4 ≤ n ≤ 1000; the target vector is not all zeros.

Example

Input:

5
king 5 1 0
queen 5 4 0
man 1 0 0
woman 1 3 0
apple 0 1 5
king man woman

Output:

vector 5.00 4.00 0.00
queen 1.000

Why it works

If the relation between b and a is a direction in the space, adding that direction to c lands near the word that has the same relation to c.

Examples

Example 1 · Input
5
king 5 1 0
queen 5 4 0
man 1 0 0
woman 1 3 0
apple 0 1 5
king man woman
Expected output
vector 5.00 4.00 0.00
queen 1.000
Example 2 · Input
4
paris 3 1
france 2 1
rome 3 2
italy 2 2
paris france italy
Expected output
vector 3.00 2.00
rome 1.000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Compute the target vector a − b + c, number by number.

Hint 2

Compare the target with every word except a, b and c, by cosine similarity.

Hint 3

On a tie, choose the alphabetically first word.

Solution

Show one correct solution (try it yourself first)
import math

n = int(input())
vectors = {}
for _ in range(n):
    word, *nums = input().split()
    vectors[word] = list(map(float, nums))
a, b, c = input().split()
target = [x - y + z for x, y, z in zip(vectors[a], vectors[b], vectors[c])]


def cosine(u, v):
    dot = sum(x * y for x, y in zip(u, v))
    return dot / (math.sqrt(sum(x * x for x in u)) * math.sqrt(sum(y * y for y in v)))


scores = sorted(((-cosine(target, v), w) for w, v in vectors.items() if w not in (a, b, c)))
print("vector", *[f"{x:.2f}" for x in target])
print(scores[0][1], f"{-scores[0][0]:.3f}")

Lesson: Embeddings and similarity →