tło

Budzisz się, aby zagubić się w jednowymiarowym labiryncie! Pojawia się mistyczny dżin (lub coś w tym rodzaju) i wyjaśnia, że ​​wyjście znajduje się przed tobą, ale między tobą a wyjściem jest szereg wyzwań. Przechodząc do przodu, zdajesz sobie sprawę, że wszystkie tak zwane wyzwania są jedynie zamkniętymi drzwiami. Najpierw zobaczysz drzwi z otworem na klucz w kształcie trójnika, a sam nie mając takiego klucza, cofnij się, szukając klucza o Tkształcie.

Sfrustrowany, znajdziesz na ziemi alfabetyczną zupę kluczy, z których żaden nie pasuje do drzwi, które napotkałeś. Po pewnym geniuszu geniuszu (lub idiotyzmu) decydujesz, że tklawisz w kształcie małych liter może być w stanie zmieścić się w gnieździe, jeśli wystarczająco mocno go zablokujesz. Gdy zbliżasz się do drzwi z tkluczem w dłoni, Totwór świeci na zielono, a drzwi rozpuszczają się przed tobą.

Jeden w dół, wiele więcej do zrobienia ...

Wyzwanie

Celem tego wyzwania jest określenie, ile kroków potrzeba, aby wyjść z labiryntu.

Wkładem tego wyzwania jest labirynt: jeden ciąg znaków zawierający tylko znaki [A-Za-z^$ ]. Słownik:

• ^- Początkowa przestrzeń. Dane wejściowe będą zawierać dokładnie jeden ^.
• $- Wyjście (wolność!). Dane wejściowe będą zawierać dokładnie jeden $.
• [A-Z]- Wielkie litery oznaczają drzwi. Możesz przejść przez te drzwi tylko wtedy, gdy już zebrałeś wymagany klucz.
• [a-z]- Małe litery oznaczają klawisze. Zbierasz te klucze, wchodząc na miejsce, w którym znajduje się klucz.

Na wejściu będzie co najwyżej jedna litera. Oznacza to, że całkowita liczba drzwi wyniesie od 0 do 26 włącznie.

Każde zamknięte drzwi [A-Z]będą miały dokładnie jeden odpowiedni klawisz z małymi literami [a-z]. Na wejściu może znajdować się dowolna liczba spacji ( ).

Wszystkie drzwi będą na prawo od startu i na lewo od wyjścia. W ten sposób nie będzie zbędnych drzwi. Wszystkie dane wejściowe będą rozwiązywalne.

Rezultatem tego wyzwania będzie liczba, liczba kroków, które trzeba było podjąć, aby wyjść z labiryntu.

Algorytm

Twoje metodyczne podejście do wyjścia z tego nędznego miejsca jest następujące:

• Zacznij od początku ( ^) i idź do przodu (w prawo), zbierając napotkane klucze.
• Kiedy natrafisz na drzwi, jeśli masz odpowiedni klucz, idź do przodu. Jeśli nie masz właściwego klucza, idź do tyłu (w lewo), zbierając napotkane klucze, aż znajdziesz klucz do najnowszych drzwi, których nie możesz otworzyć.
• Po zebraniu klucza do aktualnych kłopotliwych drzwi odwróć się w prawo i idź dalej.
• Powtarzaj ten proces, aż przejdziesz do exit ( $).

Doświadczeni golfiści zrozumieją, że Twój kod nie musi implementować tego konkretnego algorytmu, o ile generuje taki sam wynik, jak gdybyś uruchomił ten algorytm.

Rachunkowość

Za każdym razem, gdy przechodzisz z jednego kwadratu na drugi, liczy się to jako jeden krok. Obrót o 180º nie wymaga żadnego dodatkowego kroku. Nie można wejść do drzwi bez wymaganego klucza. Musisz wejść na klucz, aby go podnieść, i wyjść na wyjście, aby wygrać. Po pierwszym ruchu spacja początkowa ( ^) zachowuje się tak jak każda inna spacja zwykła.

