language agnostic - Código Golf: Conjetura de Collatz
language-agnostic code-golf (30)
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á utilizando 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"
Inspirado por http://xkcd.com/710/ aquí hay un código de golf para él.
El reto
Dado un entero positivo mayor que 0, imprima la secuencia de granizo para ese número.
La secuencia de Hailstone
Ver Wikipedia para más detalles ...
- Si el número es par, divídalo por dos.
- Si el número es impar, triplícalo y agrega 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 algunos 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 recursividad de cola.
Además, puntos de bonificación por 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 usando 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 de golf debe incluir la entrada y salida completa del usuario.
Perl
Decidí ser un poco anticompetitivo y mostrar cómo normalmente codificaría ese problema en Perl.
También hay un total de 46 (total) entrada de código de golf al final.
Estos primeros tres ejemplos comienzan 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ías ese último ejemplo con una versión de Perl anterior a 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 de IO siempre va a ser la parte lenta. Por lo tanto, si realmente los compara como es, debería obtener la misma velocidad de cada uno.
Para probarlos, abrí un identificador de archivo a /dev/null ( $null ) y edité cada say $n para leer en su lugar 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 haberlo ejecutado 10 veces, aquí hay una salida de muestra representativa:
Rate Recursive Iterative Optimized Recursive 1715/s -- -27% -46% Iterative 2336/s 36% -- -27% Optimized 3187/s 86% 36% --
Finalmente, una entrada real de código de golf:
perl -nlE''say;say$_=$_%2?3*$_+1:$_/2while$_>1''
46 caracteres en total
Si no necesita imprimir el valor de inicio, 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 -n . Entonces incluyo todo el ejemplo en mi conteo.
Python - 95 64 51 46 char
Obviamente no produce un desbordamiento de pila.
n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
bc 41 caracteres
Supongo que este tipo de problemas es para lo que fue inventado bc :
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 correcto:
for(n=read();n>1;){if(n%2)n=n*3+1else n/=2;print n,"/n"}
bc maneja números con hasta dígitos INT_MAX
Editar: El artículo de Wikipedia menciona esta conjetura se ha comprobado para todos los valores de hasta 20x2 58 (aproximadamente 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
prueba 2 20,000 +1 (aproximadamente 3.98e6,020 ) en 68 segundos, 144,404 ciclos.
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 16 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 Number: 3 Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
Befunge
&>:.:1-|
>3*^ @
|%2: <
v>2/>+
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);}}}
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);
}
}
}
C: 64 caracteres
main(x){for(scanf("%d",&x);x>=printf("%d,",x);x=x&1?3*x+1:x/2);}
Con gran soporte entero: 431 (necesarios) caracteres
#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 prototipos de malloc / realloc, ya que no será seguro en plataformas de 64 bits (el vacío de 64 bits se convertirá a int de 32 bits).
Este no ha sido probado enérgicamente todavía. Podría usar un poco de manteca también.
Versión anterior:
main(x){for(scanf("%d",&x);printf("%d,",x),x-1;x=x&1?3*x+1:x/2);} // 66
(eliminado 12 caracteres porque nadie sigue el formato de salida ...: |)
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;
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
La entrada del usuario, salida impresa, usa memoria y pila constantes, funciona con enteros arbitrariamente grandes.
Una muestra de ejecución de este código, dado un número de 80 dígitos de todos los "1" (!) Como entrada, es muy 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)
¿Quién de los @ y ^ # necesita condicionales, de todos modos?
(Editar: Estaba siendo "inteligente" y usé el parche. Sin él, el código bajó a 54 caracteres. edit2: bajó a 51 al factorizar f() )
Haskell: 50
c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)
Mathematica, 45 50 caracteres
c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
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.
Ruby, 43 caracteres
bignum compatible, 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, bignum compatible, 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 sabía acerca de ''p'' como un reemplazo de puts.
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 provisto en la pregunta:
def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end
TI-BASIC
No es el más corto, sino un enfoque novedoso. Cierto disminuir la velocidad 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
conjunto 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
nroff 1
Ejecutar 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 de groff
ruby, 43, posiblemente cumpliendo 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
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
El programa de Jerry Coffin tiene un número entero de flujo excesivo, prueba 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 detención total más largo es 63,728,127, con 949 pasos.
El número de menos de mil millones con el tiempo de detención total más largo es de 670,617,279, con 986 pasos.
Otra versión de ensamblador. Éste no está limitado a números de 32 bits, puede manejar números de hasta 10 65534, aunque el formato ".com" que utiliza MS-DOS está limitado a números de 80 dígitos. Escrito para el ensamblador A86 y requiere un cuadro Win-XP DOS 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
no la más corta, sino una solución clojure elegante
(defn collatz [n]
(print n "")
(if (> n 1)
(recur
(if (odd? n)
(inc (* 3 n))
(/ n 2)))))
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. 173 154 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);
}
}
}
Soy capaz de afeitar algunos personajes al estafar la idea en esta answer para usar un bucle for en lugar de un rato. 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);}}
Esquema: 72
(define(c n)(if(= n 1)`(1)(cons n(if(odd? n)(c(+(* n 3)1))(c(/ n 2))))))
Esto utiliza la recursividad, pero las llamadas son recursivas, por lo que creo que se optimizarán para la iteración. En algunas pruebas rápidas, no he podido encontrar un número para el cual la pila se desborde de todos modos. Solo por ejemplo:
(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)
... corre bien [Eso es todo un número: acabo de romperlo para que quepa en la pantalla.]
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 INTERPRETR . KTHXBYE!
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 tomó copiar / pegar la fórmula 111 veces para obtener el resultado de un número inicial de 1000.;)
Python 45 Char
Afeitado un char de la respuesta de makapuf.
n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
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 final 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)
Con el 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 ...
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);
}
}