Это вопрос подсказки для игры в гольф в Python относительно вопроса о Evil Numbers на Anarchy Golf .

Число является злом, если его двоичное расширение имеет четное число единиц. Задача состоит в том, чтобы напечатать первые 400 злых чисел 0,3,5,...,795,797,798, по одному в строке.

Представления Python 2 возглавляются llhuii с 42-байтовым решением. Следующий лучший результат - 46 байтов за mitchs, сопровождаемые пятью 47-байтовыми представлениями. Кажется, что llhuii нашел нечто поистине волшебное, что ускользнуло от многих сильных игроков в Python более 2 лет. Экономия 4 или 5 байтов огромна для такого короткого гольфа.

Я все еще на 47 байтов. Я надеюсь, что мы сможем раскрыть эту загадку как сообщество. Если мы получим ответ совместно, я отправлю его под именами всех, кто внес свой вклад. Ответом на этот вопрос может быть фрагмент кода, новая идея или фрагмент анализа. Если вы llhuii, пожалуйста, не портите нам это.

Хотя представления не раскрываются, потому что эта проблема бесконечна, нам дают некоторые выводы. Победное представление заняло 0,1699 секунд, что намного дольше, чем любое другое, что указывает на неэффективный метод. Из статистики байтов, из 42 символов 23 являются буквенно-цифровыми [0-9A-Za-z]и 19 являются символами ASCII. Это означает, что в решении llhuii нет пробелов.

Вы можете проверить свой код на странице проблемы , выбрав Python из выпадающего списка языков или загрузив .pyфайл. Обратите внимание, что:

• Python 2.7 используется
• Ваш код должен быть полной программой, которая печатает
• Там нет ввода для этой проблемы, как колмогоров-сложности
• Ваша программа просто должна напечатать 400 значений, как указано, даже если она сломается на больших значениях
• Программы имеют 2 секунды для запуска
• Программы могут завершиться с ошибкой
• Вы можете использовать exec; «exec is denied» относится к оболочке exec

Это не то же самое решение, что и llhuii, но оно также имеет длину 42 байта.

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

Попробуйте онлайн!

Благодаря @JonathanFrech мы теперь на 40 байтах.

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

Попробуйте онлайн!

Есть еще один байт, который нужно сохранить, всего 39.

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

Попробуйте онлайн!

Получение 39 байтов

Это объяснение того, как я получил 39-байтовое решение, которое Деннис и Джонатан Фрех также нашли отдельно. Или, скорее, это объясняет, как можно прийти к ответу задним числом, намного лучше, чем мой настоящий путь к нему, который был полон грязных рассуждений и тупиков.

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

Написание этого немного меньше в гольфе и с большим количеством паренов, это выглядит так:

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

Битовые соотношения

Мы начнем с идеи из моего 47-байтового решения, чтобы вывести все числа в форме, в n=2*k+bкоторой происходит kобратный отсчет, 0,1,...,399и bэто бит четности, который делает общее число равным 1.

Напишем par(x)для бита четности из x, то есть XOR ( ^) все биты в x. Это 0, если есть четное число 1-бит (число - зло), и 1, если есть нечетное число 1-бит. Ибо n=2*k+bмы имеем par(n) = par(k)^b, поэтому для достижения зла par(n)==0нам нужно b=par(k), то есть последний бит nдолжен быть четным битом предыдущих битов.

Мои первые попытки были играть в гольф на экспрессирующие par(k), сначала непосредственно с bin(k).count('1')%2, а затем с битами .

Обновления четности

Тем не менее, казалось, не было короткого выражения. Вместо этого это помогло понять, что есть больше информации для работы. Вместо того, чтобы просто вычислять битовую четность текущего числа,

k  ---->  par(k)

мы можем обновить битовую четность при увеличении kдо k+1.

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

То есть, так как мы считаем k=0,1,2,..., нам просто нужно поддерживать текущий битовый паритет, а не вычислять его с нуля каждый раз. Обновление четности битов par(k+1)^par(k)- это четность количества бит, перевернутых при переходе от kк k+1, то есть par((k+1)^k).

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

