Play Freedom Trail with DP

The cover image of this article is from a mission storyline in a game called "Fallout 4":

This rotating disk resembles a combination lock. Notice the red pointer slightly above the center. By rotating the disk, you can align the pointer with different letters and then press the central button to input the selected letter.

To trigger the mechanism and open the adjacent door, you need to rotate the disk so the pointer successively points to R, A, I, L, R, O, A, D, pressing the button each time.

The reason these specific letters form the password is hinted at in the game's storyline, which we won't delve into here.

So, what does this game scenario have to do with dynamic programming?

Let's think about it a bit: inputting these letters by rotating the disk can be cumbersome. In what sequence should you rotate the disk to minimize the number of moves required?

The number of moves required will vary depending on the method used to rotate the disk.

For instance, to align a letter with the pointer, you can rotate the disk clockwise or counterclockwise. Some letters may appear more than once, such as the uppercase letter O in the image, which appears three times at different positions on the disk. Which O should you align with to minimize the total number of moves?

As we've mentioned several times before, problems that ask for the optimal solution are typically solved using dynamic programming, as it is a type of optimization algorithm.

There's a problem on LeetCode based on this disk game, and it's rated Hard. However, I solved it quickly because I had previously considered a very interesting real-life example that can be compared to this problem. Let's briefly introduce it below.

I once practiced several piano pieces by Liszt and Chopin. Readers who haven't played the piano might not know that practicing piano scores requires determining the "fingerings" in advance.

The notes on the staff go up and down, and the fingers of both hands must coordinate with each other. This means you must decide which finger of which hand to use for each note and write it on the score.

For example, a piece I really like is called "Liebestraum," and here is the score from when I was a beginner:

The number 1 on the notes represents the thumb, 2 represents the index finger, and so on. By practicing according to the determined fingerings, you develop muscle memory and eventually master a piece.

Fingerings vary from person to person. For instance, those with larger hands might be able to cross their middle finger over their thumb, while those with smaller hands might find this awkward. Thus, the fingerings for the same piece might differ.

So the question arises: How should I design the fingerings to minimize the "awkwardness" of finger transitions, thereby maximizing the smoothness of the performance?

Here, I employed dynamic programming techniques: aren't finger transitions just state transitions? Referring to the earlier article Detailed Explanation of Dynamic Programming, we can solve this problem by clearly defining "states" and "choices."

What is a state? A state is "the next note to be played" and "the current state of the hand."

The next note to be played is simply one of the 88 keys on the piano. The state of the hand is also straightforward: with five fingers, each finger is either pressing a key or not. This results in 32 possible situations, represented by 5 binary digits.

What is a choice? A choice is "which finger should play the next note," which involves simply considering all five fingers.

Of course, considering the current state of the hands, each choice has a corresponding cost, which varies from person to person, as mentioned earlier. Therefore, I need to customize a loss function for myself to calculate the "awkwardness" of switching between different fingerings.

Now, the problem becomes a standard dynamic programming problem. We need to make the choice with the least "awkwardness" based on the loss function to ensure the most fluid performance...

However, the time complexity of this algorithm is too high. Our analysis was only for a single note, but if we string notes into a melody, the time and space complexity need to be multiplied by the number of notes in the melody, which is quite large.

Moreover, this loss function is difficult to quantify. The difficulty of hitting the black and white keys on the piano varies, and the "awkwardness" can only be felt, which is somewhat imprecise...

Nevertheless, it's not necessary to calculate the fingering for the entire piece. It's sufficient to calculate the fingering for some complex sections, making this algorithm quite effective.

Having discussed these side topics, let's get to the main point. Today's topic is LeetCode problem #514 "Freedom Trail," which shares similarities with the piano fingering problem. If you can understand the piano example, you should be able to solve this algorithm problem quickly.

