Esta es una pregunta de consejos para jugar golf en Python con respecto a la pregunta de Evil Numbers en Anarchy Golf .

Un número es malo si su expansión binaria tiene un número par de 1. El desafío es imprimir los primeros 400 números malvados 0,3,5,...,795,797,798, uno por línea.

Las presentaciones de Python 2 están dirigidas por llhuii con una solución de 42 bytes. El siguiente mejor es 46 bytes por mitchs, seguido de cinco envíos de 47 bytes. Parece que llhuii ha encontrado algo verdaderamente mágico que ha eludido a muchos golfistas fuertes de Python durante más de 2 años. Ahorrar 4 o 5 bytes es enorme para un golf tan corto.

Todavía estoy en 47 bytes. Espero que podamos resolver este rompecabezas como comunidad. Si recibimos una respuesta conjunta, la enviaría con los nombres de todos los que contribuyeron. Una respuesta a esta pregunta puede ser un código o una nueva idea o un análisis. Si eres llhuii, no nos lo estropees todavía.

Aunque las presentaciones no se revelan porque este problema es Infinito, se nos dan algunas pistas. La presentación ganadora tardó 0.1699 segundos en ejecutarse, mucho más tiempo que cualquier otra, lo que sugiere un método ineficiente. De las estadísticas de bytes, de los 42 caracteres, 23 son alfanuméricos [0-9A-Za-z]y 19 son símbolos ASCII. Esto significa que no hay espacios en blanco en la solución de llhuii.

Puede probar su código en la página del problema , eligiendo Python en el menú desplegable de idioma o cargando un .pyarchivo. Tenga en cuenta que:

• Python 2.7 es usado
• Su código debe ser un programa completo que imprima
• No hay entrada para este problema, como kolmogorov-complex
• Su programa solo tiene que imprimir los 400 valores como se indica, incluso si se rompería en valores más grandes
• Los programas tienen 2 segundos para ejecutarse
• Los programas pueden finalizar con error
• Puedes usar exec; el "exec es denegado" se refiere a shell exec

Esta no es la misma solución que la de llhuii, pero también tiene 42 bytes de longitud.

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

Pruébalo en línea!

Gracias a @JonathanFrech, ahora estamos en 40 bytes.

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

Pruébalo en línea!

Hay otro byte para guardar, para un total de 39.

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

Pruébalo en línea!

Obteniendo 39 bytes

Esta es una explicación de cómo obtuve una solución de 39 bytes, que Dennis y JonathanFrech también encontraron por separado. O, más bien, explica cómo se puede llegar a la respuesta en retrospectiva, de una manera que es mucho mejor que mi camino real, que estaba lleno de razonamientos fangosos y callejones sin salida.

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

Escribiendo esto un poco menos golfizado y con más padres, esto se ve así:

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

Paridades de bits

Comenzamos con una idea de mi solución de 47 bytes para generar todos los números del formulario n=2*k+bdonde kcuenta 0,1,...,399y bes un bit de paridad que iguala el número total de 1.

Escribamos par(x)por la paridad de bits de x, que es el xor ( ^) en el que están todos los bits x. Esto es 0 si hay un número par de 1 bits (el número es malo) y 1 si hay un número impar de 1 bits. Para n=2*k+b, tenemos par(n) = par(k)^b, así que para lograr el mal par(n)==0necesitamos b=par(k), es decir, el último bit de nser la paridad de bits de los bits anteriores.

Mis primeros esfuerzos en el golf fueron expresar par(k), al principio directamente con bin(k).count('1')%2, y luego con la manipulación de bits .

Actualizaciones de paridad

Aún así, no parecía haber una expresión corta. En cambio, ayudó a darse cuenta de que hay más información para trabajar. En lugar de simplemente calcular la paridad de bits del número actual,

k  ---->  par(k)

podemos actualizar el bit de paridad como incrementamos ka k+1.

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

Es decir, dado que estamos contando k=0,1,2,..., simplemente necesitamos mantener la paridad de bits actual en lugar de calcularla desde cero cada vez. La actualización del bit de paridad par(k+1)^par(k)es la paridad del número de bits volteado al ir de ka k+1, es decir par((k+1)^k).

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

