Rozwiąż diagram stanu stosu

15

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 02 0 1
  • D: Zduplikuj wartość na górze stosu: 1 01 0 0
  • R: Usuń najwyższą wartość ze stosu. 2 1 02 1
  • L: Zamień najwyższą wartość na listę jednoelementową zawierającą tę wartość: 2 1 02 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 , więc wygrywa najkrótsza ważna odpowiedź (w bajtach).

Esolanging Fruit
źródło
Czy możesz mieć listę zawierającą listy? EDYCJA: Nieważne, możesz, to na przykładzie.
orlp
Czy Clisty potrzeb na górnej i drugiej pozycji stosu? czy element na drugiej pozycji można dodać do listy na górze?
edc65
Cpotrzebuje list na obu pozycjach. Łączenie wartości i listy nie ma sensu.
Esolanging Fruit,

Odpowiedzi:

9

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

orlp
źródło
Czy chciałeś napisać szamiast l?
Zacharý
@ZacharyT Ups, tak. Działało podczas tasowania, ponieważ lzostało zdefiniowane w mojej REPL.
lub
Przedstawiony przykład nie działa ... ( DLLSLSCSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCLSLSCDURLCULCULSCLSLSCLSLSCDURLCULCULSCLLSLSCDURLCULCULSCSRSRSRSRUR ). Próbuje wykonać Sinstrukcję, gdy na stosie znajduje się tylko 1 wartość.
Esolanging Fruit
@ Challenger5 I zapomniałem również zaktualizować przykład ... Powinien zostać naprawiony teraz.
lub
Tak, teraz wygląda dobrze!
Esolanging Fruit,
0

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.]
Esolanging Fruit
źródło