Esta é uma pergunta de dicas para jogar golfe em Python, referente à questão dos números maus no Anarchy Golf .

Um número é ruim se sua expansão binária tiver um número par de 1's. O desafio é imprimir os primeiros 400 números malignos 0,3,5,...,795,797,798, um por linha.

Os envios do Python 2 são liderados pelo llhuii com uma solução de 42 bytes. O próximo melhor é 46 bytes por mitchs, seguidos por cinco envios de 47 bytes. Parece que llhuii encontrou algo verdadeiramente mágico que iludiu muitos jogadores fortes de Python por mais de 2 anos. Salvar 4 ou 5 bytes é enorme para um golfe tão curto.

Eu ainda estou em 47 bytes. Espero que possamos resolver esse quebra-cabeça como uma comunidade. Se recebermos uma resposta em conjunto, eu a enviaria com o nome de todos os que contribuíram. Uma resposta a essa pergunta pode ser um pedaço de código ou uma nova idéia ou um pedaço de análise. Se você é llhuii, por favor, não estrague tudo para nós ainda.

Embora as submissões não sejam reveladas porque esse problema é Infinito, recebemos algumas pistas. O envio vencedor levou 0,1699 segundos para ser executado, muito mais tempo do que qualquer outro, sugerindo um método ineficiente. Nas estatísticas de bytes, dos 42 caracteres, 23 são alfanuméricos [0-9A-Za-z]e 19 são símbolos ASCII. Isso significa que não há espaço em branco na solução do llhuii.

Você pode testar seu código na página do problema , escolhendo Python na lista suspensa de idiomas ou carregando um .pyarquivo. Observe que:

• Python 2.7 é usado
• Seu código deve ser um programa completo que imprima
• Não há entrada para este problema, como complexidade kolmogorov
• Seu programa apenas precisa imprimir os 400 valores, conforme indicado, mesmo que isso ocorra com valores maiores
• Os programas têm 2 segundos para executar
• Os programas podem terminar com erro
• Você pode usar exec; o "exec é negado" refere-se ao shell exec

Esta não é a mesma solução que a do llhuii, mas também tem 42 bytes de comprimento.

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

Experimente online!

Graças a @ JonathanFrech, estamos agora com 40 bytes.

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

Experimente online!

Há outro byte a ser salvo, totalizando 39.

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

Experimente online!

Obtendo 39 bytes

Esta é uma explicação de como obtive uma solução de 39 bytes, que Dennis e JonathanFrech encontraram separadamente também. Ou melhor, explica como alguém poderia chegar à resposta em retrospectiva, de uma maneira muito melhor do que o meu caminho real para ela, que estava cheio de raciocínio enlameado e becos sem saída.

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

Escrevendo isso um pouco menos e com mais parênteses, isso se parece com:

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

Paridades de bits

Começamos com uma idéia da minha solução de 47 bytes para gerar todos os números do formulário, n=2*k+bonde kconta 0,1,...,399e bé um bit de paridade que torna o número geral de 1s iguais.

Vamos escrever par(x)para a paridade de bits de x, ou seja, xor ( ^) em todos os bits x. Isso é 0 se houver um número par de 1 bits (número é mau) e 1 se houver um número ímpar de 1 bits. Pois n=2*k+btemos que par(n) = par(k)^b, para alcançar o mal par(n)==0, precisamos b=par(k), isto é, o último pedaço de nser a paridade de bits dos bits anteriores.

Meus primeiros esforços no golfe foram expressar o par(k), primeiro diretamente com bin(k).count('1')%2e depois com a manipulação de bits .

Atualizações de paridade

Ainda assim, não parecia haver uma expressão curta. Em vez disso, ajudou a perceber que há mais informações para trabalhar. Em vez de apenas calcular a paridade de bits do número atual,

k  ---->  par(k)

podemos atualizar o bit de paridade como incrementar ka k+1.

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

Ou seja, como estamos contando k=0,1,2,..., precisamos apenas manter a paridade de bits atual, em vez de calculá-la do zero a cada vez. A atualização de paridade de bits par(k+1)^par(k)é a paridade do número de bits ativados passando de kpara k+1, isto é 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

