Code Golf: Conjecture de Collatz

86

Inspiré par http://xkcd.com/710/, voici un code golf pour cela.

Le défi

Étant donné un entier positif supérieur à 0, imprimez la séquence de grêle pour ce nombre.

La séquence de grêle

Voir Wikipedia pour plus de détails.

  • Si le nombre est pair, divisez-le par deux.
  • Si le nombre est impair, triplez-le et ajoutez-en un.

Répétez ceci avec le nombre produit jusqu'à ce qu'il atteigne 1. (s'il continue après 1, il ira dans une boucle infinie de 1 -> 4 -> 2 -> 1... )

Parfois, le code est le meilleur moyen d'expliquer, alors voici quelques-uns de Wikipedia

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

Ce code fonctionne, mais j'ajoute un défi supplémentaire. Le programme ne doit pas être vulnérable aux débordements de pile . Il doit donc soit utiliser l'itération, soit la récursivité de queue.

En outre, des points bonus pour savoir s'il peut calculer de grands nombres et que la langue ne l'a pas déjà implémenté. (ou si vous réimplémentez la prise en charge des grands nombres en utilisant des entiers de longueur fixe)

Cas de test

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

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

En outre, le code golf doit inclure une entrée et une sortie utilisateur complètes.

Earlz
la source
20
ne doit pas être vulnérable aux débordements de pile : vous n'auriez pas dû le poster ici alors! ;)
Felix Kling
51
Mes amis ont arrêté de m'appeler, est-ce que cela signifie que j'ai résolu le problème?
Martin
18
Vous êtes sur SO, mais une fois eu des amis? ... comment était-ce?
Pops
5
La réponse de l'assembleur est cool, mais c'est un peu anti-code-golf pour sélectionner la réponse la plus longue !
John La Rooy

Réponses:

129

assemblage x86, 1337 caractères

;
; 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
la source
27
x86 asm et 1337 caractères. Je pleure de joie.
ZoogieZork
10
J'aime l'utilisation (ab) de lea pour 3n + 1.
wowest
Merci de ne pas utiliser int 23h.
Mike D.
comment puis-je me conformer à linux j'ai hâte de l'essayer
hidroto
64

Befunge

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+
Josh Lee
la source
2
Vous devriez lire ceci en 2D. <> ^ v sont des flèches qui changent la direction du "compteur de programme". | et _ sont des conditions qui montent / descendent ou gauche / droite selon que la valeur de la pile est vraie ou fausse. L'ensemble de "l'arène du code" s'enroule de haut en bas et de gauche à droite.
SF.
Et seulement 35 caractères, espaces compris! Pas mal du tout!
Potatoswatter
6
Etes-vous sûr que ce n'est pas Perl?
ijw
52

CODE LOL: 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 INTERPRÉTÉ DE JUSTIN J. MEZA . KTHXBYE!

Lunohodov
la source
51

Python - 95 64 51 46 caractères

Ne produit évidemment pas de débordement de pile.

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
makapuf
la source
4
Vous souhaiterez peut-être spécifier Python 2.x. IIRC, Python 3.x inputne fait pas de fichier eval.
Mike D.
5
Cela ne répond pas aux exigences - il n'imprime pas le premier numéro
Ben Lings
7
pourquoi est-ce accepté? ce n'est pas le plus court et il n'imprime pas le premier numéro
Claudiu
1
Je suppose que input () fait écho aux caractères que vous tapez, donc cela imprime le premier numéro :)
Danko Durbić
17
Vous pouvez imprimer le premier numéro pour un coût de seulement 2 octets en utilisantn=input()*2
John La Rooy
23

Perl

J'ai décidé d'être un peu anticoncurrentiel et de montrer comment vous coderiez normalement un tel problème en Perl.
Il y a aussi une entrée de code-golf de 46 caractères (au total) à la fin.

Ces trois premiers exemples commencent tous par cet en-tête.

#! /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( $_ );
}
  • Version récursive simple

    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 );
        }
      }
    }
    
  • Version itérative simple

    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;
      }
    }
    
  • Version itérative optimisée

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

Je vais maintenant vous montrer comment vous feriez ce dernier exemple avec une version de Perl antérieure à la v5.10.0

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

Référence

Tout d'abord, les E / S seront toujours la partie la plus lente. Donc, si vous les comparez tels quels, vous devriez obtenir à peu près la même vitesse pour chacun d'eux.

Pour les tester ensuite, j'ai ouvert un descripteur de fichier vers /dev/null( $null), et je les ai tous modifiés say $nà la place say {$null} $n. Cela permet de réduire la dépendance à l'égard des IO.

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

Après l'avoir exécuté 10 fois, voici un exemple de sortie représentatif:

            Taux récursif itératif optimisé
