Code Golf: Collatz Conjecture

86

Inspirado em http://xkcd.com/710/ aqui está um código de golfe para ele.

O desafio

Dado um número inteiro positivo maior que 0, imprima a sequência de pedras de granizo para esse número.

A sequência de Hailstone

Veja a Wikipedia para mais detalhes.

  • Se o número for par, divida-o por dois.
  • Se o número for ímpar, triplique-o e adicione um.

Repita isso com o número produzido até chegar a 1. (se continuar depois de 1, ele fará um loop infinito de 1 -> 4 -> 2 -> 1...)

Às vezes, o código é a melhor maneira de explicar, então aqui estão alguns da 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, mas estou adicionando um desafio extra. O programa não deve ser vulnerável a estouro de pilha . Portanto, ele deve usar iteração ou recursão de cauda.

Além disso, pontos de bônus se ele pode calcular grandes números e a linguagem ainda não o implementou. (ou se você reimplementar o suporte a grandes números usando inteiros de comprimento fixo)

Caso de teste

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

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

Além disso, o código de golfe deve incluir entrada e saída completas do usuário.

Earlz
fonte
20
não deve ser vulnerável a estouro de pilha : você não deveria ter postado aqui então! ;)
Felix Kling
51
Meus amigos pararam de me ligar, isso significa que resolvi o problema?
Martin
18
Você está no SO, mas já teve amigos? ... como foi isso?
Aparece
5
A resposta do montador é legal, mas é um pouco anticódigo selecionar a resposta mais longa !
John La Rooy

Respostas:

129

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
Martin
fonte
27
x86 asm e 1337 chars. Eu choro de alegria.
ZoogieZork
10
Eu gosto do (ab) uso de lea para 3n + 1.
wowest
Obrigado por não usar int 23h.
Mike D.
como faço para complie no linux mal posso esperar para experimentá-lo
hidroto
64

Befunge

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+
Josh Lee
fonte
2
Você deve ler isso em 2D. <> ^ v são setas que mudam a direção do "contador de programa". | e _ são condicionais que vão para cima / baixo ou esquerda / direita dependendo se o valor na pilha é verdadeiro ou falso. Toda a "arena do código" envolve a parte superior-inferior e a esquerda-direita.
SF.
E apenas 35 caracteres incluindo espaços em branco! Nada mal mesmo!
Potatoswatter
6
Tem certeza que não é 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

TESTADO UNDR JUSTIN J. MEZA'S INTERPRETR . KTHXBYE!

lunohodov
fonte
51

Python - 95 64 51 46 char

Obviamente, não produz um estouro de pilha.

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
makapuf
fonte
4
Você pode querer especificar Python 2.x. IIRC, Python 3.x inputnão faz um eval.
Mike D.
5
Isso não cumpre os requisitos - não imprime o primeiro número
Ben Lings
7
por que isso é aceito? não é o mais curto e não imprime o primeiro número
Claudiu
1
Eu acho que input () ecoa os caracteres que você digita, então isso imprime o primeiro número :)
Danko Durbić
17
Você pode imprimir o primeiro número por um custo de apenas 2 bytes usandon=input()*2
John La Rooy
23

Perl

Decidi ser um pouco anticompetitivo e mostrar como você normalmente codificaria esse problema em Perl.
Há também uma entrada de código de golfe de 46 (total) char no final.

Todos esses três primeiros exemplos começam com este cabeçalho.

#! /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( $_ );
}
  • Versão recursiva simples

    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 );
        }
      }
    }
    
  • Versão iterativa simples

    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;
      }
    }
    
  • Versão iterativa otimizada

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

Agora vou mostrar como você faria esse último exemplo com uma versão do Perl anterior à 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];
  }
}

Benchmark

Em primeiro lugar, o IO sempre será a parte lenta. Portanto, se você realmente os comparou como estão, deverá obter aproximadamente a mesma velocidade de cada um.

Para testá-los, abri um identificador de arquivo para /dev/null( $null) e editei todos say $npara, em vez disso, ler say {$null} $n. Isso é para reduzir a dependência 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;
  ...
}

Depois de executá-lo 10 vezes, aqui está uma saída de amostra representativa:

            Taxa recursiva iterativa otimizada
