Rantai Gozinta
(Terinspirasi oleh Project Euler # 606 )
Rantai gozinta untuk n adalah urutan di {1,a,b,...,n}
mana setiap elemen membagi dengan benar berikutnya. Misalnya, ada delapan rantai gozinta yang berbeda untuk 12:
{1,12}, {1,2,12}, {1,2,4,12}, {1,2,6,12}, {1,3,12}, {1,3,6,12}, {1,4,12} and {1,6,12}.
Tantangan
Tulis program atau fungsi yang menerima bilangan bulat positif ( n > 1
) dan mengeluarkan atau mengembalikan semua rantai gozinta yang berbeda untuk angka yang diberikan.
- Urutan dalam rantai penting (naik), urutan rantai tidak.
- Jika ada, Anda tidak dapat menggunakan builtin yang menyelesaikan tantangan.
- Ini adalah kode-golf .
Sunting: Menghapus 1
sebagai input potensial.
code-golf
sequence
arithmetic
Payung
sumber
sumber
[[1]]
saya akan mengatakan bahwa jika[1,1]
gozinta1
maka[1,1,12]
gozinta12
apa adanya[1,1,1,12]
dan sekarang kita bisa tidak lagi "kembalikan semua ..."2|4
dibaca "dua masuk ke empat" alias "dua gozinta empat".Jawaban:
Python 3 ,
6865 byteSunting: -3 byte terima kasih kepada @notjagan
Cobalah online!
Penjelasan
Setiap rantai gozinta terdiri dari nomor
x
di ujung rantai, dengan setidaknya satu pembagi di sebelah kiri itu. Untuk setiap pembagik
darix
rantai[1,...,k,x]
yang berbeda. Karena itu kita dapat untuk setiap pembagik
menemukan semua rantai gozinta yang berbeda dan menambahkannyax
ke akhir, untuk mendapatkan semua rantai gozinta yang berbeda dengank
langsung ke kirix
. Ini dilakukan secara rekursif sampai dix = 1
mana[[1]]
dikembalikan, karena semua rantai gozinta mulai dengan 1, yang berarti rekursi telah mencapai titik terendah.Kode menjadi sangat pendek karena pemahaman daftar Python memungkinkan iterasi ganda. Ini berarti bahwa nilai yang ditemukan di
f(k)
dapat ditambahkan ke daftar yang sama untuk semua pembagi yang berbedak
.sumber
Sekam , 13 byte
Pendekatan yang agak berbeda dengan H.PWiz , meskipun masih dengan kekerasan. Cobalah online!
Penjelasan
Gagasan dasarnya adalah menggabungkan semua
[1,...,n]
urutan dan membagi hasilnya menjadi sublist di mana masing-masing elemen membagi berikutnya. Dari jumlah tersebut, kami menyimpan yang dimulai dengan1
, diakhiri dengann
dan tidak mengandung duplikat. Ini dilakukan dengan built-in "rangify"…
. Kemudian tetap membuang duplikat.sumber
Jelly ,
98 byteCobalah online!
Menggunakan teknik yang mirip dengan jawaban Japt saya , dan karenanya berjalan sangat cepat pada kasus uji yang lebih besar.
Bagaimana itu bekerja
sumber
Mathematica, 77 byte
Membentuk a di
Graph
mana simpul adalahDivisors
dari input#
, dan ujung-ujungnya mewakili pembagian yang tepat, kemudian menemukanAll
jalur dari titik1
ke titik#
.sumber
Jelly , 12 byte
Tautan monadik yang menerima bilangan bulat dan mengembalikan daftar daftar bilangan bulat.
Cobalah online!
Bagaimana?
Kami ingin semua daftar bilangan bulat unik yang diurutkan antara satu dan N sedemikian rupa sehingga yang pertama adalah satu, yang terakhir adalah N, dan semua pasangan dibagi. Kode mencapai filter ini dengan memeriksa kriteria pembagian pasangan-bijaksana puas atas set daya rentang yang dimaksud, tetapi hanya memilih mereka dengan jumlah maksimum perbedaan inkremental (yang dimulai dengan satu dan berakhir dengan N akan memiliki sejumlah perbedaan inkremental N-1, yang lain akan memiliki lebih sedikit).
sumber
<slice>2<divisible>\<each>
: PƝ
sebagai ganti `2` untuk 11 byte .Japt , 17 byte
Uji secara online!
Anehnya, menghasilkan output sebagai string jauh lebih mudah daripada menghasilkannya sebagai array array ...
Penjelasan
sumber
¬
trik itu! : p¬
adalah salah satu alasan mengapa saya telah mengimplementasikan banyak fungsi yang pada dasarnya "melakukan X tanpa argumen, atau Y diberi argumen yang benar": PMathematica, 60 byte
Penggunaan bentuk multi-arg tak tercatat dari
Divisible
, di manaDivisible[n1,n2,...]
pengembalianTrue
jikan2∣n1
,n3∣n2
dan sebagainya, danFalse
sebaliknya. Kami mengambil semuaSubsets
dari daftarDivisors
input#
, kemudian kembaliCases
dari bentuk{1,___,#}
sehinggaDivisible
memberikanTrue
untukReverse
d urutan pembagi.sumber
Divisible
apakah pada dasarnya adalah builtin untuk memverifikasi rantai gozinta?Haskell, 51 byte
Secara rekursif menemukan rantai gozinta pembagi yang tepat dan tambahkan
n
.Cobalah online!
sumber
1
. Karena secara kolektif kami memutuskan untuk dibebaskan1
, dapatkah Anda menghemat 10 byte dengan menghapus kasing itu?1
bukan kasus khusus untuk algoritma ini, diperlukan sebagai kasus dasar untuk rekursi. Dengan sendirinya, persamaan pendefinisian kedua hanya dapat mengembalikan daftar kosong.[[1]]
sebagai basis.Haskell (Lambdabot),
9285 byteKebutuhan Lambdabot Haskell sejak
guard
membutuhkanControl.Monad
harus diimpor. Fungsi utama adalah fungsi anonim, yang saya diberitahu diizinkan dan memangkas beberapa byte.Terima kasih kepada Laikoni karena telah menghemat tujuh byte.
Penjelasan:
Monad sangat berguna.
Ini adalah fungsi rekursif kami yang melakukan semua pekerjaan yang sebenarnya.
x
adalah angka yang kita akumulasikan (produk dari pembagi yang tetap dalam nilainya), dany
merupakan angka berikutnya yang harus kita coba bagi ke dalamnya.Jika
x
samay
maka kita sudah selesai berulang. Cukup gunakanx
sebagai akhir dari rantai gozinta saat ini dan kembalikan.Haskell golf-isme untuk "True". Artinya, ini adalah kasus default.
Kami beroperasi di dalam daftar monad sekarang. Dalam daftar monad, kami memiliki kemampuan untuk membuat banyak pilihan sekaligus. Ini sangat membantu ketika menemukan "semua kemungkinan" dari sesuatu dengan kelelahan. The
guard
pernyataan mengatakan "hanya mempertimbangkan pilihan berikut jika kondisi benar". Dalam hal ini, hanya pertimbangkan pilihan berikut jikay
membelahx
.Jika
y
memang memecahx
, kami memiliki pilihan untuk menambahkany
ke rantai gozinta. Dalam hal ini, secara rekursif panggilan(#)
, mulai lagi dari awal diy = 2
denganx
sama denganx / y
, karena kita ingin "faktor luar" yangy
kita hanya ditambahkan ke rantai. Lalu, apa pun hasil dari panggilan rekursif ini, gandakan nilainya dengan yangy
baru saja kamiy
pertimbangkan dan tambahkan ke rantai gozinta secara resmi.Pertimbangkan pilihan berikut juga. Ini hanya menambahkan dua daftar bersama, tetapi secara monadis kita dapat menganggapnya sebagai mengatakan "pilih antara melakukan hal ini ATAU hal lain ini".
Opsi lainnya adalah terus berulang dan tidak menggunakan nilainya
y
. Jikay
tidak membagix
maka ini adalah satu-satunya pilihan. Jikay
tidak membagix
maka opsi ini akan diambil serta opsi lainnya, dan hasilnya akan digabungkan.Ini adalah fungsi utama gozinta. Itu memulai rekursi dengan memanggil
(#)
dengan argumennya. A1
ditambahkan ke setiap rantai gozinta, karena(#)
fungsi tidak pernah menempatkan orang ke dalam rantai.sumber
mod x y==0
dapat disingkat menjadimod x y<1
. Karena fungsi anonim diizinkan, fungsi utama Anda dapat ditulis sebagai pointfreemap(1:).(#2)
.Haskell,
10710095 byteMungkin ada kondisi terminasi yang lebih baik (mencoba sesuatu seperti
tapi ini lebih lama). Pemeriksaan untuk
1
tampaknya bijaksana karena menggosok ulangi1
s atau duplikat (nub
tidak dalamPrelude
) lebih banyak byte.Cobalah online.
sumber
(>>=h)
untuk(concatMap h)
u
JavaScript (Firefox 30-57), 73 byte
Nyaman
n%0<1
itu salah.sumber
Jelly , 17 byte
Cobalah online!
sumber
1
tidak terduga. Saya belum berhasil menemukan hasil yang pasti1
, tetapi saya berasumsi demikian[[1]]
. Saya tidak bisa mengatakan dengan pasti bahwa[1,1]
itu tidak benar kecuali bahwa semua hasil lainnya meningkatkan urutan. Pikiran?;€
dengan;Q¥€
).Mathematica, 104 byte
sumber
FreeQ[...]
bisa menjadiAnd@@BlockMap[#∣#2&@@#&,#,2,1]
Developer
PartitionMap :: nlen: - Teks pesan tidak ditemukan - >> `kenapa begitu?BlockMap
menggunakanDeveloper`PartitionMap
fungsi secara internal, tetapi karena ini adalah fungsi pengembang, ia tidak memiliki pesan kesalahan. Kesalahan ini disebabkan oleh daftar yang memiliki 1 atau 0 elemen, yang Anda tidak dapat membuat 2-partisi dengan.Mathematica, 72 byte
Penjelasan
Temukan semua pembagi input.
Hasilkan semua himpunan bagian dari daftar itu.
Pilih semua kotak yang sesuai dengan pola ...
Dimulai dengan 1 dan berakhir dengan
<input>
...dan memenuhi syarat ...
Elemen kiri membagi elemen kanan untuk semua 2-partisi daftar, offset 1.
sumber
TI-BASIC, 76 byte
Penjelasan
Saya bisa menyimpan 5 byte lagi jika diizinkan keluar dengan kesalahan alih-alih dengan anggun, dengan menghapus centang Ans> 1 dan kondisi loop. Tapi saya tidak yakin itu diizinkan.
sumber
Mathematica
8677 BytesBrute force menurut definisi.
Berharap ada cara yang lebih pendek untuk melakukan perbandingan elemen berurutan dari daftar.
Terima kasih kepada @Jenny_mathy dan @JungHwanMin untuk saran menghemat 9 byte
sumber
FreeQ[#∣#2&@@@Partition[#,2,1],1>2]&]
(sebagai argumen kedua) untuk menuju ke 82 byteAnd@@BlockMap[#∣#2&@@#&,#,2,1]
Sekam ,
1716 byte-1 byte, terima kasih kepada Zgarb
Cobalah online!
sumber
50
input dan waktunya habis. Apa inti dari pendekatan Anda?o`:⁰:1
dapat`Je1⁰
PHP
147141Diedit untuk menghapus tes yang berlebihan
Dijelaskan:
15 karakter boilerplate :(
Init hasil ditetapkan
[[1]]
sebagai setiap rantai dimulai dengan 1. Ini juga mengarah ke dukungan untuk 1 sebagai input.Untuk setiap nomor dari 2 sampai
$i
, kita akan memperpanjang rantai masing-masing di set kami dengan jumlah saat ini jika itu gozinta , kemudian, menambahkan rantai diperpanjang untuk hasil yang ditetapkan kami.Saring rantai perantara kami yang tidak berhasil
$i
10 karakter boilerplate :(
sumber
Mathematica
Jawaban di-cache untuk panggilan tambahan.
sumber