Форма (k+1)^k

Теперь нам нужно вычислить par((k+1)^k). Может показаться, что мы ничего не получили, потому что вычисление четности битов - это именно та проблема, которую мы пытаемся решить. Но числа, выраженные как, (k+1)^kимеют форму 1,3,7,15,.., которая на единицу меньше степени 2, факт, часто используемый в битовых хакерских атаках . Давайте посмотрим, почему это так.

Когда мы увеличиваем k, эффект двоичных переносов состоит в том, чтобы инвертировать последние 0и все 1справа, создавая новое ведение, 0если их не было. Например, взятьk=43=0b101011

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

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

Столбцы, вызывающие перенос, отмечены значком *. Они 1изменяют на a 0и передают бит переноса 1, который продолжает распространяться влево до тех пор, пока не попадет 0в k, который изменится на 1. Любые биты дальше слева не затрагиваются. Таким образом, когда k^(k+1)проверяет , какие позиции бит изменить , kчтобы k+1он находит позиции крайнего правые 0и в 1«с до его права. То есть измененные биты образуют суффикс, поэтому результатом являются 0, за которыми следует одна или несколько единиц. Без ведущих нулей существуют двоичные числа 1, 11, 111, 1111, ..., которые на единицу меньше степени 2.

вычисления par((k+1)^k)

Теперь, когда мы понимаем, что (k+1)^kэто ограничено 1,3,7,15,..., давайте найдем способ вычислить битовую четность таких чисел. Здесь, полезный факт, что 1,2,4,8,16,...чередуются по модулю 3между 1и 2, так как 2==-1 mod 3. Итак, взятие 1,3,7,15,31,63...по модулю 3дает 1,0,1,0,1,0..., что в точности соответствует их битовым соотношениям. Отлично!

Итак, мы можем сделать обновление par(k+1) = par(k) ^ par((k+1)^k)как

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

Используя bв качестве переменной, в которой мы сохраняем четность, это выглядит так

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

Написание кода

Собирая это вместе в коде, мы начинаем kи бит четности bкак в 0, затем многократно печатаем n=2*k+bи обновляем b=b^((k+1)^k)%3и k=k+1.

46 байт

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

Попробуйте онлайн!

Мы убрали скобки вокруг k+1в ((k+1)^k)%3потому , что Python старшинство делает добавление первой в любом случае, странно , как это выглядит.

Улучшения кода

Хотя мы можем добиться большего, работая напрямую с одной переменной n=2*k+bи выполняя обновления непосредственно над ней. Делать k+=1соответствует n+=2. И, обновление b^=(k+1^k)%3соответствует n^=(k+1^k)%3. Здесь, k=n/2перед обновлением n.

44 байта

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

Попробуйте онлайн!

Мы можем сократить n/2+1^n/2(помните, что это (n/2+1)^n/2), переписав

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

Так как /2удаляет последний бит, не имеет значения, делаем ли мы это до или после копирования. Итак, у нас есть n^=(n+2^n)/2%3. Мы можем сохранить еще один байт, отметив , что по модулю 3, /2эквивалентно *2эквивалентно -, отметив , что n+2^nдаже поэтому разделение актуально сращивание без напольного покрытия. Это даетn^=-(n+2^n)%3

41 байт

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

Попробуйте онлайн!

Наконец, мы можем объединить операции n^=c;n+=2в n=(n+2)^c, где cнемного. Это работает, потому что ^cдействует только на последний бит и +2не заботится о последнем бите, поэтому операции коммутируют. Опять же, приоритет позволяет нам опускать парены и писать n=n+2^c.

39 байт

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

Попробуйте онлайн!

Это дает моё (xnor) 47-байтовое решение и мышление, которое привело меня к нему. Не читайте это, если вы хотите понять это самостоятельно.

Первая естественная идея - перебирать числа от 0 до 799, печатая только двоичные числа с четным числом 1.

52 байта

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

Попробуйте онлайн!

