To jest pytanie z poradami do gry w golfa w Pythonie, dotyczące pytania zła liczba na Anarchy Golf .

Liczba jest zła, jeśli jej rozwinięcie binarne ma parzystą liczbę 1. Wyzwanie polega na wydrukowaniu pierwszych 400 złych liczb 0,3,5,...,795,797,798, po jednym w wierszu.

Zgłoszenia w języku Python 2 są prowadzone przez llhuii z 42-bajtowym rozwiązaniem. Następny najlepszy to 46 bajtów po mitchu, a następnie pięć 47-bajtowych zgłoszeń. Wygląda na to, że Lhuhu odkrył coś naprawdę magicznego, co wymyka się wielu silnym golfistom Python przez ponad 2 lata. Oszczędność 4 lub 5 bajtów jest ogromna jak na tak krótki golf.

Nadal mam 47 bajtów. Mam nadzieję, że uda nam się złamać tę łamigłówkę jako społeczność. Jeśli otrzymamy odpowiedź wspólnie, prześlę ją pod nazwiskami wszystkich, którzy wnieśli swój wkład. Odpowiedź na to pytanie może być fragmentem kodu, nowym pomysłem lub analizą. Jeśli jesteś llhuii, nie psuj tego jeszcze dla nas.

Chociaż zgłoszenia nie zostały ujawnione, ponieważ ten problem jest nieskończony, otrzymaliśmy kilka wskazówek. Zwycięskie zgłoszenie zajęło 0,1699 sekundy, znacznie dłużej niż jakikolwiek inny, co sugeruje nieefektywną metodę. Ze statystyk bajtów, spośród 42 znaków, 23 to znaki alfanumeryczne, [0-9A-Za-z]a 19 to symbole ASCII. Oznacza to, że w rozwiązaniu Lhuhu nie ma białych znaków.

Możesz przetestować swój kod na stronie problemu , wybierając Python z menu rozwijanego języka lub przesyłając .pyplik. Uwaga:

• Używany jest Python 2.7
• Twój kod musi być pełnym programem, który drukuje
• Nie ma danych wejściowych dla tego problemu, takich jak złożoność kolmogorowa
• Twój program musi po prostu wydrukować 400 podanych wartości, nawet jeśli spowodowałoby to uszkodzenie większych wartości
• Programy mają 2 sekundy do uruchomienia
• Programy mogą zakończyć się z błędem
• Możesz użyć exec; „exec jest odrzucony” odnosi się do powłoki exec

To nie jest to samo rozwiązanie co llhuii, ale ma również 42 bajty.

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

Wypróbuj online!

Dzięki @JonathanFrech mamy teraz 40 bajtów.

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

Wypróbuj online!

Jest jeszcze jeden bajt do zapisania, w sumie 39.

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

Wypróbuj online!

Zdobycie 39 bajtów

To jest wyjaśnienie, w jaki sposób otrzymałem 39-bajtowe rozwiązanie, które Dennis i JonathanFrech również znaleźli osobno. A raczej wyjaśnia, w jaki sposób można dojść do odpowiedzi z perspektywy czasu, w sposób o wiele ładniejszy niż moja faktyczna ścieżka do niej, pełna błotnego rozumowania i ślepych zaułków.

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

Pisząc to trochę mniej golfa i więcej parens, wygląda to tak:

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

Bit parzystości

Zaczynamy od pomysłu z mojego 47-bajtowego rozwiązania, aby wypisywać wszystkie liczby w postaci, w n=2*k+bktórej się kliczy 0,1,...,399i bjest bitem parzystości, który sprawia, że ​​ogólna liczba jedynek jest parzysta.

Napiszmy par(x)na bit parzystości z x, czyli XOR ( ^) wszystkich bitów x. Jest to 0, jeśli liczba parzysta jest 1-bitowa (liczba jest zła), a 1, jeśli liczba parzysta jest 1-bitowa. Ponieważ n=2*k+bmamy par(n) = par(k)^b, więc aby osiągnąć zło par(n)==0, potrzebujemy b=par(k), tzn. Ostatni bit nto parzystość bitów poprzednich bitów.

Moje pierwsze starania w golfa były wyrażającym par(k), najpierw bezpośrednio z bin(k).count('1')%2, a następnie bit manipulacji .

Aktualizacje parzystości

Wydawało się jednak, że nie było krótkiego wyrazu. Zamiast tego pomógł sobie uświadomić, że jest więcej informacji do pracy. Zamiast obliczać parzystość bitową bieżącej liczby,

k  ---->  par(k)

możemy zaktualizować bit parzystości jak możemy zwiększyć kdo k+1.

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

