Dies ist eine Tippfrage zum Golfen in Python bezüglich der Evil Numbers- Frage zu Anarchy Golf .

Eine Zahl ist böse, wenn ihre binäre Erweiterung eine gerade Zahl von 1 hat. Die Herausforderung besteht darin, die ersten 400 bösen Zahlen zu drucken 0,3,5,...,795,797,798, eine pro Zeile.

Die Python 2-Einsendungen werden von llhuii mit einer 42-Byte-Lösung angeführt. Das nächstbeste sind 46 Bytes von Mitchs, gefolgt von fünf 47-Byte-Einsendungen. Es scheint, dass llhuii etwas wirklich Magisches gefunden hat, das vielen starken Python-Golfern über 2 Jahre lang entgangen ist. Das Speichern von 4 oder 5 Bytes ist für solch ein kurzes Golfspiel enorm.

Ich bin immer noch bei 47 Bytes. Ich hoffe, wir können dieses Puzzle als Community knacken. Wenn wir gemeinsam eine Antwort bekommen, würde ich sie unter den Namen aller einreichen, die dazu beigetragen haben. Eine Antwort auf diese Frage kann ein Stück Code oder eine neue Idee oder eine Analyse sein. Wenn Sie llhuii sind, verderben Sie es uns bitte noch nicht.

Obwohl Einsendungen nicht aufgedeckt werden, weil dieses Problem endlos ist, erhalten wir einige Hinweise. Die erfolgreiche Einreichung dauerte 0,1699 Sekunden, viel länger als jede andere, was auf eine ineffiziente Methode hindeutet. Aus der Bytestatistik sind von den 42 Zeichen 23 alphanumerisch [0-9A-Za-z]und 19 ASCII-Symbole. Dies bedeutet, dass die Lösung von llhuii keine Leerzeichen enthält.

Sie können Ihren Code auf der Problemseite testen , indem Sie in der Dropdown-Liste "Sprache" die Option "Python" auswählen oder eine .pyDatei hochladen . Beachten Sie, dass:

• Python 2.7 wird verwendet
• Ihr Code muss ein vollständiges Programm sein, das gedruckt wird
• Es gibt keine Eingabe für dieses Problem, wie Kolmogorov-Komplexität
• Ihr Programm muss nur die 400 Werte wie angegeben ausgeben, auch wenn es bei größeren Werten abbrechen würde
• Programme müssen 2 Sekunden ausgeführt werden
• Programme werden möglicherweise mit einem Fehler beendet
• Sie können verwenden exec; Die Angabe "exec wird abgelehnt" bezieht sich auf die Shell exec

Dies ist nicht die gleiche Lösung wie die von llhuii, aber es ist auch 42 Byte lang.

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

Probieren Sie es online!

Dank @JonathanFrech sind wir jetzt bei 40 Bytes.

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

Probieren Sie es online!

Es muss noch ein Byte gespeichert werden, insgesamt 39.

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

Probieren Sie es online!

39 Bytes bekommen

Dies ist eine Erklärung, wie ich zu einer 39-Byte-Lösung gekommen bin, die Dennis und JonathanFrech ebenfalls separat gefunden haben. Oder vielmehr, es erklärt, wie man im Nachhinein zu der Antwort gelangen kann, und zwar auf eine Weise, die viel schöner ist als mein tatsächlicher Weg dahin, der voller schlammiger Überlegungen und Sackgassen war.

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

Wenn Sie dies etwas weniger golfen und mit mehr Parens schreiben, sieht das so aus:

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

Bitparitäten

Wir beginnen mit einer Idee von meiner 47-Byte - Lösung alle Zahlen der Form ausgeben , n=2*k+bwo kaufwärts zählt, 0,1,...,399und bist ein Paritätsbit, das die Gesamtzahl von 1 macht , auch.

Schreiben wir par(x)für die Bitparität von x, das ist das xor ( ^) aller Bits in x. Dies ist 0, wenn es eine gerade Anzahl von 1-Bits gibt (die Anzahl ist böse), und 1, wenn es eine ungerade Anzahl von 1-Bits gibt. Denn n=2*k+bwir haben par(n) = par(k)^b, um das Böse zu erreichen par(n)==0, müssen wir b=par(k)das letzte Bit nder Bit-Parität der vorhergehenden Bits sein.

