Ini adalah pertanyaan kiat untuk bermain golf di Python tentang pertanyaan Nomor Jahat di Golf Anarki .

Angka jahat jika ekspansi binernya memiliki angka genap 1. Tantangannya adalah untuk mencetak 400 angka kejahatan pertama 0,3,5,...,795,797,798, satu per baris.

Pengiriman Python 2 dipimpin oleh llhuii dengan solusi 42 byte. Yang terbaik berikutnya adalah 46 byte oleh mitch, diikuti oleh lima pengiriman 47 byte. Tampaknya llhuii telah menemukan sesuatu yang benar-benar ajaib yang telah menghindari banyak pegolf Python yang kuat selama lebih dari 2 tahun. Menyimpan 4 atau 5 byte sangat besar untuk golf singkat.

Saya masih di 47 byte. Saya berharap kami dapat memecahkan teka-teki ini sebagai sebuah komunitas. Jika kami mendapat jawaban bersama, saya akan mengirimkannya di bawah nama semua orang yang berkontribusi. Jawaban untuk pertanyaan ini bisa berupa kode atau ide baru atau analisis. Jika Anda llhuii, tolong jangan merusaknya untuk kami.

Meskipun pengiriman tidak diungkapkan karena masalah ini tidak ada habisnya, kami diberi beberapa petunjuk. Pengajuan pemenang membutuhkan waktu 0,1699 detik untuk berjalan, lebih lama dari yang lainnya, menunjukkan metode yang tidak efisien. Dari statistik byte, dari 42 karakter, 23 adalah alfanumerik [0-9A-Za-z]dan 19 adalah simbol ASCII. Ini berarti tidak ada spasi putih dalam solusi llhuii.

Anda dapat menguji kode Anda pada halaman masalah , memilih Python dari dropdown bahasa atau mengunggah .pyfile. Perhatikan bahwa:

• Python 2.7 digunakan
• Kode Anda harus berupa program lengkap yang dicetak
• Tidak ada input untuk masalah ini, seperti kolmogorov-kompleksitas
• Program Anda hanya perlu mencetak 400 nilai seperti yang diberikan, bahkan jika itu akan merusak nilai yang lebih besar
• Program memiliki 2 detik untuk dijalankan
• Program dapat berakhir dengan kesalahan
• Anda dapat menggunakan exec; "exec ditolak" mengacu pada shell exec

Ini bukan solusi yang sama dengan llhuii, tetapi juga panjangnya 42 byte.

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

Cobalah online!

Terima kasih kepada @JonathanFrech, kami sekarang berada di 40 byte.

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

Cobalah online!

Ada byte lain yang harus disimpan, dengan total 39.

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

Cobalah online!

Mendapatkan 39 byte

Ini adalah penjelasan tentang bagaimana saya mendapatkan solusi 39-byte, yang ditemukan Dennis dan JonathanFrech secara terpisah. Atau, lebih tepatnya, itu menjelaskan bagaimana seseorang bisa sampai pada jawaban di belakang, dengan cara yang jauh lebih baik daripada jalan saya yang sebenarnya untuk itu, yang penuh dengan alasan berlumpur dan jalan buntu.

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

Menulis ini sedikit kurang golf dan dengan lebih banyak parens, ini seperti:

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

Paritas bit

Kita mulai dengan sebuah ide dari solusi 47-byte saya untuk menampilkan semua angka dari formulir di n=2*k+bmana kdihitung 0,1,...,399dan bmerupakan bit paritas yang membuat angka keseluruhan 1 genap.

Mari kita menulis par(x)untuk bit paritas dari x, itu adalah xor ( ^) semua bit dalam x. Ini adalah 0 jika ada angka genap 1-bit (angka itu jahat), dan 1 jika ada angka ganjil 1-bit. Karena n=2*k+b, kita harus par(n) = par(k)^b, untuk mencapai kejahatan yang par(n)==0kita butuhkan b=par(k), yaitu bit terakhir nuntuk menjadi bit paritas bit sebelumnya.

Upaya pertama saya dalam bermain golf adalah mengekspresikan par(k), pertama langsung dengan bin(k).count('1')%2, dan kemudian dengan sedikit manipulasi .

Pembaruan paritas

Tetap saja, sepertinya tidak ada ekspresi pendek. Alih-alih, itu membantu untuk menyadari bahwa ada lebih banyak info untuk dikerjakan. Daripada hanya menghitung paritas bit dari angka saat ini,

k  ---->  par(k)

kita dapat memperbarui paritas bit seperti yang kita kenaikan kuntuk k+1.

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

Yaitu, karena kita menghitung k=0,1,2,..., kita hanya perlu mempertahankan paritas bit saat ini daripada menghitungnya dari awal setiap kali. Update bit paritas par(k+1)^par(k)adalah paritas dari jumlah bit membalik untuk pergi dari kke k+1, yang par((k+1)^k).

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

