Aide mon fils à retrouver ses lettres

17

Contexte

Basé sur un jeu que mon fils de quatre ans a obtenu de son rabbin.

Le «but» est de «trouver» les lettres dans un ordre donné, par exemple aecdb. On vous donne une pile de cartes-lettres, par exemple daceb. Vous ne pouvez rechercher dans la pile que dans l'ordre indiqué, bien que cycliquement. Lorsque vous rencontrez une lettre dont vous avez besoin, vous la retirez de la pile.

Objectif

Étant donné un ordre et une pile (permutations sans doublons les uns des autres), trouvez la séquence des lettres de la pile supérieure (tout est ASCII imprimable) que vous voyez en jouant.

Exemple pas à pas

Nous devons trouver la commande aecdb, compte tenu de la pile daceb:

Haut de la pile d: Non ce que nous cherchons ( a), donc nous l' ajouterons à la séquence: det alternons pour obtenir la pile: acebd.

Haut de la pile a: Oui! si l' on ajoute à la séquence: daet le retirer de la pile: cebd.

Haut de la pile c: Non ce que nous cherchons ( e), donc nous l' ajouterons à la séquence: dacet alternons pour obtenir la pile: ebdc.

Haut de la pile e: Oui! si l' on ajoute à la séquence: daceet le retirer de la pile: bdc.

Haut de la pile b: Non ce que nous cherchons ( c), donc nous l' ajouterons à la séquence: dacebet alternons pour obtenir la pile: dcb.

Haut de la pile d: Non ce que nous cherchons ( c), donc nous l' ajouterons à la séquence: dacebdet alternons pour obtenir la pile: cbd.

Haut de la pile c: Oui! si l' on ajoute à la séquence: dacebdcet le retirer de la pile: bd.

Haut de la pile b: Non ce que nous cherchons ( d), donc nous l' ajouterons à la séquence: dacebdcbet alternons pour obtenir la pile: db.

Haut de la pile d: Oui! si l' on ajoute à la séquence: dacebdcbdet le retirer de la pile: b.

Haut de la pile b: Oui! si l' on ajoute à la séquence: dacebdcbdbet le retirer de la pile: .

Et nous avons terminé. Le résultat est dacebdcbdb.

Implémentation de référence

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

Essayez-le en ligne!

Cas de test

try, yrtyrtyry

1234, 43214321432434

ABCDEFGHIJKLMNOPQRSTUVWXYZ, RUAHYKCLQZXEMPBWGDIOTVJNSFRUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ

?, ??

a, a a a

abcd, abcdabcd

Adam
la source

Réponses:

5

Trois méthodes assez différentes donnent des nombres d'octets égaux.

Python 2 , 59 octets

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

Essayez-le en ligne!

Imprime chaque caractère sur sa propre ligne.


Python 2 , 59 octets

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

Essayez-le en ligne!

Prend des listes en entrée et sort une liste.


Python 3 , 59 octets

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

Essayez-le en ligne!

xnor
la source
1
Hm, je me méfie des deux premières versions ... pourquoi 99spécifiquement?
Erik the Outgolfer
@EriktheOutgolger C'est au moins le nombre de caractères ASCII imprimables, tout comme au moins la longueur de chaque entrée.
xnor
5

APL (Dyalog Classic) , 21 octets

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

Essayez-le en ligne!

Ceci est un train équivalent à {∊⍵,(⊂⍵)~¨(,\⍺⊂⍨1,2>/⍺⍋⍵)}

donne la permutation de l'argument droit dans l'argument gauche

1,2>/comparer des paires consécutives avec >et ajouter un 1

⍺⊂⍨utilisez le masque booléen ci-dessus pour vous diviser en groupes; 1s dans le masque marque le début d'un nouveau groupe

,\ concaténations cumulatives des groupes

(⊂⍵)~¨ complément de chacun par rapport à

⍵, ajouter

aplatir comme une seule chaîne

ngn
la source
4

Lot, 155 octets

@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%

Prend la cible et la pile comme entrées sur STDIN.

Neil
la source
4

JavaScript (ES6), 54 octets

Prend la cible comme une chaîne et la pile comme un tableau de caractères. Renvoie une chaîne.

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

Cas de test

Comment?

À chaque itération, nous extrayons le caractère cen haut de la pile et l'ajoutons au résultat final. Nous effectuons ensuite un appel récursif dont les paramètres dépendent du résultat de c == t[0], où t[0]est le prochain caractère attendu.

Si ccorrespond t[0]:

  • on retire cde la chaîne cible en passantt.slice(1)
  • on retire cde la pile en passants inchangé

