language-agnostic - コードゴルフ：コラッツ予想

Question

http://xkcd.com/710/にインスパイアされたコードゴルフです。

チャレンジ

0 より大きい正の整数を指定すると、その数値の雹のシーケンスを出力します。

ヘイルストーンシーケンス

詳細については、ウィキペディアを参照してください。

偶数の場合は2で割ります。
奇数なら3倍にして1足すればいい。

これを出た数だけ1になるまで繰り返す（1以降続くとの無限ループに入る1 -> 4 -> 2 -> 1...）

コードで説明するのが最善の方法である場合もあるので、ウィキペディアからいくつか引用します

function collatz(n)
  show n
  if n > 1
    if n is odd
      call collatz(3n + 1)
    else
      call collatz(n / 2)

このコードは機能しますが、追加の課題を追加しています。プログラムは、スタックオーバーフローに対して脆弱であってはなりません。したがって、反復または末尾再帰のいずれかを使用する必要があります。

また、大きな数を計算でき、言語にまだ実装されていない場合のボーナスポイント。(または、固定長整数を使用して大きな数のサポートを再実装する場合)

テストケース

Number: 21
Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

また、コードゴルフには、完全なユーザー入力と出力が含まれている必要があります。

score 129 · Accepted Answer

x86 アセンブリ、1337 文字

;
; To assemble and link this program, just run:
;
; >> $ nasm -f elf collatz.asm && gcc -o collatz collatz.o
;
; You can then enjoy its output by passing a number to it on the command line:
;
; >> $ ./collatz 123
; >> 123 --> 370 --> 185 --> 556 --> 278 --> 139 --> 418 --> 209 --> 628 --> 314
; >> --> 157 --> 472 --> 236 --> 118 --> 59 --> 178 --> 89 --> 268 --> 134 --> 67
; >> --> 202 --> 101 --> 304 --> 152 --> 76 --> 38 --> 19 --> 58 --> 29 --> 88
; >> --> 44 --> 22 --> 11 --> 34 --> 17 --> 52 --> 26 --> 13 --> 40 --> 20 --> 10
; >> --> 5 --> 16 --> 8 --> 4 --> 2 --> 1
; 
; There's even some error checking involved:
; >> $ ./collatz
; >> Usage: ./collatz NUMBER
;
section .text
global main
extern printf
extern atoi

main:

  cmp dword [esp+0x04], 2
  jne .usage

  mov ebx, [esp+0x08]
  push dword [ebx+0x04]
  call atoi
  add esp, 4

  cmp eax, 0
  je .usage

  mov ebx, eax
  push eax
  push msg

.loop:
  mov [esp+0x04], ebx
  call printf

  test ebx, 0x01
  jz .even

.odd:
  lea ebx, [1+ebx*2+ebx]
  jmp .loop

.even:

  shr ebx, 1
  cmp ebx, 1
  jne .loop

  push ebx
  push end
  call printf

  add esp, 16
  xor eax, eax
  ret

.usage:
  mov ebx, [esp+0x08]
  push dword [ebx+0x00]
  push usage
  call printf
  add esp, 8
  mov eax, 1
  ret

msg db "%d --> ", 0
end db "%d", 10, 0
usage db "Usage: %s NUMBER", 10, 0

score 64 · Accepted Answer

64

ベフンゲ

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+

于 2010-03-05T18:03:34.380 に答える

score 52 · Accepted Answer

LOLCODE: 406 CHARAKTERZ

HAI
BTW COLLATZ SOUNDZ JUS LULZ

CAN HAS STDIO?

I HAS A NUMBAR
BTW, I WANTS UR NUMBAR
GIMMEH NUMBAR

VISIBLE NUMBAR

IM IN YR SEQUENZ
  MOD OF NUMBAR AN 2
  BOTH SAEM IT AN 0, O RLY?
    YA RLY, NUMBAR R QUOSHUNT OF NUMBAR AN 2
    NO WAI, NUMBAR R SUM OF PRODUKT OF NUMBAR AN 3 AN 1
  OIC
  VISIBLE NUMBAR
  DIFFRINT 2 AN SMALLR OF 2 AN NUMBAR, O RLY?
    YA RLY, GTFO
  OIC
IM OUTTA YR SEQUENZ

KTHXBYE

JUSTIN J. MEZA 'S INTERPRETRの下でテスト済み。KTHXさようなら！

score 51 · Accepted Answer

Python - 95 64 51 46 文字

明らかに、スタックオーバーフローは発生しません。

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n

score 23 · Accepted Answer

パール

私は少し反競争的になることに決め、Perl でこのような問題を通常どのようにコーディングするかを示しました。
_{最後に合計 46 文字のコードゴルフエントリもあります。}

これらの最初の 3 つの例はすべて、このヘッダーから始まります。

#! /usr/bin/env perl
use Modern::Perl;
# which is the same as these three lines:
# use 5.10.0;
# use strict;
# use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}

単純な再帰バージョン

use Sub::Call::Recur;
sub Collatz{
  my( $n ) = @_;
  $n += 0; # ensure that it is numeric
  die 'invalid value' unless $n > 0;
  die 'Integer values only' unless $n == int $n;
  say $n;
  given( $n ){
    when( 1 ){}
    when( $_ % 2 != 0 ){ # odd
      recur( 3 * $n + 1 );
    }
    default{ # even
      recur( $n / 2 );
    }
  }
}

シンプルな反復バージョン