Bentuk dari (k+1)^k

Sekarang kita perlu menghitung par((k+1)^k). Sepertinya kita tidak mendapatkan apa-apa karena menghitung bit parity adalah masalah yang ingin kita pecahkan. Tapi, angka-angka yang dinyatakan (k+1)^kmemiliki bentuk 1,3,7,15,.., yaitu satu di bawah kekuatan 2, fakta yang sering digunakan dalam peretasan bit . Mari kita lihat mengapa begitu.

Ketika kita bertambah k, efek dari binary carry adalah membalikkan yang terakhir 0dan semuanya 1ke kanan, menciptakan pemimpin baru 0jika tidak ada. Sebagai contoh, ambilk=43=0b101011

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

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

Kolom yang menyebabkan carry ditandai dengan *. Ini memiliki 1perubahan ke 0dan meneruskan sedikit carry 1, yang terus menyebar ke kiri sampai menyentuh 0dalam k, yang berubah menjadi 1. Setiap bit lebih jauh ke kiri tidak terpengaruh. Jadi, ketika k^(k+1)cek yang sedikit posisi berubah kuntuk k+1, ia menemukan posisi paling kanan 0dan 1's untuk yang benar. Yaitu, bit yang diubah membentuk akhiran, jadi hasilnya 0's diikuti oleh satu atau lebih 1's. Tanpa nol terkemuka, ada angka biner 1, 11, 111, 1111, ...yang satu di bawah kekuatan 2.

Komputasi par((k+1)^k)

Sekarang kita mengerti bahwa (k+1)^kterbatas 1,3,7,15,..., mari kita cari cara untuk menghitung bit paritas dari angka-angka tersebut. Di sini, fakta yang berguna adalah 1,2,4,8,16,...modulo alternatif itu 3antara 1dan 2, sejak 2==-1 mod 3. Jadi, mengambil memberi 1,3,7,15,31,63...modulo , yang persis paritas bit mereka. Sempurna!31,0,1,0,1,0...

Jadi, kita bisa melakukan pembaruan par(k+1) = par(k) ^ par((k+1)^k)sebagai

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

Menggunakan bsebagai variabel tempat kita menyimpan paritas, ini terlihat seperti

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

Menulis kodenya

Menyatukan ini dalam kode, kita mulai kdan paritas bkeduanya 0, kemudian berulang kali mencetak n=2*k+bdan memperbarui b=b^((k+1)^k)%3dan k=k+1.

46 byte

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

Cobalah online!

Kami menghapus parens k+1di sekitar ((k+1)^k)%3karena prioritas Python melakukan penambahan pertama, aneh seperti yang terlihat.

Perbaikan kode

Kita bisa melakukan yang lebih baik dengan bekerja secara langsung dengan satu variabel n=2*k+bdan melakukan pembaruan langsung di atasnya. Melakukan k+=1sesuai dengan n+=2. Dan, memperbarui b^=(k+1^k)%3berkorespondensi dengan n^=(k+1^k)%3. Di sini, k=n/2sebelum memperbarui n.

44 byte

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

Cobalah online!

Kita dapat mempersingkat n/2+1^n/2(ingat ini (n/2+1)^n/2) dengan menulis ulang

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

Sejak /2menghapus bit terakhir, tidak masalah jika kita melakukannya sebelum atau sesudah xor-ing. Jadi, sudah n^=(n+2^n)/2%3. Kita dapat menyimpan byte lain dengan mencatat modulo itu 3, /2sama dengan *2ekivalen dengan -, mencatat bahwa n+2^nmeskipun demikian pembagiannya adalah separuh sebenarnya tanpa lantai. Ini memberin^=-(n+2^n)%3

41 byte

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

Cobalah online!

Akhirnya, kita bisa menggabungkan operasi n^=c;n+=2menjadi n=(n+2)^c, di mana cada sedikit. Ini berfungsi karena ^chanya bertindak pada bit terakhir dan +2tidak peduli dengan bit terakhir, jadi operasi pun jadi. Sekali lagi, diutamakan mari kita hilangkan orangtua dan menulis n=n+2^c.

39 byte

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

Cobalah online!

Ini memberikan solusi 47-byte (xnor) dan pemikiran yang mengarahkan saya ke sana. Jangan baca ini jika Anda ingin mencari tahu sendiri.

Gagasan pertama yang alami adalah beralih melalui angka 0 hingga 799, hanya mencetak angka-angka genap 1 dalam biner.

52 byte

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

Cobalah online!

Di sini, ~dibutuhkan bit komplemen untuk beralih even<->odddalam penghitungan dan memberikan nilai yang benar hanya pada penghitungan genap.