Récursif 1715 / s - -27% -46%
Itératif 2336 / s 36% - -27%
Optimisé 3187 / s 86% 36% -

Enfin, une véritable entrée de code-golf:

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

46 caractères au total

Si vous n'avez pas besoin d'imprimer la valeur de départ, vous pouvez supprimer 5 caractères supplémentaires.

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

41 caractères totalisent
31 caractères pour la partie de code réelle, mais le code ne fonctionnera pas sans le -ncommutateur. J'inclus donc l'exemple entier dans mon décompte.

Brad Gilbert
la source
Votre version optimisée ne l'est pas.
Motti
@Motti Ces exemples sont très dépendants des E / S. Après les avoir testées plusieurs fois, la version optimisée conserve toujours une avance significative.
Brad Gilbert
@Brad, lorsque vous exécutez Collatz sur un numéro, l'optimisation est une pessimisation car aucun numéro ne doit apparaître plus d'une fois (sauf si la conjecture est fausse). La raison pour laquelle vous voyez une amélioration est que vous exécutez de nombreux numéros (comme dans le problème Euler), en fait, j'ai récemment écrit un article de blog à propos de cela lanzkron.wordpress.com/2010/01/18
Motti
2
@Motti, c'est l'optimisation dont je parlais. De plus, en Perl, il $i + 1y a toujours addition (réponse à l'entrée du blog). L'utilisation Sub::Call::Recurest également une optimisation. Sinon j'utiliserais @_=$n;goto &Collatz. (Il est 10-20% plus lent si vous changez state @nextpourmy @next
Brad Gilbert
3
Je crois que les standards de comptage des coups de golf de Perl ne comptent pas les coups obligatoires pour invoquer l'interprète ni les guillemets, mais comptent un pour chaque drapeau à côté de E. En utilisant ces règles, vos dernières entrées comptent respectivement 37 caractères et 32 ​​caractères.
R. Martinho Fernandes
23

Haskell, 62 caractères 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

L'entrée utilisateur, la sortie imprimée, utilise la mémoire et la pile constantes, fonctionne avec des entiers arbitrairement grands.

Un exemple d'exécution de ce code, avec un nombre à 80 chiffres de tous les «1» (!) En entrée, est assez amusant à regarder.


Version d'origine, fonction uniquement:

Haskell 51 caractères

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

Qui le @ & ^ # a besoin de conditions, de toute façon?

(edit: j'étais "intelligent" et j'ai utilisé un correctif. Sans cela, le code est tombé à 54 caractères. edit2: est tombé à 51 en factorisant f())

MtnViewMark
la source
Après avoir publié mon article sur Miranda (qui est essentiellement un Haskell plus ancien), au moins dans Miranda, vous pouvez réduire cela en utilisant un seul point d'exclamation chacun - fn = n: [[], [f (n div 2), f (3 * n + 1)]! (n mod 2)]! (1 mod n) - Fonctionne :)
Derek H
Oh, oui, il vous manque des entrées et des sorties.
R. Martinho Fernandes
@Martinho: Moi aussi, mais grâce à une évaluation paresseuse, les tableaux sont encore beaucoup plus cool que dans d'autres langues.
Dario
1
En utilisant l'idée de jleedev: c 1=[1];c n=n:(c$div(nmod 2*(5*n+2)+n)2)- 41 caractères, cela utilise le fait que c'est k * (3n + 1) + (1-k) * n / 2 où k = n mod 2
sdcvvc
2
J'ai supprimé mon autre entrée et déplacé mon code ici, et incorporé encore plus d'idées de ces commentaires. Augmenté à 76 caractères, mais fait entrée et sortie.
MtnViewMark
22

Golfscript: 20 caractères

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

Cela équivaut à

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
la source
2
"doit inclure une entrée et une sortie utilisateur complètes"
F'x
2
@FX, en remplaçant le 21par ~, le programme utilisera un nombre de stdin
John La Rooy
@gnibbler: Golfscript.rb est-il mis à jour? J'ai eu (eval):1:in la méthode initialize ': undefined leftparen' for nil:NilClass (NoMethodError)lors du remplacement 21par ~.
kennytm
@KennyTM, Malheureusement, GolfScript ne peut pas lire stdin de manière interactive, vous devez diriger quelque chose dans stdin, commeecho 21 | ruby golfscript.rb collatz.gs
John La Rooy
19

bc 41 caractères

Je suppose que ce genre de problèmes est ce bcpour quoi il a été inventé:

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

Tester:

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

Code approprié:

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

bcgère les nombres avec jusqu'à INT_MAXchiffres

Edit: L' article de Wikipedia mentionne que cette conjecture a été vérifiée pour toutes les valeurs jusqu'à 20x2 58 (environ 5.76e18 ). Ce programme:

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

tests 2 20000 +1 (environ 3,98e6,020 ) en 68 secondes, 144404 cycles.

Carlos Gutiérrez
la source
Remplacez «n! = 1» par «n> 1» pour 54 caractères.
Jerry Coffin
4
Voici une ligne de commande pour générer des nombres aléatoires de longueur arbitraire pour cette entrée (10000 chiffres dans ce cas): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc
indiv
3
@indiv - J'ai dû le tester :), il a fallu 3 minutes et 12 secondes pour traiter le nombre de 10000 chiffres. J'ai enregistré la sortie dans un fichier, il fait environ 1,2 Go de long, mais oui, il s'est terminé correctement en 1. Point pourbc
Carlos Gutiérrez
16

Perl: 31 caractères

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

Modifié pour supprimer 2 espaces inutiles.

Modifié pour supprimer 1 espace inutile.

a'r
la source
Vous pouvez supprimer deux espaces inutiles (après disons et après un moment)
sorpigal
Essayez perl -E 'dites $ _ = 10; dites $ _ = $ _% 2? $ _ * 3 + 1: $ _ / 2 pendant que $ _> 1'
sorpigal
J'ai pensé que l'utilisateur serait au courant du numéro de départ de la séquence ;-).
2010
41
Parfois, lorsque je rencontre du texte encodé en base64, je le confond parfois avec du code source Perl.
Martin
21
@Martin: Je ne peux pas imaginer comment vous feriez ça. Base64 est beaucoup plus lisible.
Jerry Coffin
15