Forma de (k+1)^k

Ahora necesitamos calcular par((k+1)^k). Puede parecer que no hemos llegado a ninguna parte porque calcular la paridad de bits es exactamente el problema que estamos tratando de resolver. Pero, los números expresados ​​como (k+1)^ktienen la forma 1,3,7,15,.., es decir, uno por debajo de una potencia de 2, un hecho que a menudo se usa en hacks de bits . Veamos por qué es eso.

Cuando incrementamos k, el efecto de los acarreos binarios es invertir el último 0y todo 1a su derecha, creando un nuevo líder 0si no hubiera ninguno. Por ejemplo, tomek=43=0b101011

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

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

Las columnas que causan un acarreo están marcadas con *. Estos tienen un 1cambio en ay 0pasan un bit de acarreo de 1, que se sigue propagando a la izquierda hasta que llega a un 0in k, que cambia a 1. Cualquier parte más a la izquierda no se ve afectada. Por lo tanto, cuando se k^(k+1)comprueba qué bit posiciones cambian ka k+1, encuentra las posiciones de la derecha 0y de la 1's de su derecha. Es decir, los bits modificados forman un sufijo, por lo que el resultado son 0 seguidos de uno o más 1. Sin los ceros a la izquierda, hay números binarios 1, 11, 111, 1111, ...que están uno debajo de una potencia de 2.

Informática par((k+1)^k)

Ahora que entendemos que (k+1)^kse limita a 1,3,7,15,..., busquemos una manera de calcular la paridad de bits de dichos números. Aquí, un hecho útil es ese 1,2,4,8,16,...módulo alternativo 3entre 1y 2, desde 2==-1 mod 3. Entonces, tomar 1,3,7,15,31,63...módulos 3da 1,0,1,0,1,0..., que son exactamente sus paridades de bits. ¡Perfecto!

Entonces, podemos hacer la actualización par(k+1) = par(k) ^ par((k+1)^k)como

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

Usando bcomo la variable en la que estamos almacenando la paridad, esto parece

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

Escribiendo el código

Poniendo esto junto en el código, comenzamos ky el bit de paridad ben ambos 0, luego imprimimos n=2*k+by actualizamos repetidamente b=b^((k+1)^k)%3y k=k+1.

46 bytes

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

Pruébalo en línea!

Hemos eliminado parens alrededor k+1de ((k+1)^k)%3porque Python precedencia hace la adición primero de todos modos, raro como parece.

Mejoras de codigo

Sin embargo, podemos hacerlo mejor si trabajamos directamente con una sola variable n=2*k+by realizamos las actualizaciones directamente en ella. Hacer k+=1corresponde a n+=2. Y, la actualización b^=(k+1^k)%3corresponde a n^=(k+1^k)%3. Aquí, k=n/2antes de actualizar n.

44 bytes

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

Pruébalo en línea!

Podemos acortar n/2+1^n/2(recuerde que esto es (n/2+1)^n/2) reescribiendo

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

Como /2elimina el último bit, no importa si lo hacemos antes o después de xor-ing. Entonces, tenemos n^=(n+2^n)/2%3. Podemos ahorrar otro byte por señalar que en módulo 3, /2es equivalente a *2es equivalente a -, señalando que n+2^nes aun así la división es reducir a la mitad real y sin suelo. Esto dan^=-(n+2^n)%3

41 bytes

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

Pruébalo en línea!

Finalmente, podemos combinar las operaciones n^=c;n+=2en n=(n+2)^c, donde ces un poco. Esto funciona porque ^cactúa solo en el último bit y +2no le importa el último bit, por lo que las operaciones conmutan. Nuevamente, la precedencia nos permite omitir parens y escribir n=n+2^c.

39 bytes

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

Pruébalo en línea!

Esto le da a mi (xnor) una solución de 47 bytes y el pensamiento que me llevó a ello. No leas esto si quieres resolverlo tú mismo.

Una primera idea natural es iterar a través de los números del 0 al 799, imprimiendo solo aquellos con un número par de 1 en binario.

52 bytes

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

Pruébalo en línea!

Aquí, ~toma el complemento de bits para cambiar even<->oddel conteo y dar un valor de verdad solo en conteos pares.