sub Collatz{
  my( $n ) = @_;
  $n += 0; # ensure that it is numeric
  die 'invalid value' unless $n > 0;
  die 'Integer values only' unless $n == int $n;
  say $n;
  while( $n > 1 ){
    if( $n % 2 ){ # odd
      $n = 3 * $n + 1;
    } else { #even
      $n = $n / 2;
    }
    say $n;
  }
}

最適化された反復バージョン

sub Collatz{
  my( $n ) = @_;
  $n += 0; # ensure that it is numeric
  die 'invalid value' unless $n > 0;
  die 'Integer values only' unless $n == int $n;
  #
  state @next;
  $next[1] //= 0; # sets $next[1] to 0 if it is undefined
  #
  # fill out @next until we get to a value we've already worked on
  until( defined $next[$n] ){
    say $n;
    #
    if( $n % 2 ){ # odd
      $next[$n] = 3 * $n + 1;
    } else { # even
      $next[$n] = $n / 2;
    }
    #
    $n = $next[$n];
  }
  say $n;
  # finish running until we get to 1
  say $n while $n = $next[$n];
}

ここで、v5.10.0 より前のバージョンの Perl で最後の例を実行する方法を示します。

#! /usr/bin/env perl
use strict;
use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}
{
  my @next = (0,0); # essentially the same as a state variable
  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;

    # fill out @next until we get to a value we've already worked on
    until( $n == 1 or defined $next[$n] ){
      print $n, "\n";

      if( $n % 2 ){ # odd
        $next[$n] = 3 * $n + 1;
      } else { # even
        $next[$n] = $n / 2;
      }
      $n = $next[$n];
    }
    print $n, "\n";

    # finish running until we get to 1
    print $n, "\n" while $n = $next[$n];
  }
}

基準

まず、IO は常に遅い部分になります。したがって、実際にそれらをそのままベンチマークした場合、それぞれからほぼ同じ速度が得られるはずです。

次にこれらをテストするために、/dev/null( ) へのファイルハンドルを開き、代わりに read に$nullすべて編集しました。これは、IO への依存を減らすためです。say $nsay {$null} $n

#! /usr/bin/env perl
use Modern::Perl;
use autodie;

open our $null, '>', '/dev/null';

use Benchmark qw':all';

cmpthese( -10,
{
  Recursive => sub{ Collatz_r( 31 ) },
  Iterative => sub{ Collatz_i( 31 ) },
  Optimized => sub{ Collatz_o( 31 ) },
});

sub Collatz_r{
  ...
  say {$null} $n;
  ...
}
sub Collatz_i{
  ...
  say {$null} $n;
  ...
}
sub Collatz_o{
  ...
  say {$null} $n;
  ...
}

10 回実行した後の代表的な出力例を次に示します。

            レート再帰反復最適化
再帰 1715/s -- -27% -46%
反復 2336/秒 36% -- -27%
最適化された 3187/秒 86% 36% --

最後に、実際のコードゴルフエントリ:

perl -nlE'say;say$_=$_%2?3*$_+1:$_/2while$_>1'

合計 46 文字

開始値を出力する必要がない場合は、さらに 5 文字を削除できます。

perl -nE'say$_=$_%2?3*$_+1:$_/2while$_>1'

_{実際のコード部分は}41 文字で合計31 文字ですが、_{スイッチがないとコードは機能しません。}_{そのため、例全体をカウントに含めます。}
_-n

score 23 · Accepted Answer

Haskell、62 文字63 76 83、86、97、137

c 1=[1]
c n=n:c(div(n`mod`2*(5*n+2)+n)2)
main=readLn>>=print.c

ユーザー入力、印刷出力、定数メモリとスタックの使用、任意の大きな整数で動作します。

入力としてすべて 1 (!) の 80 桁の数字が与えられたこのコードのサンプル実行は、見ていてとても楽しいものです。

オリジナル、機能のみのバージョン:

Haskell 51 文字

f n=n:[[],f([n`div`2,3*n+1]!!(n`mod`2))]!!(1`mod`n)

とにかく、@&^# が条件を必要とするのは誰ですか?

（編集：私は「賢い」ので、修正を使用しました。それがないと、コードは54文字に落ちました.edit2：因数分解して51に落ちましたf()）

score 22 · Accepted Answer

