Ceci est une question de astuce pour le golf en Python concernant la question de Evil Numbers sur Anarchy Golf .

Un nombre est mauvais si son extension binaire a un nombre pair de 1. Le défi consiste à imprimer les 400 premiers nombres pervers 0,3,5,...,795,797,798, un par ligne.

Les soumissions Python 2 sont dirigées par llhuii avec une solution à 42 octets. Le second meilleur est 46 octets par mitchs, suivi de cinq soumissions de 47 octets. Il semble que llhuii ait trouvé quelque chose de vraiment magique qui a échappé à de nombreux golfeurs de Python depuis plus de 2 ans. Enregistrer 4 ou 5 octets est énorme pour un golf aussi court.

Je suis toujours à 47 octets. J'espère que nous pourrons résoudre ce casse-tête en tant que communauté. Si nous obtenons une réponse conjointement, je la soumettrais sous le nom de toutes les personnes qui ont contribué. Une réponse à cette question peut être un morceau de code, une nouvelle idée ou une analyse. Si vous êtes llhuii, s'il vous plait, ne le gâtez pas pour nous encore.

Bien que les soumissions ne soient pas révélées parce que ce problème est sans fin, nous avons quelques pistes. La soumission gagnante a pris 0,1699 secondes, beaucoup plus longtemps que toute autre, suggérant une méthode inefficace. Parmi les statistiques sur les octets, sur les 42 caractères, 23 sont alphanumériques [0-9A-Za-z]et 19 sont des symboles ASCII. Cela signifie qu'il n'y a pas d'espace dans la solution de llhuii.

Vous pouvez tester votre code sur la page du problème , en choisissant Python dans la liste déroulante des langues ou en téléchargeant un .pyfichier. Notez que:

• Python 2.7 est utilisé
• Votre code doit être un programme complet qui imprime
• Il n'y a pas d'entrée pour ce problème, comme kolmogorov-complex
• Votre programme doit simplement imprimer les 400 valeurs telles qu'elles sont données, même s'il se casserait avec des valeurs plus grandes
• Les programmes ont 2 secondes pour s'exécuter
• Les programmes peuvent se terminer avec une erreur
• Vous pouvez utiliser exec; le "exec est refusé" se réfère à shell exec

Ce n'est pas la même solution que celle de llhuii, mais c'est aussi 42 octets.

n=0;exec'print n;n^=(n^n+2)%3/2;n+=2;'*400

Essayez-le en ligne!

Grâce à @JonathanFrech, nous sommes maintenant à 40 octets.

n=0;exec'print n;n=n+2^(n^n+2)/2%3;'*400

Essayez-le en ligne!

Un autre octet doit être sauvegardé, pour un total de 39.

n=0;exec'print n;n=n+2^-(n^n+2)%3;'*400

Essayez-le en ligne!

Obtenir 39 octets

C'est une explication de la façon dont j'ai obtenu une solution de 39 octets, que Dennis et Jonathan Frech ont également trouvée séparément. Ou plutôt, il explique comment on pourrait arriver à la réponse avec le recul, d’une manière beaucoup plus agréable que mon chemin actuel, qui était plein de raisonnements boueux et d’impasses.

n=0
exec"print n;n=n+2^-(n+2^n)%3;"*400

En écrivant ceci un peu moins golfé et avec plus de parens, cela ressemble à:

n=0
for _ in range(400):
  print n
  n=(n+2)^(-((n+2)^n))%3

Bits parités

Nous commençons par une idée de ma solution de 47 octets qui consiste à sortir tous les nombres de la forme n=2*k+boù ils kcomptent 0,1,...,399et bconstituent un bit de parité qui rend le nombre total de 1 égal.

Écrivons par(x)pour la parité de bitsx , c’est-à-dire que xor ( ^) contient tous les bits x. C'est 0 s'il y a un nombre pair de 1 bits (le nombre est mauvais) et 1 s'il y a un nombre impair de 1 bits. Pour n=2*k+b, nous avons par(n) = par(k)^b, pour ainsi atteindre le mal dont par(n)==0nous avons besoin b=par(k), à savoir le dernier bit de nsoit la parité binaire des bits précédents.

Mes premiers efforts au golf ont été d’exprimer le par(k), d’abord directement avec bin(k).count('1')%2, puis avec un peu de manipulation .

