Code Golf: Conjetura de Collatz

86

Inspirado por http://xkcd.com/710/ aquí hay un código de golf para ello.

El reto

Dado un número entero positivo mayor que 0, imprima la secuencia de granizo para ese número.

La secuencia del granizo

Consulte Wikipedia para obtener más detalles.

  • Si el número es par, divídelo por dos.
  • Si el número es impar, triplícalo y suma uno.

Repita esto con el número producido hasta que llegue a 1. (si continúa después de 1, irá en un bucle infinito de 1 -> 4 -> 2 -> 1...)

A veces, el código es la mejor manera de explicarlo, así que aquí hay algo de Wikipedia.

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

Este código funciona, pero estoy agregando un desafío adicional. El programa no debe ser vulnerable a desbordamientos de pila . Por lo tanto, debe usar iteración o recursión de cola.

Además, puntos de bonificación si puede calcular números grandes y el idioma aún no lo tiene implementado. (o si vuelve a implementar el soporte de números grandes utilizando enteros de longitud fija)

Caso de prueba

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

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

Además, el código golf debe incluir la entrada y salida completa del usuario.

Earlz
fuente
20
no debe ser vulnerable a desbordamientos de pila : ¡entonces no debería haberlo publicado aquí! ;)
Felix Kling
51
Mis amigos dejaron de llamarme, ¿eso significa que resolví el problema?
Martin
18
¿Estás en SO, pero alguna vez tuviste amigos? ... ¿como fue eso?
Pops
5
La respuesta del ensamblador es genial, ¡pero es un poco anti-código-golf seleccionar la respuesta más larga !
John La Rooy

Respuestas:

129

ensamblado x86, 1337 caracteres

;
; 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
Martín
fuente
27
asm x86 y 1337 caracteres. Lloro de alegría.
ZoogieZork
10
Me gusta el uso (ab) de lea para 3n + 1.
wowest
Gracias por no usar int 23h.
Mike D.
¿Cómo puedo cumplir en linux? No puedo esperar para probarlo
hidroto
64

Befunge

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+
Josh Lee
fuente
2
Deberías leer esto en 2D. <> ^ v son flechas que cambian la dirección en la que se desplaza el "contador de programa". | y _ son condicionales que van hacia arriba / abajo o hacia la izquierda / derecha dependiendo de si el valor en la pila es verdadero o falso. Todo el "campo del código" se envuelve de arriba a abajo y de izquierda a derecha.
SF.
¡Y solo 35 caracteres, incluidos los espacios en blanco! ¡No está mal!
Potatoswatter
6
¿Estás seguro de que no es Perl?
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. MEZA'S INTERPRETR . KTHXBYE!

lunohodov
fuente
51

Python - 95 64 51 46 caracteres

Obviamente no produce un desbordamiento de pila.

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
makapuf
fuente
4
Es posible que desee especificar Python 2.x. IIRC, Python 3.x inputno hace un eval.
Mike D.
5
Esto no cumple con los requisitos - no imprime el primer número
Ben Lings
7
¿Por qué se acepta esto? no es el más corto y no imprime el primer número
Claudiu
1
Supongo que input () hace eco de los caracteres que escribe, así que imprime el primer número :)
Danko Durbić
17
Puede imprimir el primer número por un costo de solo 2 bytes usandon=input()*2
John La Rooy
23

Perl

Decidí ser un poco anticompetitivo y mostrar cómo codificaría normalmente ese problema en Perl.
También hay una entrada de golf de código de 46 caracteres (total) al final.

Estos tres primeros ejemplos comienzan todos con este encabezado.

#! /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( $_ );
}
  • Versión recursiva 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 );
        }
      }
    }
    
  • Versión iterativa 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;
      }
    }
    
  • Versión iterativa optimizada

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

Ahora voy a mostrar cómo haría ese último ejemplo con una versión de Perl anterior a 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];
  }
}

Punto de referencia

Primero, el IO siempre será la parte lenta. Entonces, si realmente los comparó como están, debería obtener aproximadamente la misma velocidad de cada uno.

Para probarlos, abrí un identificador de archivo en /dev/null( $null) y edité cada say $npara leer say {$null} $n. Esto es para reducir la dependencia de 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;
  ...
}

Después de ejecutarlo 10 veces, aquí hay una salida de muestra representativa:

            Calificar iterativo recursivo optimizado
