tło

Na podstawie gry, którą mój czterolatek dostał od swojego rabina.

„Celem” jest „znalezienie” liter w określonej kolejności, np aecdb. Otrzymujesz stos kart listowych, np daceb. Możesz przeszukiwać stos tylko w podanej kolejności, aczkolwiek cyklicznie. Kiedy napotkasz potrzebny list, wyjmiesz go ze stosu.

Cel

Biorąc pod uwagę kolejność i stos (wzajemne permutacje bez duplikatów), znajdź sekwencję liter najwyższego stosu (wszystkie to ASCII do wydrukowania), które widzisz podczas gry.

Przykład krok po kroku

Musimy znaleźć zamówienie aecdb, biorąc pod uwagę stos daceb:

Na górę stosu d: Nie to, czego szukasz ( a), więc możemy go dodać do sekwencji: di obracać, aby uzyskać stos: acebd.

Szczyt stosu a: Tak! więc dodać go do sekwencji: dai usunąć go ze stosu: cebd.

Na górę stosu c: Nie to, czego szukasz ( e), więc możemy go dodać do sekwencji: daci obracać, aby uzyskać stos: ebdc.

Szczyt stosu e: Tak! więc dodać go do sekwencji: dacei usunąć go ze stosu: bdc.

Na górę stosu b: Nie to, czego szukasz ( c), więc możemy go dodać do sekwencji: dacebi obracać, aby uzyskać stos: dcb.

Na górę stosu d: Nie to, czego szukasz ( c), więc możemy go dodać do sekwencji: dacebdi obracać, aby uzyskać stos: cbd.

Szczyt stosu c: Tak! więc dodać go do sekwencji: dacebdci usunąć go ze stosu: bd.

Na górę stosu b: Nie to, czego szukasz ( d), więc możemy go dodać do sekwencji: dacebdcbi obracać, aby uzyskać stos: db.

Szczyt stosu d: Tak! więc dodać go do sekwencji: dacebdcbdi usunąć go ze stosu: b.

Szczyt stosu b: Tak! więc dodać go do sekwencji: dacebdcbdbi usunąć go ze stosu: .

I skończone. Rezultat jest dacebdcbdb.

Realizacja referencyjna

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

Wypróbuj online!

Przypadki testowe

try, yrt→yrtyry

1234, 4321→4321432434

ABCDEFGHIJKLMNOPQRSTUVWXYZ, RUAHYKCLQZXEMPBWGDIOTVJNSF→RUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ

?, ?→?

a, a →a a

abcd, abcd→abcd

Trzy dość różne metody dają równe liczby bajtów.

Python 2 , 59 bajtów

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

Wypróbuj online!

Drukuje każdy znak we własnej linii.

Python 2 , 59 bajtów

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

Wypróbuj online!

Pobiera listy jako dane wejściowe i wyświetla listę.

Python 3 , 59 bajtów

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

Wypróbuj online!

APL (Dyalog Classic) , 21 bajtów

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

Wypróbuj online!

Jest to pociąg równoważny {∊⍵,(⊂⍵)~¨(,\⍺⊂⍨1,2>/⍺⍋⍵)}

⍋daje permutację prawego argumentu ⍵w lewym argumencie⍺

1,2>/porównaj kolejne pary >i przygotuj 1

⍺⊂⍨użyj powyższej maski logicznej, aby podzielić ⍺na grupy; 1s w masce oznaczają początek nowej grupy

,\ skumulowane konkatenacje grup

(⊂⍵)~¨ uzupełnienie każdego w odniesieniu do ⍵

⍵, prepend ⍵

∊ spłaszczyć jako pojedynczy ciąg

Partia, 155 bajtów

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

Bierze cel i stos jako dane wejściowe w STDIN.

JavaScript (ES6), 54 bajty

Bierze cel jako ciąg, a stos jako tablicę znaków. Zwraca ciąg.

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

Przypadki testowe

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

W jaki sposób?

Przy każdej iteracji wyodrębniamy postać cna wierzchu stosu i dołączamy do końcowego wyniku. Następnie wykonujemy wywołanie rekurencyjne, którego parametry zależą od wyniku c == t[0], gdzie t[0]jest następny oczekiwany znak.

