Code Golf: Collatz-Vermutung

86

Inspiriert von http://xkcd.com/710/ ist hier ein Code Golf dafür.

Die Herausforderung

Bei einer positiven Ganzzahl größer als 0 drucken Sie die Hagelkornsequenz für diese Zahl aus.

Die Hagelkörner-Sequenz

Siehe Wikipedia für weitere Details.

  • Wenn die Zahl gerade ist, teilen Sie sie durch zwei.
  • Wenn die Zahl ungerade ist, verdreifachen Sie sie und fügen Sie eine hinzu.

Wiederholen Sie dies mit der erzeugten Zahl, bis es 1 erreicht. (Wenn es nach 1 fortgesetzt wird, wird es in einer Endlosschleife von 1 -> 4 -> 2 -> 1...)

Manchmal ist Code der beste Weg, um dies zu erklären. Hier sind einige aus Wikipedia

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

Dieser Code funktioniert, aber ich füge eine zusätzliche Herausforderung hinzu. Das Programm darf nicht anfällig für Stapelüberläufe sein . Es muss also entweder Iteration oder Schwanzrekursion verwendet werden.

Außerdem Bonuspunkte, wenn es große Zahlen berechnen kann und die Sprache es noch nicht implementiert hat. (oder wenn Sie die Unterstützung großer Zahlen mit Ganzzahlen fester Länge erneut implementieren)

Testfall

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

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

Außerdem muss der Code Golf vollständige Benutzereingaben und -ausgaben enthalten.

Earlz
quelle
20
darf nicht anfällig für Stapelüberläufe sein : Sie sollten es dann hier nicht gepostet haben! ;)
Felix Kling
51
Meine Freunde haben aufgehört, mich anzurufen. Heißt das, ich habe das Problem gelöst?
Martin
18
Du bist auf SO, hast aber mal Freunde gehabt? ... wie war das?
Pops
5
Die Assembler-Antwort ist cool, aber es ist ein bisschen Anti-Code-Golf , die längste Antwort auszuwählen !
John La Rooy

Antworten:

129

x86-Assembly, 1337 Zeichen

;
; 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
Martin
quelle
27
x86 asm und 1337 Zeichen. Ich weine vor Freude.
ZoogieZork
10
Ich mag die (ab) Verwendung von lea für 3n + 1.
Wowest
Vielen Dank, dass Sie nicht verwenden int 23h.
Mike D.
Wie kann ich mich an Linux halten? Ich kann es kaum erwarten, es zu versuchen
Hidroto
64

Befunge

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+
Josh Lee
quelle
2
Sie sollten dies in 2D lesen. <> ^ v sind Pfeile, die die Richtung ändern, in die der "Programmzähler" wandert. | und _ sind Bedingungen, die nach oben / unten oder links / rechts gehen, je nachdem, ob der Wert auf dem Stapel wahr oder falsch ist. Die gesamte "Code-Arena" verläuft von oben nach unten und von links nach rechts.
SF.
Und nur 35 Zeichen inklusive Leerzeichen! Gar nicht so schlecht!
Potatoswatter
6
Bist du sicher, dass es nicht Perl ist?
ijw
52

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

TESTD UNDR JUSTIN J. MEZAS INTERPRETR . KTHXBYE!

Lunohodov
quelle
51

Python - 95 64 51 46 char

Erzeugt offensichtlich keinen Stapelüberlauf.

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
makapuf
quelle
4
Möglicherweise möchten Sie Python 2.x angeben. IIRC, Python 3.x inputmacht keine eval.
Mike D.
5
Dies erfüllt nicht die Anforderungen - es druckt nicht die erste Nummer
Ben Lings
7
Warum wird das akzeptiert? es ist nicht die kürzeste und es druckt nicht die erste Zahl
Claudiu
1
Ich denke, input () gibt die von Ihnen eingegebenen Zeichen wieder, sodass hier die erste Zahl gedruckt wird :)
Danko Durbić
17
Sie können die erste Zahl für einen Preis von nur 2 Bytes drucken, indem Sien=input()*2
John La Rooy
23

Perl

Ich habe mich entschlossen, ein wenig wettbewerbswidrig zu sein und zu zeigen, wie Sie ein solches Problem normalerweise in Perl codieren würden.
Es gibt auch einen 46 (insgesamt) Char Code-Golf-Eintrag am Ende.

Diese ersten drei Beispiele beginnen alle mit diesem Header.