Meine ersten Bemühungen um Golf waren die auf ausdrücken par(k), zunächst direkt mit bin(k).count('1')%2, und dann mit Bit - Manipulation .

Paritätsaktualisierungen

Trotzdem schien es keinen kurzen Ausdruck zu geben. Stattdessen hat es geholfen zu erkennen, dass es mehr Informationen gibt, mit denen man arbeiten kann. Anstatt nur die Bit-Parität der aktuellen Zahl zu berechnen,

k  ---->  par(k)

wir können die Bit - Parität aktualisieren , wie wir erhöhen kzu k+1.

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

Das heißt, da wir aufwärts zählen k=0,1,2,..., müssen wir nur die aktuelle Bitparität beibehalten, anstatt sie jedes Mal von Grund auf neu zu berechnen. Die Bitparitätsaktualisierung par(k+1)^par(k)ist die Parität der Anzahl von Bits, die beim Wechseln von knach k+1, d par((k+1)^k). H., Gewechselt werden .

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

Eine Form von (k+1)^k

Jetzt müssen wir rechnen par((k+1)^k). Es scheint, als hätten wir nichts erreicht, weil die Berechnung der Bit-Parität genau das Problem ist, das wir zu lösen versuchen. Zahlen, die als ausgedrückt werden, (k+1)^khaben jedoch die Form 1,3,7,15,.., dh eine unter einer Potenz von 2, eine Tatsache, die häufig in Bit-Hacks verwendet wird . Mal sehen, warum das so ist.

Wenn wir inkrementieren k, besteht der Effekt der binären Überträge darin, die letzten 0und alle 1nach rechts zu invertieren und eine neue Führung zu erzeugen, 0wenn keine vorhanden wäre. Nehmen wir zum Beispielk=43=0b101011

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

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

Die Spalten, die einen Übertrag verursachen, sind mit gekennzeichnet *. Diese haben eine 1Änderung von a 0und leiten ein Übertragsbit von weiter 1, das sich so lange nach links ausbreitet, bis es ein 0In trifft k, das sich zu ändert 1. Etwaige Bits weiter links bleiben davon unberührt. Also, wenn k^(k+1)überprüft , welche Positionen ändern biß kzu k+1, findet er die Positionen der äußersten rechten 0und der 1‚s auf der rechten Seite . Das heißt, die geänderten Bits bilden ein Suffix. Das Ergebnis sind also Nullen, gefolgt von einer oder mehreren Einsen. Ohne die führenden Nullen gibt es Binärzahlen 1, 11, 111, 1111, ..., die unter einer Zweierpotenz liegen.

Computing par((k+1)^k)

Nun, da wir verstehen, dass dies auf (k+1)^kbeschränkt ist 1,3,7,15,..., wollen wir einen Weg finden, die Bitparität solcher Zahlen zu berechnen. Hier ist eine nützliche Tatsache, dass 1,2,4,8,16,...abwechselnd modulo 3zwischen 1und 2, da 2==-1 mod 3. Also, unter 1,3,7,15,31,63...Modulo 3gibt 1,0,1,0,1,0..., was genau ihre Bit-Paritäten sind. Perfekt!

So können wir das Update durchführen par(k+1) = par(k) ^ par((k+1)^k)als

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

Unter Verwendung bals Variable wir die Parität in sind speichern, das sieht aus wie

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

Code schreiben

Setzen wir dies in Code zusammen, starten wir kund setzen das Paritätsbit bbeide auf 0, drucken n=2*k+bund aktualisieren dann wiederholt b=b^((k+1)^k)%3und k=k+1.

46 Bytes

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

Probieren Sie es online!

Wir haben Parens k+1in entfernt, ((k+1)^k)%3weil Python die Addition sowieso zuerst ausführt, komisch, wie es aussieht.

Code Verbesserungen