Recursivo 1715 / s - -27% -46%
Iterativo 2336 / s 36% - -27%
3187 / s otimizado 86% 36% -

Finalmente, uma entrada real de código de golfe:

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

46 caracteres no total

Se você não precisa imprimir o valor inicial, pode remover mais 5 caracteres.

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

41 chars totalizam
31 chars para a parte do código real, mas o código não funcionará sem o -nswitch. Portanto, incluo o exemplo completo em minha contagem.

Brad Gilbert
fonte
Sua versão otimizada, não é.
Motti
@Motti Esses exemplos são muito dependentes de IO. Depois de testá-los várias vezes, a versão otimizada sempre mantém uma liderança significativa.
Brad Gilbert,
@Brad, quando você executa Collatz em um número, a otimização é uma pessimização, pois nenhum número deve aparecer mais de uma vez (a menos que a conjectura esteja errada). A razão pela qual você está vendo uma melhoria é que você está executando muitos números (como no problema de Euler). Na verdade, eu escrevi uma postagem no blog sobre isso recentemente lanzkron.wordpress.com/2010/01/18/…
Motti
2
@Motti é dessa otimização que eu estava falando. Além disso, em Perl $i + 1sempre adição (resposta à entrada do blog). Usar Sub::Call::Recurtambém é uma otimização. Caso contrário, eu usaria @_=$n;goto &Collatz. (É 10-20% mais lento se você mudar state @nextparamy @next
Brad Gilbert,
3
Acredito que os padrões de contagem de tacadas de golfe perl não contam as tacadas obrigatórias para invocar o intérprete nem as aspas, mas contam uma para cada bandeira ao lado de E. Usando essas regras, suas últimas entradas contam respectivamente 37 caracteres e 32 caracteres.
R. Martinho Fernandes
23

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

A entrada do usuário, a saída impressa, usa memória e pilha constantes, funciona com números inteiros arbitrariamente grandes.

Um exemplo de execução deste código, dado um número de 80 dígitos de todos os '1s (!) Como entrada, é muito divertido de olhar.


Versão original, somente função:

Haskell 51 chars

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

Quem o @ & ^ # precisa de condicionais, afinal?

(editar: eu estava sendo "inteligente" e usei o conserto. Sem ele, o código caiu para 54 caracteres. edit2: caiu para 51 por fatoração f())

MtnViewMark
fonte
Depois de fazer minha postagem de Miranda (que é basicamente apenas o Haskell mais antigo), pelo menos em Miranda você pode cortar isso usando apenas um ponto de exclamação cada - fn = n: [[], [f (n div 2), f (3 * n + 1)]! (n mod 2)]! (1 mod n) - Funciona :)
Derek H
Oh, sim, está faltando entrada e saída.
R. Martinho Fernandes
@Martinho: Eu também, mas graças à avaliação preguiçosa, as tabelas estão ainda mais bacanas do que em outras línguas.
Dario
1
Usando a ideia de jleedev: c 1=[1];c n=n:(c$div(nmod 2*(5*n+2)+n)2)- 41 caracteres, usa o fato de que este é k * (3n + 1) + (1-k) * n / 2 onde k = n mod 2
sdcvvc
2
Excluí minha outra entrada, movi meu código aqui e incorporei ainda mais ideias desses comentários. Aumentado para 76 caracteres, mas oferece entrada e saída.
MtnViewMark
22

Golfscript: 20 caracteres

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

Isso é 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
fonte
2
"deve incluir entrada e saída completas do usuário"
F'x
2
@FX, a substituição de 21por ~fará com que o programa use um número de stdin
John La Rooy
@gnibbler: Golfscript.rb foi atualizado? Eu consegui (eval):1:in inicializar ': método indefinido leftparen' for nil:NilClass (NoMethodError)ao substituir 21por ~.
kennytm
@KennyTM, Infelizmente, GolfScript não consegue ler stdin interativamente, você tem que canalizar algo em stdin, comoecho 21 | ruby golfscript.rb collatz.gs
John La Rooy,
19

bc 41 chars

Acho que bcfoi inventado para esse tipo de problema :

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

Teste:

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

Código adequado:

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

bclida com números com até INT_MAXdígitos

Edit: O artigo da Wikipedia menciona que esta conjectura foi verificada para todos os valores até 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