Kami dapat meningkatkan metode ini dengan menghasilkan semua nilai alih-alih memfilter. Perhatikan bahwa nilai-nilai output adalah angka 0 hingga 399, masing-masing dengan sedikit ditambahkan untuk membuat jumlah 1 bit genap.

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

Jadi, angka nke-2 adalah 2*n+bdengan salah satu b=0atau b=1. Bit bdapat ditemukan dengan menghitung 1dalam bit ndan mengambil modulo 2 hitungan.

49 byte

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

Cobalah online!

Kita dapat memotong 2 byte 2*dengan mengulangi 0,2,4,..., yang tidak menghitung hitungan 1. Kita bisa melakukan ini dengan menggunakan satu execloop yang berjalan 400 kali dan bertambah n2 setiap loop.

47 byte

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

Cobalah online!

Dan, itu solusi 47-byte saya. Saya menduga sebagian besar jika tidak semua solusi 47-byte lainnya adalah sama.

Pengajuan Python 3 llhuii

Berikut ini adalah pengiriman Python 3 untuk Nomor Jahat pada saat penulisan:

llhuii mungkin porting trik mereka ke Python 3, dan datang dengan solusi itu

• 3 byte lebih lama dari solusi Python 2 mereka, dan
• memiliki 45 - (25 + 18) = 2 byte spasi.

Porting 47n xnor ke Python 3 secara harfiah, kami mendapatkan 50B ini:

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

Saya mengirimkannya sebagai ppcg(xnor). (Ia menambahkan tanda kurung ke execdan print, yang sekarang berfungsi.) Ia memiliki statistik kode yang berbeda dari jawaban Python 3 lainnya, yang semuanya memiliki sejumlah spasi putih di dalamnya. Menarik!

Namun ada cara yang lebih singkat untuk menulis ulang ( execcenderung kehilangan keunggulan kompetitifnya di Python 3):

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

Ini 49 byte. Saya mengirimkannya sebagai ppcg(xnor,alternative). Ini memiliki dua byte spasi, seperti jawaban llhui! Ini membuat saya percaya bahwa jawaban Python 3 llhuii terlihat seperti ini (baris baru, kemudian whileloop). Jadi llhuii mungkin digunakan execdalam Python 2 dan whilePython 3, sama seperti kita; ini menjelaskan perbedaan spasi putih.

47B kami menjadi 49B dalam Python 3. Yang menarik, sekarang, adalah bahwa 42B llhuii tidak menjadi 44B, itu menjadi 45B! Sesuatu tentang solusi llhuii membutuhkan satu byte tambahan dalam Python 3. Ini bisa berarti berbagai hal.

• Hal pertama yang terlintas dalam pikiran adalah pembagian : mungkin llhuii menggunakan /Python 2, yang menjadi //Python 3. (Jika mereka menghitung dalam dua-dua seperti kita, maka n/2dapat digunakan untuk beralih nkembali ke kanan dengan satu bit?)

• Hal lain yang terlintas dalam pikiran adalah operator unary setelah mencetak . Kami print blahmenjadi print(blah)(1 byte tambahan), tetapi jika llhuii menulis sesuatu seperti print~-blahdi Python 2, itu akan menjadi print(~-blah)di Python 3.

• Mungkin ada ide lain. Tolong beritahu saya.

Statistik kode untuk semua solusi Py3, termasuk milik saya sekarang:

Pendekatan lain

1) Menggunakan rumus untuk A001969

Daripada mengkonversi ke biner, dimungkinkan untuk mengambil keuntungan dari rumus berikut (dari 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

Saya sangat buruk bermain golf di Python, jadi saya bahkan tidak akan mencoba. Tapi di sini ada upaya cepat di JS.

^{NB: Saya tidak berpikir itu akan menjadi pengiriman JS yang valid karena hanya mengisi array tanpa menampilkannya. Dan meskipun demikian, ini 5 byte lebih lama dari solusi JS terbaik saat ini (yaitu 45 byte). Tapi toh bukan itu intinya di sini.}

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

Semoga ini bisa memberi inspirasi.

Menggunakan array mungkin bukan ide yang baik karena perlu diinisialisasi dan diperbarui. Mungkin lebih efisien (ukuran kode bijaksana) untuk menggunakan fungsi rekursif sebagai gantinya, yang akan menjelaskan mengapa solusi yang menang mengambil lebih banyak waktu daripada yang lain.

2) Membangun urutan Thue-Morse dengan penggantian

Secara teori, kode ini harus berfungsi:

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

Cobalah online! (versi runnable terbatas hingga 20 istilah)

Itu menghitung urutan Thue-Morse dengan pergantian berturut-turut dan mencari posisi 1 (Nomor Jahat) dalam loop yang sama.

Tapi:

• Terlalu panjang dalam bentuknya saat ini
• Dengan cepat menyebabkan memori meluap

