# Solve a Stack State Diagram

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 02 0 1
• D: Duplicate the value on top of the stack: 1 01 0 0
• R: Remove the top value on the stack. 2 1 02 1
• L: Turn the top value into a one-element list containing that value: 2 1 02 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 , so the shortest valid answer (in bytes) wins.

• Can you have a list containing lists? EDIT: Nevermind, you can, it's in the example. – orlp Dec 20 '16 at 18:56
• Does the C need lists on top and second position of stack? or the element in second position could be added to a list on top? – edc65 Dec 21 '16 at 11:55
• C needs lists on both positions. It doesn't make sense to concatenate a value and a list. – Esolanging Fruit Dec 21 '16 at 17:52

# 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).

• Did you mean to type s instead of l? – Zacharý Dec 20 '16 at 20:23
• @ZacharyT Oops, yep. It worked while shuffling things around because l was defined on my REPL. – orlp Dec 20 '16 at 20:53
• The example shown doesn't seem to work... (DLLSLSCSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCLSLSCDURLCULCULSCLSLSCLSLSCDURLCULCULSCLLSLSCDURLCULCULSCSRSRSRSRUR ). It tries to execute an S instruction when there's only 1 value on the stack. – Esolanging Fruit Dec 20 '16 at 21:54
• @Challenger5 And I also forgot to update the example... Should be fixed now. – orlp Dec 20 '16 at 21:58
• Yep, looks good now! – Esolanging Fruit Dec 20 '16 at 22:55

## 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.]