Hintergrund

Sie wachen auf und befinden sich in einem eindimensionalen Labyrinth! Ein mystischer Geist (oder etwas anderes) erscheint und erklärt, dass der Ausgang vor Ihnen liegt, aber dass zwischen Ihnen und dem Ausgang eine Reihe von Herausforderungen besteht. Während Sie vorwärts wandern, stellen Sie fest, dass alle sogenannten Herausforderungen nur verschlossene Türen sind. Sie sehen zuerst eine Tür mit einem t-förmigen Schlüsselloch und haben selbst keinen solchen Schlüssel. Verfolgen Sie Ihre Schritte und suchen Sie nach einem Schlüssel mit einer TForm.

Frustriert findest du eine Buchstabensuppe mit Schlüsseln auf dem Boden, von denen keine mit der Tür übereinstimmt, auf die du gestoßen bist. Durch einen genialen Schachzug (oder Schwachsinn) entscheiden Sie, dass der tkleingeschriebene Schlüssel möglicherweise in den Steckplatz passt, wenn Sie ihn fest genug einklemmen. Wenn Sie sich der Tür mit dem Kleinbuchstabenschlüssel nähern t, Tleuchtet das Loch grün und die Tür löst sich vor Ihnen auf.

Eins runter, noch viele ...

Herausforderung

Das Ziel dieser Herausforderung ist es zu markieren, wie viele Schritte Sie benötigen, um das Labyrinth zu verlassen.

Die Eingabe dieser Herausforderung ist das Labyrinth: eine Zeichenfolge, die nur Zeichen enthält [A-Za-z^$ ]. Glossar:

• ^- Der Startraum. Die Eingabe enthält genau einen ^.
• $- Der Ausgang (Freiheit!). Die Eingabe enthält genau einen $.
• [A-Z]- Großbuchstaben kennzeichnen Türen. Sie können diese Tür nur betreten, wenn Sie den erforderlichen Schlüssel bereits abgeholt haben.
• [a-z]- Kleinbuchstaben kennzeichnen Schlüssel. Sie sammeln diese Schlüssel, indem Sie auf das Feld gehen, in dem sich der Schlüssel befindet.

Die Eingabe enthält höchstens einen Großbuchstaben. Dies bedeutet, dass die Gesamtzahl der Türen zwischen einschließlich 0 und 26 liegt.

Jede verschlossene Tür [A-Z]hat genau einen entsprechenden Kleinbuchstabenschlüssel [a-z]. Die Eingabe kann beliebig viele Leerzeichen ( ) enthalten.

Alle Türen befinden sich rechts vom Start und links vom Ausgang. Somit gibt es keine überflüssigen Türen. Alle Eingaben sind lösbar.

Die Ausgabe für diese Herausforderung ist eine Zahl, die Anzahl der Schritte, die erforderlich waren, um das Labyrinth zu verlassen.

Algorithmus

Ihr methodischer Ansatz, um diesen elenden Ort zu verlassen, lautet wie folgt:

• Beginnen Sie am Anfang ( ^) und gehen Sie vorwärts (rechts), um alle Schlüssel zu sammeln, auf die Sie stoßen.
• Wenn Sie auf eine Tür stoßen und den richtigen Schlüssel haben, gehen Sie geradeaus zur Tür. Wenn Sie nicht den richtigen Schlüssel haben, gehen Sie rückwärts (links) und sammeln die Schlüssel, auf die Sie stoßen, bis Sie den Schlüssel für die letzte Tür finden, die Sie nicht öffnen konnten.
• Sobald Sie den Schlüssel für die aktuelle problematische Tür gesammelt haben, biegen Sie nach rechts ab und fahren fort.
• Wiederholen Sie diesen Vorgang, bis Sie zum Ausgang ( $) gelangen.

Erfahrene Golfer werden verstehen, dass Ihr Code diesen spezifischen Algorithmus nicht implementieren muss, solange er dasselbe Ergebnis ausgibt, als ob Sie diesen Algorithmus ausgeführt hätten.

Zählen

Jedes Mal, wenn Sie von einem Feld auf ein anderes Feld treten, zählt dies als ein Schritt. Beim Drehen um 180 ° wird kein zusätzlicher Schritt ausgeführt. Sie können eine Tür nicht ohne den erforderlichen Schlüssel betreten. Sie müssen auf einen Schlüssel treten, um ihn aufzuheben, und müssen auf den Ausgang treten, um zu gewinnen. Nach Ihrem ersten Zug ^verhält sich das Startfeld ( ) wie jedes andere reguläre Feld.