Recursivo 1715 / s - -27% -46%
Iterativo 2336 / s 36% - -27%
Optimizado 3187 / s 86% 36% -

Finalmente, una entrada de código de golf real:

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

46 caracteres en total

Si no necesita imprimir el valor inicial, puede eliminar 5 caracteres más.

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

41 caracteres en total
31 caracteres para la parte del código real, pero el código no funcionará sin el -ninterruptor. Así que incluyo el ejemplo completo en mi recuento.

Brad Gilbert
fuente
Tu versión optimizada, no lo es.
Motti
@Motti Estos ejemplos dependen mucho de IO. Después de haberlos probado varias veces, la versión optimizada siempre mantiene una ventaja significativa.
Brad Gilbert
@Brad, cuando ejecuta Collatz en un número, la optimización es una pesimización, ya que ningún número debería aparecer más de una vez (a menos que la conjetura sea incorrecta). La razón por la que está viendo una mejora es que está ejecutando muchos números (como en el problema de Euler), de hecho, escribí una publicación de blog sobre esto recientemente lanzkron.wordpress.com/2010/01/18/…
Motti
2
@Motti, esa es la optimización de la que estaba hablando. Además, en Perl $i + 1es siempre la suma (respuesta a la entrada del blog). Usar Sub::Call::Recurtambién es una optimización. De lo contrario, usaría @_=$n;goto &Collatz. (Es un 10-20% más lento si cambia state @nextamy @next
Brad Gilbert
3
Creo que los estándares de recuento de golpes de golf de Perl no cuentan los golpes obligatorios para invocar al intérprete ni las citas, pero sí cuentan uno para cada bandera al lado de E. Usando esas reglas, sus últimas entradas cuentan respectivamente 37 caracteres y 32 caracteres.
R. Martinho Fernandes
23

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

Entrada de usuario, salida impresa, utiliza memoria y pila constantes, trabaja con enteros arbitrariamente grandes.

Una ejecución de muestra de este código, dado un número de 80 dígitos de todos los '1' (!) Como entrada, es bastante divertido de ver.


Versión original, solo función:

Haskell 51 caracteres

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

De todas formas, ¿quién @ & ^ # necesita condicionales?

(editar: estaba siendo "inteligente" y usé la corrección. Sin él, el código se redujo a 54 caracteres. edit2: se redujo a 51 al factorizar f())

MtnViewMark
fuente
Después de hacer mi publicación de Miranda (que es básicamente un Haskell más antiguo), al menos en Miranda puedes reducir eso usando solo un signo de exclamación cada uno: fn = n: [[], [f (n div 2), f (3 * n + 1)]! (n mod 2)]! (1 mod n) - Funciona :)
Derek H
Oh, sí, te faltan entradas y salidas.
R. Martinho Fernandes
@Martinho: Yo también, pero gracias a la evaluación perezosa, las tablas son mucho más geniales que en otros idiomas.
Dario
1
Usando la idea de jleedev: c 1=[1];c n=n:(c$div(nmod 2*(5*n+2)+n)2)- 41 caracteres, esto usa el hecho de que esto es k * (3n + 1) + (1-k) * n / 2 donde k = n mod 2
sdcvvc
2
Eliminé mi otra entrada, moví mi código aquí e incorporé aún más ideas de estos comentarios. Incrementado a 76 caracteres, pero tiene entrada y salida.
MtnViewMark
22

Golfscript: 20 caracteres

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

Esto es equivalente a

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
fuente
2
"debe incluir la entrada y salida completa del usuario"
F'x
2
@FX, reemplazar el 21con ~hará que el programa use un número de stdin
John La Rooy
@gnibbler: ¿Golfscript.rb está actualizado? Obtuve (eval):1:in initialize ': método indefinido leftparen' for nil:NilClass (NoMethodError)al reemplazar 21con ~.
kennytm
@KennyTM, lamentablemente GolfScript no puede leer stdin de forma interactiva, tienes que canalizar algo en stdin, comoecho 21 | ruby golfscript.rb collatz.gs
John La Rooy
19

bc 41 caracteres

Supongo que este tipo de problemas es para lo que bcse inventó:

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

Prueba:

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

Código adecuado:

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

bcmaneja números con hasta INT_MAXdígitos

Editar: El artículo de Wikipedia menciona que esta conjetura ha sido verificada para todos los valores hasta 20x2 58 (aprox. 5.76e18 ). Este programa:

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

