La secuencia de Collatz a partir de un entero positivo n se define de esta manera:
- si n es par, divídalo por 2 (
n' = n / 2
) - si n es impar, multiplíquelo por 3 y agregue 1 (
n' = 3n + 1
)
Repita la iteración anterior hasta que n alcance 1.
No se sabe (es un problema importante no resuelto en teoría de números) si la secuencia finalmente alcanzará el número 1, independientemente de qué número entero positivo se elija inicialmente.
Una máquina de dos contadores (2CM) es una máquina equipada con dos registros que pueden contener un valor entero no negativo y pueden programarse con el siguiente conjunto de instrucciones:
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
Un programa de 2CM es simplemente una secuencia de instrucciones, por ejemplo, el siguiente programa simplemente copia el contenido del registro X para registrar Y:
cp: DJZX end
INCY
JMP cp
end: HALT
Tenga en cuenta que un 2CM es Turing completo (es decir, puede calcular todas las funciones computables con una codificación de entrada adecuada, pero aquí es irrelevante). También tenga en cuenta que el conjunto de instrucciones es un poco diferente al del artículo de Wikipedia.
El reto
Escriba el programa 2CM más corto, que calcule e imprima la secuencia de collatz hasta 1 y se detenga (el registro X inicialmente contiene el valor inicial n
y el registro Y inicialmente contiene 0). Tenga en cuenta que la longitud de un programa de 2CM es la cantidad de instrucciones utilizadas (no la longitud del texto).
Por ejemplo, cuando se inicia desde X = 3, debe imprimir: 3 10 5 16 8 4 2 1
y HALT.
Por lo tanto, puede usar su idioma favorito para construir un simulador / intérprete de 2CM, pero el código final (más corto) que ingrese en la respuesta debe estar en el idioma de 2CM .
fuente
Respuestas:
18 instrucciones
Estaba un poco decepcionado de haber llegado tarde a la escena, ya que la naturaleza minimalista del problema y el lenguaje hacen que (aparentemente) solo haya un enfoque general para una buena respuesta. Recibí una respuesta de 19 instrucciones con bastante rapidez, pero no sentí que trajera lo suficiente a la mesa como para publicarla. Pero después de mucho rascarme la cabeza, mi experiencia de ensamblaje hacky z80 llegó y encontré una manera de guardar una instrucción reutilizando un bloque de código para un propósito para el que no estaba destinado.
fuente
PUNTUACIÓN: 21
Aquí está mi intento:
main
: imprimeX
y salta afinish
(siX==1
).divisibility
: hace una distinción siX%2==0
oX%2==1
. También copiaX
aY
y haceX==0
. Salta aisDivisible
(ifX%2==0
) oisNotDivisible
(ifX%2==1
).isDivisible
: bucle utilizado cuandoY%2==0
. Por cada disminución deY
2, aumentaX
en 1. CuandoY==0
, salta amain
.isNotDivisible
: utilizado cuandoY%2==1
. AumentaX
en 1.notDivLoop
: bucle utilizado cuandoY%2==1
. Por cada disminución deY
1, aumentaX
en 3. CuandoY==0
, salta amain
.finish
: se detieneSuministrado con 3 (utilizando el intérprete proporcionado por @orlp), el resultado producido es:
fuente
19 instrucciones
Escribí mi propio intérprete porque soy elegante así. Aquí está mi solución para mi propio intérprete:
Y así es como se ve con una sintaxis compatible con el otro intérprete:
fuente
19 instrucciones
Puedes ejecutarlo con mi intérprete .
fuente