Hintergrund

Basierend auf einem Spiel, das mein Vierjähriger von seinem Rabbiner bekommen hat.

Das "Ziel" ist es, die Buchstaben in einer bestimmten Reihenfolge "zu finden", z aecdb. Sie erhalten einen Stapel Briefkarten, zdaceb . Sie können den Stapel nur in der angegebenen Reihenfolge durchsuchen, wenn auch zyklisch. Wenn Sie einen Brief finden, den Sie brauchen, nehmen Sie diesen aus dem Stapel.

Zielsetzung

Suchen Sie bei gegebener Reihenfolge und einem Stapel (duplikationsfreie Permutationen) die Reihenfolge der obersten Stapelbuchstaben (alles druckbare ASCII-Zeichen), die Sie während des Spiels sehen.

Beispiel Schritt für Schritt

Wir müssen die Reihenfolge aecdbanhand des Stapels finden daceb:

Top of Stack d: Nicht das, was wir suchen ( a), so dass wir es mit der Sequenz hinzufügen: dund drehen Sie den Stapel erhalten: acebd.

Stapeloberseite a: Ja! Also fügen wir es der Sequenz hinzu: daund entfernen es vom Stapel:cebd.

Top of Stack c: Nicht das, was wir suchen ( e), so dass wir es mit der Sequenz hinzufügen: dacund drehen Sie den Stapel erhalten: ebdc.

Stapeloberseite e: Ja! so dass wir es mit der Sequenz hinzufügen: daceund entfernen Sie sie aus dem Stapel: bdc.

Top of Stack b: Nicht das, was wir suchen ( c), so dass wir es mit der Sequenz hinzufügen: dacebund drehen Sie den Stapel erhalten: dcb.

Top of Stack d: Nicht das, was wir suchen ( c), so dass wir es mit der Sequenz hinzufügen: dacebdund drehen Sie den Stapel erhalten: cbd.

Stapeloberseite c: Ja! so dass wir es mit der Sequenz hinzufügen: dacebdcund entfernen Sie sie aus dem Stapel: bd.

Top of Stack b: Nicht das, was wir suchen ( d), so dass wir es mit der Sequenz hinzufügen: dacebdcbund drehen Sie den Stapel erhalten: db.

Stapeloberseite d: Ja! so dass wir es mit der Sequenz hinzufügen: dacebdcbdund entfernen Sie sie aus dem Stapel: b.

Stapeloberseite b: Ja! so dass wir es mit der Sequenz hinzufügen: dacebdcbdbund entfernen Sie sie aus dem Stapel: .

Und wir sind fertig. Das Ergebnis ist dacebdcbdb.

Referenzimplementierung

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

Probieren Sie es online!

Testfälle

try, yrt→yrtyry

1234, 4321→4321432434

ABCDEFGHIJKLMNOPQRSTUVWXYZ, RUAHYKCLQZXEMPBWGDIOTVJNSF→RUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ

?, ?→?

a, a →a a

abcd, abcd→abcd

Drei ziemlich unterschiedliche Methoden geben gleiche Bytezahlen an.

Python 2 , 59 Bytes

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

Probieren Sie es online!

Gibt jedes Zeichen in einer eigenen Zeile aus.

Python 2 , 59 Bytes

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

Probieren Sie es online!

Übernimmt Listen als Eingabe und gibt eine Liste aus.

Python 3 , 59 Bytes

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

Probieren Sie es online!

APL (Dyalog Classic) , 21 Byte

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

Probieren Sie es online!

Dies ist ein Zug, der dem entspricht {∊⍵,(⊂⍵)~¨(,\⍺⊂⍨1,2>/⍺⍋⍵)}

⍋Gibt die Permutation des rechten Arguments ⍵im linken Argument an⍺

1,2>/Vergleichen Sie aufeinanderfolgende Paare mit >und stellen Sie eine 1 voran

⍺⊂⍨Verwenden Sie die obige boolesche Maske, um sie ⍺in Gruppen aufzuteilen . Einsen in der Maske markieren den Beginn einer neuen Gruppe

,\ kumulative Verkettungen der Gruppen

(⊂⍵)~¨ Komplement von jedem in Bezug auf ⍵

⍵, voranstellen ⍵

∊ als einzelne Zeichenfolge abflachen

Batch, 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%

Nimmt das Ziel und den Stapel als Eingaben für STDIN.

JavaScript (ES6), 54 Byte

Nimmt das Ziel als String und den Stack als Array von Zeichen. Gibt eine Zeichenfolge zurück.

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

Testfälle

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

console.log(f('try',[...'yrt']))
console.log(f('1234',[...'4321']))
console.log(f('aecdb',[...'daceb']))
console.log(f('ABCDEFGHIJKLMNOPQRSTUVWXYZ',[...'RUAHYKCLQZXEMPBWGDIOTVJNSF']))
console.log(f('?',[...'?']))
console.log(f(' a',[...'a ']))
console.log(f('abcd',[...'abcd']))