Golfscript : 20 文字

  ~{(}{3*).1&5*)/}/1+`
# 
# Usage: echo 21 | ruby golfscript.rb collatz.gs

これは、

stack<int> s;
s.push(21);
while (s.top() - 1) {
  int x = s.top();
  int numerator = x*3+1;
  int denominator = (numerator&1) * 5 + 1;
  s.push(numerator/denominator);
}
s.push(1);
return s;

score 19 · Accepted Answer

紀元前41文字

bcこの種の問題は、次の目的で発明されたものだと思います。

for(n=read();n>1;){if(n%2)n=n*6+2;n/=2;n}

テスト：

bc1 -q collatz.bc
21
64
32
16
8
4
2
1

適切なコード:

for(n=read();n>1;){if(n%2)n=n*3+1else n/=2;print n,"\n"}

bc桁までの数字を処理しますINT_MAX

編集:ウィキペディアの記事では、この推測は20x2 ⁵⁸ (約5.76e18 )までのすべての値についてチェックされていると述べています。このプログラム：

c=0;for(n=2^20000+1;n>1;){if(n%2)n=n*6+2;n/=2;c+=1};n;c

テスト2 ^20,000 +1 (約3.98e6,020 ) 68秒で、144,404サイクル。

score 16 · Accepted Answer

Perl : 31 文字

perl -nE 'say$_=$_%2?$_*3+1:$_/2while$_>1'
#         123456789 123456789 123456789 1234567

2 つの不要なスペースを削除するように編集されました。

不要なスペースを 1 つ削除するように編集しました。

score 15 · Accepted Answer

MS Excel、35 文字

=IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)

ウィキペディアから直接引用：

In cell A1, place the starting number.
In cell A2 enter this formula =IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1) 
Drag and copy the formula down until 4, 2, 1

数式を 111 回コピーして貼り付けるだけで、開始番号 1000 の結果が得られました。;)

score 14 · Accepted Answer

C：64文字

main(x){for(scanf("%d",&x);x>=printf("%d,",x);x=x&1?3*x+1:x/2);}

大きな整数のサポートあり：431（必要な）文字

#include <stdlib.h>
#define B (w>=m?d=realloc(d,m=m+m):0)
#define S(a,b)t=a,a=b,b=t
main(m,w,i,t){char*d=malloc(m=9);for(w=0;(i=getchar()+2)/10==5;)
B,d[w++]=i%10;for(i=0;i<w/2;i++)S(d[i],d[w-i-1]);for(;;w++){
while(w&&!d[w-1])w--;for(i=w+1;i--;)putchar(i?d[i-1]+48:10);if(
w==1&&*d==1)break;if(*d&1){for(i=w;i--;)d[i]*=3;*d+=1;}else{
for(i=w;i-->1;)d[i-1]+=d[i]%2*10,d[i]/=2;*d/=2;}B,d[w]=0;for(i=0
;i<w;i++)d[i+1]+=d[i]/10,d[i]%=10;}}

注：#include <stdlib.h>少なくともmalloc / reallocのプロトタイプを作成せずに削除しないでください。削除すると、64ビットプラットフォームでは安全ではなくなります（64ビットのvoid *は32ビットのintに変換されます）。

これはまだ精力的にテストされていません。ショートニングも使用できます。

以前のバージョン：

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

（出力形式に誰も従わないため、12文字を削除しました...：|）

score 12 · Accepted Answer

別のアセンブラバージョン。^{これは 32 ビットの数値に限定されず、10 65534}までの数値を処理できますが、MS-DOS が使用する「.com」形式は 80 桁の数値に制限されています。A86 アセンブラ用に書かれており、実行するには Win-XP DOS ボックスが必要です。180 バイトにアセンブルします。

    mov ax,cs
    mov si,82h
    add ah,10h
    mov es,ax
    mov bh,0
    mov bl,byte ptr [80h]
    cmp bl,1
    jbe ret
    dec bl
    mov cx,bx
    dec bl
    xor di,di
 p1:lodsb
    sub al,'0'
    cmp al,10
    jae ret
    stosb
    loop p1
    xor bp,bp
    push es
    pop ds
 p2:cmp byte ptr ds:[bp],0
    jne p3
    inc bp
    jmp p2
    ret
 p3:lea si,[bp-1]
    cld
 p4:inc si
    mov dl,[si]
    add dl,'0'
    mov ah,2
    int 21h
    cmp si,bx
    jne p4
    cmp bx,bp
    jne p5
    cmp byte ptr [bx],1
    je ret
 p5:mov dl,'-'
    mov ah,2
    int 21h
    mov dl,'>'
    int 21h
    test byte ptr [bx],1
    jz p10
    ;odd
    mov si,bx
    mov di,si
    mov dx,3
    dec bp
    std
 p6:lodsb
    mul dl
    add al,dh
    aam
    mov dh,ah
    stosb
    cmp si,bp
    jnz p6
    or dh,dh
    jz p7
    mov al,dh
    stosb
    dec bp
 p7:mov si,bx
    mov di,si
 p8:lodsb
    inc al
    xor ah,ah
    aaa
    stosb
    or ah,ah
    jz p9
    cmp si,bp
    jne p8
    mov al,1
    stosb
    jmp p2
 p9:inc bp
    jmp p2
    p10:mov si,bp
    mov di,bp
    xor ax,ax
p11:lodsb
    test ah,1
    jz p12
    add al,10
p12:mov ah,al
    shr al,1
    cmp di,bx
    stosb
    jne p11
    jmp p2

score 10 · Accepted Answer

DC - 24 文字25 28

dcは、このシーケンスに適したツールです。

?[d5*2+d2%*+2/pd1<L]dsLx

dc -f collatz.dc
21
64
32
16
8
4
2
1

また、 Golfscriptエントリの式を使用した 24 文字:

?[3*1+d2%5*1+/pd1<L]dsLx

仕様を満たす57 文字:

[Number: ]n?[Results: ]ndn[d5*2+d2%*+2/[ -> ]ndnd1<L]dsLx

dc -f collatz-spec.dc
数: 3
結果: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

score 9 · Accepted Answer

スキーム: 72

(define(c n)(if(= n 1)`(1)(cons n(if(odd? n)(c(+(* n 3)1))(c(/ n 2))))))

これは再帰を使用していますが、呼び出しは末尾再帰であるため、反復に最適化されると思います。いくつかの簡単なテストでは、とにかくスタックがオーバーフローする数値を見つけることができませんでした. ちょうど例：

(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)

...問題なく動作します。[これはすべて 1 つの数字です -- 画面に収まるように分割しました。]

score 8 · Accepted Answer

8

マテマティカ、4550文字

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&

于 2010-03-05T17:38:21.087 に答える

score 7 · Accepted Answer

Ruby、50 文字、スタックオーバーフローなし

基本的にmakapufのPythonソリューションの直接の裂け目:

def c(n)while n>1;n=n.odd?? n*3+1: n/2;p n end end

Ruby、45文字、オーバーフローします

基本的に、質問で提供されたコードの直接的な裂け目:

def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end

score 7 · Accepted Answer

