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!
