I tried to submit this question through the Add Question option, but it seems that the description below is too long to fit in the field, so I posted here instead.
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 a door.
Here's a sample of how it works (warning: the link contains spoilers to the game):
- A string r is engraved on the outer ring, with the first character r initially aligned at the 12:00 position. You are asked to spell a keyword k.
- To spell the keyword k, you start by finding the first character k on the outer ring and rotate the ring in order to align k at the 12:00 position. Each character being moved past the 12:00 position during the rotation counts as 1 step: for example, if k == r, it will take you 5 steps to rotate to k.
- After k had been moved in place, press the center of the inner circle to input k. Inputs also count as 1 step each.
- Repeat steps 2. and 3. for all characters k[i] in k to finish entering the keyword and unlock the door.
Given the engraved string r and the keyword k, you are asked to count the minimum number of steps to open the door given the following cases:
- If r does not contain any duplicate characters, and you are only allowed to rotate the ring counter-clockwise.
- If r does not contain any duplicate characters, and you are allowed to rotate the ring in either directions for each character k[i].
- If r contains duplicate characters, and you are allowed to rotate the ring in either directions for each character k[i].