Agora precisamos calcular par((k+1)^k). Pode parecer que não chegamos a lugar algum porque a paridade de bits de computação é exatamente o problema que estamos tentando resolver. Mas, os números expressos como (k+1)^ktêm a forma 1,3,7,15,.., isto é, um abaixo da potência de 2, um fato frequentemente usado em hacks de bits . Vamos ver porque é isso.

Quando incrementamos k, o efeito dos carregamentos binários é inverter o último 0e tudo 1à sua direita, criando um novo líder, 0se não houver. Por exemplo, peguek=43=0b101011

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

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

As colunas que causam um transporte estão marcadas com *. Eles 1mudam para 0ae transmitem um bit de carry 1, que continua propagando para a esquerda até atingir um 0in k, que muda para 1. Quaisquer bits mais à esquerda não são afetados. Assim, quando k^(k+1)verifica que picaram posições mudar kpara k+1, ele encontra as posições da extrema direita 0eo 1's à direita. Ou seja, os bits alterados formam um sufixo, portanto, o resultado é 0 seguido de um ou mais 1. Sem os zeros à esquerda, existem números binários 1, 11, 111, 1111, ...abaixo de uma potência de 2.

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

Agora que entendemos que isso (k+1)^ké limitado 1,3,7,15,..., vamos encontrar uma maneira de calcular a paridade de bits desses números. Aqui, um fato útil é esse 1,2,4,8,16,...módulo alternativo 3entre 1e 2, desde 2==-1 mod 3. Então, pegar 1,3,7,15,31,63...módulos 3dá 1,0,1,0,1,0..., que são exatamente suas paridades de bits. Perfeito!

Então, podemos fazer a atualização par(k+1) = par(k) ^ par((k+1)^k)como

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

Usando bcomo a variável em que estamos armazenando a paridade, isso parece

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

Escrevendo o código

Juntando isso no código, iniciamos ke o bit de paridade em bat 0, depois imprimimos n=2*k+be atualizamos repetidamente b=b^((k+1)^k)%3e k=k+1.

46 bytes

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

Experimente online!

Nós removemos parênteses em torno k+1de ((k+1)^k)%3porque Python precedência faz a adição primeiro de qualquer maneira, estranho quanto parece.

Aprimoramentos de código

Podemos fazer melhor trabalhando diretamente com uma única variável n=2*k+be executando as atualizações diretamente nela. Fazer k+=1corresponde a n+=2. E, a atualização b^=(k+1^k)%3corresponde a n^=(k+1^k)%3. Aqui, k=n/2antes de atualizar n.

44 bytes

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

Experimente online!

Podemos encurtar n/2+1^n/2(lembre-se disso (n/2+1)^n/2) reescrevendo

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

Como /2remove o último bit, não importa se o fazemos antes ou depois do xoring. Então nós temos n^=(n+2^n)/2%3. Podemos salvar outro byte observando que modulo 3, /2é equivalente a *2equivale a -, observando que n+2^né mesmo assim, a divisão é reduzir para metade real, sem pavimentação. Isto dán^=-(n+2^n)%3

41 bytes

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

Experimente online!

Finalmente, podemos combinar as operações n^=c;n+=2em n=(n+2)^c, onde cestá um pouco. Isso funciona porque ^catua apenas no último bit e +2não se importa com o último bit, portanto as operações são comutadas. Novamente, a precedência permite omitir parênteses e escrever n=n+2^c.

39 bytes

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

Experimente online!

Isso fornece minha solução de 47 bytes (xnor) e o pensamento que me levou a ela. Não leia isso se você quiser descobrir isso sozinho.

Uma primeira idéia natural é percorrer os números de 0 a 799, imprimindo apenas aqueles com um número par de 1's em binário.

52 bytes

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

Experimente online!

Aqui, o ~pega o complemento de bit para mudar even<->odda contagem e fornecer um valor verdadeiro apenas nas contagens pares.