#! /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( $_ );
}
  • Einfache rekursive Version

    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 );
        }
      }
    }
    
  • Einfache iterative Version

    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;
      }
    }
    
  • Optimierte iterative Version

    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];
    }
    

Jetzt werde ich zeigen, wie Sie dieses letzte Beispiel mit einer Version von Perl vor v5.10.0 machen würden

#! /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];
  }
}

Benchmark

Zunächst einmal wird das IO immer der langsame Teil sein. Wenn Sie sie also tatsächlich so wie sie sind verglichen haben, sollten Sie mit jedem ungefähr die gleiche Geschwindigkeit erreichen.

Um diese dann zu testen, öffnete ich ein Dateihandle für /dev/null( $null) und bearbeitete jedes, say $num es stattdessen zu lesen say {$null} $n. Dies soll die Abhängigkeit von IO verringern.

#! /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;
  ...
}

Nach zehnmaliger Ausführung finden Sie hier eine repräsentative Beispielausgabe:

            Rate Recursive Iterative Optimized
Rekursive 1715 / s - -27% -46%
Iterative 2336 / s 36% - -27%
Optimierte 3187 / s 86% 36% -

Endlich ein echter Code-Golf-Eintrag:

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

46 Zeichen insgesamt

Wenn Sie den Startwert nicht drucken müssen, können Sie 5 weitere Zeichen entfernen.

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

41 Zeichen insgesamt
31 Zeichen für den eigentlichen Codeteil, aber der Code funktioniert ohne den -nSchalter nicht. Also beziehe ich das gesamte Beispiel in meine Zählung ein.

Brad Gilbert
quelle
Ihre optimierte Version ist nicht.
Motti
@Motti Diese Beispiele sind sehr E / A- abhängig. Nach mehrmaligem Testen behält die optimierte Version immer einen signifikanten Vorsprung.
Brad Gilbert
@Brad, wenn Sie Collatz für eine Nummer ausführen, ist die Optimierung eine Pessimierung, da keine Nummer mehr als einmal erscheinen sollte (es sei denn, die Vermutung ist falsch). Der Grund, warum Sie eine Verbesserung sehen, ist, dass Sie viele Zahlen verwenden (wie beim Euler-Problem). Tatsächlich habe ich kürzlich einen Blog-Beitrag über diesen lanzkron.wordpress.com/2010/01/18/…
Motti
2
@Motti das ist die Optimierung, über die ich gesprochen habe. Auch in Perl $i + 1ist immer zusätzlich (Antwort auf den Blogeintrag). Auch mit Sub::Call::Recurist auch eine Optimierung. Sonst würde ich verwenden @_=$n;goto &Collatz. (Es ist 10-20% langsamer, wenn Sie state @nextzumy @next
Brad Gilbert
3
Ich glaube, dass Perl-Golf-Strichzählstandards weder die obligatorischen Striche zum Aufrufen des Dolmetschers noch die Anführungszeichen zählen, sondern einen für jede Flagge neben E. Nach diesen Regeln zählen Ihre letzten Einträge jeweils 37 Zeichen und 32 Zeichen.
R. Martinho Fernandes
23

Haskell, 62 Zeichen 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

Benutzereingabe, gedruckte Ausgabe, verwendet konstanten Speicher und Stapel, arbeitet mit beliebig großen ganzen Zahlen.

Ein Beispiellauf dieses Codes mit einer 80-stelligen Anzahl aller Einsen (!) Als Eingabe macht ziemlich viel Spaß.


Original, nur Funktionsversion:

Haskell 51 Zeichen

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

Wen braucht das @ & ^ # überhaupt Bedingungen?

(Bearbeiten: Ich war "schlau" und habe Fix verwendet. Ohne diesen Code ist der Code auf 54 Zeichen gesunken. Bearbeiten2: Durch Ausklammern auf 51 gesunken. f())

MtnViewMark
quelle
Nachdem Sie meinen Miranda-Beitrag verfasst haben (der im Grunde nur ein älterer Haskell ist), können Sie ihn zumindest in Miranda mit jeweils nur einem Ausrufezeichen reduzieren - fn = n: [[], [f (n div 2), f (3) * n + 1)]! (n mod 2)]! (1 mod n) - Works :)
Derek H
Oh ja, Ihnen fehlen Ein- und Ausgänge.
R. Martinho Fernandes
@ Martininho: Ich auch, aber dank fauler Auswertung sind die Tabellen noch viel cooler als in anderen Sprachen.
Dario
1
Unter Verwendung der Idee von jleedev: c 1=[1];c n=n:(c$div(nmod 2*(5*n+2)+n)2)- 41 Zeichen wird die Tatsache verwendet, dass dies k * (3n + 1) + (1-k) * n / 2 ist, wobei k = n mod 2
sdcvvc
2
Ich habe meinen anderen Eintrag gelöscht, meinen Code hierher verschoben und noch mehr Ideen aus diesen Kommentaren aufgenommen. Auf 76 Zeichen erhöht, aber Eingabe und Ausgabe.
MtnViewMark
22

