Le dan una máquina con dos registros de 16 bits, xy y. Los registros se inicializan x=1y y=0. La única operación que puede hacer la máquina es el módulo de adición 65536. Es decir:

• x+=y- xse sustituye por (x + y) mod 65536; yno ha cambiado
• y+=x - de manera similar para y
• x+=x- xse sustituye por 2x mod 65536; legal solo si xes par
• y+=y - de manera similar para y

El objetivo es obtener un número predeterminado en uno de los registros (ya sea xo y).

Escriba un programa o una subrutina que reciba un número (en stdin, argvparámetro de función, parte superior de la pila o cualquier otro lugar convencional) y genere un programa para obtener este número. La salida debe ir a stdout, o (si su idioma no tiene stdout) a cualquier otro dispositivo de salida convencional.

El programa de salida puede estar hasta el 100% más 2 pasos lejos de ser óptimo. Es decir, si el programa más corto para obtener el número objetivo tiene npasos, su solución no puede ser más larga que 2n+2. Esta restricción es para evitar soluciones "demasiado fáciles" (por ejemplo, contar 1, 2, 3, ...) pero no requiere una optimización completa; Espero que el programa más corto sea más fácil de encontrar, pero no puedo estar seguro ...

Por ejemplo: Entrada = 25. Salida:

y+=x
x+=y
x+=y
x+=x
x+=x
x+=x
y+=x

Otro ejemplo: para cualquier número de Fibonacci, la salida tiene este patrón alterno. Para Entrada = 21, la salida es

y+=x
x+=y
y+=x
x+=y
y+=x
x+=y
y+=x

El código más corto (medido en bytes) gana.

(este rompecabezas se inspiró en un código para un procesador de 16 bits que tuve que generar recientemente)

PD: ¿para qué número es el programa óptimo más largo?

CJam, 31

Al igual que la respuesta de @Tobia , mi algoritmo también es robado descaradamente inspirado por la respuesta de @CChak . Pero, empuñando la magia negra que es CJam, logré hacer una implementación aún más pequeña del algoritmo.

Pruébalo aquí.

Golfizado:

qi{_4%!:X)/X!-'xX+"
y+="@}h;]W%`

Sin golf:

qi          "Read input and convert to integer.";
{           "Do...";
  _4%!:X    "Assign (value mod 4 == 0) to X.";
  )/X!-     "If X, divide value by 2. If not X, decrement value.";
  'xX+      "If X, put 'y' on the stack. If not X, put 'x' on the stack.";
  "
y+="        "Put '\ny+=' on the stack.";
  @         "Rotate top 3 elements of stack left so the value is on top.";
}h          "... while value is not zero.";
;           "Discard zero value on stack.";
]W%         "Collect stack into array and reverse.";

Corríjame si me equivoco, pero creí que la operación del módulo 65536 utilizada en respuestas con un algoritmo similar es innecesaria. Interpreté la pregunta de tal manera que podemos suponer que la entrada será un número entero de 16 bits sin signo válido, y cualquier valor intermedio o resultado de este algoritmo también lo será.

Perl 107 97

Primer post, así que aquí va.

