This problem asks:

Given: A collection of at most 5 pairs of permutations, all of which have length 10.

Return: The reversal distance between each permutation pair.

Required reading

  1. Permutation reversal
  2. Reversal distance
  3. Synteny blocks
  4. Euna Park’s Master’s Project
  5. A popularization of Park’s thesis

Restate the problem

I need to find the least number of steps required to transform one 10-digit string into another 10-digit string when each step is a reversal of a contiguous subset of the changing string.

The hint given with the challenge is:

“Don’t be afraid to try an ugly solution.”

Solution steps

First, encouraged by the hint about ugly being acceptable, I tried randomly reversing contiguous subset of strings until I stumbled into to the correct order, but that took forever and was never guaranteed to find the shortest path, so I gave up on that quickly as a waste of time.

Then, after failing to come up with an original approach on my own, I went searching online and found Euna Park’s paper, which outlines what she proposes to be an optimal solution to this problem.

Even after reading the paper twice and investing several hours in coding out the algorithm in python, I did not make any substantial progress until I read this article by Matt West.

I wrote my solution while referring to West’s code.