Freedom Trail


  • 2
    R

    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):
    http://www.polygon.com/fallout-4/2015/11/12/9721010/road-to-freedom

    1. A string r is engraved on the outer ring, with the first character r[0] initially aligned at the 12:00 position. You are asked to spell a keyword k.
    2. To spell the keyword k, you start by finding the first character k[0] on the outer ring and rotate the ring in order to align k[0] 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[0] == r[5], it will take you 5 steps to rotate to k[0].
    3. After k[0] had been moved in place, press the center of the inner circle to input k[0]. Inputs also count as 1 step each.
    4. 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:

    1. If r does not contain any duplicate characters, and you are only allowed to rotate the ring counter-clockwise.
    2. If r does not contain any duplicate characters, and you are allowed to rotate the ring in either directions for each character k[i].
    3. If r contains duplicate characters, and you are allowed to rotate the ring in either directions for each character k[i].

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.