Podemos mejorar este método generando todos los valores en lugar de filtrar. Observe que los valores de salida son los números del 0 al 399, cada uno con un bit agregado para igualar el número de 1 bit.

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

Entonces, el nnúmero th es 2*n+bcon uno b=0o con b=1. El bit bse puede encontrar contando 1los bits ny tomando el módulo de conteo 2.

49 bytes

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

Pruébalo en línea!

Podemos cortar los 2 bytes para 2*iterar 0,2,4,..., lo que no da la posibilidad de contar 1. Podemos hacer esto usando un execciclo que se ejecuta 400 veces y aumentando nen 2 cada ciclo.

47 bytes

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

Pruébalo en línea!

Y esa es mi solución de 47 bytes. Sospecho que la mayoría, si no todas las otras soluciones de 47 bytes son iguales.

Presentación de Python 3 de llhuii

Estas son las presentaciones de Python 3 para Evil Numbers al momento de escribir:

llhuii probablemente portó su truco a Python 3, y se le ocurrió una solución que es

• 3 bytes más largos que su solución Python 2, y
• tiene 45 - (25 + 18) = 2 bytes de espacio en blanco.

Portando el 47B de xnor a Python 3 literalmente, obtenemos este 50B:

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

Lo envié como ppcg(xnor). (Agrega paréntesis execy print, que ahora son funciones). Tiene estadísticas de código diferentes de las otras respuestas de Python 3, que tienen una cierta cantidad de espacio en blanco. ¡Interesante!

Sin embargo, hay una forma más corta de reescribirlo ( exectiende a perder su ventaja competitiva en Python 3):

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

Son 49 bytes. Lo envié como ppcg(xnor,alternative). ¡Esto tiene dos bytes de espacio en blanco, al igual que la respuesta de llhui! Esto me lleva a creer que la respuesta de Python 3 de llhuii se parece a esto (nueva línea, luego un whilebucle). Entonces, llhuii probablemente se usó execen Python 2 y whileen Python 3, al igual que nosotros; Esto explica la discrepancia de espacios en blanco.

Nuestro 47B se convirtió en un 49B en Python 3. Lo interesante, ahora, es que el 42B de llhuii no se convirtió en un 44B, ¡se convirtió en un 45B! Algo sobre la solución de llhuii toma un byte extra en Python 3. Esto podría significar una variedad de cosas.

• Lo primero que viene a la mente es la división : tal vez llhuii usa /en Python 2, que se convirtió //en Python 3. (Si están contando en dos como nosotros, ¿ n/2podría usarse para nretroceder un poco hacia la derecha?)

• La otra cosa que viene a la mente es operadores unarios después de la impresión . Nuestro se print blahconvirtió en print(blah)(1 byte extra), pero si llhuii escribió algo así como print~-blahen Python 2, se convertiría print(~-blah)en Python 3.

• Tal vez hay otras ideas. Por favor hagamelo saber.

Estadísticas de código para todas las soluciones Py3, incluida la mía ahora:

Otros enfoques

1) Usando una fórmula para A001969

En lugar de convertir a binario, podría ser posible aprovechar la siguiente fórmula (de 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

Soy muy malo jugando al golf en Python, así que ni siquiera voy a intentarlo. Pero aquí hay un intento rápido en JS.

^{NB: No creo que sea una presentación JS válida, ya que solo está llenando una matriz sin mostrarla. Y aun así, es 5 bytes más largo que la mejor solución JS actual (que es de 45 bytes). Pero ese no es el punto aquí de todos modos.}

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

Espero que pueda dar algo de inspiración.

Usar una matriz probablemente no sea una buena idea porque debe inicializarse y actualizarse. Podría ser más eficiente (en cuanto al tamaño del código) usar una función recursiva , lo que explicaría por qué la solución ganadora está tomando más tiempo que las otras.

2) Construyendo la secuencia Thue-Morse con sustituciones

En teoría, este código debería funcionar:

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

Pruébalo en línea! (versión ejecutable limitada a 20 términos)

Calcula la secuencia Thue-Morse con sustituciones consecutivas y busca la posición de 1 (Números malvados) en el mismo bucle.

Pero:

• Es demasiado largo en su forma actual
• Rápidamente conduce a un desbordamiento de memoria