Jeśli cpasuje t[0]:

• usuwamy cz ciągu docelowego, przekazująct.slice(1)
• usuwamy cze stosu, przekazując sbez zmian

Jeśli cnie pasuje t[0]:

• przekazujemy ciąg docelowy bez zmian t.slice(0)
• odpychamy cna końcu stosu

Python 2 , 73 bajty

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

Wypróbuj online!

Podejrzewam, że to bardzo gra w golfa.

Python 2 , 65 bajtów

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

Wypróbuj online!

Haskell , 49 46 bajtów

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

Wypróbuj online!

Dość proste. Lewy argument to „cel”, a prawy stos. Jeśli główka bramki pasuje do górnej części stosu, przygotowujemy ją i powtarzamy z resztą bramki i stosu (bez ponownego dodawania przedmiotu na górze). W przeciwnym razie dodamy najwyższy element i powtórzymy z tym samym celem, czytając najwyższy element na końcu stosu. Gdy cel jest pusty, dopasowanie wzorca wybiera drugą linię i pusta lista jest zwracana.

EDYCJA: -3 bajty dzięki @GolfWolf i @Laikoni!

Czysty , 85 bajtów

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

Wypróbuj online!

Definiuje fprzyjmowanie funkcji częściowej, [Char]a [Char]gdzie pierwszy argument jest celem, a drugi stosem.

Java 8, 88 bajtów

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

Dane wejściowe jako char[]i java.util.LinkedList<Character>(java.util.Queue wdrożenie)

Wyjaśnienie:

Wypróbuj online.

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 bajtów

Edycja: Pelikan turkusowy ma tutaj znacznie lepsze ><>podejście , które zamienia metody wprowadzania

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

Wypróbuj online!

Bierze porządek liter przez -sflagę, a stos przez wejście.

Jak to działa:

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 bajtów

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

Wypróbuj online!

> <> , 21 16 bajtów

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

Wypróbuj online!

Zmieniono przepływ, aby wykorzystać puste miejsca i usunąć dodatkowe przekierowywanie kodu. (-5 bajtów) - Dzięki @JoKing

> <> , 21 bajtów

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

Wypróbuj online!

Inną odpowiedź> <> można znaleźć tutaj.

Wyjaśnienie

Stos zaczyna się od początkowego zestawu znaków przy użyciu flagi -s. Dane wejściowe to kolejność znaków podana przez użytkownika. To wyjaśnienie będzie zgodne z przepływem kodu.

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 bajty

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

Pobiera swój pierwszy argument, kolejność, jako listę znaków, a drugi stos, jako ciąg.

Nie golfowany:

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

Czy zastanawiałeś się kiedyś, po co były te wszystkie niejasne zmienne regularne? Najwyraźniej zostały zaprojektowane do tego właśnie wyzwania. Dopasowujemy obecną postać $x(którą niestety trzeba uciec, jeśli jest to znak specjalny wyrażenia regularnego). To wygodnie dzieli ciąg na „przed dopasowaniem” $`, „dopasowaniem” $&i „po dopasowaniu” $'. Podczas cyklicznego wyszukiwania wyraźnie widzieliśmy każdą postać przed meczem i odkładaliśmy ją z powrotem na stos. Widzieliśmy również obecną postać, ale jej nie przywróciliśmy. Tak więc dodajemy „przed dopasowaniem” do listy „widziane” $zi konstruujemy stos z „po dopasowaniu”, a następnie „przed dopasowaniem”.

SNOBOL4 (CSNOBOL4) , 98 bajtów

	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

Wypróbuj online!

Drukuje każdą literę na nowej linii. Użyj tej wersji, aby uzyskać wszystko do drukowania w tej samej linii. Pobiera dane wejściowe jako stos, a następnie cel, oddzielone znakiem nowej linii.

	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 bajty

Obejmuje +4 dla-lF

Podaj dane wejściowe jak na STDIN jako cel, a następnie stos (w odwrotnej kolejności z przykładów):

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

Jeśli nie przeszkadza ci końcowy znak nowej linii, 40działa to :

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