You awake to find yourself lost in a one dimensional labyrinth! A mystical genie (or something) appears and explains that the exit lies in front of you, but that between you and the exit is a series of challenges. As you wander forward you realize that all of the so-called challenges are merely locked doors. You first see a door with a tee-shaped key-hole, and having no such key yourself, retrace your steps, looking for a key with a
Frustrated, you find an alphabet soup of keys on the ground, none of which match the door you've come across. By some stroke of genius (or idiocy), you decide that the lower-case
t-shaped key might be able to fit in the slot if you jam it in there hard enough. As you approach the door with the lower-case
t key in hand, the
T hole glows green and the door dissolves in front of you.
One down, many more to go...
The goal of this challenge is to mark how many steps it takes you to exit the labyrinth.
The input of this challenge is the labyrinth: one string containing only characters
^-- The start space. The input will contain exactly one
$-- The exit (freedom!). The input will contain exactly one
[A-Z]-- Capital letters signify doors. You can only go through this door if you have already collected the requisite key.
[a-z]-- Lower case letters signify keys. You collect these keys by walking onto the space that contains the key.
There will be at most one of each capital letter in the input. This means the total number of doors will be between 0-26 inclusive.
Every locked door
[A-Z] will have exactly one corresponding lower case key
[a-z]. There may be any number of spaces (
All of the doors will be to the right of the start, and to the left of the exit. Thus there will be no superfluous doors. All inputs will be solvable.
The output for this challenge will be a number, the number of steps it took to exit the labyrinth.
Your methodical approach to exiting this wretched place is as follows:
- Start at the beginning (
^) and move forward (right) collecting any keys you come across.
- When you come across a door, if you have the correct key, you proceed forward onto the door. If you don't have the correct key, you walk backwards (left) collecting keys you come across until you find the key for the most recent door that you couldn't open.
- Once you collect the key for the current troublesome door, you turn back to the right and proceed onward.
- Repeat this process until you step on to the exit (
Experienced golfers will understand that your code doesn't have to implement this specific algorithm as long as it outputs the same result as if you had run this algorithm.
Each time you step from one square onto another square, that counts as one step. Turning 180º incurs no additional step. You cannot step forward onto a door without the requisite key. You must step onto a key to pick it up, and must step onto the exit to win. After your first move, the start space (
^) behaves just like any other regular space.
In these examples I've left the spaces as underscores for human-readability.
_a_^_A__$__. The output is
11. You take
1 step forward, notice that you have no key for the
A door, and then about face. You walk backward until you occupy the space containing the
3 steps backward, now
4 total). You then walk forward until you occupy the space containing the exit (
7 steps forward,
b__j^__a_AJB_$. The output is
41 You make two separate trips to the back of the labyrinth, one to get the
j key, and the next one to get the
__m__t_^__x_T_MX_$____. The output is
44. You won't make any extra trip to get the
x key, as you picked it up on your way from the start to door
g_t_^G_T$. The output is
12. You cannot move onto the
G space without a key, and immediately about-face. You're lucky enough to pick up the
t key on the way to the
g key, and thus open both doors on your way to freedom.
_^_____$. The output is
6. That was easy.
I/O Guidelines and Winning Criterion
Standard I/O rules apply. This is a code-golf challenge.