Wir können es jedoch besser machen, indem wir direkt mit einer einzelnen Variablen arbeiten n=2*k+bund die Aktualisierungen direkt darauf durchführen. Tun k+=1entspricht n+=2. Und die Aktualisierung b^=(k+1^k)%3entspricht n^=(k+1^k)%3. Hier k=n/2vor dem Update n.

44 Bytes

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

Probieren Sie es online!

Wir können n/2+1^n/2dies (n/2+1)^n/2durch Umschreiben verkürzen (denken Sie daran )

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

Da /2das letzte Bit entfernt wird, spielt es keine Rolle, ob wir es vor oder nach dem xor-ing machen. Also haben wir n^=(n+2^n)/2%3. Wir können ein weiteres Byte speichern mit der Feststellung , dass Modulo 3, /2gleichwertig ist *2äquivalent ist -, unter Hinweis darauf , dass n+2^nist sogar so die Division ohne Boden tatsächliches Halbieren ist. Das gibtn^=-(n+2^n)%3

41 Bytes

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

Probieren Sie es online!

Schließlich können wir die Operationen n^=c;n+=2in kombinieren n=(n+2)^c, wo cein bisschen ist. Dies funktioniert, weil ^cnur das letzte Bit bearbeitet wird und das letzte Bit +2nicht berücksichtigt wird, sodass die Operationen pendeln. Wieder lässt uns der Vorrang die Parens auslassen und schreiben n=n+2^c.

39 Bytes

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

Probieren Sie es online!

Dies gibt meine (xnor) 47-Byte-Lösung und das Denken, das mich dazu geführt hat. Lesen Sie dies nicht, wenn Sie dies selbst herausfinden möchten.

Eine natürliche erste Idee ist, durch die Zahlen 0 bis 799 zu iterieren und nur die mit einer geraden Zahl von Einsen im Binärformat zu drucken.

52 Bytes

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

Probieren Sie es online!

Hier ~nimmt das Bit das Komplement, um even<->odddie Zählung einzuschalten und nur bei geraden Zählungen einen wahren Wert zu geben.

Wir können diese Methode verbessern, indem wir alle Werte generieren, anstatt sie zu filtern. Beachten Sie, dass die Ausgabewerte die Zahlen 0 bis 399 sind, wobei jeweils ein Bit angehängt wird, um die Anzahl der 1-Bits gerade zu machen.

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

Also ist die nth Nummer entweder 2*n+bmit entweder b=0oder b=1. Das Bit bkann durch Zählen 1in den Bits von nund Ermitteln des Zählmoduls 2 gefunden werden.

49 Bytes

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

Probieren Sie es online!

Wir können die 2 Bytes 2*durch Iteration kürzen 0,2,4,..., was die Anzahl der Bytes nicht verändert 1. Wir können dies tun, indem wir eine execSchleife verwenden, die 400-mal ausgeführt wird und njede Schleife um 2 erhöht .

47 Bytes

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

Probieren Sie es online!

Und das ist meine 47-Byte-Lösung. Ich vermute die meisten, wenn nicht alle anderen 47-Byte-Lösungen gleich sind.

llhuii's Python 3 Einreichung

Hier sind die Python 3-Einreichungen für Evil Numbers zum Zeitpunkt des Schreibens:

llhuii hat ihren Trick wahrscheinlich auf Python 3 portiert und eine Lösung gefunden

• 3 Bytes länger als ihre Python 2-Lösung, und
• hat 45 - (25 + 18) = 2 Bytes Leerzeichen.

Wenn wir xnors 47B buchstäblich nach Python 3 portieren, erhalten wir diese 50B:

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

Ich reichte es als ppcg(xnor). (Es fügt Klammern zu execund hinzu print, die jetzt funktionieren.) Es hat andere Codestatistiken als die anderen Python 3-Antworten, in denen alle eine gewisse Menge an Leerzeichen enthalten sind. Interessant!

Es gibt jedoch einen kürzeren Weg, es umzuschreiben ( execverliert in Python 3 tendenziell seinen Wettbewerbsvorteil):

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