Здесь ~биты дополняют бит, чтобы включить even<->oddсчетчик и дать истинное значение только на четных счетах.

Мы можем улучшить этот метод, генерируя все значения вместо фильтрации. Обратите внимание, что выходные значения - это числа от 0 до 399, каждое из которых содержит бит, добавленный к четному числу 1 бит.

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

Итак, nномер th либо 2*n+bс либо, b=0либо b=1. Бит bможно найти, считая 1в битах nи считая по модулю 2.

49 байтов

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

Попробуйте онлайн!

Мы можем сократить 2 байта 2*, выполнив итерацию 0,2,4,..., что не повлияет на число 1. Мы можем сделать это, используя execцикл, который выполняется в 400 раз и увеличивая nна 2 каждый цикл.

47 байт

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

Попробуйте онлайн!

И это мое 47-байтовое решение. Я подозреваю, что большинство, если не все остальные 47-байтовые решения одинаковы.

представление питона 3 от lhuii

Вот Python 3 представления для Evil Numbers на момент написания:

llhuii, вероятно, перенесли свой трюк на Python 3 и придумали решение, которое

• На 3 байта длиннее, чем их решение на Python 2, и
• имеет 45 - (25 + 18) = 2 байта пробела.

Буквально портируя xnor 47B на Python 3, получаем 50B:

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

Я представил это как ppcg(xnor). (Он добавляет круглые скобки в execи print, которые теперь являются функциями.) Он имеет статистику кода, отличную от других ответов Python 3, в которых есть некоторое количество пробелов. Интересно!

Хотя есть более короткий способ переписать его ( execкак правило, теряет свое конкурентное преимущество в Python 3):

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

Это 49 байтов. Я представил это как ppcg(xnor,alternative). Это имеет два байта пробела, как и ответ llhui! Это заставляет меня поверить, что ответ llhuii на Python 3 выглядит примерно так ( whileперевод строки, затем цикл.) Таким образом, llhuii, вероятно, используется execв Python 2 и whileв Python 3, как и мы; это объясняет расхождение в пробелах.

Наш 47B стал 49B в Python 3. Теперь интересно то, что 42B llhuii не стал 44B, а стал 45B! Что-то в решении llhuii требует дополнительного байта в Python 3. Это может означать разные вещи.

• Первое, что приходит на ум, - это деление : может быть, llhuii использует /в Python 2, который стал //в Python 3. (Если они n/2считают по двое, как мы, то могли бы быть использованы для сдвига nназад вправо на один бит?)

• Еще одна вещь, которая приходит на ум, это унарные операторы после печати . Наш print blahстал print(blah)(дополнительно 1 байт), но если llhuii написал что-то вроде print~-blahPython 2, он стал бы print(~-blah)в Python 3.

• Может быть, есть другие идеи. Пожалуйста, дайте мне знать.

Статистика кода для всех решений Py3, включая мое сейчас:

Другие подходы

1) Использование формулы для A001969

Вместо преобразования в двоичный код можно воспользоваться следующей формулой (из 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

Я очень плохо играю в гольф на Python, поэтому даже не собираюсь пробовать. Но вот быстрая попытка в JS.

^{NB: Я не думаю, что это будет правильная отправка JS, поскольку она просто заполняет массив, не отображая его. И даже в этом случае он на 5 байт длиннее, чем текущее лучшее решение JS (которое составляет 45 байт). Но дело тут не в этом.}

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

Надеюсь, это может дать некоторое вдохновение.

Использование массива, вероятно, не очень хорошая идея, потому что его нужно инициализировать и обновить. Вместо этого может быть более эффективным (с точки зрения размера кода) использовать рекурсивную функцию , которая объясняет, почему выигрышное решение отнимает больше времени, чем другие.

2) Построение последовательности Туэ-Морса с подстановками

Теоретически этот код должен работать:

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

Попробуйте онлайн! (работоспособная версия ограничена 20 терминами)

Он вычисляет последовательность Туэ-Морса с последовательными заменами и ищет положение 1 (злых чисел) в том же цикле.

Но:

