Dugaan Collatz (OEIS A006577)

66

Ini adalah dugaan Collatz (OEIS A006577 ):

  • Mulai dengan bilangan bulat n > 1.
  • Ulangi langkah-langkah berikut:
    • Jika n adalah genap, bagilah dengan 2.
    • Jika n ganjil, kalikan dengan 3 dan tambahkan 1.

Terbukti bahwa untuk semua bilangan bulat positif hingga 5 * 2 60 , atau sekitar 576400000000000000000 , n pada akhirnya akan menjadi 1 .

Tugas Anda adalah untuk mengetahui berapa banyak iterasi yang dibutuhkan (untuk membagi dua atau tiga kali lipat-plus-satu) untuk mencapai 1 .

Xkcd relevan :)

Aturan:

  • Kode terpendek menang.
  • Jika angka <2 adalah input, atau non-integer, atau non-angka, output tidak menjadi masalah.

Uji kasus

2  -> 1
16 -> 4
5  -> 5
7  -> 16
code-golf math Gagang pintu
sumber

Jawaban:

19

GolfScript, 24 23 21 20 18 karakter

~{(}{3*).2%6\?/}/,

Mengasumsikan input pada stdin. Tes online

Keriangan
sumber
3
1+adalah kasus khusus ).
Peter Taylor
@PeterTaylor tentu saja, lupakan itu;)
Volatilitas
1
Kerja bagus! <! - padding ->
Peter Taylor
1
@ Peter: The <! - -> tidak berfungsi dalam komentar. Gunakan ini sebagai gantinya.
Ilmari Karonen
2
Atau ini.
Timwi
15

C - 50 47 karakter

Sayangnya, si C kecil yang malang membutuhkan sejumlah besar kode untuk I / O dasar, jadi menyingkat semua itu membuat UI sedikit tidak intuitif.

b;main(a){return~-a?b++,main(a&1?3*a+1:a/2):b;}

Kompilasi dengan misalnya gcc -o 1 collatz.c. Inputnya unary dengan digit yang dipisahkan oleh spasi, dan Anda akan menemukan jawabannya di kode keluar. Contoh dengan angka 17:

$> ./1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
$> echo $?
12
$>
Untuk S
sumber
1
return~-a?menghemat 1. Juga pindah b++ke ?kasing harus menyimpan b--.
ugoren
Hehe Anda membungkuk aturan begitu banyak: P 1 untuk kreativitas dan menggunakan bahasa biasanya tidak digunakan untuk golf
Doorknob
Ugoren terima kasih! Saya pasti mabuk ketika menulisnya. :)
Fors
12

Perl 34 (+1) karakter

$\++,$_*=$_&1?3+1/$_:.5while$_>1}{

Menyalahgunakan $\untuk hasil akhir, seperti biasa. Jalankan dengan -popsi baris perintah, input diambil dari stdin.

Disimpan satu byte karena Elias Van Ootegem . Secara khusus, pengamatan bahwa dua berikut ini setara:

$_=$_*3+1
$_*=3+1/$_

Meskipun satu byte lebih lama, ia menghemat dua byte dengan memperpendek $_/2menjadi hanya .5.

Penggunaan sampel:

$ echo 176 | perl -p collatz.pl
18

PHP 54 byte

<?for(;1<$n=&$argv[1];$c++)$n=$n&1?$n*3+1:$n/2;echo$c;

Arkeologi Javascript untuk Penghargaan Sendok Kayu tampaknya telah gagal dalam tantangan ini. Namun, tidak ada banyak ruang untuk kreativitas dengan masalah ini. Input diambil sebagai argumen baris perintah.

Penggunaan sampel:

$ php collatz.php 176
18
primo
sumber
1
Butuh waktu beberapa saat untuk mencari tahu apa yang dilakukan kurung yang tak tertandingi :)
marinus
1
Mengulangi $_di terner tampaknya boros, Anda bisa mencukur habis karakter lain dengan menggunakan *=seperti ini: $\++,$_*=$_&1?3+1/$_:.5while$_>1}{. Mengalikan dengan 1/$_memiliki efek yang sama dengan +1, jadi $_*=3+1/$_berfungsi dengan baik
Elias Van Ootegem
@EliasVanOotegem $_*=3+1/$_brilian, terima kasih!
primo
11

Mathematica (35)

If[#>1,#0@If[OddQ@#,3#+1,#/2]+1,0]&

Pemakaian:

If[#>1,#0[If[OddQ@#,3#+1,#/2]]+1,0]&@16
>> 4
mil
sumber
Ini bukan fungsi yang valid, 10.3 mengeluh tentang bajingan @ pada akhirnya
CalculatorFeline
@ menelepon argumen, saya tidak tahu mengapa itu ada di sana, hanya edit cepat
mil
Harus hati-hati :)
CalculatorFeline
10

Seperti yang biasa saya lakukan, saya akan memulai jawaban dengan jawaban saya sendiri.

JavaScript, 46 44 karakter (berjalan di konsol)

for(n=prompt(),c=1;n>1;n=n%2?n*3+1:n/2,++c)c
Gagang pintu
sumber
Apa gunanya ~~ prompt () jika Anda mengatakan output tidak masalah jika itu bukan bilangan bulat? Anda dapat menyimpan dua karakter dengan menghilangkan ~~.
Resorath
@Resorath Ah, lupa tentang casting otomatis JS: P terima kasih
Doorknob
9

Java, 165, 156, 154,134,131,129,128 , 126 (bahasa verbal juga butuh cinta)

class a{public static void main(String[]a){for(int x=Short.valueOf(a[0]),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y));}}

Semua dilakukan di dalam untuk

for(int x=Short.valueOf(a[0]),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y))