import java.math.BigInteger;
public class SortaJava {

    static final BigInteger THREE = new BigInteger("3");
    static final BigInteger TWO = new BigInteger("2");

    interface BiFunc<R, A, B> {
      R call(A a, B b);
    }

    interface Cons<A, B> {
      <R> R apply(BiFunc<R, A, B> func);
    }

    static class Collatz implements Cons<BigInteger, Collatz> {
      BigInteger value;
      public Collatz(BigInteger value) { this.value = value; }
      public <R> R apply(BiFunc<R, BigInteger, Collatz> func) {
        if(BigInteger.ONE.equals(value))
          return func.call(value, null);
        if(value.testBit(0))
          return func.call(value, new Collatz((value.multiply(THREE)).add(BigInteger.ONE)));
        return func.call(value, new Collatz(value.divide(TWO)));
      }
    }

    static class PrintAReturnB<A, B> implements BiFunc<B, A, B> {
      boolean first = true;
      public B call(A a, B b) {
        if(first)
          first = false;
        else
          System.out.print(" -> ");
        System.out.print(a);
        return b;
      }
    }

    public static void main(String[] args) {
      BiFunc<Collatz, BigInteger, Collatz> printer = new PrintAReturnB<BigInteger, Collatz>();
      Collatz collatz = new Collatz(new BigInteger(args[0]));
      while(collatz != null)
        collatz = collatz.apply(printer);
    }
}

score 7 · Accepted Answer

Python 45 文字

makapuf の回答から char を削りました。

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n

score 5 · Accepted Answer

TIベーシック

最短ではありませんが、斬新なアプローチです。大きなシーケンスでかなり遅くなることは確かですが、オーバーフローするべきではありません。

PROGRAM:COLLATZ
:ClrHome
:Input X
:Lbl 1
:While X≠1
:If X/2=int(X/2)
:Then
:Disp X/2→X
:Else
:Disp X*3+1→X
:End
:Goto 1
:End

score 4 · Accepted Answer

Scala + Scalaz

import scalaz._
import Scalaz._
val collatz = 
   (_:Int).iterate[Stream](a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) // This line: 61 chars

そして実際に：

scala> collatz(7).toList
res15: List[Int] = List(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2)

Scala 2.8

val collatz = 
   Stream.iterate(_:Int)(a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) :+ 1

これには、末尾の1も含まれます。

scala> collatz(7)
res12: scala.collection.immutable.Stream[Int] = Stream(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

次の暗黙の

implicit def intToEven(i:Int) = new {
  def ~(even: Int=>Int, odd: Int=>Int) = { 
    if (i%2==0) { even(i) } else { odd(i) }
  }
}

これはに短縮することができます

val collatz = Stream.iterate(_:Int)(_~(_/2,3*_+1)).takeWhile(1<) :+ 1

編集-58文字 （入力と出力を含みますが、初期番号は含まれません）

var n=readInt;while(n>1){n=Seq(n/2,n*3+1)(n%2);println(n)}

改行が必要ない場合は、2つ減らすことができます...

score 4 · Accepted Answer

nroff ¹

で実行nroff -U hail.g

.warn
.pl 1
.pso (printf "Enter a number: " 1>&2); read x; echo .nr x $x
.while \nx>1 \{\
.  ie \nx%2 .nr x \nx*3+1
.  el .nr x \nx/2
\nx
.\}

^{1.groffバージョン}

score 4 · Accepted Answer

ルビー、43文字

スタックオーバーフローの影響を受けやすく、bignum がサポートされています。

def c(n)p n;n%2>0?c(3*n+1):c(n/2)if n>1 end

...さらに 50 文字、bignum をサポート、スタックオーバーフローなし:

def d(n)while n>1 do p n;n=n%2>0?3*n+1:n/2 end end

ヨルダンに敬意を表します。puts の代わりに 'p' があることを知りませんでした。

score 4 · Accepted Answer

4

ハスケル：50

c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)

于 2010-03-05T17:26:01.740 に答える

score 4 · Accepted Answer

C#: 216 文字

using C=System.Console;class P{static void Main(){var p="start:";System.Action<object> o=C.Write;o(p);ulong i;while(ulong.TryParse(C.ReadLine(),out i)){o(i);while(i > 1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}o("\n"+p);}}}

長い形式で:

using C = System.Console;
class P
{
    static void Main()
    {
        var p = "start:"; 
        System.Action<object> o = C.Write; 
        o(p); 
        ulong i; 
        while (ulong.TryParse(C.ReadLine(), out i))
        {
            o(i); 
            while (i > 1)
            {
                i = i % 2 == 0 ? i / 2 : i * 3 + 1; 
                o(" -> " + i);
            } 
            o("\n" + p);
        }
    }
}

新しいバージョンは、コマンドラインから提供される入力として 1 つの数値を受け入れます。入力の検証はありません。~~173~~ 154 文字。

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;var i=ulong.Parse(a[0]);o(i);while(i>1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}}}

長い形式で:

using System;
class P
{
    static void Main(string[]a)
    {
        Action<object>o=Console.Write;
        var i=ulong.Parse(a[0]);
        o(i);
        while(i>1)
        {
            i=i%2==0?i/2:i*3+1;
            o(" -> "+i);
        }
    }
}

この回答のアイデアをはぎ取って、しばらくではなく for ループを使用することで、いくつかの文字を削ることができます。150文字。

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;for(var i=ulong.Parse(a[0]);i>1;i=i%2==0?i/2:i*3+1)o(i+" -> ");o(1);}}

score 4 · Accepted Answer

最短ではありませんが、エレガントな clojure ソリューションです