3) Construyendo la secuencia Thue-Morse con operaciones bit a bit

A partir de la definición directa de Wikipedia de la secuencia Thue-Morse , he llegado a este algoritmo (volviendo a JS ... lo siento):

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

donde hacemos un seguimiento de la maldad actual de la secuencia en e y utilizamos 170 como una máscara de bits de bits extraños en un byte.

Enfoque de contadores anidados

Tengo una idea para un enfoque diferente, pero no tengo suficiente experiencia en el golf de pitón, así que lo dejaré aquí para que ustedes lo consideren como otro posible punto de partida para el golf.

La idea no golfista:

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

Pruébalo en línea!

Nueve niveles de profundidad de anidación, todos los bucles son iguales, por lo que en mi opinión deberían ser construidos por exec"something"*9+"deepest stuff". En la práctica, no sé si es posible hacer algo así con un ciclo for.

Cosas a considerar para jugar al golf:

• tal vez exista alguna otra posibilidad de hacer un ciclo dos veces que no sea un bucle for (probé un enfoque tipo quine con la cadena que se ejecutará y se pasó a sí misma como un argumento de formato dos veces, pero mi cabeza explotó).

• también podría haber una mejor alternativa if n<800:, que es necesaria aquí porque de lo contrario seguiríamos imprimiendo números malvados hasta 2 ^ 10

Idea: paridad de bits más corta

Se necesitan muchos caracteres para bin(n).count('1')%2calcular la paridad del recuento de bits. Tal vez una forma aritmética sea más corta, especialmente dada una longitud de bits limitada.

Una manera linda de la misma longitud es int(bin(n)[2:],3)%2interpretar el valor binario como base 3(o cualquier base impar). Desafortunadamente, 4 de los bytes se gastan eliminando el 0bprefijo. También funciona para hacer int(bin(n)[2:])%9%2.

Otra idea viene de combinar bits usando xor. Si ntiene representación binaria abcdefghi, entonces

n/16 = abcde
n%16 =  fghi

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

Entonces, r=n/16^n%16es malo si y solo si nes malo. Entonces podemos repetir eso como s=r/4^r%4un valor sen el 0,1,2,3cual 1y 2no son malvables, comprobable con 0<s<3.

52 bytes

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

Pruébalo en línea!

Esto resultó mucho más tiempo. Sin embargo, hay muchos botones para girar sobre cómo dividir el número, cómo verificar el número final (tal vez una tabla de búsqueda basada en bits). Sin embargo, sospecho que estos solo pueden llegar tan lejos.

Por construcción, n+n^nsiempre es malo, pero mis pobres habilidades en Python solo podrían llegar a una solución de 61 bytes:

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

Gracias a @Peilonrayz por guardar 5 bytes y a @ Mr.Xcoder por guardar 1 byte:

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

Idea: A006068 ("a (n) está codificado en gris en n")

La idea de Neil de ordenar todo 2n XOR nme intrigó, así que traté de encontrar los índices detrás de este tipo. Escribí este código , y revela que podemos escribir algo como esto:

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

¿Dónde a(n)está A006068 (n). Pruébalo en línea!

Sin embargo, esto supone que tenemos una forma corta de calcular A006068. Esto ya es de 38 bytes, suponiendo que podamos calcularlo en 4 bytes (la a(n)parte). La implementación real (en el encabezado TIO) es mucho más larga que eso. No hay mucha esperanza para esto, creo.

Idea: Reducir sobre XOR

Si haces XOR todos los fragmentos njuntos, será 0para el mal y 1para el no mal. Puede hacer esto con una función recursiva (que puede haber tomado más tiempo), de esta manera:

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

Esto devuelve 1 para el mal.

Eso es 35 bytes y comprueba si un número es malo o no. Desafortunadamente, filterya es de 6 bytes, por lo que esta no era la solución óptima literalmente, pero esta idea probablemente se pueda jugar.

Método de sustitución: {1 -> {1, -1}, -1 -> {-1, 1}}

También puede hacer esta sustitución 10 veces {1 -> {1, -1}, -1 -> {-1, 1}}, luego aplanar y verificar las posiciones de 1

aquí está el código matemático

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