Itu pria cantik yang menakutkan. Terima kasih kepada Pater Taylor !!!, dan gagasan menggunakan for for dicuri dari ugoren

Saya mengganti Integer untuk Short.

jsedano
sumber
1
Anda dapat dengan mudah menyimpan panjangnya i(,++y). Anda dapat menyimpan dua lagi dengan menggunakan <bukan ==.
Peter Taylor
@PeterTaylor Anda benar, perbandingan saya akan lebih pendek dengan <, tapi saya tidak mengerti bagian dari kenaikan pra
jsedano
2
Kedua sisi terner kedua Anda secara struktural identik, sehingga Anda dapat mendorong terner ke argumen pertama dari panggilan rekursif.
Peter Taylor
1
OH ALLAH SAYA ITULAH BRILLIANT
jsedano
2
Aku tahu itu sudah sekitar 3,5 tahun, tapi Anda masih bisa golf dengan 5 byte : class a{public static void main(String[]a){for(int x=new Short(a[0]),y=0;x>1;System.out.println(++y))x=x%2<1?x/2:x*3+1;}}Perubahan yang dilakukan: 1) Diganti Short.valueOf(...)dengan new Short(...)untuk -4 byte dan 2) saya sudah menempatkan x=x%2<1?x/2:x*3+1;di tubuh for-loop untuk menyingkirkan koma untuk -1 byte .
Kevin Cruijssen
9

Rebmu : 28

u[++jE1 AeEV?a[d2A][a1M3a]]j

Pada masalah yang singkat dan matematis ini, GolfScript kemungkinan akan menang beberapa persen terhadap Rebmu (jika tidak diharuskan untuk mengatakan, baca file dari internet atau hasilkan file JPG). Namun saya pikir sebagian besar akan setuju bahwa logika Golfscript tidak mudah untuk diikuti, dan total stack yang dapat dieksekusi menjalankannya lebih besar.

Meskipun pencipta Rebol sendiri Carl Sassenrath mengatakan kepada saya bahwa dia menemukan Rebmu "tidak dapat dibaca", dia sibuk, dan tidak punya waktu untuk benar-benar mempraktikkan transformasi seperti babi-latin melalui tanpa penyaringan . Ini benar-benar hanya ditransformasikan menjadi:

u [
    ++ j
    e1 a: e ev? a [
        d2 a
    ] [
        a1 m3 a
    ]
]
j

Perhatikan bahwa ruang diperlukan untuk mendapatkan a: bukan a . Ini adalah "set-word!" dan evaluator memperhatikan jenis simbol yang memicu tugas.

Jika ditulis dalam bahasa yang tidak disatukan (Rebol yang ditulis dengan canggung), Anda akan mendapatkan:

until [
    ++ j
    1 == a: either even? a [
        divide a 2
    ] [
        add 1 multiply 3 a
    ]
 ]
 j

Rebol, seperti Ruby, mengevaluasi blok ke nilai terakhirnya. Loop UNTIL adalah bentuk loop aneh yang tidak memerlukan kondisi loop, itu hanya berhenti loop ketika bloknya mengevaluasi sesuatu yang tidak SALAH atau TIDAK. Jadi pada titik bahwa 1 ==hasil penugasan A (argumen untuk rebmu) ke hasil persyaratan Collatz (baik adalah IF-ELSE yang mengevaluasi ke cabang yang dipilihnya) ... loop terputus.

