Dalam semangat xkcd ini
Tulis program yang memainkan golf regex dengan daftar daftar yang berubah-ubah. Program setidaknya harus berusaha untuk membuat regex pendek, sebuah program yang hanya menghasilkan /^(item1|item2|item3|item4)$/
atau serupa tidak diperbolehkan.
Penilaian didasarkan pada kemampuan untuk menghasilkan regex terpendek. Daftar tes adalah daftar kandidat presiden AS yang berhasil dan tidak berhasil, ditemukan di sini (terima kasih @Peter). Tentu saja, program harus bekerja untuk semua daftar yang terpisah, jadi hanya mengembalikan jawaban untuk presiden yang tidak diperhitungkan.
regular-expression
metagolf
Manishearth
sumber
sumber
/^item1|atem2|item3|item4$/
mungkin memiliki prioritas yang tidak disengaja (string harus dimulai denganitem1
, mengandungatem2
, berisiitem3
, atau diakhiri denganitem4
).Jawaban:
Perl (
111110122 karakter)Ini menggunakan modul CPAN yang dipanggil
Regexp::Assemble
untuk mengoptimalkan ekspresi reguler. Karena apa bahasa yang lebih baik untuk ekspresi reguler daripada Perl.Juga, versi yang mudah dibaca, hanya untuk bersenang-senang (dibuat dengan bantuan
-MO=Deparse
).Output sampel (saya lakukan setelah CTRL-D
item4
).Juga, sebagai bonus, saya menulis regex untuk setiap kata dalam pertanyaan.
Juga, daftar presiden (262 byte).
sumber
Bukan solusi saya (jelas saya bukan peter norvig!) Tapi inilah solusi dari pertanyaan (sedikit dimodifikasi) dari dia: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb
program yang dia berikan adalah sebagai berikut (pekerjaannya, bukan pekerjaan saya):
di mana pemenang dan pecundang adalah pemenang dan pecundang masing-masing (atau 2 daftar saja) lihat artikel untuk penjelasan rinci.
sumber
Solusi saya ditulis dalam Factor :
Ini algoritma yang sama dengan Norvig. Jika merusak keterbacaan adalah tujuannya, maka Anda mungkin bisa bermain golf lebih banyak karakter.
sumber
Kode saya tidak dalam mode golf-ish dan kental, tetapi Anda dapat memeriksanya di https://github.com/amitayd/regexp-golf-coffeescript/ (atau secara khusus algoritma di src / regexpGolf.coffee).
Ini didasarkan pada algoritma Peter Norvig, dengan dua peningkatan:
(Dan juga melemparkan keacakan opsional)
Untuk kumpulan pemenang / pecundang dalam kuis ini, saya menemukan 76 chars regex menggunakannya:
Beberapa lebih detail di posting blog saya tentang porting solver ke coffeescript .
sumber