Memecahkan Diagram Status Tumpukan

15

Diagram keadaan tumpukan menunjukkan bagaimana nilai pada satu tumpukan diubah menjadi yang lain. Sebagai contoh, ini adalah diagram status tumpukan:

3 0 2 1 0

Ini berarti ada tumpukan yang awalnya berisi 3 nilai ( 3bagian). Nilai-nilai ini diindeks dari 0 sampai 2, dengan 0 di bagian atas: 2 1 0. Bagian selanjutnya 0 2 1 0menjelaskan keadaan akhir stack: nilai yang semula di atas stack telah disalin ke belakang juga.

Transformasi ini terjadi pada tumpukan yang memiliki dukungan untuk beberapa tipe data:

  • Jenis "nilai", yang merupakan aslinya pada tumpukan. Ini bisa berupa string, integer, dll. Tetapi nilainya tidak perlu diketahui.
  • Tipe "daftar", yang merupakan daftar yang berisi nilai dari semua tipe data.

Untuk memodelkan transformasi ini, operasi berikut diizinkan:

  • S: Tukar kedua nilai di atas tumpukan: 2 1 0→2 0 1
  • D: Gandakan nilai di atas tumpukan: 1 0→1 0 0
  • R: Hapus nilai teratas pada tumpukan. 2 1 0→2 1
  • L: Ubah nilai teratas menjadi daftar satu elemen yang berisi nilai itu: 2 1 0→2 1 (0)
  • C: Menggabungkan dua daftar teratas di tumpukan: 2 (1) (0)→2 (1 0)
  • U: Tempatkan semua nilai dari daftar ke tumpukan: 2 (1 0)→2 1 0

Ini sama dengan perintah Underload~ : ! a * ^ , asalkan tidak ada perintah lain yang digunakan.

S, D, R, Dan Ldapat digunakan dengan nilai-nilai di atas tumpukan, namun Cdan Uharus memiliki daftar di atas tumpukan untuk fungsi. Kiriman yang urutan urutannya dihasilkan mencoba untuk membentuk operasi yang tidak valid (seperti Dpada tumpukan kosong atau Upada non-daftar) salah dan harus dihukum diperbaiki.

Untuk memecahkan diagram keadaan tumpukan, temukan urutan perintah yang akan mengubah keadaan tumpukan awal dengan benar menjadi yang baru. Sebagai contoh, salah satu solusinya 3: 0 2 1 0adalah 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

Tugas Anda adalah menulis sebuah program yang mengambil diagram status tumpukan dan menghasilkan solusi.

Uji Kasus

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

Ini adalah kode-golf , sehingga jawaban terpendek yang valid (dalam byte) menang.

code-golf code-generation stack Buah Esolanging
sumber
Bisakah Anda memiliki daftar yang berisi daftar? EDIT: Nevermind, Anda bisa, itu dalam contoh.
orlp
Apakah Cdaftar kebutuhan berada di posisi teratas dan kedua stack? atau elemen di posisi kedua dapat ditambahkan ke daftar di atas?
edc65
Cperlu daftar di kedua posisi. Tidak masuk akal untuk menggabungkan nilai dan daftar.
Buah Esolanging

Jawaban:

9

Python 3, 84 byte

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

Pemakaian:

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

Penjelasan: Untuk memulai, kami menduplikasi nol dan membungkusnya dalam daftar:

DL -> 3 2 1 0 (0)

Ini basis kami. Sekarang saya akan menjelaskan algoritma umum yang berubah ... 1 0 (x)menjadi ... 1 0 (i x)bilangan bulat acak i. Saya akan gunakan sebagai contoh i = 2, dan kami memiliki beberapa daftar arbitrer (x). Kami mulai dengan membungkus daftar kami saat ini (x)ke daftar lain:

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

Sekarang kita ulangi urutan iwaktu berikut :

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

Sekarang kita siap untuk memasukkan 2 ke dalam daftar (x). Ini berlaku sebagai berikut:

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)

Perhatikan bahwa kami terus mendorong bilangan bulat baru di sebelah kiri. Jadi yang pertama (0)kami mulai dengan tetap di sebelah kanan.

Setelah kami memasukkan setiap bilangan bulat yang kami butuhkan ke dalam daftar, kami menghapus sisa tumpukan dengan menukar dan menghapus waktu n ( SR). Akhirnya kami membongkar daftar kami dan menghapus yang pertama 0kami masukkan untuk memulai daftar kami ( UR).

orlp
sumber
Apakah Anda bermaksud mengetik, sbukan l?
Zacharý
@ ZacharyT Ups, ya. Ini bekerja sambil mengacak-acak sekitar karena ldidefinisikan pada REPL saya.
orlp
Contoh yang ditampilkan tampaknya tidak berfungsi ... ( DLLSLSCSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCSLSCLSLSCDURLCULCULSCLSLSCSLSCLSLSCDURLCULCULSCLSLSCLSLSCDURLCULCULSCLLSLSCDURLCULCULSCSRSRSRSRUR ). Mencoba menjalankan Sinstruksi ketika hanya ada 1 nilai pada stack.
Buah Esolanging
@ Challenger5 Dan saya juga lupa memperbarui contoh ... Harus diperbaiki sekarang.
orlp
Yap, terlihat bagus sekarang!
Buah Esolanging
0

CJam, 54 byte

Hanya terjemahan dari solusi Python orlp ke CJam. Tidak ada yang baru di sini.

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

Penjelasan:

"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.]
Buah Esolanging
sumber