Help my son find his letters

Question

Background

Based on a game my four-year-old got from his rabbi.

The "goal" is to "find" the letters in a given order, e.g. aecdb. You are given a stack of letter cards, e.g. daceb. You can only search through the stack in the order given, albeit cyclically. When you meet a letter you need, you take that out of the stack.

Objective

Given an order and a stack (duplicate-free permutations of each other), find the sequence of top stack letters (it is all printable ASCII) you see while playing the game.

Step-by-step example

We need to find the order aecdb, given the stack daceb:

Top of stack d: Not what we are looking for (a), so we add it to the sequence:d and rotate to get the stack:acebd.

Top of stack a: Yes! so we add it to the sequence:da and remove it from the stack:cebd.

Top of stack c: Not what we are looking for (e), so we add it to the sequence:dac and rotate to get the stack:ebdc.

Top of stack e: Yes! so we add it to the sequence:dace and remove it from the stack:bdc.

Top of stack b: Not what we are looking for (c), so we add it to the sequence:daceb and rotate to get the stack:dcb.

Top of stack d: Not what we are looking for (c), so we add it to the sequence:dacebd and rotate to get the stack:cbd.

Top of stack c: Yes! so we add it to the sequence:dacebdc and remove it from the stack:bd.

Top of stack b: Not what we are looking for (d), so we add it to the sequence:dacebdcb and rotate to get the stack:db.

Top of stack d: Yes! so we add it to the sequence:dacebdcbd and remove it from the stack:b.

Top of stack b: Yes! so we add it to the sequence:dacebdcbdb and remove it from the stack:.

And we are done. The result is dacebdcbdb.

Reference implementation

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 it online!

Test cases

try, yrt → yrtyry

1234, 4321 → 4321432434

ABCDEFGHIJKLMNOPQRSTUVWXYZ, RUAHYKCLQZXEMPBWGDIOTVJNSF → RUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ

?, ? → ?

a, a → a a

abcd, abcd → abcd

Answer 1

APL (Dyalog Classic), 21 bytes

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

Try it online!

This is a train equivalent to {∊⍵,(⊂⍵)~¨(,\⍺⊂⍨1,2>/⍺⍋⍵)}

⍋ gives the permutation of right argument ⍵ in left argument ⍺

1,2>/ compare consecutive pairs with > and prepend a 1

⍺⊂⍨ use the above boolean mask to split ⍺ into groups; 1s in the mask mark the start of a new group

,\ cumulative concatenations of the groups

(⊂⍵)~¨ complement of each with respect to ⍵

⍵, prepend ⍵

∊ flatten as a single string

Answer 2

Three fairly different methods are giving equal byte counts.

Python 2, 59 bytes

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

Try it online!

Prints each character in its own line.

---

Python 2, 59 bytes

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

Try it online!

Takes lists as input, and outputs a list.

---

Python 3, 59 bytes

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

Try it online!

Answer 3

JavaScript (ES6), 54 bytes

Takes the target as a string and the stack as an array of characters. Returns a string.

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

Test cases

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

How?

At each iteration, we extract the character c on the top of the stack and append it to the final result. We then perform a recursive call whose parameters depend on the result of c == t[0], where t[0] is the next expected character.

If c matches t[0]:

• we remove c from the target string by passing t.slice(1)
• we remove c from the stack by passing s unchanged

If c doesn't match t[0]:

• we let the target string unchanged by passing t.slice(0)
• we push c back at the end of the stack

Answer 4

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%

Takes the target and stack as inputs on STDIN.

Answer 5

Haskell, 49 46 bytes

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

Try it online!

Fairly simple. Left argument is the "goal" and the right is the stack. If the head of the goal matches the top of the stack we prepend it, and recur with the rest of the goal and the stack (without re-adding the item on top). Otherwise we prepend the top item and recur with the same goal, reading the top item to the end of the stack. When the goal is empty the pattern matching chooses the second line and the empty list is returned.

EDIT: -3 bytes thanks to @GolfWolf and @Laikoni!

Answer 6

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

Try it online!

I suspect this is very highly golfable.

Answer 7

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

Try it online!

Answer 8

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

Try it online!

Defines the partial function f taking [Char] and [Char], where the first argument is the target and the second is the stack.

Answer 9

><>, 38 32 bytes

Edit: Teal pelican has a much better ><> approach here that swaps the input methods

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

Try it online!

Takes the order of the letters through the -s flag, and the stack through input.

How It Works:

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

Answer 10

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

Inputs as char[] and java.util.LinkedList<Character> (java.util.Queue implementation)

Explanation:

Try it 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

Answer 11

><>, 21 16 bytes

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

Try it online!

Flow changed to utilize the empty spaces and remove extra code rerouting. (-5 bytes) - Thanks to @JoKing

><>, 21 bytes

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

Try it online!

The other ><> answer can be found here.

Explanation

The stack starts with an initial set of characters using the -s flag. Input is the user given character order. This explanation will follow the flow of the 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]

Answer 12

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

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

Try it online!

Answer 13

Perl, 62 bytes

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

Takes its first argument, the order, as a list of characters and its second, the stack, as a string.

Ungolfed:

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

You ever wonder what all those obscure regex variables were for? Clearly, they were designed for this exact challenge. We match on the current character $x (which unfortunately has to be escaped in case it's a regex special character). This conveniently splits the string into "before the match" $`, "the match" $&, and "after the match" $'. In the cyclic search, we clearly saw every character before the match and put them back into the stack. We also saw the current character but didn't put it back. So we append "before the match" to the "seen" list $z and construct the stack out of "after the match" followed by "before the match".

Answer 14

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

Try it online!

Prints each letter on a newline. Use this version to get everything to print on the same line. Takes input as stack, then target, separated by a newline.

	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

Answer 15

Perl, 44 bytes

Includes +4 for -lF

Give input as on STDIN as target then stack (this is the reverse order from the examples):

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

If you don't mind a trailing newline this 40 works:

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