Ayuda a mi hijo a encontrar sus cartas

17

Antecedentes

Basado en un juego que mi hijo de cuatro años obtuvo de su rabino.

El "objetivo" es "encontrar" las letras en un orden dado, por ejemplo aecdb. Le dan una pila de cartas, por ejemplo daceb. Solo puede buscar en la pila en el orden dado, aunque cíclicamente. Cuando encuentras una carta que necesitas, la sacas de la pila.

Objetivo

Dado un orden y una pila (permutaciones libres de duplicados entre sí), encuentre la secuencia de letras de la pila superior (todo es ASCII imprimible) que ve al jugar el juego.

Ejemplo paso a paso

Necesitamos encontrar el orden aecdb, dada la pila daceb:

La parte superior de la pila d: No es lo que estamos buscando ( a), por lo que lo añadimos a la secuencia: dy giran para conseguir la pila: acebd.

Parte superior de la pila a: ¡Sí! así que agregamos a la secuencia: day sacarlo de la pila: cebd.

La parte superior de la pila c: No es lo que estamos buscando ( e), por lo que lo añadimos a la secuencia: dacy giran para conseguir la pila: ebdc.

Parte superior de la pila e: ¡Sí! así que agregamos a la secuencia: dacey sacarlo de la pila: bdc.

La parte superior de la pila b: No es lo que estamos buscando ( c), por lo que lo añadimos a la secuencia: daceby giran para conseguir la pila: dcb.

La parte superior de la pila d: No es lo que estamos buscando ( c), por lo que lo añadimos a la secuencia: dacebdy giran para conseguir la pila: cbd.

Parte superior de la pila c: ¡Sí! así que agregamos a la secuencia: dacebdcy sacarlo de la pila: bd.

La parte superior de la pila b: No es lo que estamos buscando ( d), por lo que lo añadimos a la secuencia: dacebdcby giran para conseguir la pila: db.

Parte superior de la pila d: ¡Sí! así que agregamos a la secuencia: dacebdcbdy sacarlo de la pila: b.

Parte superior de la pila b: ¡Sí! así que agregamos a la secuencia: dacebdcbdby sacarlo de la pila: .

Y ya hemos terminado. El resultado es dacebdcbdb.

Implementación de referencia

def letters(target, stack):
    string = ''
    while stack:
        string += stack[0]
        if stack[0] == target[0]:
            stack.pop(0)
            target = target[1:]
        else:
            stack.append(stack.pop(0))
    return string

print letters('aecdb', list('daceb'))

Pruébalo en línea!

Casos de prueba

try, yrtyrtyry

1234, 43214321432434

ABCDEFGHIJKLMNOPQRSTUVWXYZ, RUAHYKCLQZXEMPBWGDIOTVJNSFRUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ

?, ??

a, a a a

abcd, abcdabcd

Adán
fuente

Respuestas:

5

Tres métodos bastante diferentes están dando recuentos de bytes iguales.

Python 2 , 59 bytes

s,t=input()
for c in s*99:
 if c in t:print c;t=t.lstrip(c)

Pruébalo en línea!

Imprime cada personaje en su propia línea.


Python 2 , 59 bytes

lambda s,t:[c==t[0]and t.pop(0)or c for c in s*99if c in t]

Pruébalo en línea!

Toma listas como entrada y genera una lista.


Python 3 , 59 bytes

def f(s,t):
 for c in t:p,q=s.split(c);s=q+p;print(end=p+c)

Pruébalo en línea!

xnor
fuente
1
Hm, sospecho de las dos primeras versiones ... ¿por qué 99específicamente?
Erik the Outgolfer
@EriktheOutgolger Es al menos el número de caracteres ASCII imprimibles y, por lo tanto, es al menos la longitud de cada entrada.
xnor
5

APL (Dyalog Classic) , 21 bytes

∊⊢,⊢∘⊂~¨(,\⊣⊂⍨1,2>/⍋)

Pruébalo en línea!

Este es un tren equivalente a {∊⍵,(⊂⍵)~¨(,\⍺⊂⍨1,2>/⍺⍋⍵)}

da la permutación del argumento derecho en el argumento izquierdo

1,2>/comparar pares consecutivos con >y anteponer un 1

⍺⊂⍨use la máscara booleana anterior para dividir en grupos; 1s en la máscara marcan el inicio de un nuevo grupo

,\ concatenaciones acumulativas de los grupos

(⊂⍵)~¨ complemento de cada uno con respecto a

⍵, anteponer

aplanar como una sola cadena

ngn
fuente
4

Lote, 155 bytes

