Solve a Stack State Diagram

Question

A stack state diagram shows how the values on one stack are changed into the other. For example, this is a stack state diagram:

3 0 2 1 0

This means that there is a stack initially containing 3 values (the 3 part). These values are indexed from 0 to 2, with 0 at the top: 2 1 0. The next part 0 2 1 0 describes the final state of the stack: the value that was originally on top of the stack has been copied to the back as well.

These transformations happen on a stack that has support for several data types:

• The "value" type, which is what is originally on the stack. This could be a string, integer, etc. but its value does not need to be known.
• The "list" type, which is a list containing values of any data type.

To model this transformation, the following operations are permitted:

• S: Swap the two values on top of the stack: 2 1 0 → 2 0 1
• D: Duplicate the value on top of the stack: 1 0 → 1 0 0
• R: Remove the top value on the stack. 2 1 0 → 2 1
• L: Turn the top value into a one-element list containing that value: 2 1 0 → 2 1 (0)
• C: Concatenate the top two lists on the stack: 2 (1) (0) → 2 (1 0)
• U: Place all the values from a list onto the stack: 2 (1 0) → 2 1 0

These are equivalent to the Underload commands ~ : ! a * ^, provided that no other commands are used.

S, D, R, and L can be used with any values on top of the stack, but C and U must have lists on top of the stack to function. A submission whose generated sequences attempt to preform invalid operations (like D on an empty stack or U on a non-list) is wrong and must be punished fixed.

To solve a stack state diagram, find a sequence of commands that will correctly transform the initial stack state into the new one. For example, one solution to 3: 0 2 1 0 is LSLCSLCULSLCLSLDCSC USLCU:

   2 1 0
L  2 1 (0)
S  2 (0) 1
L  2 (0) (1)
C  2 (0 1)
S  (0 1) 2
L  (0 1) (2)
C  (0 1 2)
U  0 1 2
L  0 1 (2)
S  0 (2) 1
L  0 (2) (1)
C  0 (2 1)
L  0 ((2 1))
S  ((2 1)) 0
L  ((2 1)) (0)
D  ((2 1)) (0) (0)
C  ((2 1)) (0 0)
S  (0 0) ((2 1))
C  (0 0 (2 1))
U  0 0 (2 1)
S  0 (2 1) 0
L  0 (2 1) (0)
C  0 (2 1 0)
U  0 2 1 0

Your task is to write a program that takes a stack state diagram and outputs a solution.

Test Cases

2 1 0       ->

3 2 0       -> SR

9           -> RRRRRRRRR

2 0 1 0     -> LSLCDCUR

2 0 1 1     -> SD

6 2         -> RRSRSRSR

5 0 1 2 3 4 -> LSLCSLCSLCSLCU

4 2 0 1 3 2 -> LSLCSLSCSLCULSLSCSLSCLSLDCSCUSLCU

This is code-golf, so the shortest valid answer (in bytes) wins.

Answer 1

Python 3, 84 bytes

lambda n,*s:"DLL"+"L".join(i*"SLSC"+"LSLSCDURLCULCULSC"for i in s[::-1])+n*"SR"+"UR"

Usage:

# Example: 4 2 0 1 3 2 -> LSLCSLSCSLCULSLSCSLSCLSLDCSCUSLCU
>>> f = lambda ...
>>> f(4, 2, 0, 1, 3, 2)
'DLLSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCLSLSCDURLCULCULSCLLSLSCDURLCULCULSCLSLSCSLSCLSLSCDURLCULCULSCSRSRSRSRUR'

Explanation: To start off we duplicate the zero and wrap it in a list:

DL -> 3 2 1 0 (0)

This is our base. Now I will explain a general algorithm that turns ... 1 0 (x) into ... 1 0 (i x) for arbitrary integer i. I will use as an example i = 2, and we have some arbitrary list (x). We start by wrapping our current list (x) into another list:

L -> 3 2 1 0 ((x))

Now we repeat the following sequence i times:

SLSC -> 3 2 1 (0 (x))
SLSC -> 3 2 (1 0 (x))

Now we're ready to insert the 2 into list (x). This goes as follows:

LSLSC -> 3 (2 (1 0 (x)))
DU -> 3 (2 (1 0 (x))) 2 (1 0 (x))
RLCU -> 3 2 (1 0 (x)) 2
LCU -> 3 2 1 0 (x) 2
LSC -> 3 2 1 0 (2 x)

Note that we keep pushing new integers on the left. So the very first (0) we started with stays on the right.

After we have inserted every integer we need into the list we remove the rest of the stack by swapping and removing n time (SR). Finally we unpack our list and delete the first 0 we inserted to start our list (UR).

Answer 2

CJam, 54 bytes

Just a translation from orlp's Python solution into CJam. There's nothing new here.

"DLL"q~("SR"*\W%{"SLSC"*"LSLSCDURLCULCULSC"+}%'L*\"UR"

Explanation:

"DLL"                  e# Push string
q~                     e# Read input and evaluate
(                      e# Pop the first value
"SR"                   e# Push string
*                      e# Repeat string n times
\                      e# Swap (bring s to front)
W%                     e# Reverse
{                      e# For each:
  "SLSC"               e#   Push string
  *                    e#   Repeat i times
  "LSLSCDURLCULCULSC"+ e#   Append string to end
}%                     e# End
'L*                    e# Join with 'L'
\                      e# Swap (bring "SR"*n to front)
"UR"                   e# Push string
                       e# [Stack is implicitly output.]