J dan K diinisialisasi ke nilai integer nol di Rebmu. Dan seperti yang disebutkan di atas, semuanya mengevaluasi ke nilai terakhir. Jadi referensi J di akhir program berarti Anda mendapatkan jumlah iterasi.

Pemakaian:

>> rebmu/args [u[++jE1 AeEV?a[d2A][a1M3a]]j] 16
== 4
Rebmu
sumber
8

Ulangi Python, 48

Saya tidak yakin bahwa tidak ada ekspresi yang lebih pendek daripada n=3*n+1;n/=1+n%2*5;. Saya mungkin menemukan selusin ekspresi berbeda dengan panjang yang sama ...

i=0
n=input()
while~-n:n=3*n+1;n/=1+n%2*5;i+=1
i

sunting: Saya telah menemukan solusi lain yang tidak akan pernah bersaing, tetapi terlalu menyenangkan untuk tidak dibagikan.

s='s'
i=s
n=i*input()
while 1:
 while n==n[::2]+n[::2]:i+=s;n=n[::2]
 if n==s:i.rindex(s);break
 n=3*n+s
 i+=s
stan
sumber
1
Otak saya sakit sekarang.
daniero
1
@daniero solusi kedua hanya untuk Anda.
boothby
Oh wow. Saya merasa terhormat!
daniero
4
(n//2,n*3+1)[n%2]lebih pendek.
Evpok
1
@Eppok tidak akan n/2berfungsi sebaik yang kita tahu itu genap?
george
7

APL (31)

A←0⋄A⊣{2⊤⍵:1+3×⍵⋄⍵÷2}⍣{⍺=A+←1}⎕
marinus
sumber
jawaban lama, namun, 27:{1=⍵:0⋄2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2}
Uriel
1
{1=⍵:0⋄1+∇⊃⍵⌽0 1+.5 3×⍵}
ngn
7

J, 30 karakter

<:#-:`(1+3&*)`]@.(2&|+1&=)^:a:

Ternyata sedikit lebih lama dari yang diinginkan

pemakaian:

   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:2
1
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:16
4
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:5
5
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:7
16
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:27
111

  • -:`(1+3&*)`]adalah gerund yang terdiri dari tiga kata kerja, digunakan pada tiga kesempatan. -:berarti "membagi dua", (1+3&*)atau (1+3*])mengkodekan langkah multiplikasi dan ](identitas) bantuan pemutusan.

  • 2&|+1&=membentuk indeks ke gerund. secara harfiah, "sisanya setelah pembagian dengan dua ditambah apakah sama dengan satu".

  • #verb^:a:iterates fungsi sampai hasilnya stabil (di sini, dipaksa secara eksplisit), sambil mengumpulkan langkah-langkah, lalu hitung. Dicuri dari @JB . <:mengurangi hitungan langkah dengan satu untuk menyelaraskan dengan persyaratan pertanyaan.

John Dvorak
sumber
6
Setiap kali saya melihat pengiriman J, saya menghitung smilies. Satu ini tidak cukup baik: <:, #-:, :`(, &*), =), )^:.
Primo
3
@rimo bagus; ingin penjelasan mereka? :-) <:berarti "pengurangan" atau "kurang atau sama", #berarti "hitungan" atau "n kali", -:berarti "membagi dua" atau "kesetaraan epsilon", :`(berarti pada akhirnya akhir kata "membagi dua", ikatan antara dua kata kerja dalam gerund dan tanda kurung kiri (digunakan untuk pengelompokan). &*)berarti "sth. terikat dengan perkalian" (3 terikat dengan perkalian menciptakan "kali tiga" operator) dan akhir pengelompokan. =melakukan pemeriksaan kesetaraan atau, dalam arti unary, klasifikasi diri. ^:adalah kekuatan konjungsi (iterasi kata kerja). Karena banyak kata kerja J diakhiri dengan tanda titik dua, ... :-)
John Dvorak
Bertahun-tahun kemudian ... Blok loop ditingkatkan: '- & 2 # (> & 1 * -: + 2 & | * +: +>: @ -:) ^: a:' -> -1 char. : P
randomra
Bertahun-tahun kemudian ... <:#a:2&(<*|+|6&*%~)19 byte (-11)
mil
6