Mises à jour de parité

Pourtant, il ne semblait pas y avoir d’expression courte. Au lieu de cela, cela a aidé à réaliser qu'il y avait plus d'informations avec lesquelles travailler. Plutôt que de simplement calculer la parité de bits du nombre actuel,

k  ---->  par(k)

nous pouvons mettre à jour la parité bit comme on incrémente kà k+1.

k   ---->  par(k)
      |
      v
k+1 ---->  par(k+1)

En d'autres termes, puisque nous k=0,1,2,...comptons, nous devons simplement maintenir la parité de bits actuelle au lieu de la calculer à partir de zéro à chaque fois. La mise à jour de parité de bit par(k+1)^par(k)est la parité du nombre de bits basculés en allant kvers k+1, soit par((k+1)^k).

par(k+1) ^ par(k) = par((k+1)^k)
par(k+1) = par(k) ^ par((k+1)^k)

Forme de (k+1)^k

Maintenant, nous devons calculer par((k+1)^k). Il peut sembler que nous n'ayons nulle part abouti, car le calcul de la parité entre bits est exactement le problème que nous essayons de résoudre. Mais, les nombres exprimés sous (k+1)^kla forme 1,3,7,15,.., c’est-à-dire une valeur inférieure à une puissance de 2, fait souvent utilisé pour le piratage des bits . Voyons pourquoi.

Lorsque nous incrémentons k, l’effet des transferts binaires est d’inverser le dernier 0et tout 1à sa droite, créant ainsi un nouveau principal 0s’il n’y en avait pas. Par exemple, prenezk=43=0b101011

      **
  101011  (43)
 +     1
  ------
= 101100  (44)

  101011  (43)
 ^101100  (44)
  ------
= 000111  (77)   

Les colonnes provoquant un report sont identifiées par *. Celles-ci ont un 1changement en a 0et transmettent un peu de retenue 1, ce qui continue à se propager jusqu'à ce qu'il frappe un 0dans k, qui devient 1. Les bits plus à gauche ne sont pas affectés. Ainsi, lorsque les k^(k+1)contrôles qui changent les positions de bits kà k+1, il trouve les positions des plus à droite 0et 1est à sa droite. C'est-à-dire que les bits modifiés forment un suffixe, le résultat est donc un 0 suivi d'un ou plusieurs 1. Sans les zéros au début, il existe des nombres binaires 1, 11, 111, 1111, ...inférieurs à une puissance de 2.

L'informatique par((k+1)^k)

Maintenant que nous comprenons que cela (k+1)^kse limite à 1,3,7,15,..., trouvons un moyen de calculer la parité de bits de ces nombres. Ici, un fait utile est ce 1,2,4,8,16,...modulo alternatif 3entre 1et 2, depuis 2==-1 mod 3. Donc, en prenant 1,3,7,15,31,63...modulo 3donne 1,0,1,0,1,0..., qui sont exactement leurs parités de bits. Parfait!

Donc, nous pouvons faire la mise par(k+1) = par(k) ^ par((k+1)^k)à jour en tant que

par(k+1) = par(k) ^ ((k+1)^k)%3

En utilisant bcomme variable dans laquelle nous stockons la parité, cela ressemble à

b^=((k+1)^k)%3

Écrire le code

En regroupant cela dans le code, nous commençons ket le bit de parité bà 0, puis, imprimons n=2*k+bet mettons à jour de manière répétée b=b^((k+1)^k)%3et k=k+1.

46 octets

k=b=0
exec"print 2*k+b;b^=(k+1^k)%3;k+=1;"*400

Essayez-le en ligne!

Nous avons retiré parens autour k+1de ((k+1)^k)%3parce que la priorité Python fait d'abord l'addition de toute façon, bizarre qu'il regarde.

Améliorations du code

Nous pouvons toutefois faire mieux en travaillant directement avec une seule variable n=2*k+bet en effectuant les mises à jour directement sur celle-ci. Faire k+=1correspond à n+=2. Et, mise b^=(k+1^k)%3à jour correspond à n^=(k+1^k)%3. Ici, k=n/2avant de mettre à jour n.

44 octets

n=0
exec"print n;n^=(n/2+1^n/2)%3;n+=2;"*400