3) Membangun urutan Thue-Morse dengan operasi bitwise

Mulai dari Definisi Langsung Wikipedia tentang urutan Thue-Morse , saya telah sampai pada algoritma ini (beralih kembali ke JS ... maaf):

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

di mana kita melacak kejahatan saat ini dari urutan dalam e dan menggunakan 170 sebagai bitmask bit aneh dalam satu byte.

Pendekatan penghitung bersarang

Saya punya ide untuk pendekatan yang berbeda, tapi saya tidak cukup berpengalaman dalam golf python, jadi saya akan meninggalkannya di sini untuk kalian pertimbangkan sebagai titik awal lain yang mungkin untuk bermain golf.

Gagasan yang tidak diserang:

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

Cobalah online!

Sembilan tingkat bersarang kedalaman, semua loop adalah sama, jadi dalam pikiranku mereka harus dibangun oleh exec"something"*9+"deepest stuff". Dalam praktiknya saya tidak tahu apakah mungkin untuk melakukan hal seperti ini dengan siklus for.

Hal-hal yang perlu dipertimbangkan untuk bermain golf:

• mungkin ada beberapa kemungkinan lain untuk siklus dua kali selain untuk loop (saya mencoba pendekatan seperti quine dengan string yang akan dieksekusi dilewatkan ke dirinya sendiri sebagai argumen format dua kali, tapi kepala saya meledak).

• mungkin juga ada alternatif yang lebih baik if n<800:, yang diperlukan di sini karena jika tidak kita akan terus mencetak angka jahat hingga 2 ^ 10

Ide: Paritas bit lebih pendek

Dibutuhkan banyak karakter untuk bin(n).count('1')%2menghitung paritas bit-count. Mungkin cara aritmatika lebih pendek, terutama mengingat panjang bit terbatas.

Cara lucu yang sama panjangnya adalah int(bin(n)[2:],3)%2, menafsirkan nilai biner sebagai basis 3(atau basis ganjil). Sayangnya, 4 byte dihabiskan untuk menghapus 0bawalan. Ini juga berfungsi untuk dilakukan int(bin(n)[2:])%9%2.

Gagasan lain datang dari menggabungkan bit menggunakan xor. Jika nmemiliki representasi biner abcdefghi, maka

n/16 = abcde
n%16 =  fghi

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

Jadi, r=n/16^n%16adalah kejahatan jika dan hanya jika itu nadalah kejahatan. Kita kemudian dapat mengulangi bahwa sebagai s=r/4^r%4, nilai sdi 0,1,2,3, yang 1dan 2tidak jahat, checkable dengan 0<s<3.

52 byte

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

Cobalah online!

Ini ternyata jauh lebih lama. Ada banyak tombol untuk membalikkan bagaimana cara membagi angka, bagaimana memeriksa angka akhir (mungkin tabel pencarian berbasis bit). Saya menduga ini hanya bisa sejauh ini.

Dengan konstruksi, n+n^nselalu jahat, tetapi kemampuan Python saya yang buruk hanya bisa menghasilkan solusi 61-byte:

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

Terima kasih kepada @Peilonrayz untuk menghemat 5 byte dan @ Mr.Xcoder untuk menghemat 1 byte:

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

Ide: A006068 ("a (n) diberi kode Abu-abu menjadi n")

Gagasan Neil untuk menyortir semua 2n XOR nmembuat saya penasaran, jadi saya mencoba menemukan indeks di balik jenis ini. Saya menulis kode ini , dan itu mengungkapkan bahwa kita dapat menulis sesuatu seperti ini:

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

Di mana a(n)A006068 (n). Cobalah online!

Namun, ini mengasumsikan kita memiliki beberapa cara singkat untuk menghitung A006068. Ini sudah 38 byte, dengan asumsi kita dapat menghitungnya dalam 4 byte ( a(n)bagian). Implementasi nyata (dalam header TIO) jauh lebih lama dari itu. Tidak banyak harapan untuk ini, saya pikir.

Ide: Kurangi lebih dari XOR

Jika Anda XOR semua bit nbersama, itu akan 0untuk kejahatan dan 1untuk non-kejahatan. Anda dapat melakukan ini dengan fungsi rekursif (yang mungkin membutuhkan waktu lebih lama?), Seperti:

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

Ini mengembalikan 1 untuk kejahatan.

Itu 35 byte, dan memeriksa apakah angka itu jahat atau tidak. Sayangnya, filtersudah 6 byte jadi ini bukan solusi yang optimal kata demi kata tetapi ide ini mungkin bisa golf.

Metode substitusi: {1 -> {1, -1}, -1 -> {-1, 1}}

Anda juga dapat membuat substitusi ini 10 kali {1 -> {1, -1}, -1 -> {-1, 1}}, lalu ratakan dan periksa posisi 1's

di sini adalah kode Mathematica

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