Skema Gambit, 106 98 karakter, 40 tanda kurung

(let((f(lambda(x)(cond((= x 1) 0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))))(f(read)))

91 89 karakter dengan define secara langsung

(define(f x)(cond((= x 1)0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))(f(read))

Valentin CLEMENT
sumber
Saya belum ada untuk waktu yang lama, tetapi saya perhatikan bahwa biasanya orang mengirim 1 jawaban per bahasa pemrograman.
jsedano
Maaf, saya tidak menyadarinya :)
Valentin CLEMENT
Diedit untuk menghapus satu Python.
Valentin CLEMENT
1
Tidak benar! Orang - orang cenderung memposting satu jawaban per bahasa pemrograman, tetapi itu karena mereka berusaha untuk tidak bersaing secara langsung dengan orang lain dengan jawaban yang lebih pendek. Tetapi tidak ada yang akan mengeluh jika Anda memposting jawaban yang berbeda dalam bahasa yang sama.
kotak roti
@breadbox tidak benar. Saya mengirim satu jawaban per bahasa jika masing-masing solusi menarik dengan sendirinya dibandingkan dengan yang lain. Jika kedua solusi masing-masing sama menariknya dengan keduanya (algoritma yang sama, tidak ada trik bahasa yang menarik), saya mempostingnya sebagai satu. Biasanya saya tidak memposting banyak solusi karena saya memilih bahasa terlebih dahulu, kemudian menyelesaikan masalah dalam bahasa itu - maka saya biasanya terlalu malas untuk menulis yang sama dalam bahasa yang berbeda - atau saya memulai perjalanan untuk mempelajari lagi pemrograman lain bahasa.
John Dvorak
6

PowerShell: 77 74 71 70 61

Kode golf:

for($i=(read-host);$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x

Catatan:

Saya awalnya mencoba mengambil input pengguna tanpa memaksanya ke integer, tapi itu pecah dengan cara yang menarik. Setiap input aneh akan diproses secara tidak akurat, tetapi bahkan input akan bekerja dengan baik. Butuh satu menit untuk menyadari apa yang sedang terjadi.

Saat melakukan penggandaan atau penambahan, PowerShell memperlakukan input yang tidak diketik sebagai string terlebih dahulu. Jadi, '5'*3+1menjadi '5551' alih-alih 16. Input genap berperilaku baik karena PowerShell tidak memiliki aksi default untuk pembagian terhadap string. Bahkan input genap yang akan maju melalui angka ganjil bekerja dengan baik karena, pada saat PowerShell sampai ke angka ganjil dalam loop, variabel itu tetap dipaksa menjadi bilangan bulat oleh operasi matematika.

Terima kasih kepada Danko Durbic untuk menunjukkan saya hanya bisa membalikkan operasi perkalian, dan tidak harus read-hostmelakukan int karena PowerShell mendasarkan operasinya pada objek pertama.

Tip PowerShell Golfer: Untuk beberapa skenario, seperti ini, switchketukan if/else. Di sini, perbedaannya adalah 2 karakter.

Atas izin Danko Durbic : Untuk skenario khusus ini, sebuah array dapat digunakan sebagai ganti switch, untuk menyimpan 8 karakter lagi!

Tidak ada kesalahan memeriksa nilai-nilai non-integer, atau integer kurang dari dua.

Jika Anda ingin mengaudit skrip, letakkan ;$isesaat sebelum kurung tutup terakhir pada skrip.

Saya tidak yakin persis seberapa baik PowerShell menangani angka yang berkembang menjadi nilai yang sangat besar, tetapi saya berharap akurasi hilang di beberapa titik. Sayangnya, saya juga berharap tidak banyak yang bisa dilakukan tentang hal itu tanpa serius membengkak skrip.

Kode tidak dikunci, dengan komentar:

# Start for loop to run Collatz algorithm.
# Store user input in $i.
# Run until $i reaches 1.
# Increment a counter, $x, with each run.
for($i=(read-host);$i-ne1;$x++)
{
    # New $i is defined based on an array element derived from old $i.
    $i=(
        # Array element 0 is the even numbers operation.
        ($i/2),
        # Array element 1 is the odd numbers operation.
        (3*$i+1)
    # Array element that defines the new $i is selected by $i%2.
    )[$i%2]
}

# Output $x when the loop is done.
$x

# Variable cleanup. Don't include in golfed code.
rv x,i

Kasus uji:

Berikut adalah beberapa sampel dengan audit yang diaktifkan. Saya juga mengedit output untuk kejelasan, dengan menambahkan label pada input dan jumlah akhir dan menempatkan jarak untuk memisahkan nilai-nilai Collatz.

---
Input: 2

1

Steps: 1

---
Input: 16

8
4
2
1

Steps: 4

---
Input: 5

16
8
4
2
1

Steps: 5

---
Input: 7

22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 16

---
Input: 42

21
64
32
16
8
4
2
1

Steps: 8

---
Input: 14

7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 17

---
Input: 197

592
296
148
74
37
112
56
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 26

---
Input: 31

94
47
142
71
214
107
322
161
484
242
121
364
182
91
274
137
412
206
103
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Steps: 106

---
Input: 6174

3087
9262
4631
13894
6947
20842
10421
31264
15632
7816
3908
1954
977
2932
1466
733
2200
1100
550
275
826
413
1240
620
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Steps: 111

---
Input: 8008135

24024406
12012203
36036610
18018305
54054916
27027458
13513729
40541188
20270594
10135297
30405892
15202946
7601473
22804420
11402210
5701105
17103316
8551658
4275829
12827488
6413744
3206872
1603436
801718
400859
1202578
601289
1803868
901934
450967
1352902
676451
2029354
1014677
3044032
1522016
761008
380504
190252
95126
47563
142690
71345
214036
107018
53509
160528
80264
40132
20066
10033
30100
15050
7525
22576
11288
5644
2822
1411
4234
2117
6352
3176
1588
794
397
1192
596
298
149
448
224
112
56
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 93
---

Bit menarik tentang nomor input yang bukan dari kasus uji pertanyaan:

Iszi
sumber
2
Bagus! Anda masih dapat mempersingkatnya, dengan menggantinya switchdengan$i=(($i/2),($i*3+1))[$i%2]
Danko Durbić
2
Juga, Anda tidak perlu mengonversi read-hostke angka - cukup ubah $i*3ke 3*$i.
Danko Durbić
Array alih-alih beralih? Cemerlang! Dan bertukar $i*3- mengapa saya belum memikirkan itu?
Iszi
1
param($i)for(;$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x- menukar read-host dengan parameter, untuk mendapatkan 56 byte . Tautan Try It Online
TessellatingHeckler
6

80386 unit, 16 byte

Contoh ini menggunakan sintaks AT&T dan konvensi pemanggilan cepat, argumennya menjadi ecx:

collatz:
        or $-1,%eax              # 3 bytes, eax = -1;
.Loop:  inc %eax                 # 1 byte,  eax += 1;
        lea 1(%ecx,%ecx,2),%edx  # 4 bytes, edx = 3*ecx + 1;
        shr %ecx                 # 2 bytes, CF = ecx & 1;
                                 #          ecx /= 2;
                                 #          ZF = ecx == 0;
        cmovc %edx,%ecx          # 3 bytes, if (CF) ecx = edx;
        jnz .Loop                # 2 bytes, if (!ZF) goto .Loop;
        ret                      # 1 byte,  return (eax);

Berikut adalah 16 byte kode mesin yang dihasilkan:

83 c8 ff 40 8d 54 49 01 d1 e9 0f 42 ca 75 f4 c3
FUZxxl
sumber
6

Brachylog , 16 byte

1b|{/₂ℕ|×₃+₁}↰+₁

Cobalah online!

Penjelasan

         Either:
  1        The input is 1.
  b        In which case we unify the output with 0 by beheading the 1
           (which removes the leading digit of the 1, and an "empty integer"
           is the same as zero).
|        Or:
  {        This inline predicate evaluates a single Collatz step on the input.
           Either:
    /₂       Divide the input by 2.
    ℕ        And ensure that the result is a natural number (which is
             equivalent to asserting that the input was even).
  |        Or:
    ×₃+₁     Multiply the input by 3 and add 1.
  }
  ↰        Recursively call the predicate on this result.
  +₁       And add one to the output of the recursive call.

Solusi alternatif pada jumlah byte yang sama:

;.{/₂ℕ|×₃+₁}ⁱ⁾1∧

Cobalah online!

;.          The output of this is a pair [X,I] where X is the input and
            I will be unified with the output.
{/₂ℕ|×₃+₁}  This is the Collatz step predicate we've also used above.
ⁱ⁾          We iterate this predicate I times on X. Since we haven't actually
            specified I, it is still a free variable that Brachylog can backtrack
            over and it will keep adding on iterations until the next
            constraint can be satisfied.
1           Require the result of the iteration to be 1. Once this is
            satisfied, the output variable will have been unified with
            the minimum number of iterations to get here.
∧           This AND is just used to prevent the 1 from being implicitly
            unified with the output variable as well.
Martin Ender
sumber
5

GolfScript (23 karakter)

~{.1&{.3*)}*.2/.(}do;],

Tes online

Peter Taylor
sumber
5

F # - 65 karakter

let rec c n=function 1->n|i->c(n+1)(if i%2=0 then i/2 else i*3+1)
Daniel
sumber
5

Python 68 58 54 52 karakter

f=lambda n:1+(n-2and f((n/2,3*n+1)[n%2]));f(input())

Terima kasih kepada Bakuriu dan Stanby untuk tipsnya :)

Valentin CLEMENT
sumber
Anda dapat menggunakan n%2and 3*n+1or n/2untuk menyimpan 5 karakter. Juga di python2 Anda dapat menghapus panggilan ke int, mengurangi ukuran hingga 58 byte.
Bakuriu
Oh, Anda bahkan bisa mendapatkan lebih pendek dari itu: [n/2,3*n+1][n%2].
boothby
Itu bagus!
Valentin CLEMENT
Apakah ini python 2.7? Saya mendapatkan kesalahan dalam Python 3.5.1? unsupported operand type(s) for -: 'str' and 'int'
george
5

Retina , 43 byte

11
2
(2+)1
$1$1$0$0$0$0
2.*
$0x
)`2
1
1?x
1

Mengambil input dan mencetak output secara unary.

Setiap baris harus menuju ke file sendiri. 1 byte per file tambahan ditambahkan ke byte-count.

Anda dapat menjalankan kode sebagai satu file dengan -sbendera. Misalnya:

> echo -n 1111111|retina -s collatz
1111111111111111

Algoritme adalah loop untuk melakukan langkah Collatz dengan angka unary dan menambahkan penanda langkah baru xdi akhir string jika angkanya bukan 1.

Ketika loop berakhir dengan 1, kami mengonversi marker ke nomor unary (menghapus yang memimpin 1) yang merupakan output yang diinginkan.

randomra
sumber
5

Jelly , tidak bersaing

12 byte Jawaban ini tidak bersaing, karena tantangan mendahului pembuatan Jelly.

×3‘$HḂ?ß0’?‘

Cobalah online!

Bagaimana itu bekerja

×3‘$HḂ?ß0’?‘  Main link. Argument: n (integer)

     Ḃ?       Yield the last bit of n is 1:
   $            Evaluate the three links to the left as a monadic chain:
×3                Multiply n by 3.
  ‘               Increment the product by 1.
    H           Else, halve n.
         ’?   If n-1 is non-zero:
       ß        Recursively call the main link.
        0     Else, yield 0.
           ‘  Increment the result by 1.
Dennis
sumber
4

dc, 27 karakter

Menerapkan ilmu hitam booth :

?[d3*1+d2%5*1+/d1<x]dsxxkzp

Saya tidak begitu yakin apakah saya mengerti bagaimana - atau itu - itu berhasil.

Pemakaian: 
$ dc collatz.dc <<< 7
16

dc, 36 karakter

Ciptaan saya sendiri; pendekatan yang agak lebih tradisional, bahkan saya harus bertengkar dengan bahasa yang adil untuk mengatasi kurangnya elsebagian untuk ifpernyataan:

?[2/2Q]se[dd2%[0=e3*1+]xd1<x]dsxxkzp

Secara internal ia menghasilkan semua nomor urutan dan menyimpannya di tumpukan, lalu muncul final 1dan menampilkan ketinggian tumpukan.

daniero
sumber
1
Paritas bukanlah ilmu hitam.
stan
1
Tidak, tapi ini trik yang sangat rapi! Saya sebenarnya telah melakukan hal serupa sendiri, saya hanya tidak memikirkannya dalam kasus ini. Apa yang membuat saya tersandung sejenak adalah pembagian, tetapi saya mengerti: Anda membaginya dengan enam, mengembalikan operasi pertama (* = 3, + = 1) dengan pembagian kedua jika paritasnya salah, dan karena pembagian bilangan bulat penambahan berjalan pergi juga, dan kami pada dasarnya telah melakukan / = 2. Sangat pintar :)
daniero
1
+1. Saya pikir saya akan menghancurkan tantangan ini dengan dc, tetapi hanya mencapai 40. Saya melihat jawaban Anda. Baiklah.
Digital Trauma
Saya belum melihat tantangan ini, tetapi blog beberapa waktu lalu tentang mencetak urutan Collatz di dc. Pendekatan saya mirip dengan Anda tetapi kalah dengan satu byte jadi saya tidak benar-benar melihat alasan untuk mempostingnya. Namun, ketika saya melihat milik saya untuk melihat bagaimana dengan mudah beralih dari mencetak setiap langkah ke mencetak sejumlah langkah, saya melihat sesuatu yang dapat golf byte dari Anda ... Karena urutan Collatz akan selalu berubah dari 2 menjadi 1, Anda dapat mengubah persyaratan Anda ke 2<xdan menyingkirkan k. Kalau-kalau Anda ingin byte kembali setelah empat tahun. : D
brhfl
4

brainfuck , 59 56 byte

,-[<->[[>]+<[-<]>>]>[-<<[++>+<]>->]<<[+>+++<]<<+>>>]<<<.

Cobalah online! (Sedikit dimodifikasi untuk kemudahan penggunaan)

Input dan output sebagai kode karakter. Ini lebih berguna dengan sel berukuran sewenang-wenang, tetapi masih dapat bekerja dengan nilai kecil dalam ukuran sel terbatas.

Bagaimana itu bekerja

Tape Format:
Counter 0 Copy Number Binary...
^End           ^Start

,-[ Get input, decrement by 1 and start loop
  <->                  Initialises the copy of the value at -1
  [[>]+<[-<]>>]        Converts the input to binary while preserving a negative copy
  <+>>[-<<[++>+<]>->] If the last digit of the binary is 1 (n-1 is odd), divide by 2 and decrement
  <<[+>+++<]            If the last digit of the binary is 0 (n-1 is even), multiply by 3
  <<+>>>               Increment counter and end on n-1
]<<<.                 End loop and print counter
Jo King
sumber
4

Hexagony , 48 44 byte

?(]$_)"){{?{*')}/&!/={:<$["/>&_(.<@2'%<>./>=

Cobalah online!

Diperluas:

     ? ( ] $ _
    ) " ) { { ?
   { * ' ) } / &
  ! / = . { < $ [
 " / > & _ ( . < @
  2 ' % < > : / >
   = . . . . . .
    . . . . . .
     . . . . .

Perhatikan bahwa ini gagal 1karena uhh ... alasan . Jujur, saya tidak begitu yakin bagaimana ini bekerja lagi. Yang saya tahu adalah bahwa kode untuk angka ganjil dijalankan mundur untuk angka genap? Entah bagaimana?

Versi baru jauh lebih bersih dari yang sebelumnya, tetapi memiliki beberapa arah lebih banyak dalam perbandingan dan juga berakhir dengan kesalahan divide-by-zero. Satu-satunya kasus itu tidak kesalahan adalah ketika itu benar-benar menangani 1dengan benar.

Jo King
sumber
If a number < 2 is input ... output does not matter.: o)
Sok
@ Oke Yap, itu sebabnya saya mempostingnya bukannya menjadi gila mencoba memperbaikinya
Jo King
3

C, 70 69 karakter

Cukup sederhana, tidak ada trik.
Membaca input dari stdin.

a;
main(b){
    for(scanf("%d",&b);b-1;b=b%2?b*3+1:b/2)a++;
    printf("%d",a);
}
ugoren
sumber
3

Q, 46

{i::0;{x>1}{i+:1;$[x mod 2;1+3*x;(_)x%2]}\x;i}
tmartin
sumber
32 byte dengan(#)1_(1<){(1+3*x;x%2)0=x mod 2}\
streetster
3

Ruby 1.9, 49 karakter

Rubyfied Valentin CLEMENT's menjawab Python , menggunakan sintaks lambda yang stabby. Sqeezed itu menjadi satu pernyataan untuk menambah keterbacaan.

(f=->n{n>1&&1+f[[n/2,3*n+1][n%2]]||0})[gets.to_i]

Beberapa overhead karena Ruby, tidak seperti Python, tidak senang mencampur angka dengan boolean.

daniero
sumber
3

C ++ ( 51 48)

Ini adalah fungsi rekursif yang melakukan ini; masukan bacaan datang secara terpisah.

int c(n){return n==1?0:1+(n%2?c(n*3+1):c(n/2));}

Saya yakin saya bisa melakukan semacam "dan / atau" trik dengan == 0barang - barang itu, tetapi saya tidak tahu caranya.

Joe Z.
sumber
Anda dapat menghapus ==0dan menukar sisi kondisional
Gagang Pintu
Juga, tidak perlu menangani n==1karena saya tentukan dalam pertanyaan bahwa jumlahnya selalu lebih besar dari 1
Gagang Pintu
Masalahnya adalah itu n==1adalah kasus rekursi dasar. Menempatkan di n==2sana tidak akan meningkatkan skor apa pun.
Joe Z.
Ah, maka Anda bisa menggantinya dengan ini: return~-n?dan menukar sisi bersyarat
Gagang Pintu
. n==1== n<2.
CalculatorFeline
3

~ - ~! (Tidak Ada Komentar) - 71 53

Bahasa ini jelas bukan yang terbaik untuk bermain golf karena tidak memiliki banyak fungsi asli, tetapi itulah keindahannya.

'=|*;~~[*,~~~-~]*/~~|:''=|'''==~[*]'''='&''':''&*+~|:

Pertama, atur '''input Anda. Fungsi ''tersebut kemudian dapat dipanggil dengan %input dan akan mengembalikan jawabannya, seperti:

'''=~~~~~:''&%:

Ini akan kembali ~~~~~. Ini sebenarnya berfungsi untuk n==1(itu loop selamanya dengan n==0).

Seperti biasa dengan bahasa ini, tidak diuji.

cjfaure
sumber
3

JavaScript (ES6) - 29 Karakter

f=x=>x>1?f(x%2?x*3+1:x/2)+1:0

Membuat fungsi fyang menerima argumen tunggal dan mengembalikan jumlah iterasi.

JavaScript - 31 Karakter

for(c=0;n>1;n=n%2?n*3+1:n/2)++c

Mengasumsikan bahwa input berada dalam variabel ndan membuat variabel cyang berisi jumlah iterasi (dan juga akan output cke konsol sebagai perintah terakhirnya).

MT0
sumber
1
28 byte
Shaggy
3

Perl 6, 40 byte

Metode fungsi rekursif, sesuai Valentin CLEMENT dan daniero : 40 karakter

sub f(\n){n>1&&1+f n%2??3*n+1!!n/2}(get)

Metode daftar malas: 32 karakter

+(get,{$_%2??$_*3+1!!$_/2}...^1)
Mouq
sumber
3

> <>, 27 26 23 byte

\ln;
\::2%:@5*1+2,*+:2=?

Seperti jawaban>> lainnya, ini membangun urutan pada tumpukan. Setelah urutan mencapai 2, ukuran tumpukan adalah jumlah langkah yang diambil.

Berkat @Hohmannfan, tersimpan 3 byte dengan metode komputasi yang sangat cerdas secara langsung. Rumus yang digunakan untuk menghitung nilai selanjutnya dalam urutan adalah:

f(n)=n⋅5(nmod2)+12+(nmod2)

Fraksi memetakan angka genap menjadi 0,5, dan angka ganjil menjadi 3. Mengalikan dengan ndan menambahkan n%2melengkapi perhitungan - tidak perlu memilih nilai berikutnya sama sekali!

Sunting 2: Ini versi pre- @ Hohmannfan:

\ln;
\:::3*1+@2,@2%?$~:2=?

Kuncinya di sini adalah bahwa keduanya 3n+1dan n/2dihitung pada setiap langkah dalam urutan, dan yang akan dihapus dari urutan dipilih sesudahnya. Ini berarti bahwa kode tidak perlu di-branch sampai 1 tercapai, dan perhitungan urutannya bisa hidup pada satu baris kode.

Sunting: Memotong karakter lain setelah menyadari bahwa satu-satunya bilangan bulat positif yang dapat mengarah ke 1 adalah 2. Karena output dari program tidak masalah untuk input <2, pembuatan urutan dapat berakhir ketika 2 tercapai, meninggalkan ukuran tumpukan menjadi jumlah persis langkah yang diperlukan.

Versi sebelumnya:

\~ln;
\:::3*1+@2,@2%?$~:1=?
Sok
sumber
1
Anda dapat membuatnya menjadi 23 jika Anda membatalkan cabang kedua lebih banyak lagi:\::2%:@5*1+2,*+:2=?
Hohmannfan