Oznacza to, że ponieważ zliczamy k=0,1,2,..., musimy jedynie zachować bieżącą parzystość bitową, a nie za każdym razem obliczać ją od zera. Aktualizacja parzystości bitów par(k+1)^par(k)to parzystość liczby bitów przechodzących od kdo k+1, to znaczy par((k+1)^k).

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

Forma (k+1)^k

Teraz musimy obliczyć par((k+1)^k). Może się wydawać, że nigdzie nie doszliśmy, ponieważ parzystość bitów to problem, który staramy się rozwiązać. Ale liczby wyrażone jako (k+1)^kmają postać 1,3,7,15,.., czyli jeden poniżej potęgi 2, fakt często używany w bitowych hackach . Zobaczmy, dlaczego tak jest.

Kiedy zwiększamy k, efektem przeniesień binarnych jest odwrócenie ostatniego 0i wszystkich 1po jego prawej stronie, tworząc nowe prowadzenie, 0jeśli nie było żadnego. Na przykład weźk=43=0b101011

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

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

Kolumny powodujące przenoszenie są oznaczone symbolem *. Mają one 1zmieni się 0i przechodzą na kawałku przeniesienia 1, który utrzymuje rozmnożeniowego lewo, aż natrafi 0in k, która zmienia się 1. Nie ma to wpływu na bity dalej po lewej stronie. Tak więc, gdy k^(k+1)kontrole, które nieco zmieniają pozycje kna k+1to znajdzie pozycje na prawo 0i na 1„s po prawej stronie. Oznacza to, że zmienione bity tworzą przyrostek, więc wynikiem są 0, po których następuje jeden lub więcej 1. Bez wiodących zer istnieją liczby binarne, 1, 11, 111, 1111, ...które są o jeden poniżej potęgi 2.

Przetwarzanie danych par((k+1)^k)

Teraz, gdy rozumiemy, że (k+1)^kjest to ograniczone 1,3,7,15,..., znajdźmy sposób na obliczenie parzystości bitowej takich liczb. Przydatnym faktem jest to, że 1,2,4,8,16,...naprzemiennie modulo 3między 1i 2, ponieważ 2==-1 mod 3. Biorąc więc 1,3,7,15,31,63...modulo 3daje 1,0,1,0,1,0..., które są dokładnie ich bitowymi parzystościami. Doskonały!

Możemy więc wykonać aktualizację par(k+1) = par(k) ^ par((k+1)^k)jako

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

Używając bjako zmiennej, w której przechowujemy parzystość, wygląda to tak

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

Pisanie kodu

Łącząc to w kod, zaczynamy ki bit parzystości bzarówno w 0, a następnie wielokrotnie drukujemy n=2*k+bi aktualizujemy b=b^((k+1)^k)%3i k=k+1.

46 bajtów

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

Wypróbuj online!

Usunęliśmy pareny, ponieważ pierwszeństwok+1 w Pythonie jest dodawane jako pierwsze, co dziwne, jak się wydaje.((k+1)^k)%3

Ulepszenia kodu

Możemy to zrobić lepiej, pracując bezpośrednio z jedną zmienną n=2*k+bi wykonując aktualizacje bezpośrednio na niej. Robienie k+=1odpowiada n+=2. I aktualizacja b^=(k+1^k)%3odpowiada n^=(k+1^k)%3. Tutaj k=n/2przed aktualizacją n.

44 bajty

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

Wypróbuj online!

Możemy skrócić n/2+1^n/2(pamiętaj, że jest (n/2+1)^n/2) poprzez przepisanie

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

Ponieważ /2usuwa ostatni bit, nie ma znaczenia, czy zrobimy to przed, czy po przeforsowaniu. Więc mamy n^=(n+2^n)/2%3. Możemy zaoszczędzić kolejny bajt, zauważając, że modulo 3, /2jest równoważne *2jest równoważne do -, zauważając, że n+2^nnawet tak, że podział jest o połowę bez podłogi. To dajen^=-(n+2^n)%3

41 bajtów

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

Wypróbuj online!

Wreszcie możemy połączyć operacje n^=c;n+=2w n=(n+2)^c, gdzie cjest trochę. Działa to, ponieważ ^cdziała tylko na ostatni bit i +2nie dba o ostatni bit, więc operacje dojeżdżają do pracy. Ponownie, pierwszeństwo pozwala nam pomijać pareny i pisać n=n+2^c.

39 bajtów

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

Wypróbuj online!

To daje moje (xnor) 47-bajtowe rozwiązanie i sposób myślenia, który mnie do tego doprowadził. Nie czytaj tego, jeśli chcesz to zrozumieć.

Naturalnym pierwszym pomysłem jest iteracja liczb od 0 do 799, wypisywanie tylko tych z parzystą liczbą 1 w postaci binarnej.

52 bajty

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

Wypróbuj online!

W tym ~przypadku bit uzupełnia się tak, aby przełączyć even<->oddliczenie i podać prawdziwą wartość tylko dla liczb parzystych.