testa 2 20.000 +1 (aprox. 3,98e 6.020 ) em 68 segundos, 144.404 ciclos.

Carlos Gutiérrez
fonte
Altere 'n! = 1' para 'n> 1' para 54 caracteres.
Jerry Coffin,
4
Aqui está uma linha de comando para gerar números aleatórios de comprimento arbitrário para esta entrada (10.000 dígitos neste caso): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc
indiv
3
@indiv - Eu tive que testar :), levou 3 minutos e 12 segundos para processar o número de 10.000 dígitos. Salvei a saída em um arquivo, tem cerca de 1,2 gb de comprimento, mas sim terminou corretamente em 1. Ponto parabc
Carlos Gutiérrez
16

Perl: 31 caracteres

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

Editado para remover 2 espaços desnecessários.

Editado para remover 1 espaço desnecessário.

a'r
fonte
Você pode remover dois espaços desnecessários (depois de dizer e depois de algum tempo)
sorpigal
Tente perl -E 'dizer $ _ = 10; diga $ _ = $ _% 2? $ _ * 3 + 1: $ _ / 2 enquanto $ _> 1'
sorpigal
Achei que o usuário estaria ciente do número inicial da sequência ;-).
2010
41
Às vezes, quando encontro texto codificado em base64, às vezes confundo com o código-fonte Perl.
Martin
21
@Martin: Não consigo imaginar como você faria isso. Base64 é muito mais legível.
Jerry Coffin
15

MS Excel, 35 caracteres

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

Retirado direto da 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

Bastou copiar / colar a fórmula 111 vezes para obter o resultado de um número inicial de 1000.;)

Lance McNearney
fonte
16
Acho que é tarde demais para eu apontar que é para isso que serve a alça de preenchimento, hein? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :)
Jordan Running
Esse é um recurso muito útil que eu nem sabia que existia. Acabei de copiar a primeira célula e, em seguida, destaque todas as outras células e colei uma vez.
Lance McNearney
Aprendi sobre pasta de área aproximadamente dez anos depois de descobrir a alça de preenchimento. figuras.
Jimmy,
14

C: 64 caracteres

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

Com suporte a grande número inteiro: 431 caracteres (necessários)

#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 : Não remova #include <stdlib.h>sem pelo menos prototipar malloc / realloc, pois isso não será seguro em plataformas de 64 bits (void * de 64 bits será convertido para int de 32 bits).

Este ainda não foi testado vigorosamente. Ele poderia usar um pouco de encurtamento também.


Versões prévias:

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

(removeu 12 caracteres porque ninguém segue o formato de saída ...: |)

KennyTM
fonte
12

Outra versão do montador. Este não está limitado a números de 32 bits, ele pode lidar com números de até 10 65534 embora o formato ".com" que o MS-DOS usa esteja limitado a números de 80 dígitos. Escrito para o assembler A86 e requer uma caixa Win-XP DOS para funcionar. Monta até 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
fonte
10

dc - 24 caracteres 25 28

dc é uma boa ferramenta para esta sequência:

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

Também 24 caracteres usando a fórmula da entrada Golfscript :

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

57 caracteres para atender às especificações:

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

Esquema: 72

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

Isso usa recursão, mas as chamadas são recursivas no final, então acho que serão otimizadas para iteração. Em alguns testes rápidos, não consegui encontrar um número para o qual a pilha estourou de qualquer maneira. Por exemplo:

(C 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)

... funciona muito bem. [isso é tudo um número - eu apenas quebrei para caber na tela.]

Jerry Coffin
fonte
8

Mathematica, 45 50 chars

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
Pillsy
fonte
Contei 58 caracteres. E você pode substituir OddQ[#]por OddQ@#para economizar 1 caractere.
kennytm
2
50 caracteres:c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&]
Michael Pilat
7

Ruby, 50 caracteres, sem estouro de pilha

Basicamente, uma cópia direta da solução Python de makapuf :

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

Ruby, 45 caracteres, irá transbordar

Basicamente, uma cópia direta do código fornecido na pergunta:

