Jalur Collatz: Maju dan Mundur di sepanjang Dugaan Collatz

8

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 1atau 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 1angka, 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 20dari 1:

1     *2
2     *2
4     *2
8     *2
16    *2
5     (-1)/3
10    *2
20    *2

Anda juga bisa mendapatkan 3dari 10dengan mengurangi 1 dan membaginya dengan 3.

Dengan alat-alat ini, Anda dapat melintasi jalur Collatz dari satu nomor ke yang lain. Misalnya, jalur dari 20ke 3adalah (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, pdan q.

  • Input adalah dua bilangan bulat positif kurang dari 2^20untuk menghindari bilangan bulat bilangan bulat. Metode input diserahkan kepada kebijaksanaan pegolf. Bilangan bulat mungkin sama, dalam hal ini, panjang jalur Collatz adalah 0.
  • Output harus berupa satu bilangan bulat, yang menunjukkan panjang jalur Collatz terpendek antara pdan q.

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!

Sherlock9
sumber
1
Komputer kami tidak akan tahan array setidaknya 2 ^ 31 elemen.
@MatthewRoh Challenge sejak itu telah diedit.
Sherlock9
Ini cukup banyak tantangan pencarian-jalan grafik-teori . Dan saya cukup yakin kita memiliki yang hampir identik sebelumnya.
flawr
Kemungkinan duplikat jalur terpendek dalam grafik pembagi
flawr
2
@ flawr Saya tidak setuju dengan duplikat. Ya, kedua tantangan ingin menemukan jalur dalam grafik, tetapi grafiknya berbeda, dan menyandikan struktur grafik dalam jawaban Anda adalah bagian yang unik, IMO. Lihat misalnya jawaban saya, dan bandingkan dengan jawaban di pertanyaan 'rangkap' Anda.
orlp

Jawaban:

3

Haskell, 170 158 157 146 143 137 135 112 109 108 106 100 99 byte

a!b=length$fst$break(elem b)$iterate(>>= \n->2*n:cycle[div n 2,n*3+1]!!n:[div(n-1)3|mod n 6==4])[a]

Saya 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 20 21 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 diberikan b.

cacat
sumber
Anda melewatkan satu ruang:iterate s [a] -> iterate s[a]
Laikoni
Manis ~ Inlining smenghemat tiga byte lagi! iterate(nub.concat.map f)[a]Juga, apakah Anda benar-benar membutuhkannya nub?
Lynn
Katakan padaku ketika kamu selesai bermain golf: D Terima kasih banyak. Sayangnya saya masih kesulitan memahami monad.
flawr
@nimi Sekali lagi, terima kasih banyak, saya tidak pernah menyangka bahwa ini jauh lebih golf! Saya tidak tahu breakdan spansangat berguna!
flawr
1
Mengganti [div n 2,n*3+1]!!mod n 2dengan cycle[div n 2,n*3+1]!!nmenghemat satu byte lagi :)
Lynn
2

Python 2, 110 byte

a=lambda p,q,s={0}:1+a(p,q,s.union(*({p,n*2,[n/2,n*3+1][n%2]}|set([~-n/3]*(n%6==4))for n in s)))if{q}-s else-1
orlp
sumber
1

Pyth, 30 byte

|q*FQ2ls-M.pm.u&n2N?%N2h*3N/N2

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.

  *FQ                        product of the input
|q   2                       if that equals 2, return 1 (True), else:
            m                  map for d in input:
             .u                  cumulative fixed-point: starting at N=d, iterate N ↦
               &n2N?%N2h*3N/N2     N != 2 and (N*3 + 1 if N % 2 else N/2)
                                 until a duplicate is found, and return the sequence
          .p                   permutations
        -M                     map difference
       s                       concatenate
      l                        length
Anders Kaseorg
sumber
1

Python 2, 156 179 191 209 181 172 177 171 byte

Karena jalur Collatz dapat dibayangkan sebagai a(1,p)dan a(1,q)digabungkan pada nomor pertama yang umum untuk kedua urutan dan a(1,n)merupakan dugaan Collatz asli, fungsi ini menghitung urutan Collatz dari pdan q, dan menghitung panjang dari sana. Ini bukan golf yang cantik, jadi saran bermain golf sangat disambut. Satu-satunya pengecualian adalah kapan p or q == 1. Kemudian, karena kita dapat melompat langsung dari 4ke yang 1bertentangan dengan urutan Collatz biasa, kita perlu mengurangi langkah dari hasilnya.

Sunting: Banyak perbaikan bug.

Sunting: Banyak dan banyak perbaikan bug

f=lambda p:[p]if p<3else f([p//2,p*3+1][p%2])+[p]
def a(p,q):
 i=1;c=f(p);d=f(q)
 if sorted((p,q))==(1,2):return 1
 while c[:i]==d[:i]!=d[:i-1]:i+=1
 return len(c+d)-2*i+2

Cobalah online!

Sherlock9
sumber
Pendekatan Anda tidak berfungsi, misalnya a(3,1)mengembalikan 7 sedangkan harus mengembalikan 6, karena jalur terpendek adalah3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1
flawr
@ flawr Diedit. Semoga itu berfungsi sekarang
Sherlock9
Mengapa Anda menganggap bahwa algoritme yang Anda gambarkan berfungsi? Tidak bisakah jalur terpendek terdiri dari beberapa kali "bolak-balik"?
flawr
2
Biarkan fmenunjukkan langkah maju, blangkah mundur dalam urutan collatz. Polanya b->ftidak dapat berada di jalur terpendek, karena itu adalah identitas (tidak fdapat dihilangkan bdalam hal apa pun.) Jadi jalur terpendek hanya dapat terdiri dari pola f->f, f->bdan b->b. Itu berarti lagi bahwa jalur terpendek selalu dari bentuk f->f->...->fatau b->b->...->batauf->...->f->b->...->b
flawr
3
PS: Saya memiliki kesan jumlah byte Anda pergi ke arah yang salah. : D
flawr
0

JavaScript (ES6), 135 byte

f=(x,y,a=[(s=[],s[0]=s[x]=1,x)],z=a.shift())=>z-y?[z*2,z/2,z%2?z*3+1:~-z/3].map(e=>e%1||s[e]?0:s[a.push(e),e]=-~s[z])&&f(x,y,a):~-s[y]

Melakukan pencarian luas pertama. xadalah angka awal, ytujuan, alarik nilai percobaan, slarik jumlah langkah inklusif pada rantai dari x, znilai saat ini. Jika zdan ytidak sama, hitung z*2, z/2dan salah satu z*3+1atau (z-1)/3, tergantung pada apakah zganjil atau genap, kemudian filter fraksi dan nilai yang terlihat sebelumnya dan tambahkan ke daftar pencarian.

Neil
sumber
0

Python 2, 80 byte

p=lambda n:n-2and{n}|p([n/2,n*3+1][n%2])or{n}
lambda m,n:m*n==2or len(p(m)^p(n))

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.

Anders Kaseorg
sumber