fundo

Você acorda e se vê perdido em um labirinto unidimensional! Um gênio místico (ou algo assim) aparece e explica que a saída está à sua frente, mas que entre você e a saída há uma série de desafios. À medida que você avança, percebe que todos os desafios são meramente portas trancadas. Você vê pela primeira vez uma porta com um buraco de chave em forma de T e, sem essa chave, refaça seus passos, procurando uma chave com uma Tforma.

Frustrado, você encontra uma sopa de letras do alfabeto no chão, nenhuma das quais corresponde à porta pela qual você se deparou. Por algum golpe de gênio (ou idiotice), você decide que a tchave em forma de minúscula pode caber no slot se você o apertar com força suficiente. Quando você se aproxima da porta com a tchave minúscula na mão, o Tburaco brilha em verde e a porta se dissolve à sua frente.

Um para baixo, muito mais para ir ...

Desafio

O objetivo deste desafio é marcar quantas etapas são necessárias para sair do labirinto.

A entrada desse desafio é o labirinto: uma sequência contendo apenas caracteres [A-Za-z^$ ]. Glossário:

• ^- O espaço inicial. A entrada conterá exatamente um ^.
• $- A saída (liberdade!). A entrada conterá exatamente um $.
• [A-Z]- Letras maiúsculas significam portas. Você só pode passar por esta porta se já tiver coletado a chave necessária.
• [a-z]- Letras minúsculas significam chaves. Você coleta essas chaves caminhando para o espaço que contém a chave.

Haverá no máximo uma de cada letra maiúscula na entrada. Isso significa que o número total de portas estará entre 0 e 26, inclusive.

Cada porta trancada [A-Z]terá exatamente uma chave minúscula correspondente [a-z]. Pode haver qualquer número de espaços ( ) na entrada.

Todas as portas estarão à direita do início e à esquerda da saída. Assim, não haverá portas supérfluas. Todas as entradas serão solucionáveis.

O resultado desse desafio será um número, o número de etapas necessárias para sair do labirinto.

Algoritmo

Sua abordagem metódica para sair deste lugar miserável é a seguinte:

• Comece no começo ( ^) e siga em frente (direita) coletando as chaves que encontrar.
• Quando você se deparar com uma porta, se tiver a chave correta, prossiga para a porta. Se você não tiver a chave correta, caminhe para trás (esquerda) coletando as chaves que encontrar até encontrar a chave da porta mais recente que não pôde abrir.
• Depois de coletar a chave da porta problemática atual, você vira para a direita e prossegue.
• Repita esse processo até passar para a saída ( $).

Jogadores experientes entenderão que seu código não precisa implementar esse algoritmo específico, desde que produza o mesmo resultado como se você tivesse executado esse algoritmo.

Contando

Cada vez que você pula de um quadrado para outro, isso conta como um passo. Girar 180º não exige etapa adicional. Você não pode avançar para uma porta sem a chave necessária. Você deve pisar em uma chave para buscá-la e pisar na saída para vencer. Após seu primeiro movimento, o espaço inicial ( ^) se comporta como qualquer outro espaço regular.

Exemplos

Nestes exemplos, deixei os espaços como sublinhados para a legibilidade humana.

Entrada é _a_^_A__$__. A saída é 11. Você dá um 1passo à frente, percebe que não tem chave para a Aporta e depois sobre o rosto. Você caminha para trás até ocupar o espaço que contém os a( 3passos para trás, agora 4total). Você então avança até ocupar o espaço que contém a saída ( 7avança, 11total).

Entrada é b__j^__a_AJB_$. O resultado é que 41você faz duas viagens separadas para a parte de trás do labirinto, uma para pegar a jchave e a próxima para pegar a bchave.

Entrada é __m__t_^__x_T_MX_$____. A saída é 44. Você não fará nenhuma viagem extra para pegar a xchave, pois a pegou no caminho desde o início até a porta T.

Entrada é g_t_^G_T$. A saída é 12. Você não pode se mover para o Gespaço sem uma chave e imediatamente inverter. Você tem sorte o suficiente para pegar a tchave no caminho para a gchave e, assim, abrir as duas portas no seu caminho para a liberdade.

Entrada é _^_____$. A saída é 6. Essa foi fácil.

Diretrizes de E / S e critério de vencimento

Aplicam-se as regras de E / S padrão. Este é um desafio do código-golfe .

CJam, 45

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

Experimente online

Explicação:

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)

Pitão, 51 bytes

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

some a distância entre a porta e sua chave (dobrada, para fazer a viagem de ida e volta), ignorando as chaves "aninhadas" e a distância do início ao fim:

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

mesmo algoritmo em 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

Edit: Obrigado a @ user2357112 e @loovjo por seus comentários que me ajudaram a remover outros 20 26 bytes da minha solução!

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

Este é o meu primeiro post no Code Golf, espero que seja de qualidade de golfe alta o suficiente para um primeiro post. Definitivamente um desafio divertido e uma pergunta incrível!

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

Este programa abusa muito bem do fato de que o PHP não precisa que você pré-declare nenhuma variável antes de usá-lo.

Também se revelou alguns bytes mais curto na minha solução final para iniciar em 0 e redefinir a contagem de etapas quando o caractere de início for encontrado, em vez de iniciar no '^'.

Todas as dicas são definitivamente bem-vindas!

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)

Porto da resposta de Pyth de 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 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)}

Provavelmente existe um algoritmo mais rígido, mas foi isso que eu criei.

Observe que estou usando gawk. Algumas implementações de AWKpodem não dividir uma string ""dessa maneira.

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

Versão não destruída:

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

    }
}

Nada sofisticado aqui, basta percorrer a string e mudar de direção com base no caractere e se a chave está contida em uma string de chaves.

m = a corda do labirinto

k = a sequência de teclas

f = a direção (true está à frente no labirinto)

b = a chave a ser pesquisada ao retornar

c = espaço reservado para m [j] salvar alguns bytes devido ao uso frequente

j = o índice de caracteres da string a ser observada

t = a contagem

Ainda relativamente novo no golfe, por isso, se você vir algum lugar, eu posso reduzi-lo, avise-me!