Vous obtenez une machine avec deux registres 16 bits, xet y. Les registres sont initialisés x=1et y=0. La seule opération que la machine peut effectuer est l'addition du module 65536. C'est-à-dire:

• x+=y- xest remplacé par (x + y) mod 65536; yest inchangé
• y+=x - de même pour y
• x+=x- xest remplacé par 2x mod 65536; légal que si xest pair
• y+=y - de même pour y

Le but est d'obtenir un nombre prédéterminé dans l'un des registres (soit xou y).

Écrire un programme ou un sous - programme qui reçoit un certain nombre (dans stdin, argv, paramètre de fonction, en haut de la pile ou tout autre lieu conventionnel), et délivre un programme pour obtenir ce nombre. La sortie doit aller vers stdout, ou (si votre langue n'en a pas stdout) vers tout autre périphérique de sortie conventionnel.

Le programme de sortie peut être jusqu'à 100% plus 2 étapes loin d'être optimal. Autrement dit, si le programme le plus court pour obtenir le nombre cible comporte des nétapes, votre solution ne peut pas être plus longue que 2n+2. Cette restriction vise à éviter les solutions "trop ​​faciles" (par exemple compter 1, 2, 3, ...) mais ne nécessite pas une optimisation complète; Je m'attends à ce que le programme le plus court soit le plus facile à trouver, mais je ne peux pas en être sûr ...

Par exemple: Entrée = 25. Sortie:

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

Un autre exemple: pour tout nombre de fibonacci, la sortie a ce modèle alternatif. Pour Input = 21, output est

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

Le code le plus court (mesuré en octets) gagne.

(ce puzzle a été inspiré par du code pour un processeur 16 bits que j'ai dû générer récemment)

PS Je me demande - pour quel numéro le programme optimal est le plus long?

CJam, 31

Comme la réponse de @Tobia , mon algorithme est également éhonté volé inspiré par la réponse de @CChak . Mais, brandissant la magie noire qu'est CJam, j'ai réussi à faire une implémentation encore plus petite de l'algorithme.

Essayez-le ici.

Golfé:

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

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

Veuillez me corriger si je me trompe, mais je pensais que l'opération modulo 65536 utilisée dans les réponses avec un algorithme similaire n'est pas nécessaire. J'ai interprété la question de telle sorte que nous pouvons supposer que l'entrée sera un entier 16 bits non signé valide, et toutes les valeurs intermédiaires ou les résultats de cet algorithme le seront également.

Perl 107 97

Premier post, alors voilà.

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

Ce qui correspond à tous les critères d'ajout de registre, mais je n'ai pas effectué de vérification exhaustive pour voir si ma réponse était toujours à moins de 2n + 2 du nombre optimal d'étapes. Il est cependant bien en deçà de la limite pour chaque numéro de Fibonacci.

Voici une ventilation plus détaillée

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.

Comme je l'ai mentionné, c'est ma première tentative de golf, donc je suis sûr que cela peut être amélioré. De plus, je ne sais pas si l'appel initial du sous-programme doit être compté dans un appel récursif ou non, ce qui pourrait nous faire grimper de quelques caractères.

Fait intéressant, nous pouvons réduire le code de 11 octets * et améliorer notre "efficacité" en termes de nombre d'opérations de registre, en assouplissant l'exigence selon laquelle seules les valeurs paires peuvent être "doublées". Je l'ai inclus pour le plaisir ici:

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

Commencer l'addendum:

J'ai vraiment aimé ce problème, et je l'ai tripoté de temps en temps au cours des deux dernières semaines. Je pensais publier mes résultats.

Quelques chiffres:

En utilisant un algorithme BFS pour trouver une solution optimale, dans les 2 ^ 16 premiers nombres, seuls 18 nombres nécessitent 23 étapes. Ce sont: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

En utilisant l'algorithme récursif décrit ci-dessus, le nombre "le plus difficile" à atteindre est 65535, à 45 opérations. (65534 prend 44, et il y a 14 nombres qui prennent 43 étapes) 65535 est également le plus grand écart par rapport à l'optimal, 45 vs 22. La différence de 23 étapes est 2n + 1. (Seuls trois nombres ont atteint 2n: 65534, 32767, 32751.) À l'exception des cas triviaux (zéro), sur la plage définie, la méthode récursive représente en moyenne 1,4 fois la solution optimale.

Conclusion: pour les nombres 1-2 ^ 16, l'algorithme récursif ne franchit jamais le seuil défini de 2n + 2, donc la réponse est valide. Je soupçonne cependant qu'il commencerait à s'écarter trop loin de la solution optimale pour des registres plus grands / plus de bits.

Le code que j'ai utilisé pour créer le BFS était bâclé, gourmand en mémoire, non commenté et délibérément non inclus. Donc ... vous n'avez pas à faire confiance à mes résultats, mais je suis assez confiant en eux.

Python 3, 202 octets

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)

(Merci à @rationalis pour quelques octets)

Voici une solution extrêmement simple. J'aimerais pouvoir mieux jouer la dernière ligne, mais je suis actuellement à court d'idées. Appelez avec S(25).

Le programme ne fait qu'un simple BFS sans mise en cache, il est donc très lent. Voici S(97), pour un exemple de sortie:

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

Dyalog APL, 49 caractères / octets *

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

Algorithme inspiré sans vergogne par la réponse de @CChak .

Exemple:

    {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

Non 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 prend en charge un jeu de caractères hérité dont les symboles APL sont mappés aux valeurs supérieures de 128 octets. Par conséquent, un programme APL qui utilise uniquement des caractères ASCII et des symboles APL peut être considéré comme des octets == caractères.}

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)