(defn collatz [n]
 (print n "")
 (if (> n 1)
  (recur
   (if (odd? n)
    (inc (* 3 n))
    (/ n 2)))))

score 3 · Accepted Answer

ルビー、43歳、おそらくI/O要件を満たしている

で実行ruby -n hail

n=$_.to_i
(n=n%2>0?n*3+1: n/2
p n)while n>1

score 3 · Accepted Answer

C# : BigInteger をサポートする 659 文字

using System.Linq;using C=System.Console;class Program{static void Main(){var v=C.ReadLine();C.Write(v);while(v!="1"){C.Write("->");if(v[v.Length-1]%2==0){v=v.Aggregate(new{s="",o=0},(r,c)=>new{s=r.s+(char)((c-48)/2+r.o+48),o=(c%2)*5}).s.TrimStart('0');}else{var q=v.Reverse().Aggregate(new{s="",o=0},(r, c)=>new{s=(char)((c-48)*3+r.o+(c*3+r.o>153?c*3+r.o>163?28:38:48))+r.s,o=c*3+r.o>153?c*3+r.o>163?2:1:0});var t=(q.o+q.s).TrimStart('0').Reverse();var x=t.First();q=t.Skip(1).Aggregate(new{s=x>56?(x-57).ToString():(x-47).ToString(),o=x>56?1:0},(r,c)=>new{s=(char)(c-48+r.o+(c+r.o>57?38:48))+r.s,o=c+r.o>57?1:0});v=(q.o+q.s).TrimStart('0');}C.Write(v);}}}

アンゴルフ

using System.Linq;
using C = System.Console;
class Program
{
    static void Main()
    {
        var v = C.ReadLine();
        C.Write(v);
        while (v != "1")
        {
            C.Write("->");
            if (v[v.Length - 1] % 2 == 0)
            {
                v = v
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = r.s + (char)((c - 48) / 2 + r.o + 48), o = (c % 2) * 5 })
                    .s.TrimStart('0');
            }
            else
            {
                var q = v
                    .Reverse()
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = (char)((c - 48) * 3 + r.o + (c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 28 : 38 : 48)) + r.s, o = c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 2 : 1 : 0 });
                var t = (q.o + q.s)
                    .TrimStart('0')
                    .Reverse();
                var x = t.First();
                q = t
                    .Skip(1)
                    .Aggregate(
                        new { s = x > 56 ? (x - 57).ToString() : (x - 47).ToString(), o = x > 56 ? 1 : 0 }, 
                        (r, c) => new { s = (char)(c - 48 + r.o + (c + r.o > 57 ? 38 : 48)) + r.s, o = c + r.o > 57 ? 1 : 0 });
                v = (q.o + q.s)
                    .TrimStart('0');
            }
            C.Write(v);
        }
    }
}

score 3 · Accepted Answer

PHP

function Collatz($n)
{
        $i = 0;
    while($n>1)
    {
        if($n % 2)
        {
            $n = (3*$n) + 1;
            $i++;
            echo "step $i:  $n <br/>";
        }

        else 
        {
            $n = $n/2;
            $i++;
            echo "step $i:  $n <br/>";
        }
    }

}

score 3 · Accepted Answer

Common Lisp、141 文字:

(defun c ()
  (format t"Number: ")
  (loop for n = (read) then (if(oddp n)(+ 1 n n n)(/ n 2))
     until (= n 1)
     do (format t"~d -> "n))
  (format t"1~%"))

テスト走行：

Number: 171
171 -> 514 -> 257 -> 772 -> 386 -> 193 -> 580 -> 290 -> 145 -> 436 ->
218 -> 109 -> 328 -> 164 -> 82 -> 41 -> 124 -> 62 -> 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

score 3 · Accepted Answer

JavaScript - 68 文字

他の JS (および他のほとんどの言語) とは異なり、これは実際->には出力のに準拠しています。

for(s='',c=' -> ',i=readline();i>1;i=i%2?i*3+1:i/2)s+=i+c
print(s+1)

これを回避する場合、これは53 文字の代替であり、1 行に 1 つの数値を出力します。

for(p=print,i=readline(),p(i);i>1;)p(i=i%2?i*3+1:i/2)

SpiderMonkey で実行する場合:

echo 21 | js thisfile.js

21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

score 3 · Accepted Answer

3

Windows コマンド - 68 文字

@set/pd=
:l 
@set/ad=(d+d%%2*(d*5+2))/2&echo %d%&if %d% NEQ 1 goto:l

于 2010-03-18T09:02:23.590 に答える

score 3 · Accepted Answer

F#、90 文字

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))

> c 21;;
val it : seq<int> = seq [21; 64; 32; 16; ...]

または、結果を表示するために F# インタラクティブを使用していない場合は、102 文字:

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))>>printf"%A"

score 3 · Accepted Answer

Jerry Coffin のプログラムには整数オーバーフローがあります。これを試してください:

#include <iostream>

int main(unsigned long long i)
{
    int j = 0;
    for(  std::cin>>i; i>1; i = i&1? i*3+1:i/2, ++j)
        std::cout<<i<<" -> ";

    std::cout<<"\n"<<j << " iterations\n";
}

でテスト済み

合計停止時間が最長の 1 億未満の数は、949 ステップで 63,728,127 です。

合計停止時間が最も長い 10 億未満の数は、986 ステップで 670,617,279 です。

score 2 · Accepted Answer

Fortran: 71 文字

n=1
1 if(n==1)read*,n
n=merge(n/2,3*n+1,mod(n,2)==0)
print*,n
goto1
end

誰かがそれをしなければならなかったので:)

