Lösen Sie ein Stapelzustandsdiagramm

15

Ein Stapelzustandsdiagramm zeigt, wie die Werte auf einem Stapel in den anderen geändert werden. Dies ist beispielsweise ein Stapelzustandsdiagramm:

3 0 2 1 0

Dies bedeutet, dass es einen Stapel gibt, der anfänglich 3 Werte enthält (das 3Teil). Diese Werte werden von 0 bis 2 indiziert, mit 0 an der Spitze: 2 1 0. Der nächste Teil 0 2 1 0beschreibt den Endzustand des Stapels: Der Wert, der ursprünglich oben auf dem Stapel lag, wurde ebenfalls nach hinten kopiert.

Diese Transformationen werden auf einem Stapel ausgeführt, der mehrere Datentypen unterstützt:

  • Der "Wert" -Typ, der ursprünglich auf dem Stapel gespeichert war. Dies kann eine Zeichenfolge, eine Ganzzahl usw. sein, ihr Wert muss jedoch nicht bekannt sein.
  • Der Typ "Liste", bei dem es sich um eine Liste handelt, die Werte eines beliebigen Datentyps enthält.

Um diese Umwandlung zu modellieren, sind die folgenden Operationen zulässig:

  • S: Vertauschen Sie die beiden Werte oben auf dem Stapel: 2 1 02 0 1
  • D: Den Wert oben auf dem Stapel duplizieren: 1 01 0 0
  • R: Entfernen Sie den obersten Wert vom Stapel. 2 1 02 1
  • L: Verwandeln Sie den obersten Wert in eine Liste mit einem Element, die diesen Wert enthält: 2 1 02 1 (0)
  • C: Verketten Sie die beiden obersten Listen auf dem Stapel: 2 (1) (0)2 (1 0)
  • U: Alle Werte aus einer Liste auf den Stapel legen: 2 (1 0)2 1 0

Diese sind äquivalent zu den Unterlast Befehle ~ : ! a * ^, vorausgesetzt , dass keine anderen Befehle verwendet werden.

S, D, R, Und Lkann mit irgendwelchen Werten oben auf dem Stapel verwendet werden, aber Cund Umüssen Listen oben auf dem Stapel - Funktion. Eine Übermittlung, deren generierte Sequenzen versuchen, ungültige Operationen durchzuführen (wie Dauf einem leeren Stapel oder Uauf einer Nicht-Liste), ist falsch und muss korrigiert werden .

Um ein Stapelzustandsdiagramm zu lösen, suchen Sie eine Folge von Befehlen, die den anfänglichen Stapelzustand korrekt in den neuen umwandeln. Eine Lösung 3: 0 2 1 0ist beispielsweise 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

Ihre Aufgabe ist es, ein Programm zu schreiben, das ein Stapelzustandsdiagramm erstellt und eine Lösung ausgibt.

Testfälle

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

Das ist , also gewinnt die kürzeste gültige Antwort (in Bytes).

Esolanging Fruit
quelle
Können Sie eine Liste mit Listen haben? EDIT: Egal, Sie können, es ist in dem Beispiel.
Orlp
Befinden sich die CBedarfslisten oben und an der zweiten Position des Stapels? Oder könnte das Element an zweiter Stelle zu einer Liste oben hinzugefügt werden?
EDC65
Cbraucht Listen auf beiden Positionen. Es ist nicht sinnvoll, einen Wert und eine Liste zu verketten.
Esolanging Fruit

Antworten:

9

Python 3, 84 Bytes

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

Verwendung:

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

Erklärung: Zu Beginn duplizieren wir die Null und schreiben sie in eine Liste:

DL -> 3 2 1 0 (0)

Das ist unsere Basis. Nun werde ich einen allgemeinen Algorithmus erklären, der sich ... 1 0 (x)in ... 1 0 (i x)eine beliebige ganze Zahl verwandelt i. Ich werde als Beispiel verwenden i = 2, und wir haben einige willkürliche Liste (x). Wir beginnen damit, unsere aktuelle Liste (x)in eine andere Liste zu packen:

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

Nun wiederholen wir die folgenden Sequenzzeiten i:

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

Jetzt können wir die 2 in die Liste einfügen (x). Das geht so:

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)

Beachten Sie, dass wir immer wieder neue Ganzzahlen auf der linken Seite einfügen. Also haben (0)wir als erstes auf der rechten Seite angefangen.

Nachdem wir jede benötigte Ganzzahl in die Liste eingefügt haben, entfernen wir den Rest des Stapels, indem wir n time ( SR) tauschen und entfernen . Schließlich entpacken wir unsere Liste und löschen die erste, die 0wir eingefügt haben, um unsere Liste zu starten ( UR).

orlp
quelle
Meinten Sie tippen sstatt l?
Zacharý
@ ZacharyT Ups, yep. Es funktionierte, während die Dinge ldurcheinander gebracht wurden, weil es auf meiner REPL definiert wurde.
Orlp
Das gezeigte Beispiel scheint nicht zu funktionieren ... ( DLLSLSCSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCLSLSCDURLCULCULSCLSLSCLSLSCDURLCULCULSCLLSLSCDURLCULCULSCSRSRSRSRUR ). Es wird versucht, eine SAnweisung auszuführen , wenn sich nur 1 Wert auf dem Stapel befindet.
Esolanging Fruit
@ Challenger5 Und ich habe auch vergessen, das Beispiel zu aktualisieren ... Sollte jetzt behoben sein.
Orlp
Ja, sieht jetzt gut aus!
Esolanging Fruit
0

CJam, 54 Bytes

Nur eine Übersetzung von Orls Python-Lösung in CJam. Hier gibt es nichts Neues.

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

Erläuterung:

"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
quelle