Podemos melhorar esse método gerando todos os valores em vez de filtrar. Observe que os valores de saída são os números de 0 a 399, cada um com um bit acrescentado para igualar o número de 1 bits.

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

Portanto, o nnúmero th é 2*n+bcom b=0ou b=1. O bit bpode ser encontrado contando 1s nos bits de ne tomando o módulo de contagem 2.

49 bytes

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

Experimente online!

Podemos cortar os 2 bytes 2*iterando sobre 0,2,4,..., o que não corre o risco de contar 1s. Podemos fazer isso usando um execloop que corre 400 vezes e aumenta n2 em cada loop.

47 bytes

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

Experimente online!

E essa é a minha solução de 47 bytes. Eu suspeito que a maioria, se não todas as outras soluções de 47 bytes, são iguais.

Envio do Python 3 de llhuii

Aqui estão os envios do Python 3 para o Evil Numbers no momento da redação deste artigo:

O llhuii provavelmente portou seu truque para o Python 3 e encontrou uma solução que é

• 3 bytes a mais que a solução Python 2 e
• possui 45 - (25 + 18) = 2 bytes de espaço em branco.

Portando 47B do xnor para o Python 3 literalmente, obtemos este 50B:

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

Enviei como ppcg(xnor). (Acrescenta parênteses para exece print, que agora são funções.) Tem diferentes estatísticas de código de outros Python 3 respostas, que todos têm uma certa quantidade de espaço em branco neles. Interessante!

Existe uma maneira mais curta de reescrevê-lo ( exectende a perder sua vantagem competitiva no Python 3):

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

São 49 bytes. Enviei como ppcg(xnor,alternative). Isso tem dois bytes de espaço em branco, assim como a resposta do llhui! Isso me leva a crer que a resposta do llhuii em Python 3 se parece com isso (nova linha, depois um whileloop). Portanto, o llhuii provavelmente é usado execno Python 2 e whileno Python 3, assim como nós; isso explica a discrepância de espaço em branco.

Nosso 47B se tornou um 49B em Python 3. O que é interessante agora é que o 42B de llhuii não se tornou um 44B, se tornou um 45B! Alguma coisa na solução do llhuii exige um byte extra no Python 3. Isso pode significar uma variedade de coisas.

• A primeira coisa que vem à mente é a divisão : talvez o llhuii use /no Python 2, que se tornou //no Python 3. (Se eles estão contando em pares como nós, então n/2pode ser usado para nvoltar um pouco à direita?)

• A outra coisa que vem à mente são os operadores unários após a impressão . Nosso print blahtornou-se print(blah)(1 byte extra), mas se llhuii escreveu algo como print~-blahno Python 2, ele se tornou print(~-blah)no Python 3.

• Talvez haja outras idéias. Por favor deixe-me saber.

Estatísticas de código para todas as soluções Py3, incluindo as minhas agora:

Outras abordagens

1) Usando uma fórmula para A001969

Em vez de converter para binário, pode ser possível tirar proveito da seguinte fórmula (do 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

Eu sou muito ruim em jogar golfe em Python, então nem vou tentar. Mas aqui está uma tentativa rápida em JS.

^{NB: Eu não acho que seria uma submissão JS válida, pois está apenas preenchendo uma matriz sem exibi-la. E, mesmo assim, é 5 bytes mais longo que a melhor solução JS atual (que é de 45 bytes). Mas esse não é o ponto aqui de qualquer maneira.}

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 possa dar alguma inspiração.

Usar uma matriz provavelmente não é uma boa ideia, pois precisa ser inicializado e atualizado. Pode ser mais eficiente (em tamanho de código) usar uma função recursiva , o que explicaria por que a solução vencedora está demorando mais tempo do que as outras.

2) Construindo a sequência Thue-Morse com substituições

Em teoria, esse código deve funcionar:

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

Experimente online! (versão executável limitada a 20 termos)

Ele calcula a sequência Thue-Morse com substituições consecutivas e procura a posição dos 1s (Números do Mal) no mesmo loop.

Mas:

• É muito longo em sua forma atual
• Isso leva rapidamente a um estouro de memória