@set/pt=
@set/ps=
@set r=
:l
@set c=%s:~,1%
@set r=%r%%c%
@if %c%==%t:~,1% set t=%t:~1%&set c=
@set s=%s:~1%%c%
@if not "%t%"=="" goto l
@echo %r%

Toma el objetivo y se apila como entradas en STDIN.

Neil
fuente
4

JavaScript (ES6), 54 bytes

Toma el objetivo como una cadena y la pila como una matriz de caracteres. Devuelve una cadena.

f=(t,[c,...s])=>t&&c+f(t.slice(c==t[0]||!s.push(c)),s)

Casos de prueba

¿Cómo?

En cada iteración, extraemos el carácter cen la parte superior de la pila y lo agregamos al resultado final. Luego realizamos una llamada recursiva cuyos parámetros dependen del resultado de c == t[0], dondet[0] es el siguiente carácter esperado.

Si ccoincide t[0]:

  • eliminamos cde la cadena de destino pasandot.slice(1)
  • quitamos cde la pila pasando ssin cambios

Si cno coincide t[0]:

  • Dejamos la cadena objetivo sin cambios al pasar t.slice(0)
  • empujamos chacia atrás al final de la pila
Arnauld
fuente
3

Python 2 , 73 bytes

f=lambda o,s,S='':s and f(o[s[0]==o[0]:],s[1:]+s[:s[0]!=o[0]],S+s[0])or S

Pruébalo en línea!

Sospecho que esto es muy golfable.

Erik el Outgolfer
fuente
3

Haskell , 49 46 bytes

q@(a:b)#(c:d)|a==c=a:b#d|e<-d++[c]=c:q#e
a#_=a

Pruébalo en línea!

Bastante sencillo. El argumento izquierdo es el "objetivo" y el derecho es la pila. Si la cabeza de la portería coincide con la parte superior de la pila, la anteponemos y repetimos con el resto de la portería y la pila (sin volver a agregar el elemento en la parte superior). De lo contrario, anteponemos el elemento superior y repetimos con el mismo objetivo, leyendo el elemento superior hasta el final de la pila. Cuando el objetivo está vacío, la coincidencia de patrones elige la segunda línea y se devuelve la lista vacía.

EDITAR: -3 bytes gracias a @GolfWolf y @Laikoni!

