Un diagramme d'état de pile montre comment les valeurs d'une pile sont changées dans l'autre. Par exemple, il s'agit d'un diagramme d'état de pile:

3 0 2 1 0

Cela signifie qu'il existe une pile contenant initialement 3 valeurs (le 3 partie). Ces valeurs sont indexées de 0 à 2, avec 0 en haut: 2 1 0. La partie suivante 0 2 1 0décrit l'état final de la pile: la valeur qui était à l'origine au-dessus de la pile a également été copiée à l'arrière.

Ces transformations se produisent sur une pile prenant en charge plusieurs types de données:

• Le type "valeur", qui est à l'origine sur la pile. Il peut s'agir d'une chaîne, d'un entier, etc. mais sa valeur n'a pas besoin d'être connue.
• Le type "liste", qui est une liste contenant des valeurs de n'importe quel type de données.

Pour modéliser cette transformation, les opérations suivantes sont autorisées:

• S: Échangez les deux valeurs en haut de la pile: 2 1 0→2 0 1
• D: Dupliquez la valeur en haut de la pile: 1 0→1 0 0
• R: Supprimez la valeur supérieure de la pile. 2 1 0→2 1
• L: Transformer la première valeur en une liste à un élément contenant cette valeur: 2 1 0→2 1 (0)
• C: Concaténer les deux premières listes de la pile: 2 (1) (0)→2 (1 0)
• U: Placer toutes les valeurs d'une liste sur la pile: 2 (1 0)→2 1 0

Celles-ci sont équivalentes aux commandes Underload~ : ! a * ^ , à condition qu'aucune autre commande ne soit utilisée.

S, D, REt Lpeut être utilisé avec toutes les valeurs au - dessus de la pile, mais Cet Udoit avoir des listes sur le dessus de la pile de fonctionner. Une soumission dont les séquences générées tentent d'effectuer des opérations invalides (comme Dsur une pile vide ou Usur une non-liste) est incorrecte et doit être punie corrigée.

Pour résoudre un diagramme d'état de pile, recherchez une séquence de commandes qui transformera correctement l'état de pile initial en un nouveau. Par exemple, une solution 3: 0 2 1 0est 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

Votre tâche consiste à écrire un programme qui prend un diagramme d'état de pile et génère une solution.

Cas de test

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

Il s'agit de code-golf , donc la réponse valide la plus courte (en octets) l'emporte.

Python 3, 84 octets

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'

Explication: Pour commencer, nous dupliquons le zéro et l'enveloppons dans une liste:

DL -> 3 2 1 0 (0)

Ceci est notre base. Je vais maintenant expliquer un algorithme général qui se transforme ... 1 0 (x)en ... 1 0 (i x)entier arbitraire i. Je vais utiliser comme exemple i = 2, et nous avons une liste arbitraire (x). Nous commençons par envelopper notre liste actuelle (x)dans une autre liste:

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

Maintenant, nous répétons les itemps de séquence suivants :

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

Nous sommes maintenant prêts à insérer le 2 dans la liste (x). Cela se passe comme suit:

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)

Notez que nous continuons à pousser de nouveaux entiers sur la gauche. Donc, le tout premier, (0)nous avons commencé par rester sur la droite.

Après avoir inséré chaque entier dont nous avons besoin dans la liste, nous supprimons le reste de la pile en échangeant et en supprimant n time ( SR). Enfin, nous décompressons notre liste et supprimons la première que 0nous avons insérée pour démarrer notre liste ( UR).

CJam, 54 octets

Juste une traduction de la solution Python d'orlp dans CJam. Il n'y a rien de nouveau ici.

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

Explication:

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