Es sind 49 Bytes. Ich reichte es als ppcg(xnor,alternative). Dies hat zwei Bytes Leerzeichen, genau wie die Antwort von Llhui! Dies führt mich , dass llhuii Python 3 Antwort wie folgt aussieht irgendwie zu glauben (Newline, dann eine whileso llhuii wahrscheinlich verwendet Schleife.) execIn Python 2 und whilein Python 3, genau wie wir; Dies erklärt die Leerraum-Diskrepanz.

Unsere 47B wurde in Python 3 zu einer 49B. Interessanterweise wurde die 42B von llhuii nicht zu einer 44B, sondern zu einer 45B! Irgendetwas an der Lösung von llhuii benötigt in Python 3 ein Byte mehr. Dies könnte eine Vielzahl von Dingen bedeuten.

• Das erste , was in den Sinn kommt , ist Teilung : vielleicht llhuii verwendet /in Python 2, das wurde //in Python 3. (Wenn sie zu zweit wie wir sind zu zählen, dann n/2könnte zu verschieben verwendet werden , num ein Bit nach rechts zurück?)

• Das andere, was mir einfällt, sind unäre Operatoren nach dem Druck . Unser print blahwurde print(blah)(1 Byte extra), aber wenn llhuii so etwas wie print~-blahin Python 2 schrieb, würde es print(~-blah)in Python 3 werden.

• Vielleicht gibt es andere Ideen. Lass es mich wissen, bitte.

Codestatistik für alle Py3-Lösungen, einschließlich meiner jetzt:

Andere Ansätze

1) Verwenden einer Formel für A001969

Anstatt in eine Binärdatei zu konvertieren, kann möglicherweise die folgende Formel (aus OEIS ) verwendet werden:

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

Ich bin sehr schlecht im Golfspielen in Python, also werde ich es nicht einmal versuchen. Aber hier ist ein kurzer Versuch in JS.

^{NB: Ich glaube nicht, dass es sich um eine gültige JS-Übermittlung handelt, da sie nur ein Array ausfüllt, ohne es anzuzeigen. Und trotzdem ist es 5 Bytes länger als die derzeit beste JS-Lösung (das sind 45 Bytes). Aber darum geht es hier sowieso nicht.}

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

Hoffentlich kann es etwas Inspiration geben.

Die Verwendung eines Arrays ist wahrscheinlich keine gute Idee, da es initialisiert und aktualisiert werden muss. Es ist möglicherweise effizienter (in Bezug auf die Codegröße), stattdessen eine rekursive Funktion zu verwenden. Dies würde erklären, warum die erfolgreiche Lösung mehr Zeit in Anspruch nimmt als die anderen.

2) Aufbau der Thue-Morse-Sequenz mit Substitutionen

Theoretisch sollte dieser Code funktionieren:

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

Probieren Sie es online! (lauffähige Version auf 20 Begriffe begrenzt)

Es berechnet die Thue-Morse-Sequenz mit aufeinanderfolgenden Substitutionen und sucht nach der Position von Einsen (Evil Numbers) in derselben Schleife.

Aber:

• Es ist in seiner jetzigen Form viel zu lang
• Es kommt schnell zu einem Speicherüberlauf

3) Erstellen der Thue-Morse-Sequenz mit bitweisen Operationen

Ausgehend von Wikipedia's Direct Definition der Thue-Morse-Sequenz bin ich zu diesem Algorithmus gekommen (zurück zu JS ... sorry):

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

Dabei verfolgen wir die aktuelle Bösartigkeit der Sequenz in e und verwenden 170 als Bitmaske ungerader Bits in einem Byte.

Annäherung verschachtelter Zähler

Ich habe eine Idee für eine andere Herangehensweise, aber ich habe nicht genug Erfahrung mit Python-Golfen, daher überlasse ich es euch hier, um sie als einen weiteren möglichen Ausgangspunkt für das Golfen zu betrachten.

Die ungolfed Idee:

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

Probieren Sie es online!

