8
$\begingroup$

Serghei left a note:

R
C  +3
C  +4
A  +5
B  +4
H  +4
D  +4
G  +4
F  +5
I  +3
P  +3
F  +5
G  +3
S  +5
S  +4
I  +4
M  +4
L  +4
E  +4
S  +4
S  +2
L  +6
N  +7
L +10
B  +8
C  +6
P  +7
-----
= 122

This is the best I can come up with!

Not sure what's wrong with him, this route is all over the place, and it would take way too long...

What does the note mean & how are the numbers calculated?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Serghei's route is ...

... an optimal route through all 27 countries of the European Union that tries to minimize the travelled distance. In other words, his route solves the travelling salesman problem.

The "distance" isn't any physical distance, for example the distance between the capitals. It is the Damerau-Levenshtein distance, a common editing distance that measures how "far away" two words are. Such metrics are used when suggesting "near" alternatives to mistyped words. Here, it is applied to the names of the countries, whose first letters are given in Serghei's list.

Each deletion, insertion, substitution or swapping of adjacent letters adds one to the distance. For example, the route starts in Romania and then visits Croatia:

    • insert a C (+1).
    • keep the RO.
    • delete the M (+1).
    • keep the A.
    • substitute the N for a T (+1).
    • keep the IA.

The editing distance between "Romania" and "Croatia" is 3.

The whole path:

Romania → Croatia: 4
Croatia → Czechia: 4
Czechia → Austria: 5
Austria → Bulgaria: 4
Bulgaria → Hungary: 4
Hungary → Denmark: 4
Denmark → Germany: 4
Germany → Finland: 5
Finland → Ireland: 3
Ireland → Poland: 3
Poland → France: 5
France → Greece: 3
Greece → Sweden: 5
Sweden → Spain: 4
Spain → Italy: 4
Italy → Malta: 4
Malta → Latvia: 4
Latvia → Estonia: 4
Estonia → Slovenia: 5
Slovenia → Slovakia: 2
Slovakia → Lithuania: 6
Lithuania → Netherlands: 7
Netherlands → Luxembourg: 10
Luxembourg → Belgium: 8
Belgium → Cyprus: 6
Cyprus → Portugal: 7

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nice, this is of course correct! As a side note I used the classical Levenshtein distance in the creation of this puzzle (insertions/deletions/subs only), not sure if it even makes a difference for these words. $\endgroup$
    – Lukas Rotter
    Commented Aug 13 at 10:46
  • $\begingroup$ The classical Levenshtein distance was my first idea, too, but some things didn't work out when I tried out things, so I toggled the extra swaps check in and out. It doesn't make a difference for this puzzle though. By the way, my earliest idea was this. My next idea was that rot13(Freturv jnf Yniebi naq gung ur ivfvgrq fbzr sbervta pbhagevrf, fb gung gur fgnegvat cbvag E jbhyq or Ehffvn, bs pbhefr). $\endgroup$
    – M Oehm
    Commented Aug 13 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.