Wie?

Bei jeder Iteration extrahieren wir das Zeichen coben im Stapel und hängen es an das Endergebnis an. Wir führen dann einen rekursiven Aufruf durch, dessen Parameter vom Ergebnis abhängen c == t[0], wo t[0]das nächste erwartete Zeichen ist.

Wenn cÜbereinstimmungen t[0]:

• wir entfernen c von der Zielzeichenfolge durch Übergebent.slice(1)
• Wir entfernen uns caus dem Stapel, indem wir sunverändert passieren

Wenn cnicht übereinstimmt t[0]:

• Wir lassen die Zielzeichenfolge unverändert, indem wir übergeben t.slice(0)
• Wir drücken cam Ende des Stapels zurück

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

Probieren Sie es online!

Ich vermute, das ist sehr gut zum Golfen geeignet.

Python 2 , 65 Bytes

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

Probieren Sie es online!

Haskell , 49 46 Bytes

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

Probieren Sie es online!

Ziemlich Einfach. Das linke Argument ist das "Ziel" und das rechte ist der Stapel. Wenn der Kopf des Ziels mit der Spitze des Stapels übereinstimmt, stellen wir ihn voran und wiederholen ihn mit dem Rest des Ziels und des Stapels (ohne den oben liegenden Gegenstand erneut hinzuzufügen). Andernfalls stellen wir das oberste Element voran und wiederholen es mit demselben Ziel, indem wir das oberste Element bis zum Ende des Stapels lesen. Wenn das Ziel leer ist, wählt der Mustervergleich die zweite Zeile und die leere Liste wird zurückgegeben.

BEARBEITEN: -3 Bytes dank @GolfWolf und @Laikoni!

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

Probieren Sie es online!

Definiert die Teilfunktion ftake [Char]und [Char], wobei das erste Argument das Ziel und das zweite der Stapel ist.

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

Eingänge als char[]und java.util.LinkedList<Character>( java.util.QueueImplementierung)

Erläuterung:

Probieren Sie es online aus.

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

> <> , 38 32 Bytes

Edit: Teal Pelikan hat einen viel besseren ><>Ansatz hier , dass bei Swaps die Eingabemethoden

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

Probieren Sie es online!

Übernimmt die Reihenfolge der Buchstaben durch die -s Flag und den Stapel durch die Eingabe.

Wie es funktioniert:

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

Perl 5 , 42 + 2 ( -pl) = 44 Byte

for$i(<>=~/./g){/$i/;$\.=$`.$i;$_=$'.$`}}{

Probieren Sie es online!

> <> , 21 16 Bytes

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

Probieren Sie es online!

Der Ablauf wurde geändert, um die leeren Bereiche zu nutzen und zusätzliche Code-Umleitungen zu entfernen. (-5 Bytes) - Danke an @JoKing

> <> , 21 Bytes

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

Probieren Sie es online!

Die andere> <> Antwort finden Sie hier.

Erläuterung

Der Stapel beginnt mit einem ersten Zeichensatz, der das Flag -s verwendet. Die Eingabe ist die vom Benutzer angegebene Zeichenreihenfolge. Diese Erklärung folgt dem Ablauf des Codes.

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]

Perl, 62 Bytes

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

Nimmt sein erstes Argument, die Reihenfolge, als Liste von Zeichen und sein zweites, den Stapel, als Zeichenfolge.

Ungolfed:

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

Sie fragen sich jemals, wofür all diese obskuren Regex-Variablen gedacht waren? Offensichtlich waren sie genau für diese Herausforderung ausgelegt. Wir stimmen mit dem aktuellen Zeichen überein $x(das muss leider ausgeblendet werden, falls es sich um ein reguläres Sonderzeichen handelt). Dies teilt die Zeichenfolge zweckmäßigerweise in "vor dem Spiel" $`, "das Spiel" $&und "nach dem Spiel" auf $'. Bei der zyklischen Suche haben wir jeden Charakter vor dem Match klar gesehen und wieder in den Stapel gelegt. Wir haben auch den aktuellen Charakter gesehen, ihn aber nicht zurückgesetzt. Also hängen wir "vor dem Spiel" an die "gesehen" -Liste an $zund konstruieren den Stack aus "nach dem Spiel" und "vor dem Spiel".

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

Probieren Sie es online!

Druckt jeden Buchstaben in eine neue Zeile. Verwenden Sie diese Version , um alles in einer Zeile zu drucken. Nimmt die Eingabe als Stapel und dann als Ziel, getrennt durch eine neue Zeile.

	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

Perl, 44 Bytes

Beinhaltet +4für-lF

Geben Sie als Ziel "STDIN" ein und stapeln Sie dann (in umgekehrter Reihenfolge wie in den Beispielen):

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

Wenn Ihnen eine nachgestellte Zeile nichts ausmacht, 40funktioniert Folgendes :

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