Фон

По мотивам игры мой четырехлетний получил от своего раввина.

«Цель» - «найти» буквы в заданном порядке, например aecdb. Вам дают стопку писем, например daceb. Поиск в стеке возможен только в указанном порядке, хотя и циклически. Когда вы встречаете нужное письмо, вы берете его из стопки.

Задача

При заданном порядке и стопке (перестановки без дубликатов друг друга) найдите последовательность букв верхнего стека (это все печатные ASCII), которые вы видите во время игры.

Пошаговый пример

Нам нужно найти порядок aecdb, учитывая стек daceb:

Верх стека d: Не то , что мы ищем ( a), поэтому мы добавим его в последовательности: dи повернуть , чтобы получить стек: acebd.

Вершина стека a: да! поэтому мы добавим его в следующей последовательности: daи удалить его из стека: cebd.

Верх стека c: Не то , что мы ищем ( e), поэтому мы добавим его в последовательности: dacи повернуть , чтобы получить стек: ebdc.

Вершина стека e: да! поэтому мы добавим его в следующей последовательности: daceи удалить его из стека: bdc.

Верх стека b: Не то , что мы ищем ( c), поэтому мы добавим его в последовательности: dacebи повернуть , чтобы получить стек: dcb.

Верх стека d: Не то , что мы ищем ( c), поэтому мы добавим его в последовательности: dacebdи повернуть , чтобы получить стек: cbd.

Вершина стека c: да! поэтому мы добавим его в следующей последовательности: dacebdcи удалить его из стека: bd.

Верх стека b: Не то , что мы ищем ( d), поэтому мы добавим его в последовательности: dacebdcbи повернуть , чтобы получить стек: db.

Вершина стека d: да! поэтому мы добавим его в следующей последовательности: dacebdcbdи удалить его из стека: b.

Вершина стека b: да! поэтому мы добавим его в следующей последовательности: dacebdcbdbи удалить его из стека: .

И мы сделали. Результат есть dacebdcbdb.

Ссылочная реализация

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

Попробуйте онлайн!

Контрольные примеры

try, yrt→yrtyry

1234, 4321→4321432434

ABCDEFGHIJKLMNOPQRSTUVWXYZ, RUAHYKCLQZXEMPBWGDIOTVJNSF→RUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ

?, ?→?

a, a →a a

abcd, abcd→abcd

Три довольно разных метода дают одинаковое количество байтов.

Python 2 , 59 байт

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

Попробуйте онлайн!

Печатает каждый символ в отдельной строке.

Python 2 , 59 байт

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

Попробуйте онлайн!

Принимает списки в качестве входных данных и выводит список.

Python 3 , 59 байт

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

Попробуйте онлайн!

APL (Dyalog Classic) , 21 байт

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

Попробуйте онлайн!

Это поезд, эквивалентный {∊⍵,(⊂⍵)~¨(,\⍺⊂⍨1,2>/⍺⍋⍵)}

⍋дает перестановку правого аргумента ⍵в левый аргумент⍺

1,2>/сравнить последовательные пары с >и добавить 1

⍺⊂⍨используйте вышеупомянутую логическую маску для разделения ⍺на группы; 1 в маске отмечают начало новой группы

,\ совокупные объединения групп

(⊂⍵)~¨ дополнение каждого относительно ⍵

⍵, перед именем ⍵

∊ сплющить как одну строку

Пакетный, 155 байт

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

Принимает цель и складывается как входные данные на STDIN.

JavaScript (ES6), 54 байта

Принимает цель как строку, а стек как массив символов. Возвращает строку.

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

Контрольные примеры

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

Как?

На каждой итерации мы извлекаем символ cв верхней части стека и добавляем его к конечному результату. Затем мы выполняем рекурсивный вызов, параметры которого зависят от результата c == t[0], где t[0]следующий ожидаемый символ.

Если cсовпадает t[0]:

• мы удаляем cиз целевой строки, передаваяt.slice(1)
• мы удаляем cиз стека, передавая sбез изменений

Если cне совпадает t[0]:

• мы оставляем целевую строку неизменной, передавая t.slice(0)
• мы отталкиваем cв конце стека

Python 2 , 73 байта

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

Попробуйте онлайн!

Я подозреваю, что это очень хорошо для игры в гольф.

Python 2 , 65 байт

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

Попробуйте онлайн!

Haskell , 49 46 байтов

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

Попробуйте онлайн!

Довольно просто. Левый аргумент - это «цель», а правый - стек. Если головка цели совпадает с вершиной стека, мы добавляем ее и повторяем с остальной частью цели и стеком (без повторного добавления элемента сверху). В противном случае мы добавляем верхний элемент и возвращаемся с той же целью, читая верхний элемент до конца стека. Когда цель пуста, при сопоставлении с образцом выбирается вторая строка, и возвращается пустой список.

РЕДАКТИРОВАТЬ: -3 байта благодаря @GolfWolf и @Laikoni!

Чисто , 85 байт

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

Попробуйте онлайн!

Определяет частичную функцию fвзятия [Char]и [Char], где первый аргумент является объектом , а второй стек.

Java 8, 88 байт

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

Входы как char[]и java.util.LinkedList<Character>( java.util.Queueреализация)

Объяснение:

Попробуйте онлайн.

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 байта

Edit: Teal пеликан имеет гораздо лучший ><>подход здесь , что свопы метода ввода

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

Попробуйте онлайн!

Принимает порядок букв через -sфлаг, а стек через ввод.

Как это устроено:

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 байта

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

Попробуйте онлайн!

> <> , 21 16 байт

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

Попробуйте онлайн!

Поток изменен, чтобы использовать пустые места и убрать лишний код перенаправления. (-5 байт) - благодаря @JoKing

> <> , 21 байт

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

Попробуйте онлайн!

Другой ответ> <> можно найти здесь.

объяснение

Стек начинается с начального набора символов с использованием флага -s. Ввод - это заданный пользователем порядок символов. Это объяснение будет следовать за потоком кода.

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 байта

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

Принимает свой первый аргумент, порядок, как список символов, а его второй, стек, как строку.

Ungolfed:

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

Вы когда-нибудь задумывались, для чего все эти непонятные переменные регулярного выражения? Ясно, что они были разработаны для этой конкретной задачи. Мы сопоставляем текущий символ $x(который, к сожалению, должен быть экранирован в случае, если это специальный символ регулярного выражения). Это удобно разбивает строку на «до матча» $`, «матч» $&и «после матча» $'. В циклическом поиске мы ясно видели каждый символ перед совпадением и помещали его обратно в стек. Мы также видели текущий персонаж, но не вернули его. Таким образом, мы добавляем «перед совпадением» в список «видимых» $zи строим стек из «после совпадения», за которым следует «до совпадения».

SNOBOL4 (CSNOBOL4) , 98 байт

	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

Попробуйте онлайн!

Печатает каждую букву на новой строке. Используйте эту версию, чтобы все печаталось на одной строке. Принимает ввод как стек, затем цель, разделенный новой строкой.

	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 байта

Включает +4в себя для-lF

Введите входные данные как в STDIN в качестве цели, а затем в стек (это обратный порядок из примеров):

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

Если вы не возражаете против новой строки, это 40работает:

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