MS Excel, 35 caractères

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

Tiré directement de 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

Il n'a fallu que copier / coller la formule 111 fois pour obtenir le résultat pour un nombre de départ de 1000.;)

Lance McNearney
la source
16
Je suppose qu'il est trop tard pour moi de souligner que c'est à cela que sert la poignée de remplissage, hein? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :)
Jordan Running
C'est une fonctionnalité très pratique dont je ne savais même pas qu'elle existait. J'ai juste copié la première cellule, puis mis en évidence toutes les autres cellules et collé une fois.
Lance McNearney
J'ai appris la pâte de surface environ dix ans après avoir découvert la poignée de remplissage. Les figures.
Jimmy
14

C: 64 caractères

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

Avec prise en charge des grands nombres entiers: 431 caractères (nécessaires)

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

Remarque : ne supprimez pas #include <stdlib.h>sans au moins prototyper malloc / realloc, car cela ne sera pas sûr sur les plates-formes 64 bits (64 bits void * sera converti en 32 bits int).

Celui-ci n'a pas encore été testé vigoureusement. Il pourrait également utiliser un raccourcissement.


Versions précédentes:

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

(12 caractères supprimés car personne ne suit le format de sortie ...: |)

KennyTM
la source
12

Une autre version assembleur. Celui-ci n'est pas limité aux nombres de 32 bits, il peut gérer des nombres jusqu'à 10 65534 bien que le format ".com" utilisé par MS-DOS soit limité à 80 chiffres. Écrit pour l'assembleur A86 et nécessite une boîte DOS Win-XP pour fonctionner. Assemble à 180 octets:

    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
la source
10

dc - 24 caractères 25 28

dc est un bon outil pour cette séquence:

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

Aussi 24 caractères utilisant la formule de l' entrée Golfscript :

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

57 caractères pour répondre aux spécifications:

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

Schéma: 72

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

Cela utilise la récursivité, mais les appels sont récursifs en queue, donc je pense qu'ils seront optimisés pour l'itération. Lors de quelques tests rapides, je n'ai pas été en mesure de trouver un nombre pour lequel la pile déborde de toute façon. Juste par exemple:

