Você recebe uma máquina com dois registradores de 16 bits xe y. Os registros são inicializados x=1e y=0. A única operação que a máquina pode fazer é o módulo de adição 65536. Ou seja:

• x+=y- xé substituído por (x + y) mod 65536; yé inalterado
• y+=x - da mesma forma para y
• x+=x- xé substituído por 2x mod 65536; legal apenas se xfor mesmo
• y+=y - da mesma forma para y

O objetivo é obter um número predeterminado em um dos registros (um xou y).

Escreva um programa ou uma sub-rotina que receba um número (em stdin, argvparâmetro de função, parte superior da pilha ou qualquer outro local convencional) e envie um programa para obter esse número. A saída deve ir para stdout(ou se seu idioma não tiver stdout) para qualquer outro dispositivo de saída convencional.

O programa de saída pode ser de até 100% mais 2 etapas longe do ideal. Ou seja, se o programa mais curto para obter o número de destino tiver netapas, sua solução não poderá ser maior que 2n+2. Essa restrição é para evitar soluções "fáceis demais" (por exemplo, contando 1, 2, 3, ...), mas não requer otimização total; Espero que o programa mais curto seja o mais fácil de encontrar, mas não tenho certeza ...

Por exemplo: Entrada = 25. Saída:

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

Outro exemplo: para qualquer número de fibonacci, a saída tem esse padrão alternado. Para Input = 21, a saída é

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

O código mais curto (medido em bytes) vence.

(esse quebra-cabeça foi inspirado em algum código para um processador de 16 bits que tive que gerar recentemente)

PS eu me pergunto - para qual número o programa ideal é mais longo?

CJam, 31

Como a resposta de @Tobia , meu algoritmo também é descaradamente roubado, inspirado na resposta de @CChak . Mas, usando a magia negra que é CJam, consegui fazer uma implementação ainda menor do algoritmo.

Experimente aqui.

Golfe:

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

Ungolfed:

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.";

Corrija-me se estiver errado, mas acreditava que a operação do módulo 65536 usada nas respostas com um algoritmo semelhante é desnecessária. Interpretei a questão de modo que possamos assumir que a entrada será um número inteiro de 16 bits sem sinal válido e quaisquer valores ou resultados intermediários desse algoritmo também serão.

Perl 107 97

Primeiro post, então aqui vai.

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

O que se encaixa em todos os critérios de adição de registro, mas não fiz uma verificação exaustiva para ver se minha resposta estava sempre dentro de 2n + 2 do número ideal de etapas. Está bem dentro do limite para todos os números de Fibonacci.

Aqui está uma análise mais detalhada

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 eu mencionei, esta é minha primeira tentativa de jogar golfe, então tenho certeza de que isso pode ser melhorado. Além disso, não tenho certeza se a chamada de sub-rotina inicial deve ser contada em uma chamada recursiva ou não, o que poderia levar alguns caracteres.

Curiosamente, podemos reduzir o código em 11 bytes * e melhorar nossa "eficiência" em termos de número de operações de registro, relaxando a exigência de que apenas valores pares possam ser "dobrados". Eu incluí isso por diversão aqui:

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

Comece o adendo:

Gostei muito desse problema, e eu tenho brincado com ele de vez em quando nas últimas duas semanas. Pensei em publicar meus resultados.

Alguns números:

Usando um algoritmo BFS para encontrar uma solução ideal, nos primeiros 2 ^ 16 números, existem apenas 18 números que requerem 23 etapas. Eles são: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

Usando o algoritmo recursivo descrito acima, o número "mais difícil" de alcançar é 65535, em 45 operações. (65534 leva 44 e há 14 números que dão 43 etapas) 65535 também é a maior saída do ideal, 45 vs 22. A diferença de 23 etapas é 2n + 1. (Apenas três números atingem 2n: 65534, 32767, 32751.) Exceto nos casos triviais (etapa zero), no intervalo definido, o método recursivo calcula a média de aproximadamente 1,4 vezes a solução ideal.

Conclusão: para os números 1-2 ^ 16, o algoritmo recursivo nunca cruza o limite definido de 2n + 2, portanto a resposta é válida. Suspeito que, no entanto, começaria a se afastar muito da solução ideal para registros maiores / mais bits.

O código que eu usei para criar o BFS era desleixado, com muita memória, não comentado e deliberadamente não incluído. Então ... você não precisa confiar nos meus resultados, mas estou bastante confiante neles.

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)

(Obrigado a @rationalis por alguns bytes)

Aqui está uma solução extremamente básica. Eu gostaria de poder jogar melhor a última linha, mas atualmente estou sem ideias. Ligue com S(25).

