A sequência Collatz iniciando com um número inteiro positivo n é definida desta maneira:

• se n for par, então divida-o por 2 ( n' = n / 2)
• se n for ímpar, multiplique-o por 3 e adicione 1 ( n' = 3n + 1)

Repita a iteração acima até n atingir 1.

Não se sabe (é um grande problema não resolvido na teoria dos números) se a sequência eventualmente alcançará o número 1, independentemente do número inteiro positivo escolhido inicialmente.

Uma máquina de dois contadores (2CM) é uma máquina equipada com dois registradores que podem conter um valor inteiro não negativo e podem ser programados com o seguinte conjunto de instruções:

INCX    increase the value of register X
INCY    increase the value of register Y
JMP n   jump to instruction n
DJZX n  if register X is zero jump to instruction n,
        otherwise decrement its value
DJZY n  if register Y is zero jump to instruction n,
        otherwise decrement its value
HALT    halt (and accept)
PRINTX  print the content of register X

Um programa de 2cm é simplesmente uma sequência de instruções, por exemplo, o programa a seguir copia o conteúdo do registro X para registrar Y:

cp:   DJZX end
      INCY
      JMP cp
end:  HALT

Observe que um 2CM é Turing Complete (ou seja, pode calcular todas as funções computáveis ​​com uma codificação de entrada adequada, mas é irrelevante aqui). Observe também que o conjunto de instruções é um pouco diferente daquele no artigo da Wikipedia.

O desafio

Escreva o programa mais curto de 2CM, que calcula e imprime a sequência de collatz até 1 e pára (o registro X inicialmente contém o valor inicial ne o registro Y inicialmente contém 0). Observe que o comprimento de um programa de 2cm é o número de instruções usadas (não o comprimento do texto).

Por exemplo, quando iniciado a partir de X = 3, ele deve imprimir: 3 10 5 16 8 4 2 1e HALT.

Portanto, você pode usar seu idioma favorito para criar um simulador / intérprete de 2CM, mas o código final (mais curto) que você colocou na resposta deve estar no idioma de 2CM .

18 instruções

Fiquei um pouco desapontado por ter chegado tarde à cena, pois a natureza minimalista do problema e a linguagem fazem ali (aparentemente) apenas uma abordagem geral para uma boa resposta. Eu recebi uma resposta de 19 instruções rapidamente, mas não achei que fosse suficiente para postá-la na mesa. Mas, depois de muito esforço, minha experiência em montagem do z80 hacky veio à tona e eu encontrei uma maneira de salvar uma instrução reutilizando um bloco de código para um propósito a que não se destinava!

# Let N be the previous number in the Collatz sequence.

# Print N, and if N==1, halt.
# X=N, Y=0
Main:           PRINTX          # Print N.
                DJZX Done       # X=N-1 (N shouldn't be zero, so this never jumps)
                DJZX Done       # If N-1==0, halt. Otherwise, X=N-2.

# Find the parity of N and jump to the proper code to generate the next N.
# X=N-2, Y=0
FindParity:     INCY
                DJZX EvenNext   # If N%2==0, go to EvenNext with X=0, Y=N-1.
                INCY
                DJZX OddNext    # If N%2==1, go to OddNext with X=0, Y=N-1.
                JMP FindParity

# Find the next N, given that the previous N is even.
# X=0, Y=N-1
EvenNext:       INCX
                DJZY Main       # Y=Y-1 (Y should be odd, so this never jumps)
                DJZY Main       # If Y==0, go to Main with X=(Y+1)/2=N/2, Y=0.
                JMP EvenNext

# Find the next N, given that the previous N is odd.
# X=0, Y=N-1
OddNext:        INCX
                INCX
                INCX
                DJZY EvenNext   # If Y==0, go to EvenNext with X=(Y+1)*3=N*3, Y=0.
                JMP OddNext     # ^ Abuses EvenNext to do the final INCX so X=N*3+1.

# Halt.
Done:           HALT

PONTUAÇÃO: 21

Aqui está a minha tentativa:

main: imprime Xe pula para finish(se X==1).

divisibility: faz uma distinção se X%2==0ou X%2==1. Também copia Xa Ye faz X==0. Salta para isDivisible(se X%2==0) ou isNotDivisible(se X%2==1).

isDivisible: loop usado quando Y%2==0. Para cada diminuição de Y2, aumenta Xem 1. Quando Y==0, salta para main.

isNotDivisible: usado quando Y%2==1. Aumenta Xem 1.

notDivLoop: loop usado quando Y%2==1. Para cada diminuição de Y1, aumenta Xem 3. Quando Y==0, pula para main.

finish: pára

main:           PRINTX              # print X
                DJZX main           # here X is always >0 and jump never fires (it is just for decreasing)
                DJZX finish         # if initially X==1 this jumps to finish
                INCX                # establish the previous state of X
                INCX
                                    # continue with X>1

divisibility:   DJZX isDivisible    # if X%2==0, then this will fire (when jumping Y=X)
                INCY
                DJZX isNotDivisible # if X%2==1, this fires (when jumping Y=X)
                INCY
                JMP divisibility    # jump to the beginning of loop

isDivisible:    DJZY main           # this jumps to the main loop with X=X/2
                DJZY main           # this jump will never fire, because X%2==0
                INCX                # for every partition 2 of Y, increase X (making X=Y/2)
                JMP isDivisible     # jump to beginning of loop

isNotDivisible: INCX                # X=0, increase for 1
notDivLoop:     DJZY main           # in each iteration, increase X for 3 (when Y==0, X=3Y+1)
                INCX
                INCX
                INCX
                JMP notDivLoop      # jump to beginning of loop

finish:         HALT                # finally halt

Fornecido com 3 (usando o intérprete fornecido pelo @orlp), o resultado produzido é:

3
10 
5 
16 
8
4
2
1

19 instruções

Escrevi meu próprio intérprete porque sou assim. Aqui está minha solução para meu próprio intérprete:

MP
 XE
 XE
HY
 XV
 XO
 JH
WX
VYM
 JW
LYM
 X
 X
OX
 X
 X
 X
 JL
EH

E aqui está o que parece com sintaxe compatível com o outro intérprete:

# x = n, y = 0
main:    printx
         djzx   end
         djzx   end

# x = n - 2, y = 0 on fallthrough
half:    incy
         djzx   even
         djzx   odd
         jmp    half

evloop:  incx
# x = 0, y = n / 2  on jump to even
even:    djzy   main
         jmp    evloop

oddloop: djzy   main
         incx
         incx
# x = 0, y = (n + 1) / 2 on jump to even
odd:     incx
         incx
         incx
         incx
         jmp    oddloop

end:     halt

19 instruções

found:    PRINTX       # print input/found number
          DJZX done    # check if n == 1
          DJZX done    # after this point x == n - 2
parity:   INCY         # after this loop y == n // 2
          DJZX even
          DJZX odd
          JMP parity
odd-loop: DJZY found
          INCX
          INCX
odd:      INCX         # we enter mid-way to compute x = 6y + 4 = 3n + 1
          INCX
          INCX
          INCX
          JMP odd-loop
even:     DJZY found   # simply set x = y
          INCX
          JMP even
done:     HALT

Você pode executá-lo usando meu intérprete .