Mari kita tentukan proses penghancuran array angka. Dalam naksir kita membaca array kiri ke kanan. Jika pada suatu titik kita menemukan dua elemen yang sama dalam satu baris, kita menghapus yang pertama dan menggandakan yang kedua. Sebagai contoh di sini adalah proses menghancurkan array berikut
[5,2,2,3]
^
[5,2,2,3]
^
[5,2,2,3]
^
[5,4,3]
^
[5,4,3]
^
Elemen yang sama dapat dihancurkan beberapa kali, misalnya [1,1,2]
menjadi [4]
ketika dihancurkan.
Kami akan memanggil array yang tidak bisa dihancurkan ketika proses menghancurkan array itu tidak mengubahnya. Misalnya [1,2,3]
masih [1,2,3]
setelah dihancurkan.
Tugas Anda adalah mengambil array dan menentukan jumlah crush yang diperlukan untuk membuatnya tidak bisa dihancurkan. Anda hanya perlu mendukung bilangan bulat pada kisaran 0 hingga 2 32 -1
Ini adalah kode-golf sehingga jawaban akan dinilai dalam byte dengan lebih sedikit byte lebih baik.
Uji Kasus
[1] -> 0
[1,1] -> 1
[2,1,1] -> 2
[4,2,1,1] -> 3
[2,2,2,1,1] -> 3
[0,0,0,0] -> 1
[4,0,0,0,4] -> 1
[4,0,0,0,0,4] -> 1
[] -> 0
sumber
[1,1,2,4,8]
mengembalikan 1 atau 4?0,0,0,0
hanya itu1
. Mungkin ide untuk secara eksplisit menyebutkan suatu tempat bahwa kita menghitung berapa kali kita harus melalui array untuk menghancurkannya secara penuh dan tidak , seperti yang saya pikirkan, jumlah total kali kita menghancurkan 2 angka bersama-sama.Jawaban:
perakitan x86 (64-bit),
6665 byteInstruksi string sangat membantu. Harus memperbaiki kesalahan off-by-one dalam lingkungan 64-bit tidak.
Kode sumber yang sepenuhnya dikomentari:
Saya dapat mencoba melakukan ini dalam 32-bit, jika hanya untuk bersenang-senang, karena awalan REX itu benar-benar membunuh saya.
Sunting: mencukur satu byte mati dengan mengganti lodsq dengan add,% rdx dengan% rax, dan menciutkan dua cld menjadi satu.
sumber
Pyth , 22 byte
Verifikasi semua testcases.
sumber
Haskell , 66 byte
Cobalah online!
Penjelasan
f
adalah fungsi yang menghancurkan daftar. Itu melakukan naksir seperti yang dijelaskan dalam pertanyaan.g
adalah fungsi yang menghitung jumlah crush. Jikaf x==x
,g x=0
sebaliknyag x=1+g(f x)
.sumber
g(f x)
keg$f x
+
memiliki prioritas lebih tinggi daripada$
Paradoc (v0.2.10), 16 byte (CP-1252)
Cobalah online! / dengan header / footer yang memeriksa semua kasus uji
Mengambil daftar di tumpukan, dan menghasilkan nomor di tumpukan.
Implementasi yang cukup mudah, cukup jujur. Menghancurkan daftar dengan memulai dengan sentinel -1, melewati daftar, mendorong setiap elemen dan menambahkannya ke elemen di bawahnya jika mereka sama. Pada akhirnya kita memotong -1. Kami hanya menghancurkan angka yang sama bersama-sama dan semua angka masalahnya tidak negatif, sehingga -1 sentinel tidak akan memengaruhi proses penghancuran. Dengan crushing diimplementasikan, itu hanya masalah menghitung iterasi ke titik tetapnya.
Penjelasan:
Jika kita dapat berasumsi bahwa inputnya bukan kosong, kita tidak akan memerlukan sentinel dan dapat mencukur 2 byte:
{(\ε=k+x}]}IL(
Fakta menyenangkan lainnya: kita hanya kehilangan 2 byte jika kita memaksakan diri untuk hanya menggunakan ASCII:
{1m\{=k+x}e]1>}IL(
sumber
JavaScript (ES6), 86 byte
Tidak Diikat dan Dijelaskan
Tes
Tampilkan cuplikan kode
sumber
a.length>n
sama dengana[n]!=[]._
. Dalam hal ini (karena semua item dalam array adalah angka lebih besar dari -1), itu sama dengana[n]>-1
. Juga,a[i]==a[++i]&&x
sama dengana[i]-a[++i]||x
.1/a[i]
juga berfungsi untuk menyimpan byte lain.JavaScript, 67 byte
Cobalah online!
sumber
Brain-Flak , 144 byte
Cobalah online!
Penjelasan
Fungsi crush mengevaluasi jumlah pasangan item yang dihancurkan bersama:
sumber
Java 8, 120 byte
Seekor lambda dari
List<Long>
keInteger
. Daftar input harus menerapkanremove(int)
(misArrayList
.). Tetapkan untukFunction<List<Long>, Integer>
.Cobalah secara Online
Lambda yang tidak tersentuh
c
menghitung jumlah crush sejauh ini,i
adalah indeks ke dalam daftar, danf
menunjukkan apakah akan terus menghancurkan daftar ketika iterasi selesai. Di dalam loop, setiap pasangan yang berdekatan dibandingkan.i
bertambah tanpa syarat, jadi jika suatu elemen dihilangkan dengan menghancurkan, makai
dikurangi terlebih dahulu untuk membatalkan kenaikan. Elemen sebelumnya dihapus dari daftar.Ucapan Terima Kasih
sumber
valueOf
cache. Contoh:{128L, 128L}
. Itu karenal.get(i)==l.get(i-1)
, yang harus digantil.get(i).equals(l.get(i-1))
.l.get(i)-l.get(i-1)==0
akan berhasil. Terima kasih!Perl 5 , 96 byte
94 kode, 2 untuk
-pa
Cobalah online!
sumber
JavaScript (ES6), 70 byte
Penjelasan:
Kasus uji:
Tampilkan cuplikan kode
sumber
Python 2 ,
112110108107105100 byteEdit: disimpan 2 byte dengan menghapus
or
dalam pernyataan kembaliSunting: menyimpan 2 byte dengan memiliki
i
sebagai indeks kedua dari dua elemen yang akan diaksesEdit: disimpan 1 byte berkat @ Mr.Xcoder
Sunting: disimpan 7 byte berkat @ jferard
Cobalah online!
sumber
JavaScript (ES6), 83 byte
Penjelasan: Elemen-elemen diekstraksi secara rekursif dari array asli dan nilai-nilai unik ditambahkan ke
b
sementarac
adalah bendera untuk menunjukkan apakah array telah berhasil dihancurkan.sumber
J, 54 byte
Cobalah online!
Bukan golf terbaik saya dengan cara apa pun. Tentunya harus ada cara yang lebih baik untuk mengubah daftar dengan satu item menjadi atom.
Penjelasan
menghancurkan
Ini menghancurkan array sekali. Perlu diberi array secara terbalik karena insert J bekerja dari kanan ke kiri (sesuatu yang saya pelajari hari ini). Ini tidak terlalu penting, karena yang kita butuhkan untuk output adalah berapa kali kita dapat menghancurkan array.
waktu
Ini cukup mudah: menerapkan naksir ke array sampai hasil kami menyatu, tetapi ada beberapa masalah yang saya harus berurusan dengan hasil dalam kode lebih banyak daripada yang saya perkirakan.
Pertama, ketika penghancuran dikurangi menjadi satu elemen, elemen itu sebenarnya ada dalam satu daftar item (yaitu nonatomik), jadi fungsi tersebut diterapkan lagi yang menghasilkan penghitungan yang berlebihan. Untuk memperbaikinya, saya menggunakan peretasan yang saya buat untuk mengurangi satu daftar elemen menjadi atom
".@":
(dikonversi ke string dan kemudian mengevaluasi).Kedua,
crush
kesalahan pada daftar kosong. Saya pikir Anda dapat menentukan bagaimana suatu fungsi harus berfungsi saat menerima input kosong dengan insert (/
), tapi saya tidak bisa menemukan apa pun setelah melihat sepintas, jadi saya menggunakan solusi lain. Solusi ini adalah dengan menambahkan_
(tak terhingga) ke daftar karena itu tidak akan mempengaruhi berapa kali array dihancurkan (_ > 2^64
). Namun , ini menghasilkan daftar elemen tunggal yang terdiri dari_
ketika diberikan daftar kosong, jadi kita perlu mengkonversi ke atom lagi sebelum dihancurkan.sumber
Jelly , 21 byte
Cobalah online!
sumber
R , 142 byte
Mengerikan, saya yakin ada cara yang lebih pintar.
Bilangan bulat R sebenarnya paling banyak
2^31-1
.Cobalah online!
sumber