The problem gives you a string ring representing the characters on a circular disk (the pointer is at the 12 o'clock position, initially pointing to ring[0]), and a string key representing the string you need to input by rotating the disk. Your algorithm should return the minimum number of operations required to input this key (both rotating the disk by one position and pressing the button in the center of the disk count as one operation).

The function signature is as follows:

int findRotateSteps(String ring, String key);

int findRotateSteps(string ring, string key);

def findRotateSteps(ring: str, key: str) -> int:

func findRotateSteps(ring string, key string) int {}

var findRotateSteps = function(ring, key) {}

For example, given the problem example with input ring = "godding", key = "gd", the corresponding dial is shown below (uppercase is just for clarity; the actual input strings are in lowercase):

We need to input key = "gd", and the algorithm returns 4.

Since the pointer is currently pointing to the letter "g", you can directly press the middle button, then rotate the dial counterclockwise by two positions to point the pointer to the letter "d", and press the middle button again.

In this process, the button is pressed twice, and the dial is rotated two positions, totaling 4 operations, which is the minimum number of operations, so the algorithm should return 4.

Here, we can first make an equivalence for the problem: is rotating the dial the same as moving the pointer?

The original problem can be transformed into: with a fixed dial, we can move the pointer; now we need to move the pointer and press the button to input the string corresponding to key with the minimum number of operations.

So, how can we use dynamic programming techniques to solve this problem? Or, what are the "state" and "choices" in this problem?

The "state" is "the current character to be input" and "the current position of the dial pointer".

More specifically, the "state" consists of two variables i and j. We can use i to represent the character currently pointed to by the dial pointer (i.e., ring[i]), and j to represent the character that needs to be input (i.e., key[j]).

This way, we can write a dp function as follows:

int dp(String ring, int i, String key, int j);

int dp(string ring, int i, string key, int j);

def dp(ring: str, i: int, key: str, j: int) -> int:

func dp(ring string, i int, key string, j int) int

var dp = function(ring, i, key, j){}

The definition of this dp function is as follows:

When the disk pointer is at ring[i], at least dp(ring, i, key, j) operations are needed to input the string key[j..].

Based on this definition, the problem essentially wants to calculate the value of dp(ring, 0, key, 0). Additionally, we can write the base case for the dp function:

int dp(String ring, int i, String key, int j) {
    // base case, input is complete
    if (j == key.length()) return 0;
    // ...
}

int dp(string ring, int i, string key, int j) {
    // base case, input is completed
    if (j == key.length()) return 0;
    // ...
}

def dp(ring: str, i: int, key: str, j: int) -> int:
    # base case, input completed
    if j == len(key):
        return 0
    # ...

func dp(ring string, i int, key string, j int) int {
    // base case, input is complete
    if j == len(key) {
        return 0
    }
    // ...
}

var dp = function(ring, i, key, j) {
    // base case, input completed
    if (j === key.length) return 0;
    // ...
};

Next, consider how to make choices based on the state and how to perform state transitions.

"Choice" means "how to rotate the dial to get the desired character to input."

Specifically, for the character key[j] that you want to input, how can you rotate the dial to get this character?

For example, if the input is ring = "gdonidg", the dial's state is as shown below:

Suppose the character you want to input is key[j] = "d". There are two letters "d" on the dial, and you can rotate the pointer either clockwise or counterclockwise. Thus, there are four "choices" to input the character "d". We need to choose the rotation method that results in the fewest moves.

The general code logic is as follows:

int dp(String ring, int i, String key, int j) {
    // base case: input is complete
    if (j == key.length()) return 0;
    
    // make a choice
    int res = Integer.MAX_VALUE;
    for (int k : [字符 key[j] 在 ring 中的所有索引]) {
        res = min(
            把 i 顺时针转到 k 的代价,
            把 i 逆时针转到 k 的代价
        );
    }
    
    return res;
}

int dp(string ring, int i, string key, int j) {
    // base case: completed input
    if (j == key.length()) return 0;
    
    // make a choice
    int res = INT_MAX;
    for (int k : [字符 key[j] 在 ring 中的所有索引]) {
        res = min(
            把 i 顺时针转到 k 的代价,
            把 i 逆时针转到 k 的代价
        );
    }

    return res;
}

def dp(ring: str, i: int, key: str, j: int) -> int:
    # base case: input is complete
    if j == len(key): return 0
    
    # make a choice
    res = float('inf')
    for k in [字符 key[j] 在 ring 中的所有索引]:
        res = min(
            转到 k 顺时针的代价,
            转到 k 逆时针的代价
        )
    
    return res

func dp(ring string, i int, key string, j int) int {
    // base case: completed input
    if j == len(key) {
        return 0
    }
    
    // make a choice
    res := math.MaxInt64
    for _, k := range [字符 key[j] 在 ring 中的所有索引] {
        res = min(
            转到 k 顺时针的代价,
            转到 k 逆时针的代价
        )
    }

    return res
}

var dp = function(ring, i, key, j) {
    // base case: input is complete
    if (j === key.length) return 0;
    
    // make a choice
    var res = Infinity;
    for (var k of [字符 key[j] 在 ring 中的所有索引]) {
        res = Math.min(
            把 i 顺时针转到 k 的代价,
            把 i 逆时针转到 k 的代价
        );
    }
    
    return res;
}

As for whether to move clockwise or counterclockwise, it is quite easy to determine: whichever direction is closer should be chosen. However, with two characters "d" on the disk, can we still choose the closer one?

We cannot, because it depends on the character that needs to be input after key[i]. Let's consider the example above:

If the input is key = "di", even though the "d" on the right is closer, you should choose the "d" on the left because the "i" is right next to it, resulting in fewer "overall" operations.

So, how should we determine this? Essentially, it involves exhaustive search. You use recursive calls to the dp function to calculate the "overall" cost of both choices and then compare them.

That's about it. Let's directly look at the final code:

class Solution {
    // character -> index list
    HashMap<Character, List<Integer>> charToIndex = new HashMap<>();
    // memoization table
    int[][] memo;

    // main function
    public int findRotateSteps(String ring, String key) {
        int m = ring.length();
        int n = key.length();
        // initialize all memoization table entries to 0
        memo = new int[m][n];
        // record the mapping of characters to indices on the ring
        for (int i = 0; i < ring.length(); i++) {
            char c = ring.charAt(i);
            if (!charToIndex.containsKey(c)) {
                charToIndex.put(c, new LinkedList<>());
            }
            charToIndex.get(c).add(i);
        }
        // the disk pointer initially points to the 12 o'clock direction,
        // start inputting key from the first character
        return dp(ring, 0, key, 0);
    }

    // calculate the minimum number of operations when
    // the disk pointer is at ring[i] and inputting
    int dp(String ring, int i, String key, int j) {
        // base case: complete input
        if (j == key.length()) return 0;
        // check the memoization table to avoid overlapping subproblems
        if (memo[i][j] != 0) return memo[i][j];
        
        int n = ring.length();
        // make choices
        int res = Integer.MAX_VALUE;
        // there may be multiple characters key[j] on ring
        for (int k : charToIndex.get(key.charAt(j))) {
            // number of pointer movements
            int delta = Math.abs(k - i);
            // choose clockwise or counterclockwise
            delta = Math.min(delta, n - delta);
            // move the pointer to ring[k], continue inputting key[j+1..]
            int subProblem = dp(ring, k, key, j + 1);
            // choose the minimum number of "overall" operations
            // add one because pressing the button is also an operation
            res = Math.min(res, 1 + delta + subProblem);
        }
        // store the result in the memoization table
        memo[i][j] = res;
        return res;
    }
}

class Solution {
    // character -> index list
    unordered_map<char, vector<int>> charToIndex;
    // memoization
    vector<vector<int>> memo;

    // main function
public:
    int findRotateSteps(string ring, string key) {
        int m = ring.size();
        int n = key.size();
        // initialize all memoization to 0
        memo = vector<vector<int>>(m, vector<int>(n, 0));
        // record the mapping of characters to indices on the ring
        for (int i = 0; i < ring.size(); i++) {
            char c = ring[i];
            if (!charToIndex.count(c)) {
                charToIndex[c] = vector<int>();
            }
            charToIndex[c].push_back(i);
        }
        // the disk pointer initially points to the 12 o'clock direction,
        // start inputting key from the first character
        return dp(ring, 0, key, 0);
    }

private:
    // calculate the minimum number of operations when
    // the disk pointer is at ring[i] and inputting
    int dp(const string& ring, int i, const string& key, int j) {
        // base case: complete input
        if (j == key.size()) return 0;
        // check memoization to avoid overlapping subproblems
        if (memo[i][j] != 0) return memo[i][j];
        
        int n = ring.size();
        // make choices
        int res = INT_MAX;
        // there may be multiple characters key[j] on ring
        for (int k : charToIndex[key[j]]) {
            // number of pointer movements
            int delta = abs(k - i);
            // choose clockwise or counterclockwise
            delta = min(delta, n - delta);
            // move the pointer to ring[k] and continue inputting key[j+1..]
            int subProblem = dp(ring, k, key, j + 1);
            // choose the option with the minimum "overall" number of operations
            // add one because pressing the button is also an operation
            res = min(res, 1 + delta + subProblem);
        }
        // store the result in memoization
        memo[i][j] = res;
        return res;
    }
};

class Solution:
    def __init__(self):
        # character -> index list
        self.charToIndex = collections.defaultdict(list)
        # memoization table
        self.memo = None

    # main function
    def findRotateSteps(self, ring: str, key: str) -> int:
        m = len(ring)
        n = len(key)
        # initialize the entire memoization table to 0
        self.memo = [[0] * n for _ in range(m)]
        # record the mapping of characters to indices on the ring
        for i, c in enumerate(ring):
            self.charToIndex[c].append(i)
        # the disk pointer initially points to the 12 o'clock direction,
        # start inputting key from the first character
        return self.dp(ring, 0, key, 0)
    
    # calculate the minimum number of operations when
    # the disk pointer is at ring[i], inputting
    def dp(self, ring: str, i: int, key: str, j: int) -> int:
        # base case: input completed
        if j == len(key):
            return 0
        # check the memoization table to avoid overlapping subproblems
        if self.memo[i][j] != 0:
            return self.memo[i][j]
        
        n = len(ring)
        # make a choice
        res = float('inf')
        # there may be multiple characters key[j] on the ring
        for k in self.charToIndex[key[j]]:
            # number of pointer movements
            delta = abs(k - i)
            # choose clockwise or counterclockwise
            delta = min(delta, n - delta)
            # move the pointer to ring[k], continue inputting key[j+1..]
            subProblem = self.dp(ring, k, key, j + 1)
            # choose the option with the minimum total number of operations
            # add one because pressing the button is also an operation
            res = min(res, 1 + delta + subProblem)
        # store the result in the memoization table
        self.memo[i][j] = res
        return res

// main function
func findRotateSteps(ring string, key string) int {
	m := len(ring)
	n := len(key)
	// initialize the memoization table
	memo := make([][]int, m)
	for i := range memo {
		memo[i] = make([]int, n)
	}
	// initialize the mapping from character to indices
	charToIndex := make(map[rune][]int)
	for i, c := range ring {
		charToIndex[c] = append(charToIndex[c], i)
	}

	var dp func(ring string, i int, key string, j int, memo [][]int, charToIndex map[rune][]int) int
	dp = func(ring string, i int, key string, j int, memo [][]int, charToIndex map[rune][]int) int {
		// base case: complete the input
		if j == len(key) {
			return 0
		}
		// check the memoization table to avoid overlapping subproblems
		if memo[i][j] != 0 {
			return memo[i][j]
		}
		
		n := len(ring)
		// make a choice
		res := math.MaxInt32
		// there may be multiple characters key[j] on the ring
		for _, k := range charToIndex[rune(key[j])] {
			// number of times to move the pointer
			delta := int(math.Abs(float64(k - i)))
			// choose clockwise or counterclockwise
			delta = min(delta, n - delta)
			// move the pointer to ring[k] and continue inputting key[j+1..]
			subProblem := dp(ring, k, key, j + 1, memo, charToIndex)
			// choose the option with the least number of "overall" operations
			// add one because pressing the button is also an operation
			res = min(res, 1 + delta + subProblem)
		}
		// store the result in the memoization table
		memo[i][j] = res
		return res
	}

	// the disc pointer initially points to the 12 o'clock direction
	// start inputting key from the first character
	return dp(ring, 0, key, 0, memo, charToIndex)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

var findRotateSteps = function(ring, key) {
    // character -> index list
    let charToIndex = new Map();
    // memoization
    let memo;

    // main function
    function main(ring, key) {
        let m = ring.length;
        let n = key.length;
        // initialize all memoization to 0
        memo = Array.from({ length: m }, () => Array(n).fill(0));
        // record the mapping of characters to indices on the ring
        for (let i = 0; i < ring.length; i++) {
            let c = ring.charAt(i);
            if (!charToIndex.has(c)) {
                charToIndex.set(c, []);
            }
            charToIndex.get(c).push(i);
        }
        // the disc pointer initially points to the 12 o'clock direction
        // start inputting key from the first character
        return dp(ring, 0, key, 0);
    }

    // calculate the minimum number of operations for
    // the disc pointer at ring[i], inputting key[j..]
    function dp(ring, i, key, j) {
        // base case: complete input
        if (j == key.length) return 0;
        // check memoization to avoid overlapping subproblems
        if (memo[i][j] != 0) return memo[i][j];
        
        let n = ring.length;
        // make a choice
        let res = Infinity;
        // there may be multiple characters key[j] on ring
        for (let k of charToIndex.get(key.charAt(j))) {
            // number of pointer movements
            let delta = Math.abs(k - i);
            // choose clockwise or counterclockwise
            delta = Math.min(delta, n - delta);
            // move the pointer to ring[k], continue inputting key[j+1..]
            let subProblem = dp(ring, k, key, j + 1);
            // choose the minimum number of "overall" operations
            // add one because pressing the button is also an operation
            res = Math.min(res, 1 + delta + subProblem);
        }
        // store the result in memoization
        memo[i][j] = res;
        return res;
    }

    return main(ring, key);
};