Essayez-le en ligne!

Nous pouvons raccourcir n/2+1^n/2(rappelez-vous (n/2+1)^n/2) en réécrivant

n/2+1 ^ n/2
(n+2)/2 ^ n/2
(n+2 ^ n)/2    

Puisque /2supprime le dernier bit, peu importe si nous le faisons avant ou après le xor-ing. Donc nous avons n^=(n+2^n)/2%3. Nous pouvons économiser un autre octet en notant que modulo 3, /2est équivalent *2à -, en notant que n+2^nmême si la division est divisée en deux sans plancher. Cela donnen^=-(n+2^n)%3

41 octets

n=0
exec"print n;n^=-(n+2^n)%3;n+=2;"*400

Essayez-le en ligne!

Enfin, nous pouvons combiner les opérations n^=c;n+=2en n=(n+2)^c, où cest un peu. Cela fonctionne car ^cagit uniquement sur le dernier bit et +2ne se soucie pas du dernier bit; les opérations sont donc commutées. Encore une fois, la préséance nous permet d'omettre les parens et d'écrire n=n+2^c.

39 octets

n=0
exec"print n;n=n+2^-(n+2^n)%3;"*400

Essayez-le en ligne!

Cela donne la solution de 47 octets de mon (xnor) et la pensée qui l’a conduit à la solution. Ne lisez pas ceci si vous voulez comprendre cela vous-même.

Une première idée naturelle consiste à parcourir les nombres de 0 à 799, en imprimant uniquement ceux avec un nombre pair de 1 en binaire.

52 octets

for n in range(800):
 if~bin(n).count('1')%2:print n

Essayez-le en ligne!

Ici, le ~bit est complémentaire pour pouvoir basculer even<->odddans le compte et ne donner une valeur de vérité que sur des comptes pairs.

Nous pouvons améliorer cette méthode en générant toutes les valeurs au lieu de filtrer. Observez que les valeurs de sortie sont les nombres 0 à 399, chacune avec un bit ajouté pour rendre le nombre de 1 bits pair.

0 = 2*0 + 0
3 = 2*1 + 1
5 = 2*2 + 1
6 = 2*3 + 0
...

Ainsi, le nnombre e est soit 2*n+bavec soit b=0ou b=1. Le bit bpeut être trouvé en comptant 1dans les bits de net en prenant le compte modulo 2.

49 octets

for n in range(400):print 2*n+bin(n).count('1')%2

Essayez-le en ligne!

Nous pouvons couper les 2 octets pour 2*en itérant 0,2,4,..., ce qui ne risque pas le nombre de 1. Nous pouvons le faire en utilisant une execboucle qui s'exécute 400 fois et en augmentant nde 2 chaque boucle.

47 octets

n=0;exec"print n+bin(n).count('1')%2;n+=2;"*400

Essayez-le en ligne!

Et c'est ma solution à 47 octets. Je soupçonne que la plupart, sinon toutes les autres solutions à 47 octets sont les mêmes.

llhuii's Python 3 soumission

Voici les soumissions de Python 3 pour Evil Numbers au moment de la rédaction:

llhuii a probablement porté son astuce sur Python 3 et a proposé une solution

• 3 octets de plus que leur solution Python 2, et
• a 45 - (25 + 18) = 2 octets d’espace.

Portant littéralement 47B de xnor sur Python 3, nous obtenons ce 50B:

n=0;exec("print(n+bin(n).count('1')%2);n+=2;"*400)

Je l'ai soumis comme ppcg(xnor). (Il ajoute des parenthèses à execet print, qui sont maintenant des fonctions.) Il a des statistiques de code différentes de celles des autres réponses Python 3, qui contiennent toutes une certaine quantité d’espace. Intéressant!

Il existe cependant un moyen plus court de le réécrire (il a exectendance à perdre son avantage concurrentiel dans Python 3):

n=0
while n<800:print(n+bin(n).count('1')%2);n+=2

C'est 49 octets. Je l'ai soumis comme ppcg(xnor,alternative). Cela a deux octets d'espaces, comme la réponse de llhui! Cela me porte à croire que la réponse de llhuii à Python 3 ressemble à ceci (nouvelle ligne, puis une whileboucle). Donc llhuii a probablement été utilisé execdans Python 2 et whiledans Python 3, exactement comme nous; cela explique la différence d’espace.

