Tantangannya sangat sederhana: mengingat angka, Anda membagi angka-angkanya menjadi array angka yang lebih kecil sehingga angka yang dihasilkan tidak menurun. Tangkapannya adalah Anda harus membaginya sehingga panjang array maksimal.
Bingung?
- Anda diberi bilangan bulat positif melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dalam format input apa pun yang nyaman dan tidak ambigu.
- Anda harus mempartisi angka desimal angka menjadi kelompok-kelompok yang berdekatan dan terpisah.
- Susunan angka yang diwakili oleh grup digit ini harus diurutkan (dalam urutan biasa, tidak menurun) tanpa menata ulang grup .
- Dalam kasus di mana terdapat lebih dari satu partisi seperti itu, Anda harus mempartisi input menjadi angka sebanyak mungkin. Dalam kasus ikatan, kembalikan satu hasil seperti itu.
- Anda bisa menampilkan array ke STDOUT (atau alternatif terdekat) atau sebagai nilai pengembalian fungsi. Dalam hal STDOUT (atau alternatif terdekat), array harus dicetak dalam format daftar yang nyaman dan tidak ambigu.
- Nomor yang dipisah tidak boleh memiliki angka nol di depan. Jadi misalnya
1002003
tidak dapat dicetak sebagai salah satu[1, 002, 003]
atau[1, 2, 3]
satu-satunya jawaban yang valid untuk itu[100, 2003]
.
Kasus uji:
123456 -> [1, 2, 3, 4, 5, 6]
345823 -> [3, 4, 5, 8, 23]
12345678901234567890 -> [1, 2, 3, 4, 5, 6, 7, 8, 90, 123, 456, 7890]
102 -> [102]
302 -> [302]
324142 -> [3, 24, 142] OR [32, 41, 42]
324142434445 -> [32, 41, 42, 43, 44, 45]
1356531 -> [1, 3, 5, 6, 531]
11121111111 -> [1, 1, 1, 2, 11, 11, 111]
100202003 -> [100, 202003]
Mencetak gol
Ini adalah kode-golf sehingga kode terpendek dalam byte menang.
code-golf
number
combinatorics
set-partitions
Pengoptimal
sumber
sumber
aY
sebagai gantinya~Y]
a
. Tidak tahu kenapaint("01")
menjadi kesalahan dalam Pyth (ini tidak terjadi dengan Python).n
adalah panjang input.Mathematica,
134127 byteIni cukup tidak efisien karena menghasilkan lebih banyak partisi daripada yang valid. Kasing
324142434445
uji berjalan dalam beberapa detik, tetapi saya tidak akan mencoba12345678901234567890
.Ini mendefinisikan fungsi tanpa nama yang mengambil integer dan mengembalikan daftar integer.
Penjelasan
Urutan pembacaan kode ini sedikit di semua tempat, jadi saya akan memecah dalam urutan yang dimaksudkan untuk dibaca (dan dievaluasi untuk sebagian besar):
d=IntegerDigits@#
dapatkan digit desimal input dan tetapkan daftar inid
.SetPartitions
(yang mengharuskanNeeds@"Combinatorica`";
) memberi saya semua partisi ini. Namun, ia mengembalikan lebih banyak daripada yang sebenarnya saya inginkan karena memperlakukan input sebagai satu set . Inilah yang membuatnya tidak efisien, tapi saya menggunakan ini karena cara terpendek yang saya tahu untuk mendapatkan semua daftar partisi jauh lebih lama. Sebagai contoh, jika daftar itu{1, 2, 3}
fungsinya akan kembali:Perhatikan bahwa a) partisi berturut-turut semuanya dalam urutan yang benar dan b) partisi diurutkan dari kasar ke terbaik.
Select[...,...&]
kemudian memfilter daftar ini dengan fungsi anonim yang diteruskan sebagai argumen kedua.Join @@ # == d
memeriksa apakah kita benar-benar mendapatkan daftar partisi daripada partisi set umum.#~FreeQ~{0, __}
memeriksa apakah tidak ada partisi yang dimulai dengan nol di depannya.0 <= ## & @@ f /@ #
sedikit lebih tidak jelas. Pertama kita memetakanFromDigits
ke setiap daftar di partisi untuk memulihkan angka yang diwakili oleh digit. Kemudian kami berlaku0 <= ##
untuk angka-angka itu, di mana##
mengacu pada semua angka. Jika partisi{1, 23, 45}
kemudian diperluas0 <= 1 <= 23 <= 45
, sehingga memeriksa bahwa array diurutkan.Last@
lalu memberi saya partisi terakhir yang tersisa setelah pemfilteran - ini berfungsi karenaSetPartitions
sudah mengurutkan partisi, sehingga yang terbaik ada di akhir.f/@
memulihkan nomor dari daftar digit.sumber
Python 3, 134 byte
Agak berantakan, tapi oh well. Program ini hanya menghasilkan semua partisi yang valid secara rekursif. Bagian yang menarik adalah bahwa untuk melarang angka nol di depan, semua yang diperlukan adalah
or "1">s[i:]>""
syarat tambahan .Mengambil input suka
f("12345678901234567890")
dan mengembalikan daftar int.sumber
Pyth,
626160Penjelasan
Algoritma ini bekerja dengan menghasilkan semua angka biner antara
0
(inklusif) dan2^(n-1)
(eksklusif), di manan
panjang input.Digit biner masing-masing kemudian dipetakan ke pemisah (
N
) untuk 1 dan tidak ada untuk 0.Karakter-karakter ini kemudian disisipkan di antara masing-masing karakter input, dan hasilnya dibagi
N
, menghasilkan daftar.Nilai-nilai dalam daftar kemudian diuraikan menjadi bilangan bulat, dan daftar diurutkan berdasarkan panjangnya. Kemudian yang tersisa adalah menyaring yang tidak diurutkan dan yang telah dipisah pada nol terkemuka, setelah itu daftar terpanjang diambil.
sumber
(NON-COMPETING) Pyth, 25 byte
Cobalah online!
Bagaimana itu bekerja:
sumber
J, 109 byte
Sangat lama tetapi setidaknya memakan memori O (n * (2n)!) Dan O (n * log (n) * (2n)!) Waktu di mana n adalah panjang input. (Jadi jangan coba-coba menjalankannya dengan lebih dari 5 digit.)
Fungsi mengambil input sebagai string.
Contoh:
Metode:
sumber
Haskell, 161 byte
Uji coba:
Cara kerjanya: fungsi helper
f
membagi daftar input menjadi setiap daftar yang mungkin dari daftar.g
pertama-tama buang yang memiliki sublist yang diawali dengan0
dan kemudian yang tanpa urutan yang tepat. Pasangkan setiap daftar yang tersisa dengan panjangnya, ambil maksimum dan buang bagian panjang lagi.sumber