カウントには必要な改行が含まれます。Fortran 95 (およびそれ以降) のコードに完全に準拠しています。完全な I/O が含まれており、何度でも実行できます。

編集： gotoを使用して文字を1つ減らす（スタイルのポイント！）

score 2 · Accepted Answer

LOLCODE ソリューションに少し興味があるように見えるので、この言語での 2 つのソリューションアプローチ (反復および末尾再帰) の実装を比較してみようと思いました。

まず、203 文字の反復解があります。

HAI 1.2
    I HAS A n
    GIMMEH n
    IM IN YR l
        VISIBLE n
        BOTH SAEM 1 BIGGR OF 1 n
        O RLY?
            YA RLY
                GTFO
        OIC
        MOD OF n 2
        WTF?
            OMG 0
                n R QUOSHUNT OF n 2
                GTFO
            OMG 1
                n R SUM OF 1 PRODUKT OF 3 n
        OIC
    IM OUTTA YR l
KTHXBYE

何が起こっているかの要点を説明するには：

入力は、GIMMEHキーワードを使用して STDIN から読み取られます
IM IN YR <loopname>andIM OUTTA YR <loopname>ステートメントの間でループが行われます
VISIBLESTDOUTへの出力に使用されます
、、およびステートメントは、条件付きの If/Then/Else ロジックを処理しますO RLY?。YA RLYOIC
、、およびステートメントは、条件付き Switch/Case ロジックを処理しますWTF?。OMG <expression>OIC
割り当ては次を使用して実行されます<variable> R <value>
ループまたは条件付きスイッチ/ケースからの GTFO の中断

そして、201 の最終的なカウントのために 2 つの追加文字を削除することに成功した末尾再帰ソリューションがあります。

HAI 1.2
    HOW DUZ I c YR n
        VISIBLE n
        DIFFRINT 1 BIGGR OF 1 n
        O RLY?
            YA RLY
                MOD OF n 2
                WTF?
                    OMG 0
                        c QUOSHUNT OF n 2
                        GTFO
                    OMG 1
                        c SUM OF 1 PRODUKT OF 3 n
                OIC
        OIC
    IF U SAY SO
    I HAS A i
    GIMMEH i
    c i
KTHXBYE

ここでの違いは、HOW DUZ I <funcname> YR <args>andIF U SAY SOステートメント間の関数の定義です。関数はで呼び出され<funcname> <args>ます。

score 2 · Accepted Answer

PHP、78 72 67 文字

Pickover の本でシーケンスについて読んだ後、実際にこのプログラムを書いたのは約 2 年前です。少しクリーンアップしましたが、これは私が作成できる最小のものであり、ユーザー入力と読みやすい出力があります。

<?$n=fgets(STDIN);while($n!=1){$n=(($n&1)==0)?($n/2):(($n*3)+1);echo"$n\n";}?>

短いタグが有効になっていると仮定する必要があり、入力がすべてのコンソールで機能するかどうかはわかりません. しかし、私の Windows マシンでは完全に動作します。

更新:数学を少しごまかすことで、いくつかの文字を削ることができます。

<?$n=fgets(STDIN);while($n!=1){$n=(($n&1)==0)?$n/2:$n*3+1;echo"$n\n";}?>

アップデート：

がまたはを$n&1返すことを考えると、PHP の緩やかな型指定を利用して、さらにいくつかの文字を削除できます。10
また、以下の Christian のコメント (無限ループを防ぐための小さな変更を加えたもの) を組み込むと、もう 1 つ削除できます。
最後に、PHP スクリプトは終了文字を必要としないため、?>さらに 2 文字を削除できます。

最終結果:

<?$n=fgets(STDIN);while($n>1){$n=(!($n&1))?$n/2:$n*3+1;echo"$n\n";}

score 2 · Accepted Answer

MATLAB 7.8.0 (R2009a): 58 文字

n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2;disp(n);end

テストケース：

>> n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2;disp(n);end
21
    64
    32
    16
     8
     4
     2
     1

score 2 · Accepted Answer

2

ルビー、41文字

n=gets.to_i
p n=[n/2,n*3+1][n%2]while n>1

于 2010-03-10T10:16:28.877 に答える

score 2 · Accepted Answer

2

Javascript、67 56 文字

for(a=[i=prompt()];i-1;a.push(i=i%2?i*3+1:i/2));alert(a)

于 2010-03-09T23:34:37.917 に答える

score 1 · Accepted Answer

Bash、スペースと改行を含む130：

#!/bin/bash
if [ $1 == 1 ]; then echo $1
else if [ $(($1%2)) == 0 ]; then n=$(($1/2))
else n=$(($1*3+1))
fi
echo "$1 -> `c $n`"
fi

これは、cがスクリプトファイルの名前であり、スクリプトを実行しているユーザーのパスにあることを前提としています。

score 1 · Accepted Answer

J、45文字

(-: * 0&=@(2&|)) + (1 + 3&*) * -.@(0&=@(2&|))

私はJの専門家ではありません。平均の関数は+/％＃なので、これを短くできると確信しています。

score 1 · Accepted Answer

マイクロソフトスモールベーシック

TextWindow.Write( "Number: " )
n = TextWindow.ReadNumber()
TextWindow.Write( "Results: " )
While ( n > 1 )
  TextWindow.Write( n + " -> " )
  If Math.Remainder( n, 2 ) = 0  Then
    n = n / 2
  Else
    n = n * 3 + 1
  EndIf 
EndWhile
TextWindow.WriteLine(1)

http://smallbasic.com/program/?ZZR544で実行できます。