Możemy ulepszyć tę metodę, generując wszystkie wartości zamiast filtrować. Zauważ, że wartościami wyjściowymi są liczby od 0 do 399, każda z bitem dołączonym, aby liczba 1 bitów była parzysta.

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

Tak więc, nliczba th jest albo 2*n+bz albo b=0albo b=1. Trochęb można znaleźć, licząc 1w bitach ni biorąc zliczanie modulo 2.

49 bajtów

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

Wypróbuj online!

Możemy przeciąć 2 bajty, 2*wykonując iterację 0,2,4,..., co nie daje szansy na zliczenie 1. Możemy to zrobić za pomocą execpętli, która działa 400 razy i rośnien o 2 w każdej pętli.

47 bajtów

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

Wypróbuj online!

I to jest moje 47-bajtowe rozwiązanie. Podejrzewam, że większość, jeśli nie wszystkie pozostałe 47-bajtowe rozwiązania są takie same.

llhuii's Python 3

Oto zgłoszenia Python 3 dotyczące Złych Liczb w momencie pisania:

llhuii prawdopodobnie przeniósł swoją sztuczkę na Python 3 i wymyślił takie rozwiązanie

• 3 bajty dłuższe niż ich rozwiązanie Python 2 oraz
• ma 45 - (25 + 18) = 2 bajty białych znaków.

Przenosząc xnor 47B do Pythona 3 dosłownie, otrzymujemy 50B:

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

Przesłałem to jako ppcg(xnor). (Dodaje nawiasy do execiprint , które są teraz funkcjami.) Ma inne statystyki kodu niż inne odpowiedzi w Pythonie 3, które zawierają pewne spacje. Ciekawy!

Jest jednak krótszy sposób na przepisanie go ( execw Pythonie 3 zwykle traci przewagę konkurencyjną):

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

Ma 49 bajtów. Przesłałem to jako ppcg(xnor,alternative). Ma dwa bajty białych znaków, podobnie jak odpowiedź llhui! To prowadzi mnie do przekonania, że ​​odpowiedź llhuii na Python 3 wygląda trochę tak (nowa linia, potem whilepętla). Więc llhuii prawdopodobnie używany execw Python 2 i whilePython 3, podobnie jak my; wyjaśnia to rozbieżność białych znaków.

Nasz 47B stał się 49B w Pythonie 3. Co ciekawe, llhuii 42B nie stał się 44B, stał się 45B! Coś w rozwiązaniu llhuii wymaga dodatkowego bajtu w Pythonie 3. Może to oznaczać różne rzeczy.

• Pierwszą rzeczą, która przychodzi mi na myśl, jest podział : może llhuii używa /w Pythonie 2, który stał się //w Pythonie 3. (Jeśli liczą się w dwójkę jak my, to n/2może być wykorzystany do przesunięcia no jeden bit w prawo?)

• Inną rzeczą, która przychodzi mi na myśl, jest jednoargumentowy operator po wydrukowaniu . Nasz print blahstał się print(blah)(1 bajt dodatkowy), ale jeśli llhuii napisałby coś print~-blahw Pythonie 2, stałby się print(~-blah)w Pythonie 3.

• Może są inne pomysły. Proszę daj mi znać.

Statystyki kodu dla wszystkich rozwiązań Py3, w tym teraz moje:

Inne podejścia

1) Korzystanie ze wzoru na A001969

Zamiast konwertować na binarne, może być możliwe skorzystanie z następującej formuły (z 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

Bardzo źle gram w golfa w Pythonie, więc nawet nie spróbuję. Ale tutaj jest szybka próba w JS.

^{NB: Nie sądzę, że byłoby to prawidłowe przesłanie JS, ponieważ po prostu wypełnia tablicę bez jej wyświetlania. Mimo to jest o 5 bajtów dłuższy niż obecne najlepsze rozwiązanie JS (45 bajtów). Ale i tak nie o to tutaj chodzi.}

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

Mam nadzieję, że może to dać inspirację.

Korzystanie z tablicy prawdopodobnie nie jest dobrym pomysłem, ponieważ należy ją zainicjować i zaktualizować. Zamiast tego może być bardziej wydajne (jeśli chodzi o rozmiar kodu) użycie funkcji rekurencyjnej , co tłumaczyłoby, dlaczego zwycięskie rozwiązanie zajmuje więcej czasu niż inne.

2) Budowanie sekwencji Thue-Morse z podstawieniami

Teoretycznie ten kod powinien działać:

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

Wypróbuj online!(dostępna wersja ograniczona do 20 warunków)

Oblicza sekwencję Thue-Morse'a z kolejnymi podstawieniami i szuka pozycji 1 (Liczb Zła) w tej samej pętli.

Ale:

