41
5
Background
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 T
shape.
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...
Challenge
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 [A-Za-z^$ ]
.
Glossary:
^
-- 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 () in the input.
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.
Algorithm
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.
Counting
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.
Examples
In these examples I've left the spaces as underscores for human-readability.
Input is _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 a
(3
steps backward, now 4
total). You then walk forward until you occupy the space containing the exit (7
steps forward, 11
total).
Input is 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 b
key.
Input is __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 T
.
Input is 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.
Input is _^_____$
. The output is 6
. That was easy.
I/O Guidelines and Winning Criterion
Standard I/O rules apply. This is a code-golf challenge.
17Apart from the nice challenge, I'd like to remark how good the wording and explanation are – Luis Mendo – 2016-03-29T15:48:34.360
4"Thus there will be no superfluous doors." I think
A
inbA^aB$
wouldn't be superfluous either. ;) – Martin Ender – 2016-03-29T16:35:26.753"The goal of this challenge is to mark how many steps it takes you to exit the labyrinth." Then why not require optimality? Always going right first is not an optimal strategy. – orlp – 2016-03-29T17:06:40.840
@MartinBüttner ;) – turbulencetoo – 2016-03-29T18:27:12.533
4@orlp I'm more interested in seeing how people golf this wandering-in-the-dark algorithm. It seems trivial to do the optimal solution of "go get all the keys then go open all the doors". – turbulencetoo – 2016-03-29T18:27:16.877
@orlp, this is more interesting than optimality (for which there would almost certainly be a handful of dupe candidates). – Peter Taylor – 2016-03-29T18:27:47.237
2@PeterTaylor and turbulencetoo No it's not, who's to say all the keys are on the left side, and all doors on the right? And superfluous keys/doors would be interesting too. It'd be pretty interesting, as it would mean solving a dependency graph. – orlp – 2016-03-29T18:59:42.503
@orlp The optimal solution would be interesting, just as the present algorithm is. Maybe a future new challenge about the optimal solution? However, it may be difficult to verify that a solution is indeed optimal – Luis Mendo – 2016-03-29T19:01:30.343
5Every door has a key. Does every key have a door? – user2357112 supports Monica – 2016-03-30T00:15:39.580
1Wait. Its a
1-Dimensional Labyrinth
where you can go left?? – Distjubo – 2016-03-30T11:30:09.9431@Distjubo - hehe, yes - a single dimension denotes a line. – Tracy Cramer – 2016-03-30T16:41:32.780
I wonder if there will be any language solving this with 1 byte built-in this time? – Oleg V. Volkov – 2016-03-30T17:46:39.803
The optimal solution would to just keep going straight collecting every key as you go if it weren't for the algorithm constraint. Good thing there's no inventory constraint as well. – Pharap – 2016-03-30T18:31:23.380
@user2357112 Does it matter if every key has a door or not? – Pharap – 2016-03-30T18:32:09.683