score 1 · Accepted Answer

1

GW-BASIC - 54 文字

1INPUT N
2N=(N+(N*5+2)*(N MOD 2))/2:?N:IF N>1GOTO 2

于 2010-03-18T08:32:18.937 に答える

score 1 · Accepted Answer

VB.Net、約180文字

Sub Main()
    Dim q = New Queue(Of Integer)
    q.Enqueue(CInt(Console.ReadLine))
    Do
        q.Enqueue(CInt(If(q.Peek Mod 2 = 0, q.Dequeue / 2, q.Dequeue * 3 + 1)))
        Console.WriteLine(q.Peek)
    Loop Until q.Peek = 1
End Sub

面白いのは、このコードを C# に変換してさらに文字を作成することです

空の .vb ファイル (約 245 文字) で機能させるには

Imports System.Collections.Generic
Imports System
Module m
    Sub Main()
        Dim q = New Queue(Of Integer)
        q.Enqueue(CInt(Console.ReadLine))
        Do
            q.Enqueue(CInt(If(q.Peek Mod 2 = 0, q.Dequeue / 2, q.Dequeue * 3 + 1)))
            Console.WriteLine(q.Peek)
        Loop Until q.Peek = 1
    End Sub
End Module

score 1 · Accepted Answer

パイソン:

def collatz(n):
    if (n%2) == 0:
        return n/2
    else:
        return 3*n+1
def do_collatz(n):
    while n > 1:
        print n
        n = collatz(n)
    print n
do_collatz(int(input("Start number: ")))

スタックオーバーフローに対して脆弱ではありませんが、1 に収束しないシーケンスで終了しません。 (編集: 入力部分を忘れました)

score 1 · Accepted Answer

1

Perl、59 文字:

sub c{print my$x="@_\n";@_=$x&1?$x*3+1:$x/2,goto&c if$x!=1}

于 2010-03-05T17:35:07.677 に答える

score 1 · Accepted Answer

1

F# 82 文字

let rec f n=printfn "%A" n;if n>1I then if n%2I=0I then f(n/2I)else f(3I*n+1I)

于 2010-03-07T03:46:50.080 に答える

score 0 · Accepted Answer

Clojure-70文字

((fn[n](prn n)(if(> n 1)(recur(if(odd? n)(+(* 3 n)1)(/ n 2)))))(read))

または、適切な空白とインデントを使用します。

((fn [n]
  (prn n)
  (if (> n 1)
    (recur
      (if (odd? n)
        (+ (* 3 n) 1)
        (/ n 2)))))
  (read))

recurClojureに末尾呼び出しの再帰を使用させるため、スタックオーバーフローは発生しません。任意の大きな数値で動作します。入力と出力が含まれますが、数値以外を入力するとクラッシュします:)。

注：回答を投稿した直後に、ほぼ同じアルゴリズムを使用した別のClojure実装に気づきました。しかし、それは短くしようとはしていないので、その価値について、ここに私の答えを残しておきます。

score 0 · Accepted Answer

Grooovy-59文字

int n=args[0] as int
while(n>1){println n=n%2==0?n/2:n*3+1}

例

$ ./collatz.groovy 5
16
8
4
2
1

よりきれいな出力（66文字）

int n=args[0] as int
while(n>1){print " -> ${n=n%2==0?n/2:n*3+1}"}

例

$ ./collatz.groovy 5
-> 16 -> 8 -> 4 -> 2 -> 1

score 0 · Accepted Answer

VBScript：105文字

どうやら私は罰の大食いです。

c（InputBox（ "？"））
パブリックサブc（i）
msgbox（i）
i>1の場合
if i mod 2 = 0 Then
c（i / 2）
そうしないと
c（3 * i + 1）
終了する場合
終了する場合
サブ終了

score 0 · Accepted Answer

Smalltalk、103 文字

[:n||l|l:=OrderedCollection with:1.[n>1]whileTrue:[l addLast:n.n:=n odd ifTrue:[3*n+1]ifFalse:[n/2]].l]

メッセージ #value: と目的のパラメーターを送信して呼び出します。

[:n||l|l:=OrderedCollection with:1.[n>1]whileTrue:[l addLast:n.n:=n odd ifTrue:[3*n+1]ifFalse:[n/2]].l] value: 123

または、もっと正気です：

[:n | | result |
        result := OrderedCollection with: 1.
        [n > 1] whileTrue: [
                result addLast: n.
                n := n odd ifTrue: [3*n + 1] ifFalse: [n / 2]].
        result] value: 123

(適切な方法は、上記を Integer のメソッドとして定義することです。そのため、無名クロージャーとしてではなく、「123 collatz」と言うでしょう。)

score 0 · Accepted Answer

Perl、59 文字

$n=shift;for($i=1;$n>1;$i++){$n=$n%2==0?$n/2:$n*3+1;printf"%002s: %s\n",$i,$n;}

ただし、行番号と反復値を出力するため、79 文字 (空白を含まない) のこのバージョンの方が気に入っています。

$n = shift; for($i = 1; $n > 1; $i++){ $n = $n % 2 == 0 ? $n / 2 : $n*3 + 1; printf "%002s: %s\n", $i, $n;}

$n = shift; 

for($i = 1; $n > 1; $i++){ 
    $n = $n % 2 == 0 ? $n / 2 : $n*3 + 1; 
    printf "%002s: %s\n", $i, $n;
}

score 0 · Accepted Answer

J、31文字

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

使用法：

-:`(>:@(3&*))`1:@.(1&=+2&|)^:a: 9
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

score 0 · Accepted Answer

0

Fortran - 60 文字

