17
1
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'))
Test cases
try
, yrt
→ yrtyry
1234
, 4321
→ 4321432434
ABCDEFGHIJKLMNOPQRSTUVWXYZ
, RUAHYKCLQZXEMPBWGDIOTVJNSF
→ RUAHYKCLQZXEMPBWGDIOTVJNSFRUHYKCLQZXEMPWGDIOTVJNSFRUHYKLQZXEMPWGIOTVJNSFRUHYKLQZXMPWGIOTVJNSRUHYKLQZXMPWIOTVJNSRUYKLQZXMPWOTVNSRUYQZXPWOTVSRUYQZXPWTVSRUYQZXWTVSRUYZXWTVSUYZXWTVUYZXWVYZXWYZXYZ
?
, ?
→ ?
a
, a
→ a a
abcd
, abcd
→ abcd
1Hm, I'm suspicious of the first two versions...why
99
specifically? – Erik the Outgolfer – 2018-01-16T11:42:00.577@EriktheOutgolger It's at least the number of printable ASCII characters, and so is at least the length of each input. – xnor – 2018-01-16T19:33:37.960