Dugaan Collatz adalah dugaan yang sangat terkenal. Ambil bilangan bulat positif; jika itu genap, bagi dengan 2, yang lain, kalikan dengan 3 dan tambahkan 1. Ulangi sampai Anda mencapai 1
atau sesuatu yang lain terjadi. Dugaannya adalah proses ini selalu mencapai 1
.
Anda juga dapat membalikkan prosesnya. Mulai dari 1
, gandakan dengan 2, dan untuk bercabang ke multiply by 3 and add 1
angka, ketika Anda mencapai angka genap 1 (mod 3)
, kurangi 1 dan bagi dengan 3.
Jalur Collatz menggabungkan keduanya, mencoba untuk berpindah dari satu nomor ke nomor lainnya dengan keempat operasi itu.
Misalnya, untuk mendapatkan 20
dari 1
:
1 *2
2 *2
4 *2
8 *2
16 *2
5 (-1)/3
10 *2
20 *2
Anda juga bisa mendapatkan 3
dari 10
dengan mengurangi 1 dan membaginya dengan 3.
Dengan alat-alat ini, Anda dapat melintasi jalur Collatz dari satu nomor ke yang lain. Misalnya, jalur dari 20
ke 3
adalah (bagi dengan 2), (kurangi 1, bagi dengan 3).
Singkatnya, operasi yang tersedia adalah:
n * 2 always
n // 2 if n % 2 == 0
n * 3 + 1 if n % 2 == 1
(n-1) // 3 if n % 6 == 4
Catatan: tidak semua jalur Collatz pendek. a(7,3)
bisa berlari
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 2, 4, 8, 16, 5, 10, 3
tapi jalan yang lebih pendek adalah
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 3
Tantangan
Temukan panjang jalur Collatz terpendek antara dua bilangan bulat positif, p
dan q
.
- Input adalah dua bilangan bulat positif kurang dari
2^20
untuk menghindari bilangan bulat bilangan bulat. Metode input diserahkan kepada kebijaksanaan pegolf. Bilangan bulat mungkin sama, dalam hal ini, panjang jalur Collatz adalah0
. - Output harus berupa satu bilangan bulat, yang menunjukkan panjang jalur Collatz terpendek antara
p
danq
.
Uji Kasus
a(2,1)
1
a(4,1)
1 # 4 -> 1
a(3,1)
6 # 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1
a(11,12)
11 # 11 -> 34 -> 17 -> 52 -> 26 -> 13
# -> 40 -> 20 -> 10 -> 3 -> 6 -> 12
a(15,9)
20 # 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 13
# -> 26 -> 52 -> 17 -> 34 -> 11 -> 22 -> 7 -> 14 -> 28 -> 9
Terima kasih banyak orlp atas bantuan mereka dalam mengklarifikasi tantangan ini.
Seperti biasa, jika masalahnya tidak jelas, beri tahu saya. Semoga berhasil dan bermain golf dengan baik!
Jawaban:
Haskell,
170 158 157 146 143 137 135 112 109 108 106 10099 byteSaya tidak berharap bahwa versi asli saya jauh lebih golf, ini juga karya @nimi @Lynn dan @Laikoni!
Terima kasih @Laikoni untuk byte, @Lynn untuk
11 14 2021 byte, @nimi selama 8 byte!Ini memperluas pohon angka yang dikunjungi (dimulai dengan
a
) langkah demi langkah, dan memeriksa di setiap langkah apakah kita sampai pada angka yang diberikanb
.sumber
iterate s [a] -> iterate s[a]
s
menghemat tiga byte lagi!iterate(nub.concat.map f)[a]
Juga, apakah Anda benar-benar membutuhkannyanub
?break
danspan
sangat berguna![div n 2,n*3+1]!!mod n 2
dengancycle[div n 2,n*3+1]!!n
menghemat satu byte lagi :)Python 2, 110 byte
sumber
Pyth, 30 byte
Cobalah online
Bagaimana itu bekerja
Ambil panjang perbedaan simetris dari dua urutan Collatz maju mulai dari dua nomor input dan berakhir pada 2. Satu-satunya pengecualian adalah jika inputnya adalah
[1, 2]
atau[2, 1]
, yang kami khusus-kasus.sumber
Python 2,
156179191209181172177171 byteKarena jalur Collatz dapat dibayangkan sebagai
a(1,p)
dana(1,q)
digabungkan pada nomor pertama yang umum untuk kedua urutan dana(1,n)
merupakan dugaan Collatz asli, fungsi ini menghitung urutan Collatz darip
danq
, dan menghitung panjang dari sana. Ini bukan golf yang cantik, jadi saran bermain golf sangat disambut. Satu-satunya pengecualian adalah kapanp or q == 1
. Kemudian, karena kita dapat melompat langsung dari4
ke yang1
bertentangan dengan urutan Collatz biasa, kita perlu mengurangi langkah dari hasilnya.Sunting: Banyak perbaikan bug.
Sunting: Banyak dan banyak perbaikan bug
Cobalah online!
sumber
a(3,1)
mengembalikan 7 sedangkan harus mengembalikan 6, karena jalur terpendek adalah3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1
f
menunjukkan langkah maju,b
langkah mundur dalam urutan collatz. Polanyab->f
tidak dapat berada di jalur terpendek, karena itu adalah identitas (tidakf
dapat dihilangkanb
dalam hal apa pun.) Jadi jalur terpendek hanya dapat terdiri dari polaf->f
,f->b
danb->b
. Itu berarti lagi bahwa jalur terpendek selalu dari bentukf->f->...->f
ataub->b->...->b
atauf->...->f->b->...->b
JavaScript (ES6), 135 byte
Melakukan pencarian luas pertama.
x
adalah angka awal,y
tujuan,a
larik nilai percobaan,s
larik jumlah langkah inklusif pada rantai darix
,z
nilai saat ini. Jikaz
dany
tidak sama, hitungz*2
,z/2
dan salah satuz*3+1
atau(z-1)/3
, tergantung pada apakahz
ganjil atau genap, kemudian filter fraksi dan nilai yang terlihat sebelumnya dan tambahkan ke daftar pencarian.sumber
Python 2, 80 byte
Ambil panjang perbedaan simetris dari dua urutan Collatz maju mulai dari dua nomor input dan berakhir pada 2. Satu-satunya pengecualian adalah jika inputnya adalah 1, 2 atau 2, 1, yang kami beri kasus khusus.
sumber