(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 53987098123749825298309837432974329852309858309837432974329852309858309837432974329852309858309837432974329852309857398730873098573987305983983987553987583987553987583987

... fonctionne très bien. [c'est tout un chiffre - je viens de le casser pour qu'il tienne à l'écran.]

Jerry Coffin
la source
8

Mathematica, 45 ans 50 caractères

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
Pillsy
la source
J'ai compté 58 caractères. Et vous pouvez remplacer OddQ[#]par OddQ@#pour enregistrer 1 caractère.
kennytm
2
50 personnages:c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&]
Michael Pilat
7

Ruby, 50 caractères, pas de débordement de pile

Fondamentalement, une rip directe de la solution Python de makapuf :

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

Ruby, 45 caractères, débordera

Fondamentalement, une déchirure directe du code fourni dans la question:

def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end
Jordan Running
la source
De quelle version de Ruby s'agit-il? Je n.odd??ne suis pas défini. En outre, cela est vulnérable aux débordements de pile avec un grand nombre.
Earlz
C'est intéressant. J'ai 1.8.7. L'ajout d'un espace entre les points d'interrogation devrait résoudre ce problème. Et vous avez raison sur le débordement de pile. Je vais modifier ma réponse pour en prendre note.
Jordan Running
3
Vous pouvez enregistrer quatre personnages avecp 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
la source
50
Java: le langage dans lequel il faut utiliser BigIntegers juste pour compter le nombre de caractères dans le code de la solution.
Jared Updike
3
@Jared Je suis tout à fait d'accord pour dire que Java est verbeux. Vous devez admettre que la solution présentée a) répond aux exigences b) est bien plus longue que ce qui est vraiment nécessaire et c) joue avec le système de type java d'une manière agréable
wowest
7

Python 45 caractères

Rasé un omble de la réponse de makapuf.

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
GuillaumeDufay
la source
utilisation très intelligente de l'opérateur ~. J'ai dû le chercher pour voir ce qu'il faisait (j'essaie d'éviter les opérateurs binaires en Python, donc je ne les connais pas très bien).
Ponkadoodle
5

TI-BASIC

Pas la plus courte, mais une nouvelle approche. Certain de ralentir considérablement avec de grandes séquences, mais cela ne devrait pas déborder.

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
la source
4

Haskell: 50

c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)
Josh Lee
la source
Utilisation de l'idée de jkff: c 1=[1];c n=n:(c$[ndiv 2,3*n+1]!!(nmod 2)), 44 caractères
sdcvvc
4

pas la plus courte, mais une solution de clojure élégante

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

C #: 216 caractères

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

sous forme longue:

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

Nouvelle version, accepte un nombre comme entrée fournie via la ligne de commande, aucune validation d'entrée. 173 154 caractères.

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

sous forme longue:

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

Je suis capable de raser quelques caractères en arrachant l'idée dans cette réponse d'utiliser une boucle for plutôt qu'un moment. 150 caractères.

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
la source
Vous devez mentionner que votre code accepte plus d'une entrée. Ou enlevez-le et rasez quelques caractères.
R. Martinho Fernandes
Vous pouvez raccourcir Action <object> et éventuellement plus en dynamique en C # 4.
Dykam
@Dykam: Je viens de le vérifier: échoue avec "erreur CS0428: Impossible de convertir le groupe de méthodes 'Écriture' en type non délégué 'dynamique'. Aviez-vous l'intention d'appeler la méthode?".
R. Martinho Fernandes
Oh, bien sûr ... la conversion implicite en délégués ... nécessite de désigner le délégué. Bummer ...
Dykam
4

Rubis, 43 caractères

bignum pris en charge, avec susceptibilité de débordement de pile:

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

... et 50 caractères, bignum pris en charge, sans débordement de pile:

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

Félicitations à la Jordanie. Je ne connaissais pas «p» en remplacement des put.

Sniggerfardimungus
la source
4

nroff 1

Courir avec 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. version groff

DigitalRoss
la source
2
Effrayant! Pourtant, au moins la sortie doit être bien formatée.
Jonathan Leffler
3
Hé, lancez-le en tant que groff -U hail.get vous obtenez 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

Et en action:

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

Cela inclut également le dernier 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)

Avec ce qui suit implicite

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

cela peut être raccourci à

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

Modifier - 58 caractères (y compris l'entrée et la sortie, mais sans compter le numéro initial)

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

Peut être réduit de 2 si vous n'avez pas besoin de nouvelles lignes ...

Ben Lings
la source
3

F #, 90 caractères

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

Ou si vous n'utilisez pas F # interactif pour afficher le résultat, 102 caractères:

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
la source
3

Common Lisp, 141 caractères:

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

Essai:

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
la source
Presque. Il n'y a pas d'en-tête pour la deuxième ligne. J'aurais pu raser 3 caractères en ignorant la flèche, 3-4 en éliminant les espaces inutiles, mais je suis content d'un multiple de 3.
Vatine
3

Le programme frm Jerry Coffin a un débordement entier, essayez celui-ci:

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

testé avec

Le nombre inférieur à 100 millions avec le temps d'arrêt total le plus long est 63 728 127, avec 949 étapes.

Le nombre inférieur à 1 milliard avec le temps d'arrêt total le plus long est 670 617 279, avec 986 étapes.

Soumen Sarkar
la source
Les types d'entiers finis ne peuvent empêcher le dépassement d'entiers. Pas même unsigned long long.
kennytm
3

ruby, 43 ans, répondant peut-être aux exigences d'E / S


Courir avec ruby -n hail

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

C #: 659 caractères avec prise en charge BigInteger

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

Non golfées

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
la source