Contexte

Vous vous réveillez pour vous retrouver perdu dans un labyrinthe à une dimension! Un génie mystique (ou quelque chose) apparaît et explique que la sortie se trouve devant vous, mais qu'entre vous et la sortie est une série de défis. En avançant, vous réalisez que tous les prétendus défis ne sont que des portes verrouillées. Vous voyez d’abord une porte avec un trou de clé en forme de té; sans cette clé, revenez sur vos pas et recherchez une clé de Tforme.

Frustré, vous trouvez sur le sol une soupe de clés alphabet, dont aucune ne correspond à la porte que vous avez rencontrée. Par un coup de génie (ou d'idiotie), vous décidez que la tclé en forme de minuscule pourrait bien s'insérer dans la fente si vous l'enfoncez assez fort. Lorsque vous approchez la porte avec la tclé minuscule dans la main, le Ttrou devient vert et la porte se dissout devant vous.

Une baisse, beaucoup plus à faire ...

Défi

Le but de ce défi est de marquer le nombre de pas nécessaires pour sortir du labyrinthe.

La saisie de ce défi est le labyrinthe: une chaîne ne contenant que des caractères [A-Za-z^$ ]. Glossaire:

• ^- L'espace de départ. L'entrée contiendra exactement un ^.
• $- La sortie (liberté!). L'entrée contiendra exactement un $.
• [A-Z]- Les lettres majuscules signifient des portes. Vous ne pouvez passer par cette porte que si vous avez déjà recueilli la clé requise.
• [a-z]- Les lettres minuscules désignent les touches. Vous collectez ces clés en accédant à l'espace contenant la clé.

Il y aura au plus une de chaque lettre majuscule dans l'entrée. Cela signifie que le nombre total de portes sera compris entre 0 et 26 inclus.

Chaque porte verrouillée [A-Z]aura exactement une clé minuscule correspondante [a-z]. Il peut y avoir un nombre quelconque d'espaces ( ) dans l'entrée.

Toutes les portes seront à droite du début et à gauche de la sortie. Ainsi, il n'y aura pas de portes superflues. Toutes les entrées seront solubles.

Le résultat de ce défi sera un nombre, le nombre de pas nécessaires pour sortir du labyrinthe.

Algorithme

Votre approche méthodique pour sortir de ce lieu misérable est la suivante:

• Commencez au début ( ^) et avancez (à droite) en collectant les clés que vous rencontrez.
• Lorsque vous rencontrez une porte, si vous avez la bonne clé, vous avancez vers la porte. Si vous ne possédez pas la bonne clé, vous récupérez les clés que vous rencontrez jusqu'à ce que vous trouviez la clé de la dernière porte que vous ne pouviez pas ouvrir.
• Une fois que vous avez récupéré la clé de la porte gênante actuelle, vous retournez à droite et continuez.
• Répétez cette procédure jusqu'à ce que vous passiez à la sortie ( $).

Les golfeurs expérimentés comprendront que votre code n'a pas à implémenter cet algorithme spécifique tant qu'il génère le même résultat que si vous l'aviez exécuté.

Compte

Chaque fois que vous passez d'une case à une autre, cela compte pour une étape. Le virage à 180º ne comporte aucune étape supplémentaire. Vous ne pouvez pas avancer sur une porte sans la clé requise. Vous devez marcher sur une clé pour la récupérer et vous devez vous diriger vers la sortie pour gagner. Après votre premier déplacement, l’espace de départ ( ^) se comporte comme tout autre espace normal.

Exemples

Dans ces exemples, j'ai laissé les espaces comme des soulignés pour la lisibilité humaine.

L'entrée est _a_^_A__$__. La sortie est 11. Vous 1faites un pas en avant, remarquez que vous n’avez pas de clé pour la Aporte, puis sur votre visage. Vous marchez en arrière jusqu'à occuper l'espace contenant le a( 3pas en arrière, maintenant 4total). Vous avancez ensuite jusqu'à occuper l'espace contenant la sortie ( 7pas en avant, 11total).

L'entrée est b__j^__a_AJB_$. La sortie est 41Vous faites deux allers-retours distincts à l’arrière du labyrinthe, l’un pour récupérer la jclé et le suivant pour obtenir la bclé.

L'entrée est __m__t_^__x_T_MX_$____. La sortie est 44. Vous ne ferez aucun voyage supplémentaire pour obtenir la xclé, car vous la récupérerez du début à la fin T.

L'entrée est g_t_^G_T$. La sortie est 12. Vous ne pouvez pas vous déplacer dans l’ Gespace sans clé, et immédiatement sur votre visage. Vous avez la chance de récupérer la tclé sur le chemin de la gclé et d'ouvrir ainsi les deux portes sur votre chemin vers la liberté.

L'entrée est _^_____$. La sortie est 6. C'était facile.

Directives d'E / S et critère gagnant

Les règles d'E / S standard s'appliquent. Ceci est un défi de code-golf .

CJam, 45

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

Essayez-le en ligne

Explication:

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 octets

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

additionnez la distance entre la porte et sa clé (doublée pour effectuer l'aller-retour), en ignorant les clés "imbriquées" et la distance du début à la fin:

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

même algorithme en 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 octets

Edit: Merci à @ user2357112 et @loovjo pour leurs commentaires qui m'ont aidé à réduire de 20 à 26 octets ma 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

C, 136 octets

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 octets

Ceci est mon premier post sur Code Golf, espérons-le, il est d'une qualité de golf suffisamment élevée pour un premier post. Certainement un défi amusant et une question géniale!

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

Ce programme abuse gentiment du fait que PHP n’a pas besoin de pré-déclarer les variables avant de les utiliser.

Il s’est également avéré que la solution finale devait commencer à 0 et réinitialiser le nombre de pas lorsque le caractère de début est trouvé, plutôt que de commencer par le '^'.

Tous les conseils sont les bienvenus!

JavaScript (ES6), 110 octets

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)

Réponse du port de @ Rob's Pyth.

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 octets

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

Il y a probablement un algorithme plus strict, mais c'est ce que j'ai proposé.

Notez que j'utilise gawk. Certaines implémentations de AWKne peuvent pas diviser une chaîne de ""cette façon.

C #, 309 octets

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

Version non-golfée:

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

    }
}

Rien d'extraordinaire ici, il suffit de parcourir la chaîne et de changer de direction en fonction du caractère et si la clé est contenue dans une chaîne de clés.

m = la chaîne de labyrinthe

k = la chaîne de clés

f = la direction (true est en avant dans le labyrinthe)

b = la clé à rechercher lors d'un retour en arrière

c = espace réservé pour m [j] pour économiser des octets en raison d'une utilisation fréquente

j = l'index de caractère de la chaîne à regarder

t = le compte

Encore relativement nouveau dans le golf alors si vous voyez quelque part je peux le réduire, faites le moi savoir!