sub h{($i)=@_;return if(($i%=65536)==0);($i%4==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

Que se ajusta a todos los criterios de adición de registros, pero no ejecuté una verificación exhaustiva para ver si mi respuesta siempre estuvo dentro de 2n + 2 del número óptimo de pasos. Sin embargo, está dentro del límite para cada número de Fibonacci.

Aquí hay un desglose más detallado

sub h{                           # Declare the subroutine, it should be called referencing an integer value
   ($i)=@_;                      # Assign the i variable to the integer used in the call
   return if(($i%=65536)==0);    # Check for base condition of called by 0, and enforce modulo from the start.
   ($i%4==0) ?                   # If the value passed is even, and will result in an even number if we halve it
   do{h($i/2);say"y+=y";}        # Then do so and recurse 
   :do{h($i-1);say"y+=x";}       # Otherwise "subtract one" and recurse
}                                # Note that the print statements get called in reverse order as we exit.

Como mencioné, este es mi primer intento de jugar al golf, así que estoy seguro de que esto se puede mejorar. Además, no estoy seguro de si la llamada de subrutina inicial debe contarse en una llamada recursiva o no, lo que podría hacernos subir algunos caracteres.

Curiosamente, podemos reducir el código en 11 bytes * y mejorar nuestra "eficiencia" en términos del número de operaciones de registro, relajando el requisito de que solo los valores pares pueden "duplicarse". Lo he incluido por diversión aquí:

sub h{($i)=@_;return if(($i%=65536)==0);($i%2==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}

Comience el apéndice:

Realmente me gustó este problema, y ​​he estado jugando con él de vez en cuando durante las últimas dos semanas. Pensé que publicaría mis resultados.

Algunos numeros:

Usando un algoritmo BFS para encontrar una solución óptima, en los primeros 2 ^ 16 números solo hay 18 números que requieren 23 pasos. Ellos son: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

Usando el algoritmo recursivo descrito anteriormente, el número "más difícil" de alcanzar es 65535, en 45 operaciones. (65534 toma 44, y hay 14 números que toman 43 pasos) 65535 es también la mayor desviación de óptimo, 45 vs 22. La diferencia de 23 pasos es 2n + 1. (Solo tres números llegan a 2n: 65534, 32767, 32751.) Exceptuando los casos triviales (paso cero), en el rango definido, el método recursivo promedia aproximadamente 1.4 veces la solución óptima.

En pocas palabras: para los números 1-2 ^ 16, el algoritmo recursivo nunca cruza el umbral definido de 2n + 2, por lo que la respuesta es válida. Sin embargo, sospecho que comenzaría a alejarse demasiado de la solución óptima para registros más grandes / más bits.

El código que utilicé para crear el BFS era descuidado, requiere mucha memoria, no estaba comentado y, deliberadamente, no estaba incluido. Entonces ... no tienes que confiar en mis resultados, pero estoy bastante seguro de ellos.

Python 3, 202 bytes

def S(n):
 q=[(1,0,"")];k=65536
 while q:
  x,y,z=q.pop(0)
  if n in{x,y}:print(z);return
  q+=[((x+y)%k,y,z+"x+=y\n"),(x,(x+y)%k,z+"y+=x\n")]+[(2*x%k,y,z+"x+=x\n")]*(~x&1)+[(x,2*y%k,z+"y+=y\n")]*(~y&1)

(Gracias a @rationalis por unos pocos bytes)

Aquí hay una solución extremadamente básica. Desearía poder jugar mejor la última línea, pero actualmente no tengo ideas. Llamada con S(25).

El programa solo realiza un BFS simple sin almacenamiento en caché, por lo que es muy lento. Aquí está S(97), para algunos resultados de muestra:

y+=x
x+=y
x+=x
x+=x
x+=x
x+=x
y+=x
y+=x
x+=y

Dyalog APL, 49 caracteres / bytes *

{0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1}

Algoritmo descaradamente inspirado por la respuesta de @CChak .

Ejemplo:

    {0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1} 25
y+=x
y+=x
y+=y
y+=x
y+=x
y+=y
y+=y
y+=x

Sin golf:

{
    N←(2*16)|⍵                 # assign the argument modulo 65536 to N
    0=N: ⍬                     # if N = 0, return an empty value (that's a Zilde, not a 0)
    0=4|N: ⎕←'y+=y' ⊣ ∇N÷2     # if N mod 4 = 0, recurse with N÷2 and *then* print 'y+=y'
    ⎕←'y+=x' ⊣ ∇N-1            # otherwise, recurse with N-1 and *then* print 'y+=x'
}

_{* Dyalog APL admite un conjunto de caracteres heredado que tiene los símbolos APL asignados a los valores superiores de 128 bytes. Por lo tanto, un programa APL que solo usa caracteres ASCII y símbolos APL puede considerarse bytes == caracteres.}

Pitón, 183

def S(n):
 b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
 if n<2:return
 while~n&1:n>>=1;a+=1
 while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
 while a:s+=[c,c*b+e*2][i];i=0;a-=1
 print(s)

No puedo garantizar que este se mantenga dentro del doble del programa óptimo para números pares, pero es eficiente. Para todas las entradas válidas 0 <= n < 65536, es esencialmente instantáneo y genera un programa de como máximo 33 instrucciones. Para un tamaño de registro arbitrario n(después de corregir esa constante), tomaría O(n)tiempo con, como máximo2n+1 instrucciones.

Alguna lógica binaria

Cualquier número impar nse puede llegar en 31 pasos: hacer y+=x, conseguir x,y = 1,1, y luego seguir doblando xcon x+=x(por primera duplicación hacerlo x+=y, ya que xes extraño para empezar). xalcanzará cada potencia de 2 de esta manera (es solo un desplazamiento a la izquierda), por lo que puede configurar cualquier bit de y1 agregando la potencia correspondiente de 2. Dado que estamos utilizando registros de 16 bits, y cada bit excepto para la primera toma una duplicación para alcanzar y una y+=xpara establecer, obtenemos un máximo de 31 operaciones.

Cualquier número par nes solo una potencia de 2, llámelo a, multiplicado por un número impar, llámelo m; es decir n = 2^a * m, o equivalentemente n = m << a. Use el proceso anterior para obtener m, luego reinicie xdesplazándolo hacia la izquierda hasta que sea 0. Haga un x+=yajuste x = my luego continúe duplicando x, la primera vez usando x+=yy luego usandox+=x .

Sea lo que asea, se necesitan 16-aturnos xpara obtener y=my un aturno adicional para restablecer x=0. Otros acambios de xocurrirán después x=m. Entonces 16+ase usa un total de turnos. Hay hasta 16-abits que deben configurarse para obtener m, y cada uno de ellos tomará uno y+=x. Finalmente, necesitamos un paso adicional x=0para establecerlo en m x+=y,. Por lo tanto, se necesitan como máximo 33 pasos para obtener cualquier número par.

Puede, por supuesto, generalizar esto a cualquier tamaño de registro, en cuyo caso siempre toma como máximo 2n-1y 2n+1opta por nenteros pares e impares , respectivamente.

Óptima

Este algoritmo produce un programa que es casi óptimo (es decir, dentro de 2n+2si nes el número mínimo de pasos) para números impares. Para un número impar dado n, si el mbit th es el primer 1, entonces cualquier programa toma al menos mpasos para llegar a x=no y=n, ya que la operación que aumenta los valores de los registros más rápido es x+=xo y+=y(es decir, duplicaciones) y se necesitan mduplicaciones para llegar a el mth bit de 1. Dado que este algoritmo toma la mayoría de los 2mpasos (a lo sumo dos por duplicación, uno para el turno y uno y+=x), cualquier número impar se representa casi de manera óptima.

Los números pares no son tan buenos, ya que siempre usa 16 operaciones para restablecer xantes que nada, y 8, por ejemplo, se puede alcanzar en 5 pasos.

Curiosamente, el algoritmo anterior nunca usa y+=yen absoluto, ya quey que siempre se mantiene extraño. En ese caso, puede encontrar el programa más corto para el conjunto restringido de solo 3 operaciones.

Pruebas

# Do an exhaustive breadth-first search to find the shortest program for
# each valid input
def bfs():
    d = {(0,1):0}
    k = 0xFFFF
    s = set(range(k+1))
    current = [(0,1)]
    nexts = []
    def add(pt, dist, n):
        if pt in d: return
        d[pt] = dist
        s.difference_update(pt)
        n.append(pt)
    i = 0
    while len(s) > 0:
        i += 1
        for p in current:
            x,y = p
            add((x,x+y&k), i, nexts)
            add((y,x+y&k), i, nexts)
            if y%2 == 0: add(tuple(sorted((x,y+y&k))), i, nexts)
            if x%2 == 0: add(tuple(sorted((x+x&k,y))), i, nexts)
        current = nexts
        nexts = []
        print(len(d),len(s))

# Mine (@rationalis)
def S(n):
    b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
    if n<2:return ''
    while~n&1:n>>=1;a+=1
    while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
    while a:s+=[c,c*b+e*2][i];i=0;a-=1
    return s

# @CChak's approach
def U(i):
    if i<1:return ''
    return U(i//2)+'y+=y\n' if i%4==0 else U(i-1)+'y+=x\n'

# Use mine on odd numbers and @CChak's on even numbers
def V(i):
    return S(i) if i % 2 == 1 else U(i)

# Simulate a program in the hypothetical machine language
def T(s):
    x,y = 1,0
    for l in s.split():
        if l == 'x+=x':
            if x % 2 == 1: return 1,0
            x += x
        elif l == 'y+=y':
            if y % 2 == 1: return 1,0
            y += y
        elif l == 'x+=y': x += y
        elif l == 'y+=x': y += x
        x %= 1<<16
        y %= 1<<16
    return x,y

# Test a solution on all values 0 to 65535 inclusive
# Max op limit only for my own solution
def test(f):
    max_ops = 33 if f==S else 1000
    for i in range(1<<16):
        s = f(i); t = T(s)
        if i not in t or len(s)//5 > max_ops:
            print(s,i,t)
            break

# Compare two solutions
def test2(f,g):
    lf = [len(f(i)) for i in range(2,1<<16)]
    lg = [len(g(i)) for i in range(2,1<<16)]
    l = [lf[i]/lg[i] for i in range(len(lf))]
    print(sum(l)/len(l))
    print(sum(lf)/sum(lg))

# Test by default if script is executed
def main():
    test()

if __name__ == '__main__':
    main()

Escribí una prueba simple para verificar que mi solución realmente produce resultados correctos, y nunca supera los 33 pasos, para todas las entradas válidas ( 0 <= n < 65536).

Además, intenté hacer un análisis empírico para comparar la salida de mi solución con las salidas óptimas; sin embargo, resulta que la búsqueda de amplitud es demasiado ineficiente para obtener la longitud mínima de salida para cada entrada válida n. Por ejemplo, el uso de BFS para buscar la salida n = 65535no termina en un período de tiempo razonable. Sin embargo, me he ido bfs()y estoy abierto a sugerencias.

Sin embargo, probé mi propia solución contra la de @ CChak (implementada en Python aquí como U). Esperaba que al mío le iría peor, ya que es drásticamente ineficiente para números pares más pequeños, pero promediado en todo el rango de dos maneras, la mina produjo una producción de longitud en promedio de 10.8% a 12.3% más corta. Pensé que tal vez esto se debía a una mejor eficiencia de mi propia solución en números impares, así que Vusa el mío en números impares y @ CChak en números pares, pero Vestá en el medio (aproximadamente 10% más corto que U, 3% más largo que S).