usuario1472751
fuente
1
47 caracteres
Cristian Lupascu
También 47
Cristian Lupascu
1
46 bytes
Laikoni
1
@GolfWolf tu segunda solución (y la de Laikoni) no funciona. Produce "ytrty" en lugar de "yrtyry" debido a la precedencia del operador con (:) y (#)
user1472751
1

Limpio , 85 bytes

import StdEnv
g l[u:v][a:b]|a==u=g[a:l]v b=g[a:l][u:v](b++[a])
g l[]_=reverse l
f=g[]

Pruébalo en línea!

Define la ftoma parcial de funciones [Char]y [Char], donde el primer argumento es el objetivo y el segundo es la pila.

Οurous
fuente
1

Java 8, 88 bytes

a->b->{for(int c:a)for(char t=0;c!=t;System.out.print(t)){t=b.poll();if(c!=t)b.add(t);}}

Entradas como char[]y java.util.LinkedList<Character>( java.util.Queueimplementación)

Explicación:

Pruébalo en línea.

a->b->{                        // Method with two parameters and no return-type
  for(int c:a)                 //  Loop over the characters of the char-array
    for(char t=0;c!=t;         //   Inner loop until we've found the character in the queue
        System.out.print(t)){  //     After every iteration: print the char `t`
      t=b.poll();              //    Remove the top of the queue, and save it in `t`
      if(c!=t)                 //    If this is not the character we're looking for:
        b.add(t);}}            //     Add it at the end of the queue again
Kevin Cruijssen
fuente
1

> <> , 38 32 bytes

Editar: Teal pelican tiene un ><>enfoque mucho mejor aquí que intercambia los métodos de entrada

0[i:0(1$.
\~~l]1+{$[&
/?=&:&:o:{

Pruébalo en línea!

Toma el orden de las letras a través de la -sbandera y la pila a través de la entrada.

Cómo funciona:

0[.... Creates a new empty stack
...... This puts the order of the letters safely away
......

..i:0(1$. Takes input until EOF (-1). This means input is in reverse
..~...    And then teleports to the ~ on this line
......

......      Gets the first character from the beginning of the order
\.~l]1+{$[& And stores it in the register before going to the next line
/.....

......     Output the bottom of the stack
......     Checks if the bottom of the stack is equal to the current character
/?=&:&:o:{ If so, go to the second line, else cycle the stack and repeat

0.....      Pop the extra 0 we collected
\~~l]1+{$[& Pop the value that was equal and get the next character from the order
/.....      And go down to the last line. This will end with an error (which could be avoid with a mere 4 extra bytes
Jo King
fuente
1

> <> , 21 16 bytes

i$\~~
=?\$:{::o@

Pruébalo en línea!

El flujo cambió para utilizar los espacios vacíos y eliminar el redireccionamiento de código adicional. (-5 bytes) - Gracias a @JoKing

> <> , 21 bytes

i:{:@=?v:o$!
o~i00. >

Pruébalo en línea!

La otra respuesta> <> se puede encontrar aquí.

Explicación

La pila comienza con un conjunto inicial de caracteres usando la bandera -s. La entrada es el orden de caracteres dado por el usuario. Esta explicación seguirá el flujo del código.

i$\        : Take input, swap the top 2 stack items then move to line 2;
             [1,2,3] -> [1,2,4,3]
  \$:      : Swap the top 2 stack items then duplicate the top item;
             [1,2,4,3] -> [1,2,3,4,4]
     {::o  : Move the stack items 1 left then duplicate the stack top twice and print one;
             [1,2,3,4,4] -> [2,3,4,4,1,1]
=?\      @ : Swap the top three stack items left 1 then do an equal comparison, if equality move to line 1 else continue;
             [2,3,4,4,1,1] -> [2,3,4,1,1,4] -> [2,3,4,1]
  \~~      : Remove the top 2 stack items;
             [2,3,4,1] -> [2,3]
Pelícano verde azulado
fuente
Oh sí, ingresarlo de esa manera tiene más sentido jajaja
Jo King
¿Qué tal 17 bytes ?
Jo King
1
@JoKing: un cambio muy agradable para hacer que esas rutas redundantes desaparezcan, aunque no pude resistirme a quitarme un byte adicional: P
Teal pelican
0

Perl, 62 bytes

sub{$_=$_[1];for$x(@{$_[0]}){/\Q$x\E/;$z.="$`$&";$_="$'$`"}$z}

Toma su primer argumento, el orden, como una lista de caracteres y su segundo, la pila, como una cadena.

Sin golf:

sub {
    $_ = $_[1];
    for $x (@{$_[0]}) {
        /\Q$_\E/;
        $z.="$`$&";
        $_ = "$'$`"
    }
    $z
}

¿Alguna vez te has preguntado para qué sirven todas esas oscuras variables regex? Claramente, fueron diseñados para este desafío exacto. Coincidimos con el personaje actual $x(que desafortunadamente tiene que escaparse en caso de que sea un carácter especial regex). Esto divide convenientemente la cadena en "antes del partido" $`, "el partido" $&y "después del partido" $'. En la búsqueda cíclica, vimos claramente a todos los personajes antes del partido y los volvimos a colocar en la pila. También vimos el personaje actual pero no lo volvimos a poner. Entonces agregamos "antes del partido" a la lista "visto" $zy construimos la pila de "después del partido" seguido de "antes del partido".

Silvio Mayolo
fuente
0

SNOBOL4 (CSNOBOL4) , 98 bytes

	S =INPUT
	L =INPUT
R	S LEN(1) . X REM . S	:F(END)
	OUTPUT =X
	L POS(0) X =	:S(R)
	S =S X	:(R)
END

Pruébalo en línea!

Imprime cada letra en una nueva línea. Use esta versión para imprimir todo en la misma línea. Toma la entrada como pila, luego objetivo, separada por una nueva línea.

	S =INPUT			;*read stack
	L =INPUT			;*read letters
R	S LEN(1) . X REM . S	:F(END)	;*set X to the first letter of S and S to the remainder. If S is empty, goto END.
	OUTPUT =X			;*output X
	L POS(0) X =	:S(R)		;*if the first character of L matches X, remove it and goto R
	S =S X	:(R)			;*else put X at the end of S and goto R
END
Giuseppe
fuente
0

Perl, 44 bytes

Incluye +4para-lF

Dé entrada como en STDIN como destino y luego apile (este es el orden inverso de los ejemplos):

(echo daceb; echo aecdb) | perl -lF -E '$a=<>;say,$a=~s/^\Q$_//||push@F,$_ for@F'

Si no le importa una nueva línea final, esto 40funciona:

(echo daceb; echo aecdb) | perl -plE '$_=<>=~s%.%s/(.*)\Q$&//s;$_.=$1;$&%reg'
Ton Hospel
fuente