Golfscript: 20 Zeichen

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

Dies entspricht

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;
KennyTM
quelle
2
"muss vollständige Benutzereingabe und -ausgabe enthalten"
F'x
2
@FX, das Ersetzen 21durch ~wird das Programm veranlassen, eine Nummer von stdin zu verwenden
John La Rooy
@gnibbler: Ist Golfscript.rb aktualisiert? Ich habe (eval):1:in initialize ': undefinierte Methode leftparen' for nil:NilClass (NoMethodError)beim Ersetzen 21durch ~.
Kennytm
@KennyTM, leider kann GolfScript stdin nicht interaktiv lesen, Sie müssen etwas in stdin pfeifen, wieecho 21 | ruby golfscript.rb collatz.gs
John La Rooy
19

bc 41 Zeichen

Ich denke, diese Art von Problemen bcwurde erfunden für:

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

Prüfung:

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

Richtiger Code:

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

bcbehandelt Zahlen mit bis zu INT_MAXZiffern

Bearbeiten: Der Wikipedia-Artikel erwähnt, dass diese Vermutung auf alle Werte bis zu 20x2 58 (ca. 5.76e18 ) überprüft wurde . Dieses Programm:

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

testet 2 20.000 +1 (ca. 3.98e6.020 ) in 68 Sekunden, 144.404 Zyklen.

Carlos Gutiérrez
quelle
Ändern Sie 'n! = 1' für 54 Zeichen in 'n> 1'.
Jerry Coffin
4
Hier ist eine Befehlszeile zum Generieren von zufälligen Zahlen beliebiger Länge für diesen Eintrag (in diesem Fall 10000 Stellen): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc
indiv
3
@indiv - Ich musste es testen :), es dauerte 3 Minuten und 12 Sekunden, um die 10.000-stellige Zahl zu verarbeiten. Ich habe die Ausgabe in einer Datei gespeichert, sie ist ungefähr 1,2 GB lang, aber ja, sie wurde in 1 korrekt beendet. Punkt fürbc
Carlos Gutiérrez
16

Perl: 31 Zeichen

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

Bearbeitet, um 2 unnötige Leerzeichen zu entfernen.

Bearbeitet, um 1 unnötigen Speicherplatz zu entfernen.

a'r
quelle
Sie können zwei unnötige Leerzeichen entfernen (nach und nach)
sorpigal
Versuchen Sie Perl -E 'sagen Sie $ _ = 10; sagen Sie $ _ = $ _% 2? $ _ * 3 + 1: $ _ / 2, während $ _> 1'
sorpigal
Ich dachte mir, dass der Benutzer die Startnummer der Sequenz kennen würde ;-).
Am
41
Wenn ich auf Base64-codierten Text stoße, verwechsle ich ihn manchmal mit Perl-Quellcode.
Martin
21
@ Martin: Ich kann mir nicht vorstellen, wie du das machen würdest. Base64 ist viel besser lesbar.
Jerry Coffin
15

MS Excel, 35 Zeichen

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

Entnommen direkt aus Wikipedia :

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

Es dauerte nur 111 Mal, die Formel zu kopieren / einzufügen, um das Ergebnis für eine Startnummer von 1000 zu erhalten .;)

Lance McNearney
quelle
16
Ich denke, es ist zu spät für mich, darauf hinzuweisen, dass dies der Zweck des Füllgriffs ist, oder? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :)
Jordan Running
Das ist eine ziemlich praktische Funktion, von der ich nicht einmal wusste, dass sie existiert. Ich habe gerade die erste Zelle kopiert und dann alle anderen Zellen hervorgehoben und einmal eingefügt.
Lance McNearney
Ungefähr zehn Jahre nachdem ich den Füllgriff entdeckt hatte, lernte ich das Einfügen von Flächen. Zahlen.
Jimmy
14