Beispiele

In diesen Beispielen habe ich die Leerzeichen als Unterstriche für die Lesbarkeit belassen.

Eingabe ist _a_^_A__$__. Die Ausgabe ist 11. Sie treten einen 1Schritt vor, bemerken, dass Sie keinen Schlüssel für die ATür haben, und dann über Gesicht. Du gehst zurück, bis du den Raum besetzt, der die a( 3Schritte zurück, jetzt 4total) enthält. Sie gehen dann vorwärts, bis Sie den Raum mit dem Ausgang besetzen ( 7Schritte vorwärts, 11total).

Eingabe ist b__j^__a_AJB_$. Die Ausgabe ist 41Sie machen zwei getrennte Reisen zur Rückseite des Labyrinths, eine, um den jSchlüssel zu bekommen , und die nächste, um den bSchlüssel zu bekommen .

Eingabe ist __m__t_^__x_T_MX_$____. Die Ausgabe ist 44. Sie werden keinen zusätzlichen Ausflug machen, um den xSchlüssel zu bekommen , da Sie ihn auf dem Weg von Anfang bis zur Tür abgeholt haben T.

Eingabe ist g_t_^G_T$. Die Ausgabe ist 12. Sie können den GRaum nicht ohne Schlüssel betreten und sofort umkehren. Sie haben das Glück, tauf dem Weg zum gSchlüssel den Schlüssel abzuholen und auf dem Weg in die Freiheit beide Türen zu öffnen.

Eingabe ist _^_____$. Die Ausgabe ist 6. Das war einfach.

I / O-Richtlinien und Gewinnkriterium

Es gelten die Standard-E / A-Regeln. Dies ist eine Code-Golf- Herausforderung.

CJam, 45

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

Probieren Sie es online aus

Erläuterung:

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)

Pyth, 51 Bytes

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

Summieren Sie den Abstand zwischen der Tür und ihrem Schlüssel (verdoppelt, um die Rundfahrt zu machen), wobei Sie die "verschachtelten" Schlüssel und den Abstand vom Anfang bis zum Ende ignorieren:

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

gleicher Algorithmus 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

Python 2, 155 154 134 128 Bytes

Bearbeiten: Vielen Dank an @ user2357112 und @loovjo für ihre Kommentare, die mir geholfen haben, weitere 20 bis 26 Bytes von meiner Lösung zu entfernen !

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

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);}

PHP 5.3, 123 Bytes

Dies ist mein erster Beitrag zu Code Golf, der hoffentlich eine Golfqualität aufweist, die für einen ersten Beitrag ausreicht. Auf jeden Fall eine lustige Herausforderung und eine tolle Frage!

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;}

Dieses Programm missbraucht die Tatsache, dass Sie in PHP keine Variablen deklarieren müssen, bevor Sie sie verwenden.

Es stellte sich auch heraus, dass meine endgültige Lösung ein paar Bytes kürzer war, bei 0 zu beginnen und die Schrittzahl zurückzusetzen, wenn das Startzeichen gefunden wurde, anstatt bei '^' zu beginnen.

Irgendwelche Tipps sind auf jeden Fall willkommen!

JavaScript (ES6), 110 Byte

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 von @ Rob's Pyth Antwort.

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

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)}

Es gibt wahrscheinlich einen engeren Algorithmus, aber das ist mir eingefallen.

Beachten Sie, dass ich verwende gawk. Bei einigen Implementierungen von wird AWKeine Zeichenfolge möglicherweise nicht auf ""diese Weise aufgeteilt.

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();

    }
}

Hier ist nichts Besonderes zu bemerken. Durchlaufen Sie einfach die Zeichenfolge und ändern Sie die Richtung basierend auf dem Zeichen und ob der Schlüssel in einer Schlüsselzeichenfolge enthalten ist.

m = die Labyrinthkette

k = die Schlüsselkette

f = die Richtung (wahr ist vorwärts im Labyrinth)

b = der Schlüssel, nach dem gesucht werden soll, wenn zurückgegangen wird

c = Platzhalter für m [j] zum Speichern einiger Bytes aufgrund häufiger Verwendung

j = der Zeichenindex der zu betrachtenden Zeichenfolge

t = die Zählung

Das Golfen ist noch relativ neu. Wenn Sie also irgendwo sehen, dass ich es etwas schlanker machen kann, lassen Sie es mich wissen!