Notre 47B est devenu un 49B en Python 3. Ce qui est intéressant, c'est que le 42B de llhuii n'est pas devenu un 44B, il est devenu un 45B! Quelque chose à propos de la solution de llhuii prend un octet de plus dans Python 3. Cela pourrait vouloir dire différentes choses.

• La première chose qui me vient à l’esprit est la division : peut-être que llhuii utilise /dans Python 2, qui est devenu //Python 3. (s’ils comptent par deux comme nous, ils n/2pourraient alors être utilisés pour nrevenir d’un cran à la droite?)

• L’autre chose qui me vient à l’esprit est celle des opérateurs unaires après impression . Notre print blahest devenu print(blah)(1 octet en plus), mais si llhuii écrivait quelque chose comme print~-blahdans Python 2, cela deviendrait print(~-blah)en Python 3.

• Peut-être y a-t-il d'autres idées. S'il vous plaît, faites-moi savoir.

Statistiques de code pour toutes les solutions Py3, y compris la mienne:

Autres approches

1) Utilisation d'une formule pour A001969

Plutôt que de convertir en binaire, il pourrait être possible de tirer parti de la formule suivante (à partir d' OEIS ):

a(1) = 0
for n > 1: a(n) = 3*n-3-a(n/2) if n is even
           a(n) = a((n+1)/2)+n-1 if n is odd

Je suis très mauvais au golf en Python, donc je ne vais même pas essayer. Mais voici une tentative rapide dans JS.

^{NB: Je ne pense pas que ce serait une soumission JS valide, car il s'agit simplement de remplir un tableau sans l'afficher. Et même dans ce cas, il est 5 octets plus long que la meilleure solution JS actuelle (qui est de 45 octets). Mais ce n'est pas le point ici de toute façon.}

for(a=[n=0,3];n<199;)a.push(2*++n+a[n],6*n+3-a[n])

for(a=[n=0,3];n<199;)a.push(2*++n+a[n],6*n+3-a[n])

console.log(a.join`, `)

Espérons que cela puisse vous inspirer.

L'utilisation d'un tableau n'est probablement pas une bonne idée car il doit être initialisé et mis à jour. Il pourrait être plus efficace (en termes de taille de code) d’utiliser une fonction récursive , ce qui expliquerait pourquoi la solution gagnante prend plus de temps que les autres.

2) Construire la séquence Thue-Morse avec substitutions

En théorie, ce code devrait fonctionner:

n=0;a="1";b="0";exec"t=a;a+=b;b+=t;print(int(b[n]))+n;n+=2;"*400

Essayez-le en ligne! (version exécutable limitée à 20 termes)

Il calcule la séquence Thue-Morse avec des substitutions consécutives et recherche la position de 1 (Evil Numbers) dans la même boucle.

Mais:

• C'est beaucoup trop long dans sa forme actuelle
• Cela conduit rapidement à un débordement de mémoire

3) Construction de la séquence Thue-Morse avec des opérations au niveau des bits

En commençant par la définition directe par Wikipedia de la séquence Thue-Morse , je suis arrivé à cet algorithme (revenir à JS ... désolé):

for(e=n=0;n<799;)(e^=!(((x=n++^n)^x/2)&170))||console.log(n)

où nous gardons une trace de la perversité actuelle de la séquence en e et utilisons 170 comme masque de bits de bits impairs dans un octet.

Approche des compteurs imbriqués

J'ai une idée pour une approche différente, mais je ne suis pas assez expérimenté dans le golf python, je vais donc le laisser ici pour que vous puissiez le considérer comme un autre point de départ possible pour le golf.

L'idée ungolfed:

n=0
i=1
for _ in"01":
 i^=1
 for _ in"01":
  i^=1
  for _ in"01":
   i^=1
   for _ in"01":
    i^=1
    for _ in"01":
     i^=1
     for _ in"01":
      i^=1
      for _ in"01":
       i^=1
       for _ in"01":
        i^=1
        for _ in"01":
          i^=1
          if n<800:print i+n
          n+=2

Essayez-le en ligne!

Neuf niveaux de profondeur de nidification, toutes les boucles sont les mêmes, donc dans mon esprit elles devraient être construites par exec"something"*9+"deepest stuff". En pratique, je ne sais pas s'il est possible de faire quelque chose comme ceci avec un cycle pour.