pruebas 2 20,000 +1 (aprox. 3.98e6,020 ) en 68 segundos, 144,404 ciclos.

Carlos Gutiérrez
fuente
Cambie 'n! = 1' a 'n> 1' para 54 caracteres.
Jerry Coffin
4
Aquí hay una línea de comando para generar números aleatorios de longitud arbitraria para esta entrada (10000 dígitos en este caso): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc
indiv
3
@indiv - Tuve que probarlo :), me tomó 3 minutos y 12 segundos procesar el número de 10,000 dígitos. Guardé la salida en un archivo, tiene aproximadamente 1,2 gb de largo, pero sí, terminó correctamente en 1. Punto parabc
Carlos Gutiérrez
16

Perl: 31 caracteres

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

Editado para eliminar 2 espacios innecesarios.

Editado para eliminar 1 espacio innecesario.

a'r
fuente
Puede eliminar dos espacios innecesarios (después de decir y después de un tiempo)
sorigal
Pruebe perl -E 'say $ _ = 10; say $ _ = $ _% 2? $ _ * 3 + 1: $ _ / 2 while $ _> 1'
sorigal
Supuse que el usuario conocería el número inicial de la secuencia ;-).
2010
41
A veces, cuando me encuentro con texto codificado en base64, a veces lo confundo con el código fuente de Perl.
Martin
21
@Martin: No puedo imaginar cómo harías eso. Base64 es mucho más legible.
Jerry Coffin
15

MS Excel, 35 caracteres

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

Tomado directamente 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

Solo fue necesario copiar / pegar la fórmula 111 veces para obtener el resultado para un número inicial de 1000.;)

Lance McNearney
fuente
16
Supongo que es demasiado tarde para señalar que para esto es el controlador de llenado, ¿eh? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :)
Jordan Running
Esa es una característica bastante útil que ni siquiera sabía que existía. Simplemente copié la primera celda y luego resalté todas las demás celdas y las pegué una vez.
Lance McNearney
Aprendí sobre la pasta de área aproximadamente diez años después de descubrir el mango de relleno. cifras.
Jimmy
14

C: 64 caracteres

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

Con soporte para enteros grandes: 431 caracteres (necesarios)

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

Nota : No elimine #include <stdlib.h>sin al menos crear un prototipo de malloc / realloc, ya que hacerlo no será seguro en plataformas de 64 bits (void * de 64 bits se convertirá a int de 32 bits).

Este todavía no ha sido probado vigorosamente. También le vendría bien un poco de manteca.


Versión anterior:

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

(se eliminaron 12 caracteres porque nadie sigue el formato de salida ...: |)

KennyTM
fuente
12

Otra versión de ensamblador. Éste no está limitado a números de 32 bits, puede manejar números hasta 10 65534 aunque el formato ".com" que usa MS-DOS está limitado a números de 80 dígitos. Escrito para ensamblador A86 y requiere una caja DOS de Win-XP para ejecutarse. Se ensambla a 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
fuente
10

dc - 24 caracteres 25 28

dc es una buena herramienta para esta secuencia:

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

También 24 caracteres usando la fórmula de la entrada de Golfscript :

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

57 caracteres para cumplir con las especificaciones:

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

Esquema: 72

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

Esto usa recursividad, pero las llamadas son recursivas al final, así que creo que estarán optimizadas para la iteración. En algunas pruebas rápidas, no he podido encontrar un número para el que la pila se desborde de todos modos. Solo por ejemplo:

(c)

... funciona bien. [eso es todo un número; lo acabo de romper para que quepa en la pantalla].

2 rev.
fuente
8

Mathematica, 45 50 caracteres

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
Pillsy
fuente
Conté 58 caracteres. Y puede reemplazar OddQ[#]con OddQ@#para guardar 1 carácter.
kennytm
2
50 caracteres:c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&]
Michael Pilat
7

Ruby, 50 caracteres, sin desbordamiento de pila

Básicamente una copia directa de la solución Python de makapuf :

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

Ruby, 45 caracteres, se desbordará

Básicamente, una copia directa del código proporcionado en la pregunta:

def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end
Jordan Running
fuente
¿Qué versión de Ruby es esa? No n.odd??me definen. Además, eso es vulnerable a desbordamientos de pila con grandes números.
Earlz
Eso es interesante. Tengo 1.8.7. Agregar un espacio entre los signos de interrogación debería arreglar eso. Y tienes razón sobre el desbordamiento de la pila. Editaré mi respuesta para tomar nota de eso.
Jordan Running
3
Puedes salvar cuatro personajes conp 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);
    }
}
más asombroso
fuente
50
Java: el lenguaje donde tienes que usar BigIntegers solo para contar la cantidad de caracteres en el código de la solución.
Jared Updike
3
@Jared Estoy totalmente de acuerdo en que Java es detallado. Debe admitir que la solución presentada a) cumple con los requisitos b) es mucho más larga de lo realmente necesario yc) juega con el sistema de tipo Java de una manera agradable
wowest
7

Python 45 Char

Afeitó un carboncillo de la respuesta de makapuf.

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
GuillaumeDufay
fuente
uso muy inteligente del operador ~. Tuve que buscarlo para ver qué hacía (trato de evitar los operadores binarios en Python, así que no estoy muy familiarizado con ellos).
Ponkadoodle
5

TI-BASIC

No es el enfoque más corto, pero sí novedoso. Seguro que se ralentizará considerablemente con secuencias grandes, pero no debería desbordarse.

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
fuente
4

Haskell: 50

c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)
Josh Lee
fuente
Usando la idea de jkff: c 1=[1];c n=n:(c$[ndiv 2,3*n+1]!!(nmod 2)), 44 chars
sdcvvc
4

no es la más corta, pero sí una elegante solución clojure

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

C #: 216 caracteres

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

en forma larga:

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

Nueva versión, acepta un número como entrada proporcionada a través de la línea de comando, sin validación de entrada. 173154 caracteres.

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

en forma larga:

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

Puedo recortar algunos caracteres al copiar la idea en esta respuesta para usar un bucle for en lugar de un tiempo. 150 caracteres.

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
fuente
Debe mencionar que su código acepta más de una entrada. O elimínelo y elimine algunos caracteres.
R. Martinho Fernandes
Puede acortar Action <object> y posiblemente más a dynamic en C # 4.
Dykam
@Dykam: Acabo de marcarlo: falla con el "error CS0428: No se puede convertir el grupo de métodos 'Escribir' al tipo no delegado 'dinámico'. ¿Tenía la intención de invocar el método?".
R. Martinho Fernandes
Oh, por supuesto ... la conversión implícita a delegados ... requiere denotar al delegado. Bummer ...
Dykam
4

Ruby, 43 caracteres

compatible con bignum, con susceptibilidad de desbordamiento de pila:

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

... y 50 caracteres, compatible con bignum, sin desbordamiento de pila:

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

Felicitaciones a Jordan. No conocía la 'p' como reemplazo de las opciones de venta.

Sniggerfardimungus
fuente
4

nroff 1

Corre con 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. versión groff

DigitalRoss
fuente
2
¡De miedo! Aún así, al menos la salida debería tener un buen formato.
Jonathan Leffler
3
¡Ejecútelo como groff -U hail.gy obtendrá 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

Y en acción:

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

Esto también incluye el 1 final.

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)

Con lo siguiente implícito

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

esto se puede acortar a

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

Editar: 58 caracteres (incluida la entrada y la salida, pero sin incluir el número inicial)

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

Podría reducirse en 2 si no necesita nuevas líneas ...

Ben Lings
fuente
3

F #, 90 caracteres

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

O si no está usando F # interactivo para mostrar el resultado, 102 caracteres:

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
fuente
3

Common Lisp, 141 caracteres:

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

Prueba de funcionamiento:

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
fuente
Casi. No hay encabezado para la segunda línea. Podría haberme afeitado 3 caracteres ignorando la flecha, otros 3-4 eliminando espacios innecesarios, pero estoy contento con un múltiplo de 3.
Vatine
3

El programa de Jerry Coffin tiene un desbordamiento de enteros, pruebe este:

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

probado con

El número de menos de 100 millones con el tiempo de parada total más largo es 63,728,127, con 949 pasos.

El número de menos de mil millones con el tiempo de parada total más largo es 670,617,279, con 986 pasos.

Soumen Sarkar
fuente
Cualquier tipo de entero finito no puede evitar el desbordamiento de enteros. Ni siquiera unsigned long long.
kennytm
3

ruby, 43, posiblemente cumpliendo con el requisito de E / S


Corre con ruby -n hail

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

C #: 659 caracteres con soporte 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);}}}

Sin golf

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
fuente