C: 64 Zeichen

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

Mit Unterstützung für große Ganzzahlen: 431 (notwendige) Zeichen

#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;}}

Hinweis : Entfernen Sie nicht #include <stdlib.h>ohne Prototyping von malloc / realloc, da dies auf 64-Bit-Plattformen nicht sicher ist (64-Bit-void * wird in 32-Bit-int konvertiert).

Dieser wurde noch nicht intensiv getestet. Es könnte auch eine Verkürzung gebrauchen.


Vorherige Versionen:

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

(12 Zeichen entfernt, da niemand dem Ausgabeformat folgt ...: |)

KennyTM
quelle
12

Eine andere Assembler-Version. Dieser ist nicht auf 32-Bit-Zahlen beschränkt, sondern kann Zahlen bis zu 10 65534 verarbeiten, obwohl das von MS-DOS verwendete ".com" -Format auf 80-stellige Zahlen beschränkt ist. Geschrieben für A86 Assembler und erfordert eine Win-XP DOS-Box zum Ausführen. Zusammengesetzt zu 180 Bytes:

    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
Skizz
quelle
10

dc - 24 Zeichen 25 28

dc ist ein gutes Werkzeug für diese Sequenz:

?[d5*2+d2%*+2/pd1<L]dsLx
dc -f collatz.dc
21
64
32
16
8
4
2
1

Auch 24 Zeichen nach der Formel aus dem Golfscript- Eintrag:

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

57 Zeichen , um die Spezifikationen zu erfüllen:

[Number: ]n?[Results: ]ndn[d5*2+d2%*+2/[ -> ]ndnd1<L]dsLx
dc -f collatz-spec.dc
Nummer 3
Ergebnisse: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Carlos Gutiérrez
quelle
9

Schema: 72

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

Dies verwendet eine Rekursion, aber die Aufrufe sind endrekursiv, sodass ich denke, dass sie für die Iteration optimiert werden. In einigen schnellen Tests konnte ich keine Nummer finden, für die der Stapel ohnehin überläuft. Nur zum Beispiel:

(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 53987098123749825298309837432974329852309857807

... läuft gut. [das ist alles eine Zahl - ich habe sie gerade gebrochen, damit sie auf den Bildschirm passt.]

Jerry Coffin
quelle
8

Mathematica, 45 50 Zeichen

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
Pillsy
quelle
Ich habe 58 Zeichen gezählt. Und Sie können ersetzen OddQ[#]mit OddQ@#1 Zeichen zu speichern.
Kennytm
2
50 Zeichen:c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&]
Michael Pilat
7

Ruby, 50 Zeichen, kein Stapelüberlauf

Grundsätzlich ein direkter Rip von Makapufs Python-Lösung :

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

Ruby, 45 Zeichen, wird überlaufen

Grundsätzlich ein direkter Rip des in der Frage angegebenen Codes:

def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end
Jordan Running
quelle
Welche Version von Ruby ist das? Ich werde n.odd??nicht definiert. Dies ist auch anfällig für Stapelüberläufe mit großen Zahlen.
Earlz
Das ist interessant. Ich habe 1.8.7. Das Hinzufügen eines Leerzeichens zwischen den Fragezeichen sollte dies beheben. Und Sie haben Recht mit dem Stapelüberlauf. Ich werde meine Antwort bearbeiten, um dies zu notieren.
Jordan läuft
3
Sie können vier Zeichen mitp n=[n/2,n*3+1][n%2]
Wayne Conrad
7
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);
    }
}
wowest
quelle
50
Java: Die Sprache, in der Sie BigIntegers verwenden müssen, um die Anzahl der Zeichen im Code der Lösung zu zählen.
Jared Updike
3
@ Jared Ich stimme voll und ganz zu, dass Java ausführlich ist. Sie müssen zugeben, dass die vorgestellte Lösung a) die Anforderungen erfüllt b) viel länger als wirklich notwendig ist und c) auf angenehme Weise mit dem Java-Typ-System spielt
wowest
7

Python 45 Char

Rasierte einen Saibling von Makapufs Antwort.

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
GuillaumeDufay
quelle
sehr kluger Gebrauch des Operators ~. Ich musste es nachschlagen, um zu sehen, was es tat (ich versuche, binäre Operatoren in Python zu vermeiden, daher bin ich mit ihnen nicht sehr vertraut).
Ponkadoodle
5

TI-BASIC