read*,n
1 if(n/2*2<n)n=6*n+2
n=n/2
print*,n
if(n>1)goto1
end

于 2010-03-18T02:07:31.337 に答える

score 0 · Accepted Answer

Common Lisp、76 74 文字

(defun c(n)(if (eql n 1)'(1)(cons n(if(oddp n)(c(1+(* 3 n)))(c(/ n 2))))))

または、適切に記述された、

(defun collatz (n)
  (if (eql n 1)
      '(1)
    (cons n (if (oddp n)
                (collatz (1+ (* 3 n)))
                (collatz (/ n 2))))))

score 0 · Accepted Answer

0

ルビー 55文字

n=gets.to_i
while(n>1) do n=((n%2)==1)?3*n+1:n/2;p n end

于 2010-07-01T15:21:01.640 に答える

score 0 · Accepted Answer

C++ ~~113~~ ~~100~~ 95

#include <iostream>
int main(int i){for(std::cin>>i;i>1;i=i&1?i*3+1:i/2)std::cout<<i<<" -> ";}

score 0 · Accepted Answer

ミランダ (101 文字)

c n=" 1",if n=1
   =" "++shownum(n)++c(n*3+1),if n mod 2=1
   =" "++shownum(n)++c(n div 2),otherwise

(空白は構文的に重要です)

score 0 · Accepted Answer

Josl - 58 文字

このバージョンでは、末尾再帰によるスタックオーバーフローは発生しません。

c dup println dup 1 > if dup odd? if 3 * 1+ else 2 / end c

使用する：

main 21 c

または、他の例:

main 
  21 c
  63,728,127 c

score 0 · Accepted Answer

C: 63 文字

main(x){scanf("%d",&x);while(x>printf("%d ",x=x&1?3*x+1:x/2));}

これは、KennyTM からの回答に基づいています。for ループは while ループに変更され、コードは while 内に取り込まれました。

score 0 · Accepted Answer

PHP。69文字

fgets(STDIN) の Danko Durbić に感謝します。気にしないでください :)

<?$i=fgets(STDIN);while($i!=1){echo ($i=$i%2?$i*3+1:$i/=2),"\r\n";}?>

score 0 · Accepted Answer

バッシュ 57/61/60

別の bash エントリ。無限精度演算を実行せず、オーバーフローする可能性があります。

#!/bin/bash
x=$1;echo $x;((x>1))&&$0 $((x%2?x*3+1:x/2))

オーバーフローしてはならないバージョンは

#!/bin/bash
x=$1;echo $x;((x>1))&&exec $0 $((x%2?x*3+1:x/2))

(編集) 反復版も:

#!/bin/bash
for((x=$1;x>1;x=x%2?x*3+1:x/2));do echo $x;done

score 0 · Accepted Answer

JavaScript、入力ありの 61 70文字

反復、精度は JS 制限に依存

var i=prompt('');while(i>1){console.log(i);i=(i%2)?3*i+1:i/2}

score 0 · Accepted Answer

Powershell : 80 文字

一発ギャグ：

"Results: $(for($x=read-host Number;1%$x;$x=@($x/2;3*$x+1)[$x%2]){""$x ->""}) 1"

プリティプリント:

"Results: $( for( $x = read-host Number; 1%$x; $x = @( $x/2; 3*$x+1 )[ $x%2 ] )
             { 
                 ""$x ->"" 
             }
           ) 1"

入力プロンプトと出力フォーマットなし - 44文字:

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

score 0 · Accepted Answer

ar のコードに基づいて、出力要件に実際に準拠する perl バージョンを次に示します。

perl -E 'print"Number: ";$_=<STDIN>;chomp;print"Results: $_";$_=$_%2?$_*3+1:$_/2,print" -> ",$_ while$_!=1;say""'

長さ: perl の呼び出しと引用符を含めて 114、なしで 104

経験豊富なゴルファーなら、この粗雑なバージョンをさらに減らすことができると確信しています。

score 0 · Accepted Answer

C#、88文字だと思います。再帰的

void T(int i,string s){Console.Write("{0}{1}",s,i);if(i!=1)T(i%2==0?i/2:(i*3)+ 1,"->");}

さらに、この最初の呼び出し

T(171, "");

これは非再帰的な方法で、107文字だと思います

void T2(int i){string s="";while(i>=1){Console.Write("{0}{1}",s,i);i=i==1?-1:i=i%2==0?i/2:(i*3)+1;s="->";}}

score 0 · Accepted Answer

要因:

ゴルフなしで

USE: math
: body ( n -- n ) >integer dup . "->" . dup odd? = [ 3 * 1 + ] [ 2 / ] if ;
: hailstone ( n --  ) dup 1 > [ body hailstone ] [ . ] if  ;
21 hailstone

ゴルフした:

21 [ dup 1 > ] [ >integer dup . "->" . dup 2 mod 1 = [ 3 * 1 + ] [ 2 / ] if ] while .

出力：

21
"->"
64
"->"
32
"->"
16
"->"
8
"->"
4
"->"
2
"->"
1

score 0 · Accepted Answer

ゴー、130文字

package main
import(."os"
."strconv")
func main(){n,_:=Atoi(Args[1])
println(n)
for n>1{if n%2!=0{n=n*3+1}else{n/=2}
println(n)}}

例

./collatz 3
3
10
5
16
8
4
2
1

score 0 · Accepted Answer

Erlang、120 文字

-module (f).
-export ([f/1]).
f(1)->1;
f(N)->
    io:format("~p ",[N]),
    if N rem 2 =:= 0
        ->f(trunc(N/2));
        true->f(3*N+1)
end.