Si cne correspond past[0] :

  • nous laissons la chaîne cible inchangée en passant t.slice(0)
  • on repousse cà la fin de la pile
Arnauld
la source
3

Python 2 , 73 octets

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

Essayez-le en ligne!

Je soupçonne que c'est très jouable au golf.

Erik le Outgolfer
la source
3

Haskell , 49 46 octets

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

Essayez-le en ligne!

Assez simple. L'argument de gauche est le "but" et celui de droite est la pile. Si la tête du but correspond au haut de la pile, nous le rajoutons au début et nous reproduisons avec le reste du but et la pile (sans rajouter l'élément en haut). Sinon, nous ajoutons l'élément supérieur et réapparaissons avec le même objectif, en lisant l'élément supérieur jusqu'à la fin de la pile. Lorsque l'objectif est vide, la correspondance de modèle choisit la deuxième ligne et la liste vide est renvoyée.

EDIT: -3 octets grâce à @GolfWolf et @Laikoni!

user1472751
la source
1
47 caractères
Cristian Lupascu
Aussi 47
Cristian Lupascu
1
46 octets
Laikoni
1
@GolfWolf votre deuxième solution (et celle de Laikoni) ne fonctionne pas. Il produit "ytrty" au lieu de "yrtyry" en raison de la priorité de l'opérateur avec (:) et (#)
user1472751
1

Propre , 85 octets

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[]

Essayez-le en ligne!

Définit la fprise de fonction partielle [Char]et [Char], où le premier argument est la cible et le second la pile.

Οurous
la source
1

Java 8, 88 octets

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

Entrées au fur char[]et à mesure java.util.LinkedList<Character>( java.util.Queuemise en œuvre)

Explication:

Essayez-le en ligne.

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
la source
1

> <> , 38 32 octets

Edit: le pélican bleu canard a une bien meilleure ><>approche ici qui échange les méthodes d'entrée

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

Essayez-le en ligne!

Prend l'ordre des lettres à travers le -sdrapeau et la pile à travers l'entrée.

Comment ça fonctionne:

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
la source
1

> <> , 21 16 octets

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

Essayez-le en ligne!

Le flux a été modifié pour utiliser les espaces vides et supprimer le réacheminement du code supplémentaire. (-5 octets) - Merci à @JoKing

> <> , 21 octets

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

Essayez-le en ligne!

L'autre> <> réponse peut être trouvée ici.

Explication

La pile commence par un ensemble initial de caractères utilisant le drapeau -s. L'entrée est l'ordre de caractères donné par l'utilisateur. Cette explication suivra le flux du code.

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]
Pélican bleu canard
la source
Oh ouais, le saisir de cette façon a plus de sens lol
Jo King
Que diriez-vous de 17 octets ?
Jo King
1
@JoKing - Très bon changement pour faire disparaître ces routages redondants, je n'ai pas pu résister à prendre un octet supplémentaire: P
Pelican sarcelle
0

Perl, 62 octets

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

Prend son premier argument, l'ordre, comme une liste de caractères et son second, la pile, comme une chaîne.

Non golfé:

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

Vous êtes-vous déjà demandé à quoi servaient toutes ces variables d'expression rationnelle obscures? De toute évidence, ils ont été conçus pour ce défi précis. Nous correspondons au caractère actuel $x(qui doit malheureusement être échappé dans le cas où il s'agit d'un caractère spécial regex). Cela fractionne commodément la chaîne en "avant la correspondance" $`, "la correspondance" $&et "après la correspondance" $'. Dans la recherche cyclique, nous avons clairement vu tous les personnages avant le match et les avons remis dans la pile. Nous avons également vu le personnage actuel mais ne l'avons pas remis. Nous ajoutons donc "avant la correspondance" à la liste "vu" $zet construisons la pile à partir de "après la correspondance" suivie de "avant la correspondance".

Silvio Mayolo
la source
0

SNOBOL4 (CSNOBOL4) , 98 octets

	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

Essayez-le en ligne!

Imprime chaque lettre sur une nouvelle ligne. Utilisez cette version pour tout imprimer sur la même ligne. Prend l'entrée comme pile, puis cible, séparée par une nouvelle ligne.

	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
la source
0

Perl, 44 octets

Comprend +4pour-lF

Donnez une entrée comme sur STDIN comme cible puis empilez (c'est l'ordre inverse des exemples):

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

Si cela ne vous dérange pas une nouvelle ligne de fin, cela 40fonctionne:

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