# Modified Travelling Salesman Problem

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?

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

• 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. Commented Aug 13 at 10:46
• 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). Commented Aug 13 at 11:01