Tantangan Diambil dari kontes tantangan kode universitas saya
Ini sebenarnya adalah Hari 0 tetapi tantangan kemarin terlalu mudah dan dapat ditipu pertanyaan lain di sini.
Tetris adalah permainan video yang menjadi populer di tahun 80-an. Ini terdiri dari menempatkan serangkaian potongan dengan bentuk berbeda yang jatuh di atas papan, sehingga mereka pas dengan cara yang paling kompak.
Dalam masalah ini kita akan mengasumsikan urutan potongan yang jatuh, masing-masing dalam posisi tertentu dan dengan orientasi tertentu yang tidak dapat diubah. Potongan-potongan ditumpuk saat jatuh dan baris lengkap tidak dihilangkan (seperti dalam game asli). Tujuannya adalah untuk menentukan ketinggian akhir dari setiap kolom papan setelah semua bagian jatuh.
Ada total 7 buah yang berbeda, yang ditunjukkan pada gambar:
Tantangan
Diberikan daftar potongan, hasilkan ketinggian semua kolom dari papan setelah semua potongan jatuh
Sepotong terdiri dari tiga angka: I, R dan P. Angka pertama, I, adalah pengidentifikasi keping (angka antara 1 dan 7, dalam urutan yang sama seperti pada gambar). Angka kedua, R, adalah rotasi potongan. Ini dapat mengambil nilai 0, 90, 180 atau 270 dan mewakili sudut rotasi potongan dalam arah anti-jarum jam. Angka ketiga, P, menunjukkan posisi potongan. Merupakan kolom di sebelah kiri ditempati oleh potongan (ini bisa 1 atau 0 Indeks. Silakan tentukan).
Contoh dan Uji kasus (1 Indeks)
- Diberikan
[[1, 0, 1], [4, 0, 1], [5, 90, 4]]
- Keluaran
[3, 3, 1, 3, 2]
- Diberikan
[[6, 270, 4], [1, 180, 5], [1, 90, 6], [7, 0, 4]]
- Keluaran
[0, 0, 0, 9, 9, 8, 3, 3]
[[3,0,1],[3,180,3]]
Output yang diberikan[1,1,4,4,4]
[[2,180,1],[2,0,3]]
Output yang diberikan[2,2,4,3,3]
Catatan
- Ini adalah kode-golf
- Baris / Kolom dapat berupa Indeks 1 atau 0. Silakan tentukan.
- Anda dapat mendefinisikan kembali nilai input (mungkin Anda ingin memanggil bagian 1 sebagai A, dll.). Dalam hal ini harap tentukan
Pertanyaan
Bisakah kita menggunakan 4 nilai berbeda daripada sudut dalam derajat ?: Ya
Apakah kita seharusnya menangani "lubang" jika sepotong tidak benar-benar cocok dengan yang sebelumnya ?: Ya
Apakah tinggi atau lebar papan dibatasi? Tidak. Baik lebar maupun tinggi tidak dibatasi
Terima kasih @Arnauld untuk gambar dan test case *. *
I
,R
danP
menjadi input dalam urutan yang berbeda?Jawaban:
JavaScript (Node.js) ,
286 284 270266 bytesCobalah online! atau coba versi yang disempurnakan yang juga menampilkan papan akhir.
Pengkodean bentuk
Semua bagian disimpan persis 4 nibble (4x4 bit) dengan baris diurutkan dalam urutan terbalik dan piksel paling kiri dipetakan ke bit paling tidak signifikan. Dengan kata lain, representasi biner dari bentuk tersebut dicerminkan secara vertikal dan horizontal.
Contoh:
Fungsi hash dan tabel pencarian
Entri-entri ini dikemas sebagai:
yang mengembang ke 82 camilan berikut:
"ff"
Parameter fungsi hash dipaksakan dengan cara yang mengoptimalkan nol awal dan akhir. Fakta bahwa string dapat dikompres lagi dengan menggunakan
1e12
untuk nol di tengah dan konversi dari basis-16 ke basis-4 untuk bagian kanan hanyalah efek samping yang diterima tetapi tidak terduga. :-)Ini sebuah demonstrasi proses pembongkaran untuk semua bagian dan semua rotasi.
Berkomentar
sumber
C (dentang) ,
253239221212 byteCobalah online!
ps Sebenarnya ukuran kode adalah 221 byte (tetapi 212 karakter) karena karakter UNICODE dikodekan dalam UTF-8. Tapi tio.run memperlakukannya sebagai kode 212 byte ...
Ukuran kode pada komputer saya adalah 209 karakter (218 byte). Tapi saya tidak bisa mengganti
\225
dengan char terlihat di tio.run 😞Kode tidak dikunci
Deskripsi
Mari kita temukan garis dasar atas ( TBL ) dari setiap gambar dan menggambarkannya sebagai sejumlah sel di bawah TBL untuk setiap posisi horizontal. Juga mari kita jelaskan jumlah sel (tinggi) di atas TBL ( HAT )
Misalnya:
Mari kita gambarkan TBL dan HAT untuk setiap gambar dan setiap sudut rotasi:
Sekarang kita harus mengkodekan angka-angka ini sebagai urutan 2 bit dan dimasukkan ke dalam sebuah array (menggantikan
4 0
oleh3 1
90 ° sudut "line" untuk menyesuaikan diri 2 bit - hasil akan sama, dan penurunan lebar oleh 1).Kami akan menyandikan secara berurutan: lebar (dalam 2 LSB), TBL , HAT (mundur untuk loop mundur). Misalnya
2 2 1 1 0
untuk 270 ° sudut T-angka akan dikodekan sebagai1 0 1 2 1
(terakhir 1 adalah lebar-1 ):0b0100011001 = 281
.diperbarui 12.02:
a) Saya telah mengubah array menjadi string dan menyimpan 18 karakter (Anda dapat melihat kode 239 byte sebelumnya ) :))
b) Lebih optimasi, kode disusutkan oleh 9 karakter.
Ini adalah upaya terakhir saya (saya pikir begitu, lol!) 😀
sumber
<s> ... </s>
.Common Lisp, 634 bytes
Verbose
Menguji
Potongan-potongan adalah daftar bundar daftar angka. Sub-daftar ini masing-masing mewakili sisi bentuk, angka-angka yang menunjukkan seberapa jauh mereka dari sisi yang berlawanan. Mereka dibiarkan ke kanan ketika sisi itu di bagian bawah, kanan ke kiri ketika di atas, atas ke bawah ketika di kiri, dan bawah ke atas ketika di kanan. Pilihan desain ini menghilangkan kebutuhan untuk menulis kode untuk rotasi. Sayangnya, kurangnya kode rotasi tampaknya tidak menebus representasi bentuk yang panjang, atau logika yang agak rumit yang saya gunakan untuk menghitung ketinggian kolom baru.
Rotasi adalah bilangan bulat non-negatif. 0 = 0 derajat, 1 = 90 derajat, 2 = 180 derajat, 4 = 270 derajat
sumber
C # (Visual C # Interactive Compiler) , 308 byte
Cobalah online!
OK - Itu gila ... Saya mengirimkan jawaban yang menggunakan teknik kode-golf run-of-the-mill. Tetapi ketika saya melihat apa yang disampaikan orang lain, saya menyadari ada cara yang lebih baik.
Setiap
(shape, rotation)
tuple dikodekan ke dalam string C # literal dengan duplikat dihapus. Proses pengkodean menangkap masing-masing konfigurasi ini dalam 2 byte.Tinggi toko 3 bit terendah dan 3 lebar toko berikutnya. Karena masing-masing nilai ini tidak pernah lebih dari 4, nilai tersebut dapat dibaca langsung dari 3 bit tanpa konversi apa pun. Berikut ini beberapa contohnya:
Selanjutnya, setiap kolom disimpan dalam 3 bit. Yang paling berguna bagi saya untuk menyimpan adalah jumlah kotak yang hilang dari bagian atas dan bawah kolom.
Tidak pernah ada lebih dari 2 kotak yang hilang dari atas atau bawah, dan tidak pernah lebih dari 1 kotak hilang dari keduanya pada saat yang sama. Dengan serangkaian kendala ini, saya menghasilkan pengkodean berikut:
Karena kita harus menghitung paling banyak 3 kolom dengan kotak yang hilang di atas atau di bawah, kita dapat menyandikan setiap
(shape, rotation)
tuple dalam 15 bit.Terakhir, bentuk duplikat telah dihapus. Contoh berikut menunjukkan bagaimana beberapa
(shape,rotation)
tupel dapat menghasilkan output duplikat untuk bentuk yang sama pada rotasi yang berbeda:Semua output unik ditentukan dan disimpan ke a
byte[]
dan dikonversi ke string C # literal. Untuk mencari dengan cepat di mana bentuk didasarkan padaI
danR
, 7 byte pertama dari array terdiri dari kunci pencarian yang dikodekan.Di bawah ini adalah tautan ke program yang saya gunakan untuk mengompres bagian-bagian itu.
Cobalah online!
Lebih sedikit kode golf dan komentar:
sumber
Arang , 98 byte
Cobalah online! Tautan adalah untuk mengucapkan versi kode. Mengambil input sebagai array nilai [P, R, I], di mana saya dari 0 hingga 6, R adalah dari 0 o 3 dan P juga diindeks 0. Penjelasan:
Ulangi potongan input.
Ekstrak deskripsi potongan dan rotasi saat ini. (Lihat di bawah.)
Ekstrak posisi.
Pastikan ada ruang horizontal yang cukup untuk meletakkan potongan.
Pastikan ada ruang vertikal yang cukup untuk menempatkan potongan.
Hitung ketinggian baru dari kolom yang terpengaruh.
Ketika semua bagian telah diproses, buat daftar akhir ketinggian kolom pada baris yang berbeda.
String yang dikompresi mewakili string asli
00001923001061443168200318613441602332034173203014614341642430137
. Di sini2
s adalahI
pemisah dan1
s adalahR
pemisah. Potongan-potongan itu diterjemahkan sebagai berikut:R
Nilai yang hilang secara otomatis diisi secara siklis oleh Charcoal. Setiap digit kemudian memetakan ke dua nilai, overhang dan tinggi total, sesuai dengan tabel berikut:Overhang dan tinggi total berhubungan dengan ketinggian kolom sebagai berikut: Mengingat sepotong yang ingin kita tempatkan pada posisi tertentu
e
, dimungkinkan untuk menempatkan potongan meskipun salah satu kolom lebih tinggi darie
. Jumlah ruang cadangan diberikan oleh emperan. Ketinggian baru kolom setelah menempatkan potongan hanyalah posisi ditempatkan ditambah tinggi total.Contoh: Misalkan kita mulai dengan menempatkan
5
bagian dalam kolom 1. Karena tidak ada yang lain maka bagian itu ditempatkan di posisi 0 dan kolom 1 dan 3 sekarang memiliki tinggi 1 sedangkan kolom 2 memiliki tinggi 2. Kami kemudian ingin menempatkan6
sepotong dengan1
rotasi pada kolom 0. Di sini kita dapat menempatkan potongan ini pada posisi 0; meskipun kolom 1 memiliki tinggi 1, keping tersebut memiliki overhang 1, sehingga ada cukup ruang untuk meletakkannya. Kolom 0 berakhir dengan ketinggian 2 dan kolom 1 berakhir dengan ketinggian 3.sumber