Unlocking the Secrets to a 1-Dimensional Labyrinth

Question

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.

Answer 1

Pyth, 51 bytes

JxQ"^"K-xQ"$"JVQI&}NrG1>JxQrN0=JxQrN0=+K*2t-xQNJ;pK

sum the distance between the door and its key (doubled, to take the round trip), ignoring the "nested" keys and the distance from the start to the end:

JxQ"^"                                              #Initialize the farther point with the starting position
      K-xQ"$"J                                      #Initialize the step counter with the difference between the exit and the start
              VQ                                    #iterate over the input
                I&}NrG1>JxQrN0                      #check if is upper and if the keys is father than one stored (to eliminate nested keys)
                              =JxQrN0               #update the farther key
                                     =+K*2t-xQNJ;   #update step counter with the round trip door<>key
                                                 pK #print the step counter

same algorythm in python2.7 :

lab=raw_input()
farther_key=lab.index('^')
steps = lab.index('$') - farther_key
for i in lab:
    if i.isupper():
        if farther_key> lab.index(i.lower()):
            farther_key=lab.index(i.lower())
            steps+=((lab.index(i) - farther_key)-1)*2
print steps

Answer 2

Python 2, 155 154 134 128 bytes

Edit: Thanks to @user2357112 and @loovjo for their comments that helped me shave another 20 26 bytes off my solution!

def f(l):
 i=l.index;b=i('^');t=i('$')-b
 for d in filter(str.isupper,l):
  k=i(d.lower())
  if k<b:b=k;t+=2*(i(d)-k-1)
 print t

Answer 3

C, 136 bytes

q,x,p[300],z,c,k;main(i){for(;p[c=getchar()]=++i,c-36;z&&(k+=(x=p[c+32])&&x<q?(q=q>x?x:q,2*i-2*x-1):1))z=p[94],q||(q=z);printf("%d",k);}

Answer 4

PHP 5.3, 123 bytes

This is my first post on Code Golf, hopefully this is of golfing quality high enough for a first post. Definitely a fun challenge and an awesome question!

function n($m){while('$'!=$o=$m[$i++])$o=='^'?$b=$i+$c=0:$o>'Z'||$b<=$k=stripos($m,$o))?$c++:$c+=2*$i-3-2*$b=$k;return$c;}

This program nicely abuses the fact that PHP doesn't need you to pre-declare any variables before you use them.

It also turned out to be a couple bytes shorter in my final solution to start at 0 and reset the step count when the start character is found, rather than starting at the '^'.

Any tips are definitely welcome!

Answer 5

CJam, 45

1q_'$#<'^/~\W%:A;ee{~32+A#)_T>{:T+2*+}&]0=)}/

Try it online

Explanation:

1         initial step count; this 1 is actually for the last step :)
q_'$#<    read the input and only keep the part before the '$'
'^/~      split by '^' and dump the 2 pieces on the stack
\W%:A;    take the first piece, reverse it and store it in A
ee        enumerate the other piece (making [index char] pairs)
{…}/      for each [index char] pair
  ~32+    dump the index and character on the stack, and add 32 to the character;
           uppercase letters become lowercase and other chars become garbage
  A#)     find the index of this character in A and increment it (not found -> 0)
  _T>     check if this index (number of steps from '^' back to the key)
           is greater than T (which is initially 0)
  {…}&    if that's true (we need to go back), then
    :T    store that index in T (keeping track of how far we go back before '^')
    +     add to the other index (from the pair, number of steps we took after '^')
    2*    double the result (going back and forth)
    +     add it to the step count
  ]0=     keep only the first value from the bottom of the stack (step count)
           (if the condition above was false, we'd have 2 extra values)
  )       increment the step count (for the current step)

Answer 6

JavaScript (ES6), 110 bytes

s=>(i=c=>s.indexOf(c),p=i`^`,l=i`$`-p,s.replace(/[A-Z]/g,(c,j)=>p>(t=i(c.toLowerCase()))?l+=j-(p=t)-1<<1:0),l)

Port of @Rob's Pyth answer.

Answer 7

Python 2.7, 234 199 179

a=raw_input()
x=a.index
v=x('^')
b=x('$')-v
l=filter(str.islower,a[:v])[::-1]
for i in filter(str.isupper,a):
 k=i.lower()
 if k in l:b+=(x(i)-x(k)-1)*2;l=l[l.index(k)+1:]
print b

Answer 8

AWK, 174 Bytes

func f(xmS){x+=S
c=a[x]
if(c~/^[A-Z]/&&!k[c]){C=c
S=-S
s--}else{c=toupper(c)
k[c]=1
s++
if(c==C){S=-S;C=9}}if(c=="$"){print s}else f(x,S)}{split($0,a,"")
f(index($0,"^"),1)}

There's probably a tighter algorithm, but this is what I came up with.

Do note that I'm using gawk. Some implementations of AWK may not split a string on "" this way.

Answer 9

C#, 309 bytes

class P{static void Main(string[]a){string m=Console.ReadLine(),k="";var f=true;char b,c=b=' ';int j=m.IndexOf('^'),t=0;for(;m[j]!='$';j+=f?1:-1){c=m[j];if(char.IsUpper(c)){if(k.IndexOf(char.ToLower(c))<0){f=!f;b=c;t--;}}if(char.IsLower(c)){k+=c;if(char.ToUpper(c)==b){f=!f;t--;}}t++;}Console.WriteLine(t);}}

Ungolfed version:

    class P
{
    static void Main(string[] a)
    {
        string m = Console.ReadLine(), k = "";
        var f = true;
        char b, c = b = ' ';
        int j = m.IndexOf('^'), t = 0;
        for (; m[j] != '$'; j += f ? 1 : -1)
        {
            c = m[j];
            if (char.IsUpper(c))
            {
                if (k.IndexOf(char.ToLower(c)) < 0)
                {
                    f = !f; b = c; t--;
                }
            }

            if (char.IsLower(c))
            {
                k += c;
                if (char.ToUpper(c) == b) { f = !f; t--; }
            }


            t++;
        }
        Console.WriteLine(t);
        Console.ReadKey();

    }
}

Nothing fancy here, just iterate through the string and change direction based on the character and whether the key is contained in a keys string.

m = the maze string

k = the keys string

f = the direction (true is forward in the maze)

b = the key to search for when backtracking

c = placeholder for m[j] to save some bytes due to frequent use

j = the char index of the string to look at

t = the count

Still relatively new to golfing so if you see somewhere I can slim it down, let me know!