• W swojej obecnej formie jest zdecydowanie za długi
• Szybko prowadzi to do przepełnienia pamięci

3) Budowanie sekwencji Thue-Morse za pomocą operacji bitowych

Zaczynając od bezpośredniej definicji sekwencji Thue-Morse'a w Wikipedii , doszedłem do tego algorytmu (wracając do JS ... przepraszam):

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

gdzie śledzimy aktualną zło sekwencji w ei używamy 170 jako maskę bitów nieparzystych bitów w bajcie.

Zbliża się zagnieżdżone liczniki

Mam pomysł na inne podejście, ale nie mam wystarczającego doświadczenia w golfie w Pythonie, więc zostawię to tutaj, abyście mogli rozważyć inny punkt wyjścia do gry w golfa.

Niegolfowany pomysł:

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

Wypróbuj online!

Dziewięć poziomów zagnieżdżenia, wszystkie pętle są takie same, więc moim zdaniem powinny je zbudować exec"something"*9+"deepest stuff". W praktyce nie wiem, czy można zrobić coś takiego za pomocą cyklu for.

Rzeczy do rozważenia podczas gry w golfa:

• może istnieje jakaś inna możliwość dwukrotnego przełączania poza pętlą for (próbowałem podejścia quine z wykonanym łańcuchem przekazywanym do siebie jako argument formatujący dwa razy, ale moja głowa eksplodowała).

• może być też lepsza alternatywa if n<800:, która jest tutaj potrzebna, ponieważ w przeciwnym razie drukowalibyśmy złe liczby do 2 ^ 10

Pomysł: krótsza parzystość bitów

Zajmuje to wiele postaci bin(n).count('1')%2Obliczenie parzystości liczby bitów . Być może sposób arytmetyczny jest krótszy, szczególnie biorąc pod uwagę ograniczoną długość bitów.

Uroczym sposobem jest int(bin(n)[2:],3)%2interpretowanie wartości binarnej jako podstawy 3(lub dowolnej nieparzystej podstawy). Niestety 4 bajty spędzają na usuwaniu 0bprefiksu. Działa to również do zrobieniaint(bin(n)[2:])%9%2 .

Kolejny pomysł pochodzi z łączenia bitów za pomocą xor. Jeśli nma reprezentację binarną abcdefghi, to

n/16 = abcde
n%16 =  fghi

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

Zatem r=n/16^n%16zło jest wtedy i tylko wtedy, gdy njest złe. Możemy powtórzyć, że jako s=r/4^r%4wartość sw 0,1,2,3, z czego 1i 2nie są złe, dostępne do kontroli z 0<s<3.

52 bajty

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

Wypróbuj online!

Okazało się to znacznie dłużej. Istnieje jednak wiele pokręteł do obrócenia, jak podzielić liczbę, jak sprawdzić ostateczną liczbę (być może tablica odnośników oparta na bitach). Podejrzewam, że mogą one pójść tylko tak daleko.

Z n+n^nzałożenia jest zawsze zły, ale moje słabe umiejętności w Pythonie mogły tylko wymyślić 61-bajtowe rozwiązanie:

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

Dzięki @Peilonrayz za zapisanie 5 bajtów i @ Mr.Xcoder za zapisanie 1 bajtu:

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

Pomysł: A006068 („a (n) ma szary kod w n”)

Pomysł Neila na uporządkowanie wszystkich 2n XOR nmnie zaintrygował, więc próbowałem znaleźć wskaźniki tego rodzaju. Napisałem ten kod i ujawnia, że ​​możemy napisać coś takiego:

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

Gdzie a(n)jest A006068 (n). Wypróbuj online!

Zakłada się jednak, że mamy krótką drogę do obliczenia A006068. To już 38 bajtów, zakładając, że możemy obliczyć go w 4 bajtach ( a(n)część). Rzeczywista implementacja (w nagłówku TIO) jest znacznie dłuższa. Myślę, że niewiele nadziei na to.

Pomysł: Zmniejsz XOR

Jeśli XOR wszystkie części nrazem, będzie to 0dla zła i 1dla nie-zła. Możesz to zrobić za pomocą funkcji rekurencyjnej (co mogło zająć więcej czasu?), Na przykład:

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

Zwraca 1 za zło.

To 35 bajtów i sprawdza, czy liczba jest zła. Niestety, filterma już 6 bajtów, więc nie było to optymalne rozwiązanie dosłownie, ale ten pomysł prawdopodobnie można zastosować w golfa.

Metoda podstawienia: {1 -> {1, -1}, -1 -> {-1, 1}}

Możesz również dokonać tej zamiany 10 razy {1 -> {1, -1}, -1 -> {-1, 1}}, a następnie spłaszczyć i sprawdzić pozycje 1

tutaj jest kod matematyczny

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