# (Leetcode) Freedom Trail

I would like to know whether I could make my solution to this challenge shorter and more efficient. Below is the description of the challenge (this is a Leetcode problem) -

In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring", and use the dial to spell a specific keyword in order to open the door.

Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at the 12:00 direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at the 12:00 direction and then by pressing the center button.

At the stage of rotating the ring to spell the key character key[i] -

• You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. The final purpose of the rotation is to align one of the string ring's characters at the 12:00 direction, where this character must equal to the character key[i].

• If the character key[i] has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you've finished all the spelling.

Example -

Input: ring = "godding", key = "gd"
Output: 4

# Explanation:
# For the first key character 'g', since it is already in place, we just need 1 step to spell this character.
# For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo".
# Also, we need 1 more step for spelling.
# So the final output is 4.


Note -

• Length of both ring and key will be in range 1 to 100.

• There are only lowercase letters in both strings and might be some duplicate characters in both strings.

• It's guaranteed that string key could always be spelled by rotating the string ring.

Here is my solution to this challenge -

# Uses dynamic programming

def find_rotate_steps(ring, key):
"""
:type ring: str
:type key: str
:rtype: int
"""
dp = [[min(i, len(ring) - i) for i in range(len(ring))]]
dp.extend([[float('inf')] * len(ring) for _ in range(len(key))])
for i in range(1, len(key) + 1):
for j in range(len(ring)):
if ring[j] != key[i - 1]:
continue
min_step = float('inf')
for k in range(len(ring)):
if dp[i - 1][k] == float('inf'):
continue
step = abs(k - j)
step = min(step, len(ring) - step) + 1 + dp[i - 1][k]
min_step = min(min_step, step)
dp[i][j] = min_step
return min(dp[-1])


Here is the time taken for the example output -

# %timeit find_rotate_steps("godding", "gd")

36.2 µs ± 1.33 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)


Here is my Leetcode result for 302 test cases -

NOTE - Here is what dynamic programming means (according to freeCodeCamp) -

Dynamic programming amounts to breaking down an optimization problem into simpler sub-problems and storing the solution to each sub-problem so that each sub-problem is only solved once.

It was hard to understand, how your code works, so I started by changing variable names to more meaningful form, also unnecessary +1, -1 operation were fixed (i - 1, 1, len(key) + 1, etc):

class Solution:
def findRotateSteps(self, ring, key):
cumulative_lens = [[min(i, len(ring) - i) for i in range(len(ring))]]
cumulative_lens.extend([[float('inf')] * len(ring) for _ in range(len(key))])

for key_num in range(len(key)):
for new_ring_pos in range(len(ring)):
if ring[new_ring_pos] != key[key_num]:
continue

min_sum_len = float('inf')

for prev_ring_pos in range(len(ring)):
prev_ltr_sum_len = cumulative_lens[key_num][prev_ring_pos]

if prev_ltr_sum_len == float('inf'):
continue

clk_w_len = abs(prev_ring_pos - new_ring_pos)
a_clk_len = len(ring) - clk_w_len

new_sum_len = min(clk_w_len, a_clk_len) + prev_ltr_sum_len + 1
min_sum_len = min(min_sum_len, new_sum_len)

cumulative_lens[key_num + 1][new_ring_pos] = min_sum_len

return min(cumulative_lens[-1])


Now, it is possible to read the code like a story. The cause of low performance is how you store and search visited letter lens (cumulative_lens). You keep them in the list, thus you need to iterate through all items to find not inf ones for each key value:

for prev_ring_pos in range(len(ring)):
prev_ltr_sum_len = cumulative_lens[key_num][prev_ring_pos]

if prev_ltr_sum_len == float('inf'):
continue


Example: you have 100 letters in the ring and 10 letters in the key. You found all possible lengths in the ring (there are 3 only) to the first key's letter and move to the second. It will be good to take just needed 3 in the next key's letter processing, not checking others 97 items, which are 'infs'. It can be done by storing ring letters in the dictionary - the Python's hash table structure, like this:

letter_indexes = {
'a' : [first a's index, second a's index],
'c' : [first c's index, second c's index, third c's index],
etc
}


In this case, we can get the list of the needed letter positions by doing letter_indexes[letter], not messing with the others. I wrote my own solution, see it in the end.

Also, I did some refactoring of your code:

• changed multiple len(ring) calls to the ln_ring variable - no performance gain, but more readable.
• changed

for key_num in range(len(key)):
for new_ring_pos in range(len(ring)):
if ring[new_ring_pos] != key[key_num]:


like constructions to more pythonic:

for key_num, key_ltr in enumerate(key):
for new_ring_pos, ring_ltr in enumerate(ring):
if key_ltr != ring_ltr:


Result:

class Solution:
def findRotateSteps(self, ring, key):
ln_ring = len(ring)

cumulative_lens = [[min(i, ln_ring - i) for i in range(ln_ring)]]
cumulative_lens.extend([[float('inf')] * ln_ring for _ in range(len(key))])

for key_num, key_ltr in enumerate(key):
for new_ring_pos, ring_ltr in enumerate(ring):
if key_ltr != ring_ltr:
continue

min_sum_len = float('inf')

for prev_ring_pos, prev_ltr_sum_len in enumerate(cumulative_lens[key_num]):

if prev_ltr_sum_len == float('inf'):
continue

clk_w_len = abs(prev_ring_pos - new_ring_pos)
a_clk_len = ln_ring - clk_w_len

new_sum_len = min(clk_w_len, a_clk_len) + prev_ltr_sum_len + 1
min_sum_len = min(min_sum_len, new_sum_len)

cumulative_lens[key_num + 1][new_ring_pos] = min_sum_len

return min(cumulative_lens[-1])


### My solution:

It works similar to your, but is much faster due to dictionary usage.

class Solution:
def findRotateSteps(self, ring, key):
# the 'prev_ltr' variable should have the start value in the
# beginning, so the '#' character is choosed
# It can be changed to any character different from key's content
# In other words, it is like '-1' item with 0 index.
ltr_indexes = {'#' : [0]}

for idx, ltr in enumerate(ring):
ltr_indexes.setdefault(ltr, []).append(idx)

ln = len(ring)
l_lens = [0] * ln

prev_ltr = '#'
for ltr in key:
for pos in ltr_indexes[ltr]:
all_variants = []

for prev_pos in ltr_indexes[prev_ltr]:
clk_w = abs(prev_pos - pos)
a_clk = ln - clk_w
all_variants.append(min(clk_w, a_clk) + l_lens[prev_pos])

l_lens[pos] = min(all_variants)

prev_ltr = ltr

return min(l_lens[pos] for pos in ltr_indexes[ltr]) + len(key)

• Thanks for your amazing solution! It helped me a lot. +1 – Justin Jun 17 '19 at 15:43