Points à considérer pour le golf:

• peut-être y a-t-il une autre possibilité de faire deux fois le cycle en plus d'une boucle for (j'ai essayé une approche semblable à celle d'un quine avec la chaîne à exécuter passée à elle-même en tant qu'argument de formatage deux fois, mais ma tête a explosé).

• il pourrait aussi y avoir une meilleure alternative à if n<800:, ce qui est nécessaire ici, sinon nous continuerions à imprimer des nombres pervers jusqu'à 2 ^ 10

Idée: Parité de bits plus courte

Il faut beaucoup de caractères pour bin(n).count('1')%2calculer la parité du nombre de bits. Peut-être qu'une méthode arithmétique est plus courte, surtout si la longueur de bit est limitée.

Une façon sympa de même longueur int(bin(n)[2:],3)%2interprète la valeur binaire comme base 3(ou toute base impaire). Malheureusement, 4 octets sont utilisés pour supprimer le 0bpréfixe. Cela fonctionne aussi à faire int(bin(n)[2:])%9%2.

Une autre idée vient de la combinaison de bits utilisant xor. Si na une représentation binaire abcdefghi, alors

n/16 = abcde
n%16 =  fghi

r = n/16 ^ n%16 has binary representation (a)(b^f)(c^g)(d^h)(e^i)

Alors, r=n/16^n%16est le mal si et seulement si nest le mal. On peut alors répéter que s=r/4^r%4, une valeur sdans 0,1,2,3, dont 1et 2ne sont pas mal, avec checkable 0<s<3.

52 octets

n=0;exec"r=n/16^n%16;print(0<r/4^r%4<3)+n;n+=2;"*400

Essayez-le en ligne!

Cela s'est avéré beaucoup plus longtemps. Il y a de nombreux boutons à tourner pour savoir comment scinder le nombre, vérifier le dernier nombre (peut-être une table de conversion basée sur des bits). Je soupçonne que ceux-ci ne peuvent aller aussi loin que cela.

Par construction, n+n^nc'est toujours mauvais, mais mes pauvres compétences en Python ne pouvaient que trouver une solution à 61 octets:

for n in sorted(map(lambda n:n+n^n,range(512)))[:400]:print n

Merci à @Peilonrayz pour la sauvegarde de 5 octets et @ Mr.Xcoder pour la sauvegarde de 1 octet:

for n in sorted(n^n*2for n in range(512))[:400]:print n

Idée: A006068 («a (n) est codé en gris dans n»)

L'idée de Neil de trier tout ce qui 2n XOR nm'intriguait, j'ai donc essayé de trouver les indices derrière ce genre. J'ai écrit ce code , et il révèle que nous pouvons écrire quelque chose comme ceci:

for n in range(400):x=a(n);print 2*x^x

Où a(n)est A006068 (n). Essayez-le en ligne!

Cependant, cela suppose que nous disposons d’un moyen rapide de calculer A006068. C'est déjà 38 octets, en supposant que nous puissions le calculer en 4 octets (la a(n)partie). L'implémentation réelle (dans l'en-tête du TIO) est beaucoup plus longue que cela. Pas beaucoup d'espoir pour cela, je pense.

Idée: réduire plus de XOR

Si vous XOR tous les morceaux de nensemble, ce sera 0pour le mal et 1pour le non-mal. Vous pouvez le faire avec une fonction récursive (qui aurait donc pris plus de temps?), Comme ceci:

f=lambda n:f(n/2^n&1)if n>1else-~-n

Cela retourne 1 pour le mal.

C'est 35 octets, et vérifie si un nombre est mal. Malheureusement, la valeur filterest déjà de 6 octets, ce n’était donc pas la solution optimale mais cette idée peut probablement être mise en pratique.

Méthode de substitution: {1 -> {1, -1}, -1 -> {-1, 1}}

Vous pouvez également effectuer cette substitution 10 fois {1 -> {1, -1}, -1 -> {-1, 1}}, puis aplatir et vérifier les positions des 1

voici le code mathematica

(F = Flatten)@
Position[F@Nest[#/.{1->{1,-1},-1->{-1,1}}&,1,10],1][[;; 400]] - 1