Freedom Trail

Problem Statement

In the renowned video game Fallout 4, one challenge—"Road to Freedom"—immerses players into a scenario where they need to interact with a mechanism known as the "Freedom Trail Ring" to unlock a door. This mechanism simulation is presented with two primary data representations:

• A string ring which encaptures the sequence of characters engraved on a rotatable dial.
• A string key represents the sequence of characters (a "password") that needs to be sequentially aligned to a fixed point (the "12:00" direction) on this dial to progress in the challenge.

The task is to compute the minimum number of steps required to align each character from key in the target direction using the dial. A "step" can either be a rotation of the dial (either clockwise or anticlockwise) or the act of selecting the aligned character (by pressing a center button). The challenge initiates with the first character of the ring aligning at the "12:00" direction, serving as a starting point for the character alignment of key.

This computational problem requires optimizing the number and direction of rotations to minimize the overall steps needed to complete the alignment of all characters in key.

Examples

Example 1

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 anticlockwise by 2 steps to bring 'd' to the 12:00 position.
Also, we need 1 more step to select the character.
Total steps = 1 + 2 + 1 = 4.

Example 2

Input:

ring = "godding"
key = "godding"

Output:

13

Constraints

• 1 <= ring.length, key.length <= 100
• ring and key consist of only lowercase English letters.
• It is guaranteed that key can always be spelled by rotating ring.

Approach and Intuition

The problem can be resolved through a dynamic programming approach where the focus is on:

1. Representing each position of the dial as a state. These states change based on the rotations performed.

2. Using a memoization table to track the minimal steps required to align characters from key, starting at any index in ring.

3. For each character in key, consider:

   • All positions in ring that contain the character.
   • The steps to rotate from the current position to the target position (clockwise and anticlockwise).
   • Adding 1 step for selecting the character once it’s aligned.

4. Update the DP table to store the minimal steps required to reach each new state.

5. After processing all characters, return the minimum steps from the final DP state.

This approach leverages the circular nature of the dial and ensures all possibilities are considered efficiently using dynamic programming.

Solutions

class Solution {
public:
    int rotateSteps(string ring, string key) {
        int lenRing = ring.size();
        int lenKey = key.size();
    
        // Map to store positions of each character in the ring
        unordered_map<char, vector<int>> indexMap;
        for (int i = 0; i < ring.size(); i++) {
            char c = ring[i];
            indexMap[c].push_back(i);
        }
    
        // Min-heap to explore minimum steps first
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> minHeap;
        minHeap.push({0, 0, 0});
    
        // Set to track the visited {ring position, key index}
        unordered_set<string> visited;
    
        // Processing the heap to find the minimum rotation steps
        int minSteps = 0;
        while (!minHeap.empty()) {
            vector<int> current = minHeap.top();
            minHeap.pop();
            minSteps = current[0];
            int currentIndex = current[1];
            int currentKeyIndex = current[2];
    
            // If we have spelled the entire key
            if (currentKeyIndex == lenKey) {
                break;
            }
    
            string visitKey = to_string(currentIndex) + "-" + to_string(currentKeyIndex);
            if (visited.find(visitKey) != visited.end()) {
                continue;
            }
    
            // Marking the state as visited
            visited.insert(visitKey);
    
            // Traverse the visible states and push them to the heap
            for (int newIndex : indexMap[key[currentKeyIndex]]) {
                minHeap.push({minSteps + getMinSteps(currentIndex, newIndex, lenRing),
                              newIndex, currentKeyIndex + 1});
            }
        }
    
        return minSteps + lenKey;
    }
    
private:
    // Helper function to calculate minimal rotation steps between two indices
    int getMinSteps(int start, int dest, int length) {
        int direct = abs(start - dest);
        int reverse = length - direct;
        return min(direct, reverse);
    }
};