Przykłady

W tych przykładach zostawiłem spacje jako znaki podkreślające czytelność dla człowieka.

Dane wejściowe to _a_^_A__$__. Dane wyjściowe to 11. Robisz 1krok naprzód, zauważ, że nie masz klucza do Adrzwi, a potem o twarzy. Idziesz do tyłu, aż zajmiesz miejsce zawierające a( 3kroki do tyłu, teraz 4całkowite). Następnie idź naprzód, aż zajmiesz miejsce zawierające wyjście ( 7kroki do przodu, 11ogółem).

Dane wejściowe to b__j^__a_AJB_$. Wynik jest taki, 41że wykonujesz dwie oddzielne podróże na tył labiryntu, jedną po jklucz i drugą b.

Dane wejściowe to __m__t_^__x_T_MX_$____. Dane wyjściowe to 44. Nie zdobędziesz żadnej dodatkowej podróży, aby zdobyć xklucz, ponieważ odebrałeś go w drodze od początku do drzwi T.

Dane wejściowe to g_t_^G_T$. Dane wyjściowe to 12. Nie możesz przejść na Gpole bez klucza i natychmiast od razu. Masz szczęście, aby podnieść tklucz w drodze do gklucza, a tym samym otworzyć obie drzwi na drodze do wolności.

Wejście jest _^_____$. Dane wyjściowe to 6. To było łatwe.

Wytyczne I / O i zwycięskie kryterium

Obowiązują standardowe zasady we / wy. To wyzwanie dla golfa .

CJam, 45 lat

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

Wypróbuj online

Wyjaśnienie:

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 bajtów

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

zsumuj odległość między drzwiami a ich kluczem (podwojona, aby przejść w obie strony), ignorując „zagnieżdżone” klucze i odległość od początku do końca:

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

ten sam algorytm w 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 bajtów

Edycja: Podziękowania dla @ user2357112 i @loovjo za komentarze, które pomogły mi zgolić kolejne 20 26 bajtów mojego rozwiązania!

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 bajtów

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 bajty

To jest mój pierwszy post na Code Golf, mam nadzieję, że jest wystarczająco dobrej jakości do gry w golfa na pierwszy post. Zdecydowanie fajne wyzwanie i niesamowite pytanie!

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

Ten program ładnie narusza fakt, że PHP nie wymaga wcześniejszej deklaracji żadnych zmiennych przed ich użyciem.

Okazało się również, że w moim ostatecznym rozwiązaniu było kilka bajtów krótszych, aby zacząć od 0 i zresetować licznik kroków po znalezieniu znaku początkowego, zamiast zaczynać od „^”.

Wszelkie wskazówki są zdecydowanie mile widziane!

JavaScript (ES6), 110 bajtów

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 odpowiedzi Pyth @ Rob.

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 bajtów

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

Prawdopodobnie istnieje ścisły algorytm, ale to właśnie wymyśliłem.

Pamiętaj, że używam gawk. Niektóre implementacje AWKmogą nie dzielić łańcucha w ""ten sposób.

C #, 309 bajtów

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

Wersja bez golfa:

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

    }
}

Nic szczególnego, po prostu iteruj przez łańcuch i zmieniaj kierunek w zależności od znaku i tego, czy klucz jest zawarty w łańcuchu kluczy.

m = ciąg labiryntu

k = ciąg kluczy

f = kierunek (prawda jest w labiryncie do przodu)

b = klucz do wyszukiwania podczas cofania

c = symbol zastępczy dla m [j], aby zapisać niektóre bajty z powodu częstego używania

j = indeks char ciągu znaków do obejrzenia

t = liczba

Wciąż stosunkowo nowy w golfie, więc jeśli gdzieś zobaczysz, mogę go schudnąć, daj mi znać!