• Это слишком долго в его нынешнем виде
• Это быстро приводит к переполнению памяти

3) Построение последовательности Туэ-Морса с побитовыми операциями

Начиная с прямого определения последовательности Туэ-Морса из Википедии , я пришел к этому алгоритму (переключаясь обратно на JS ... извините):

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

где мы отслеживаем текущее зло последовательности в e и используем 170 как битовую маску нечетных битов в байте.

Подход с вложенными счетчиками

У меня есть идея для другого подхода, но я не достаточно опытен в игре в гольф на питоне, поэтому я оставлю это здесь, чтобы вы, ребята, рассмотрели в качестве еще одной возможной отправной точки для игры в гольф.

Нежелательная идея:

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

Попробуйте онлайн!

Глубина вложения девяти уровней, все петли одинаковы, поэтому, на мой взгляд, они должны быть построены exec"something"*9+"deepest stuff". На практике я не знаю, возможно ли сделать что-то подобное с циклом for.

Что нужно учитывать для игры в гольф:

• может быть, есть какая-то другая возможность циклически повторяться дважды, кроме цикла for (я пробовал похожий на квинну подход, когда выполняемая строка дважды передавалась сама себе в качестве аргумента форматирования, но моя голова взорвалась).

• может быть и лучшая альтернатива if n<800:, которая необходима здесь, потому что в противном случае мы будем печатать злые числа до 2 ^ 10

Идея: более короткое соотношение

Требуется много символов, bin(n).count('1')%2чтобы вычислить четность счета битов. Возможно, арифметический способ короче, особенно учитывая ограниченную длину в битах.

Милый способ такой же длины - int(bin(n)[2:],3)%2интерпретировать двоичное значение как основание 3(или любое нечетное основание). К сожалению, 4 байта тратятся на удаление 0bпрефикса. Это также работает, чтобы сделать int(bin(n)[2:])%9%2.

Другая идея исходит от объединения битов с использованием xor. Если nимеет двоичное представление abcdefghi, то

n/16 = abcde
n%16 =  fghi

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

Итак, r=n/16^n%16зло тогда и только тогда, когда nоно зло. Затем можно повторить , что , как s=r/4^r%4, значение sв 0,1,2,3, из которых 1и 2не являются злом, переключает с 0<s<3.

52 байта

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

Попробуйте онлайн!

Это оказалось намного дольше. Есть много ручек, чтобы повернуть, как разделить число, как проверить окончательное число (возможно, справочную таблицу на основе битов). Я подозреваю, что они могут пойти так далеко, хотя.

По построению, n+n^nэто всегда зло, но мои плохие навыки Python могли предложить только 61-байтовое решение:

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

Спасибо @Peilonrayz за сохранение 5 байтов и @ Mr.Xcoder за сохранение 1 байта:

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

Идея: A006068 («a (n) серым n»)

Идея Нейла сортировать все 2n XOR nзаинтриговала меня, поэтому я попытался найти показатели такого рода. Я написал этот код , и он показывает, что мы можем написать что-то вроде этого:

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

Где a(n)A006068 (н).Попробуйте онлайн!

Тем не менее, это предполагает, что у нас есть небольшой способ вычислить A006068. Это уже 38 байтов, при условии, что мы можем вычислить его в 4 байта ( a(n)часть). Реальная реализация (в заголовке TIO) намного длиннее. Думаю, не так много надежды на это.

Идея: уменьшить по XOR

Если вы XOR все биты nвместе, это будет 0для зла и 1не зла. Вы можете сделать это с помощью рекурсивной функции (которая может занять больше времени?), Например так:

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

Это возвращает 1 за зло.

Это 35 байтов, и проверяет, является ли число злым. К сожалению, filterуже 6 байтов, так что это не было оптимальным дословным решением, но эта идея, вероятно, может быть реализована.

Метод подстановки: {1 -> {1, -1}, -1 -> {-1, 1}}

Вы также можете сделать эту замену 10 раз {1 -> {1, -1}, -1 -> {-1, 1}}, затем сгладить и проверить позиции 1

вот код математики

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