Neun Ebenen Schachtelungstiefe, alle Schleifen sind gleich, daher sollten sie meiner Meinung nach von gebaut werden exec"something"*9+"deepest stuff". In der Praxis weiß ich nicht, ob es möglich ist, so etwas mit einem for-Zyklus zu machen.

Dinge, die Sie beim Golfen beachten sollten:

• Vielleicht gibt es eine andere Möglichkeit, zweimal zu wechseln als eine for-Schleife (ich habe versucht, einen quine-ähnlichen Ansatz zu verwenden, bei dem der String zweimal als Formatierungsargument an sich selbst übergeben wurde, aber mein Kopf explodierte).

• Es könnte auch eine bessere Alternative zu geben if n<800:, die hier benötigt wird, da wir sonst weiterhin böse Zahlen bis zu 2 ^ 10 ausgeben würden

Idee: Kürzere Bit-Parität

Es sind viele Zeichen erforderlich bin(n).count('1')%2, um die Parität der Bitanzahl zu berechnen. Möglicherweise ist eine arithmetische Methode kürzer, insbesondere bei einer begrenzten Bitlänge.

Eine nette Methode gleicher Länge ist int(bin(n)[2:],3)%2, den Binärwert als Basis 3(oder irgendeine ungerade Basis) zu interpretieren . Leider müssen 4 der Bytes das 0bPräfix entfernen . Es funktioniert auch int(bin(n)[2:])%9%2.

Eine andere Idee ergibt sich aus der Kombination von Bits mit xor. Wenn nbinäre Darstellung hat abcdefghi, dann

n/16 = abcde
n%16 =  fghi

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

Also, r=n/16^n%16ist böse , wenn und nur wenn das nBöse ist. Wir können dann wiederholen , dass als s=r/4^r%4ein Wert sin 0,1,2,3, von denen 1und 2ist nicht böse, überprüfbar mit 0<s<3.

52 Bytes

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

Probieren Sie es online!

Dies stellte sich viel länger heraus. Es gibt jedoch viele Drehknöpfe, um die Nummer zu teilen und die endgültige Nummer zu überprüfen (möglicherweise eine bitbasierte Nachschlagetabelle). Ich vermute, dass diese nur so weit gehen können.

Konstruktionsbedingt n+n^nist es immer böse, aber meine schlechten Python-Kenntnisse konnten nur mit einer 61-Byte-Lösung aufwarten:

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

Dank an @Peilonrayz für das Speichern von 5 Bytes und @ Mr.Xcoder für das Speichern von 1 Byte:

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

Idee: A006068 ("a (n) ist grau in n codiert")

Neils Idee, alles zu sortieren, 2n XOR nfaszinierte mich, also versuchte ich, die Indizes hinter dieser Art zu finden. Ich habe diesen Code geschrieben und es zeigt sich, dass wir so etwas schreiben können:

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

Wo a(n)ist A006068 (n). Probieren Sie es online!

Dies setzt jedoch voraus, dass wir einen kurzen Weg zur Berechnung von A006068 haben. Dies sind bereits 38 Bytes, vorausgesetzt, wir können es in 4 Bytes (dem a(n)Teil) berechnen . Die eigentliche Implementierung (im TIO-Header) ist weitaus länger. Ich denke nicht viel Hoffnung dafür.

Idee: Über XOR reduzieren

Wenn Sie alle Teile nzusammen XOR , wird es 0für das Böse und 1für das Nicht-Böse sein. Sie können dies mit einer rekursiven Funktion tun (die möglicherweise mehr Zeit in Anspruch genommen hat?):

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

Dies gibt 1 für das Böse zurück.

Das sind 35 Bytes und prüft, ob eine Zahl böse ist oder nicht. Leider sind filteres schon 6 Bytes, also war dies nicht die optimale Lösung, aber diese Idee kann wahrscheinlich golfen werden.

Ersetzungsmethode: {1 -> {1, -1}, -1 -> {-1, 1}}

Sie können diese Ersetzung auch 10 Mal vornehmen {1 -> {1, -1}, -1 -> {-1, 1}}, dann die Positionen der Einsen reduzieren und überprüfen

Hier ist der Mathematica-Code

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