Diagram stanu stosu pokazuje, jak wartości z jednego stosu są zamieniane na drugi. Na przykład jest to diagram stanu stosu:

3 0 2 1 0

Oznacza to, że istnieje stos początkowo zawierający 3 wartości ( 3część). Wartości te są indeksowane od 0 do 2, gdzie 0 U góry 2 1 0. Kolejna część 0 2 1 0opisuje końcowy stan stosu: wartość, która była pierwotnie na szczycie stosu, została również skopiowana na drugą stronę.

Te transformacje zachodzą na stosie obsługującym kilka typów danych:

• Typ „wartości”, który pierwotnie znajduje się na stosie. Może to być ciąg, liczba całkowita itp., Ale jego wartość nie musi być znana.
• Typ „list”, czyli lista zawierająca wartości dowolnego typu danych.

Aby modelować tę transformację, dozwolone są następujące operacje:

• S: Zamień dwie wartości na górze stosu: 2 1 0→2 0 1
• D: Zduplikuj wartość na górze stosu: 1 0→1 0 0
• R: Usuń najwyższą wartość ze stosu. 2 1 0→2 1
• L: Zamień najwyższą wartość na listę jednoelementową zawierającą tę wartość: 2 1 0→2 1 (0)
• C: Połącz dwie pierwsze listy na stosie: 2 (1) (0)→2 (1 0)
• U: Umieść wszystkie wartości z listy na stosie: 2 (1 0)→2 1 0

Są równoważne UNDERLOAD poleceń ~ : ! a * ^, pod warunkiem, że żadne inne polecenia są wykorzystywane.

S, D, R, I Lmoże być używany z dowolnym wartości na szczycie stosu, ale Ci Umuszą mieć list na wierzchu stosu funkcjonować. Przesłanie, którego wygenerowane sekwencje próbują wykonać nieprawidłowe operacje (np. DNa pustym stosie lub Una liście nie znajdującej się na liście) jest błędne i musi zostać ukarane .

Aby rozwiązać diagram stanu stosu, znajdź sekwencję poleceń, które poprawnie przekształcą początkowy stan stosu w nowy. Na przykład jednym z rozwiązań 3: 0 2 1 0jest 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

Twoim zadaniem jest napisanie programu, który pobierze diagram stanu stosu i wyświetli rozwiązanie.

Przypadki testowe

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

To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź (w bajtach).

Python 3, 84 bajtów

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

Stosowanie:

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

Objaśnienie: Na początek duplikujemy zero i zawijamy go na listę:

DL -> 3 2 1 0 (0)

To jest nasza baza. Teraz wyjaśnię ogólny algorytm, który zmienia ... 1 0 (x)się ... 1 0 (i x)w dowolną liczbę całkowitą i. Podam jako przykład i = 2i mamy dowolną listę (x). Zaczynamy od zawijania naszej aktualnej listy (x)do innej listy:

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

Teraz powtarzamy następujące iczasy sekwencji :

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

Teraz jesteśmy gotowi wstawić 2 do listy (x). Jest to następujące:

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)

Zauważ, że ciągle popychamy nowe liczby całkowite po lewej stronie. Więc po raz pierwszy (0)zaczęliśmy od pobytów po prawej stronie.

Po wstawieniu każdej liczby całkowitej, której potrzebujemy, usuwamy resztę stosu, zamieniając i usuwając n time ( SR). Na koniec rozpakowujemy naszą listę i usuwamy pierwszą, 0którą wstawiliśmy, aby uruchomić naszą listę ( UR).

CJam, 54 bajty

Tylko tłumaczenie z rozwiązania Python firmy orlp na CJam. Nie ma tu nic nowego.

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

Wyjaśnienie:

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