O programa apenas executa um BFS simples, sem cache, por isso é muito lento. Aqui está S(97), para alguns exemplos de saída:

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 na resposta de @CChak .

Exemplo:

    {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

Ungolfed:

{
    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'
}

_{* O Dyalog APL suporta um conjunto de caracteres herdado que possui os símbolos da APL mapeados para os valores superiores de 128 bytes. Portanto, um programa APL que usa apenas caracteres ASCII e símbolos APL pode ser considerado como bytes == chars.}

Python, 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)

Não posso garantir que isso fique dentro do dobro do programa ideal para números pares, mas é eficiente. Para todas as entradas válidas 0 <= n < 65536, é essencialmente instantânea e gera um programa com no máximo 33 instruções. Para um tamanho de registro arbitrário n(depois de fixar essa constante), levaria O(n)tempo com, no máximo, 2n+1instruções.

Alguma Lógica Binária

Qualquer número ímpar npode ser alcançado dentro de 31 etapas: do y+=x, obtendo x,y = 1,1e, em seguida, continuando dobrando xcom x+=x(para o primeiro duplicado x+=y, pois xé estranho, para começar). xatingirá todas as potências de 2 dessa maneira (é apenas um deslocamento para a esquerda) e, portanto, você poderá definir y1 como uma adicionando a potência correspondente a 2. Como estamos usando registradores de 16 bits, e cada bit, exceto para a primeira leva uma duplicação para alcançar e outra y+=xpara definir, temos no máximo 31 ops.

Qualquer número par né apenas uma potência de 2, ligue a, vezes um número ímpar, ligue m; ou seja n = 2^a * m, ou equivalente n = m << a. Use o processo acima para obter e m, em seguida, redefina xmovendo-o para a esquerda até chegar a 0. Faça a x+=ypara definir x = me continue dobrando x, na primeira vez, usando x+=ye subseqüentemente x+=x.

Seja o que afor, são necessárias 16-amudanças xpara obter y=me outras aalterações para redefinir x=0. Outras amudanças xocorrerão depois x=m. Portanto, um total de 16+aturnos é usado. Existem até 16-abits que precisam ser configurados para obter m, e cada um deles precisará de um y+=x. Finalmente, precisamos de uma etapa extra x=0para configurá-la como m x+=y,. Portanto, são necessários no máximo 33 etapas para obter qualquer número par.

Você pode, é claro, generalizar isso para qualquer registro de tamanho, caso em que sempre leva no máximo 2n-1e 2n+1ops para números ninteiros ímpares e pares , respectivamente.

Optimalidade

Esse algoritmo produz um programa que é quase ideal (ou seja, 2n+2se né o número mínimo de etapas) para números ímpares. Para um determinado número ímpar n, se o mth bit for o primeiro 1, qualquer programa executa pelo menos metapas para chegar a x=nou y=n, uma vez que a operação que aumenta os valores dos registros mais rapidamente é x+=xou y+=y( ou seja, duplicação) e é necessária mduplicação para obter o mth bit de 1. Como esse algoritmo executa no máximo algumas 2metapas (no máximo duas por duplicação, uma para o turno e outra y+=x), qualquer número ímpar é representado quase idealmente.

Números pares não são tão bons, pois sempre usam 16 ops para redefinir xantes de qualquer outra coisa, e 8, por exemplo, pode ser alcançado em 5 etapas.

Curiosamente, o algoritmo acima nunca usa y+=y, pois yé sempre mantido ímpar. Nesse caso, ele pode realmente encontrar o programa mais curto para o conjunto restrito de apenas 3 operações.

Teste

# 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()

Eu escrevi um teste simples para verificar se minha solução realmente produz resultados corretos, e nunca ultrapassa 33 etapas, para todas as entradas válidas ( 0 <= n < 65536).

Além disso, tentei fazer uma análise empírica para comparar a saída da minha solução com a saída ideal - no entanto, verifica-se que a pesquisa pela primeira vez é muito ineficiente para obter o comprimento mínimo de saída para cada entrada válida n. Por exemplo, o uso do BFS para encontrar a saída para n = 65535não termina em um período de tempo razoável. No entanto, eu participei bfs()e estou aberto a sugestões.

No entanto, testei minha própria solução no @ CChak's (implementado em Python aqui como U). Eu esperava que o meu fizesse pior, já que é drasticamente ineficiente para números pares menores, mas, em toda a faixa de duas maneiras, a mina produziu uma produção de comprimento em média 10,8% a 12,3% menor. Eu pensei que talvez isso fosse devido à melhor eficiência da minha própria solução em números ímpares, então Vusa o meu em números ímpares e @ CChak em números pares, mas Vestá no meio (cerca de 10% menor que U, 3% maior que S).