def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end
Jordan Running
fonte
Que versão de Ruby é essa? Eu n.odd??não fico definido. Além disso, é vulnerável a estouros de pilha com grandes números.
Earlz
Isso é interessante. Eu tenho 1.8.7. Adicionar um espaço entre os pontos de interrogação deve corrigir isso. E você está certo sobre o estouro da pilha. Vou editar minha resposta para tomar nota disso.
Jordan Running
3
Você pode salvar quatro personagens comp 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
fonte
50
Java: a linguagem onde você deve usar BigIntegers apenas para contar o número de caracteres no código da solução.
Jared Updike,
3
@Jared Concordo totalmente que Java é prolixo. Você tem que admitir que a solução apresentada a) atende aos requisitos b) é muito mais longa do que o realmente necessário ec) brinca com o sistema tipo java de uma forma agradável
wowest
7

Python 45 Char

Raspou um carvão da resposta de Makapuf.

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n
GuillaumeDufay
fonte
uso muito inteligente do operador ~. Tive que pesquisar para ver o que acontecia (tento evitar operadores binários em Python, então não estou muito familiarizado com eles).
Ponkadoodle
5

TI-BASIC

Não o mais curto, mas uma abordagem inovadora. Certamente desacelerará consideravelmente com grandes sequências, mas não deve transbordar.

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

Haskell: 50

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

não a mais curta, mas uma solução elegante de clojure

(defn collatz [n]
 (print n "")
 (if (> n 1)
  (recur
   (if (odd? n)
    (inc (* 3 n))
    (/ n 2)))))
cobbal
fonte
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);}}}

em formato longo:

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

Nova versão, aceita um número como entrada fornecida através da linha de comando, sem validação 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);}}}

em formato longo:

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

Eu sou capaz de raspar alguns caracteres retirando a ideia nesta resposta de usar um loop for em vez de um tempo. 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
fonte
Você deve mencionar que seu código aceita mais de uma entrada. Ou tire isso e raspe alguns resíduos.
R. Martinho Fernandes
Você poderia encurtar Action <object> e possivelmente mais para dinâmico em C # 4.
Dykam,
@Dykam: Apenas verifiquei: falha com "erro CS0428: Não é possível converter o grupo de métodos 'Gravar' para o tipo não delegado 'dinâmico'. Você pretendia invocar o método?".
R. Martinho Fernandes
Oh, claro ... conversão implícita em delegados ... requer denotar o delegado. Que
chatice
4

Ruby, 43 caracteres

bignum suportado, com susceptibilidade de estouro de pilha:

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

... e 50 caracteres, bignum suportado, sem estouro de pilha:

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

Parabéns a Jordan. Eu não sabia sobre 'p' como um substituto para opções de venda.

Sniggerfardimungus
fonte
4

nroff 1

Correr com 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. versão groff

DigitalRoss
fonte
2
Assustador! Ainda assim, pelo menos a saída deve ser bem formatada.
Jonathan Leffler,
3
Ei, execute-o como groff -U hail.ge você obterá 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

E em ação:

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

Isso também inclui o 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)

Com o seguinte implícito

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

isso pode ser encurtado para

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

Editar - 58 caracteres (incluindo entrada e saída, mas não incluindo o número inicial)

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

Pode ser reduzido em 2 se você não precisar de novas linhas ...

Ben Lings
fonte
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; ...]

Ou, se você não estiver usando F # interativo para exibir o 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
fonte
3

Lisp comum, 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~%"))

Execução de teste:

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
fonte
Quase. Não há cabeçalho para a 2ª linha. Eu poderia ter raspado 3 caracteres ignorando a seta, outros 3-4 eliminando espaços desnecessários, mas estou feliz com um múltiplo de 3.
Vatine
3

O programa de Jerry Coffin tem overflow de inteiros, experimente 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";
}

testado com

O número inferior a 100 milhões com o tempo total de parada mais longo é 63.728.127, com 949 passos.

O número menor que 1 bilhão com o tempo total de parada mais longo é 670.617.279, com 986 etapas.

Soumen Sarkar
fonte
Qualquer tipo de número inteiro finito não pode impedir o estouro de número inteiro. Nem mesmo unsigned long long.
kennytm,
3

ruby, 43, possivelmente atendendo ao requisito de E / S


Correr com ruby -n hail

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

C #: 659 caracteres com suporte 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);
        }
    }
}
Cameron MacFarland
fonte