3) Construindo a sequência Thue-Morse com operações bit a bit

Começando pela Definição Direta da Wikipedia da sequência Thue-Morse , cheguei a esse algoritmo (voltando ao JS ... desculpe):

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

onde mantemos o controle da maldade atual da sequência em e e usamos 170 como uma máscara de bits de bits ímpares em um byte.

Abordagem de contadores aninhados

Eu tenho uma idéia para uma abordagem diferente, mas não tenho experiência suficiente no golfe em python, então deixarei aqui para que vocês considerem como outro possível ponto de partida para o golfe.

A ideia não destruída:

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

Experimente online!

Nove níveis de profundidade de aninhamento, todos os loops são os mesmos, portanto, na minha mente, eles devem ser construídos exec"something"*9+"deepest stuff". Na prática, não sei se é possível fazer algo assim com um ciclo for.

Coisas a considerar para o golfe:

• talvez exista alguma outra possibilidade de pedalar duas vezes além de um loop for (tentei uma abordagem semelhante à de um quine com a string a ser executada passada para si mesma como um argumento de formatação duas vezes, mas minha cabeça explodiu).

• também poderia haver uma alternativa melhor if n<800:, o que é necessário aqui, porque, caso contrário, continuaríamos imprimindo números ruins até 2 ^ 10

Ideia: Paridade de bits mais curta

São necessários muitos caracteres para bin(n).count('1')%2calcular a paridade da contagem de bits. Talvez uma maneira aritmética seja mais curta, especialmente considerando um comprimento de bit limitado.

Um jeito bonito e do mesmo comprimento é int(bin(n)[2:],3)%2interpretar o valor binário como base 3(ou qualquer base ímpar). Infelizmente, 4 dos bytes são gastos removendo o 0bprefixo. Também trabalha para fazer int(bin(n)[2:])%9%2.

Outra idéia vem da combinação de bits usando xor. Se ntiver representação binária abcdefghi, então

n/16 = abcde
n%16 =  fghi

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

Então, r=n/16^n%16é mau se e somente se né mau. Podemos então repetir isso como s=r/4^r%4, um valor sem 0,1,2,3, do qual 1e 2não é mau, verificável com 0<s<3.

52 bytes

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

Experimente online!

Isso acabou por muito mais tempo. Existem muitos botões para girar sobre como dividir o número, como verificar o número final (talvez uma tabela de pesquisa baseada em bits). Eu suspeito que estes só podem ir tão longe.

Por construção, n+n^né sempre ruim, mas minhas habilidades ruins em Python só conseguiam uma solução de 61 bytes:

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

Agradecemos a @Peilonrayz por salvar 5 bytes e a @ Mr.Xcoder por salvar 1 byte:

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

Idéia: A006068 ("a (n) é codificado em cinza em n")

A idéia de Neil de classificar tudo 2n XOR nme intrigou, então tentei encontrar os índices por trás desse tipo. Eu escrevi este código , e revela que podemos escrever algo como isto:

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

Onde a(n)está A006068 (n). Experimente online!

No entanto, isso pressupõe que temos uma maneira curta de calcular o A006068. Já são 38 bytes, supondo que possamos calculá-lo em 4 bytes (a a(n)parte). A implementação real (no cabeçalho do TIO) é muito mais longa que isso. Acho que não há muita esperança nisso.

Ideia: reduzir sobre o XOR

Se você XOR todos os pedaços njuntos, será 0para o mal e 1para o não-mal. Você pode fazer isso com uma função recursiva (que pode levar mais tempo?), Assim:

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

Isso retorna 1 para o mal.

São 35 bytes e verifica se um número é ou não mau. Infelizmente, ele filterjá tem 6 bytes, portanto essa não foi a solução ideal literalmente, mas essa ideia provavelmente pode ser aproveitada.

Método de substituição: {1 -> {1, -1}, -1 -> {-1, 1}}

Você também pode fazer essa substituição 10 vezes {1 -> {1, -1}, -1 -> {-1, 1}}, achatar e verificar as posições dos 1s

aqui está o código mathematica

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