On the Subject of Levenshtein Distance

Close is further than far if you travel by car.

• Two words of length 4–8 will be displayed on the top two displays.
• There are ten buttons with digits that you can use to type in your answer, which will then be displayed on the bottom display. This number cannot have more than two digits.
• There are also three other buttons with the labels “SUB” (used to submit your answer), “CLR” (used to clear the bottom display) and “DEL” (usde to delete the last digit displayed on the bottom display, if there are any).
• Pressing any other button than “SUB” will never issue a strike.
• Pressing the button with the label “SUB” will solve the module if the number displayed on the bottom display is the correct answer.
• The module will always strike if you press the button with the label “SUB” if there is nothing displayed on the bottom display, and if the module has not yet been solved.
• The module does not reset after striking, the correct answer never changes.
• To calculate the correct answer, follow the steps below.

• First, calculate the Levenshtein Distance of the words displayed on the top two displays. Refer to Appendix Levenshtein Distance for instructions. Call the result LD.
• Multiply LD by the number of batteries present on the bomb if there is at least one. Otherwise, multiply LD by 1. You now have X.
• Multiply the number of port types with the number of indicators present on the bomb. Add this product to X to get Y.
• If any digit in the sum of the serial number digits appears in the serial number itself, subtract 1 from Y to get Z.
• The correct answer is Y modulo 100.
  • Modulo by 100 is done by repeatedly adding or subtracting 100 until the number is in the range of 0 to 99 inclusively.
  • You can keep Z for good luck. It is not needed to solve the module.

• However, if the serial number contains the letters L and D, submit the raw LD value. You are spared of all the modifications.

Appendix — Levenshtein Distance

Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.

Calculating Levenshtein Distance using recursion

The Levenshtein Distance between two words can be calculated recursively. You can use the following recursive function to calculate the Levenshtein Distance between the words w₁ and w₂:

• Let’s denote the desired result as LD(w₁, w₂). It is yielded by a function LD(w₁, w₂) that contains the following 4 rules:
  1. If w₁ has no letters, then LD(w₁, w₂) is the number of letters of w₂.
  2. If w₂ has no letters, then LD(w₁, w₂) is the number of letters of w₁.
  3. If the first letters of w₁ and w₂ are the same, LD(w₁, w₂) = LD(v₁, v₂).
  4. Otherwise LD(w₁, w₂) is one more than the minimum of the set.
     • { LD(v₁, w₂); LD(w₁, v₂); LD(v₁, v₂) }.
• In all above statements, v₁ is w₁ without its first letter and v₂ is w₂ without its first letter.

Calculating Levenshtein Distance using dynamic programming

Alternatively, you can use a method of dynamic programming, which uses a matrix to keep track of all known results, thereby eliminating the need for recursion.

Here is an example of a matrix used to calculate LD(“sitting”, “kitten”) following that mentioned method:

		k	i	t	t	e	n
	0	1	2	3	4	5	6
s	1	1	2	3	4	5	6
i	2	2	1	2	3	4	5
t	3	3	2	1	2	3	4
t	4	4	3	2	1	2	3
i	5	5	4	3	2	2	3
n	6	6	5	4	3	3	2
g	7	7	6	5	4	4	3

See the next page for a detailed description of the process.

Let’s have words w₁ and w₂ of lengths m and n respectively. Follow the steps below to calculate LD(w₁, w₂) using the previous notation:

1. Create a matrix of m + 2 rows and n + 2 columns.
2. Starting with the third cell from the top, fill in the leftmost column with w₁, letter by letter going top to bottom.
3. Starting with the third cell from the left, fill in the topmost row with w₂, letter by letter going left to right.
4. Starting with the second cell from the top, fill in the second leftmost column by numbers 0, 1, ..., m going top to bottom.
5. Starting with the third cell from the left, fill in the second topmost row by numbers 1, 2, ..., n left to right.
6. Starting in the cell that is in the intersection of the third column from the left and the third row from the top, do the following:
   • If the letter that is in the same row as this cell is the same as the letter in the same column as this cell, copy into this cell the number from a cell being diagonally adjacent to this cell via its top left corner. Do not add anything.
   • Otherwise find the minimum of the numbers in cells
     • one above this cell,
     • one to the left of this cell,
     • one diagonally adjacent to this cell via its top left corner
     and add one. Copy this result into this cell.
7. Repeat step 6 until you fill the matrix, going left to right, top to bottom.
8. The number in the bottom right corner cell of the matrix is LD(w₁, w₂).

The algorithm described here is demonstrated on the previous page. See the table for w₁ = “sitting” and w₂ = “kitten” showing that LD(“sitting”, “kitten”) = 3.

Note: This whole process can be optimized. For example, it is possible to just use two rows of a matrix at a time to save space.

For more information, see the Wikipedia page.