Nicht der kürzeste, aber ein neuartiger Ansatz. Sicherlich bei großen Sequenzen erheblich langsamer, aber es sollte nicht überlaufen.

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
Jonathan
quelle
4

Haskell: 50

c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)
Josh Lee
quelle
Mit jkffs Idee: c 1=[1];c n=n:(c$[ndiv 2,3*n+1]!!(nmod 2)), 44 Zeichen
sdcvvc
4

Nicht die kürzeste, aber eine elegante Clojure-Lösung

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

C #: 216 Zeichen

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);}}}

in langer Form:

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);
        }
    }
}

Neue Version, akzeptiert eine Nummer als Eingabe über die Befehlszeile, keine Eingabevalidierung. 173 154 Zeichen.

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);}}}

in langer Form:

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);
        }
    }
}

Ich kann ein paar Zeichen rasieren, indem ich die Idee in dieser Antwort abreiße , eine for-Schleife anstelle einer Weile zu verwenden. 150 Zeichen.

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);}}
Venr
quelle
Sie sollten erwähnen, dass Ihr Code mehr als eine Eingabe akzeptiert. Oder nehmen Sie das weg und rasieren Sie ein paar Zeichen ab.
R. Martinho Fernandes
Sie können Aktion <Objekt> und möglicherweise mehr auf Dynamik in C # 4 verkürzen.
Dykam
@Dykam: Nur überprüft: schlägt fehl mit "Fehler CS0428: Methodengruppe 'Write' kann nicht in den nicht delegierten Typ 'dynamic' konvertiert werden. Wollten Sie die Methode aufrufen?".
R. Martinho Fernandes
Oh, natürlich ... implizite Konvertierung in Delegierte ... erfordert die Angabe des Delegierten.
Schade
4

Ruby, 43 Zeichen

Bignum unterstützt, mit Stapelüberlaufanfälligkeit:

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

... und 50 Zeichen, Bignum unterstützt, ohne Stapelüberlauf:

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

Ein großes Lob an Jordanien. Ich wusste nicht über 'p' als Ersatz für Puts.

Sniggerfardimungus
quelle
4

nroff 1

Laufen Sie mit 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-Version

DigitalRoss
quelle
2
Unheimlich! Trotzdem sollte zumindest die Ausgabe gut formatiert sein.
Jonathan Leffler
3
Hey, starte es als groff -U hail.gund du bekommst PostScript! :-)
DigitalRoss
4

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

Und in Aktion:

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

Dies schließt auch die nachfolgende 1 ein.

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)

Mit folgendem impliziten

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

dies kann auf verkürzt werden

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

Bearbeiten - 58 Zeichen (einschließlich Eingabe und Ausgabe, jedoch ohne Anfangsnummer)

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

Könnte um 2 reduziert werden, wenn Sie keine Zeilenumbrüche benötigen ...

Ben Lings
quelle
3

F #, 90 Zeichen

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; ...]

Wenn Sie F # nicht interaktiv verwenden, um das Ergebnis anzuzeigen, werden 102 Zeichen angezeigt:

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"
Joel Mueller
quelle
3

Common Lisp, 141 Zeichen:

(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~%"))

Testlauf:

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 
Vatine
quelle
Fast. Es gibt keinen Header für die 2. Zeile. Ich hätte 3 Zeichen rasieren können, ohne den Pfeil zu ignorieren, weitere 3-4, die unnötige Leerzeichen entfernen, aber ich bin mit einem Vielfachen von 3 zufrieden.
Vatine
3

Das Programm von Jerry Coffin hat eine Ganzzahl über dem Fluss. Versuchen Sie Folgendes:

#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";
}

getestet mit

Die Zahl von weniger als 100 Millionen mit der längsten Gesamtstoppzeit beträgt 63.728.127 mit 949 Schritten.

Die Zahl von weniger als 1 Milliarde mit der längsten Gesamtstoppzeit beträgt 670.617.279 mit 986 Schritten.

Soumen Sarkar
quelle
Endliche Ganzzahltypen können einen Ganzzahlüberlauf nicht verhindern. Nicht einmal unsigned long long.
Kennytm
3

Ruby, 43, erfüllt möglicherweise die E / A-Anforderungen


Laufen Sie mit ruby -n hail

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

C #: 659 Zeichen mit BigInteger-Unterstützung

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);}}}

Ungolfed

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);
        }
    }
}
Cameron MacFarland
quelle