Je ne peux pas garantir que cela reste à 2 fois le programme optimal pour les nombres pairs, mais il est efficace. Pour toutes les entrées valides 0 <= n < 65536, elle est essentiellement instantanée et génère un programme d'au plus 33 instructions. Pour une taille de registre arbitraire n(après avoir fixé cette constante), cela prendrait du O(n)temps avec tout au plus des 2n+1instructions.

Un peu de logique binaire

N'importe quel nombre impair npeut être atteint en 31 étapes: faire y+=x, obtenir x,y = 1,1, puis continuer à doubler xavec x+=x(pour le premier doublement, faire x+=y, car il xest impair pour commencer). xatteindra chaque puissance de 2 de cette façon (c'est juste un décalage vers la gauche), et vous pouvez donc définir n'importe quel bit de ypour être 1 en ajoutant la puissance correspondante de 2. Puisque nous utilisons des registres 16 bits, et chaque bit sauf pour le premier, il faut un doublement pour atteindre et un y+=xpour mettre, nous obtenons un maximum de 31 ops.

Tout nombre pair nn'est qu'une puissance de 2, appelez-le a, multipliez un nombre impair, appelez-le m; à- dire n = 2^a * m, ou de manière équivalente, n = m << a. Utilisez le processus ci-dessus pour obtenir m, puis réinitialisez x-le en le déplaçant vers la gauche jusqu'à ce qu'il soit à 0. Faites un x+=ypour définir x = m, puis continuez à doubler x, la première fois x+=yet ensuite x+=x.

Quoi qu'il en asoit, il faut des 16-adécalages xpour obtenir y=met des adécalages supplémentaires pour réinitialiser x=0. Un autre achangement de xse produira après x=m. Donc, un total de 16+adécalages est utilisé. Il y a jusqu'à des 16-abits qui doivent être définis pour obtenir m, et chacun d'entre eux en prendra un y+=x. Enfin, nous avons besoin d'une étape supplémentaire x=0pour le régler sur m x+=y,. Il faut donc au maximum 33 étapes pour obtenir un nombre pair.

Vous pouvez, bien sûr, généraliser cela à n'importe quel registre de taille, auquel cas il faut toujours au plus 2n-1et 2n+1ops pour les nentiers impairs et pairs, respectivement.

L'optimalité

Cet algorithme produit un programme qui est presque optimal (c'est-à-dire dans 2n+2si nest le nombre minimum d'étapes) pour les nombres impairs. Pour un nombre impair donné n, si le me bit est le premier 1, alors tout programme prend au moins des métapes pour arriver à x=nou y=n, puisque l'opération qui augmente le plus rapidement les valeurs des registres est x+=xou y+=y(c'est-à-dire des doublons) et il faut des mdoublons pour arriver à le me bit de 1. Puisque cet algorithme prend au plus des 2métapes (au plus deux par doublement, une pour le décalage et une y+=x), tout nombre impair est représenté de façon presque optimale.

Les nombres pairs ne sont pas aussi bons, car il utilise toujours 16 opérations pour réinitialiser xavant toute autre chose, et 8, par exemple, peuvent être atteints en 5 étapes.

Fait intéressant, l'algorithme ci-dessus n'utilise jamais y+=ydu tout, car il yest toujours maintenu impair. Dans ce cas, il peut en fait trouver le programme le plus court pour l'ensemble restreint de seulement 3 opérations.

Essai

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

J'ai écrit un test simple pour vérifier que ma solution produit effectivement des résultats corrects, et ne dépasse jamais 33 étapes, pour toutes les entrées valides ( 0 <= n < 65536).

De plus, j'ai essayé de faire une analyse empirique pour comparer la sortie de ma solution aux sorties optimales - cependant, il s'avère que la recherche en largeur d'abord est trop inefficace pour obtenir la longueur de sortie minimale pour chaque entrée valide n. Par exemple, l'utilisation de BFS pour rechercher la sortie de n = 65535ne se termine pas dans un laps de temps raisonnable. Néanmoins, je suis parti bfs()et je suis ouvert aux suggestions.

J'ai cependant testé ma propre solution contre @ CChak (implémentée ici en Python U). Je m'attendais à ce que le mien fasse pire, car il est considérablement inefficace pour les petits nombres pairs, mais en moyenne sur toute la plage de deux manières, le mien a produit une production de longueur moyenne de 10,8% à 12,3% plus courte. Je pensais que cela était peut-être dû à une meilleure efficacité de ma propre solution sur les nombres impairs, donc Vutilise le mien sur les nombres impairs et @ CChak sur les nombres pairs, mais se Vsitue entre les deux (environ 10% plus court que U, 3% plus long que S).