Bayangkan saya memiliki banyak masalah pekerjaan rumah (!) Yang masing-masing diberi angka integer.
Notasi Masalah Matematika adalah notasi untuk menggambarkan himpunan bagian dari masalah menggunakan penentu masalah.
Ekspresi MPN dapat terdiri dari beberapa hal:
- Nilai tunggal. Ini merupakan set yang berisi nomor:
99 -> {99}
. - Kisaran yang sederhana. Ini merupakan set yang berisi semua angka dari awal sampai akhir rentang:
10~13 -> {10, 11, 12, 13}
. Jika sisi kiri atau kanan hilang, maka mereka diasumsikan -infinity atau Infinity masing-masing:~10 -> {x|x ≤ 10}
;~ -> ℤ
. - Ekspresi MPN, diikuti oleh "lewati" dan ekspresi MPN lainnya. Ini merupakan selisih dari dua set:
10~20 skip 12~14 -> {10, 11, 15, 16, 17, 18, 19, 20}
. - Dua ekspresi MPN, dipisahkan oleh koma. Ini merupakan penyatuan dua set:
1,8~9,15~17 -> {1,8,9,15,16,17}
.
Operator "lewati" mengikat lebih ketat daripada operator koma, jadi 16,110~112 skip 16 -> {16,110,111,112}
(16 tidak termasuk dalam set {110,111,112}
, sehingga 16 yang tidak termasuk tidak menjadi masalah.)
Anda juga dapat menaruh ekspresi dalam tanda kurung untuk disambiguasi:
1~9 skip (2~8 skip (3~7 skip (4~6 skip 5))) -> {1,3,5,7,9}
Ini adalah tata bahasanya:
<expr> ::= "(" <expr> ")"
|| <number>
|| [<number>] "~" [<number>]
|| <expr> "skip" <expr>
|| <expr> "," <expr>
Tugas Anda adalah menulis sebuah program yang membutuhkan dua input:
- Ekspresi MPN
- Sebuah angka
dan menghasilkan beberapa nilai true atau falsey tergantung pada apakah masalah itu dalam set yang dijelaskan oleh ekspresi MPN.
Spesifikasi
- Anda dapat mengasumsikan bahwa input pertama adalah ekspresi MPN yang terbentuk dengan baik (yaitu cocok dengan tata bahasa di atas)
- Angka dalam ekspresi MPN selalu bilangan bulat. Mereka bisa negatif atau nol, tetapi tidak akan pernah memiliki bagian fraksional.
- Ini adalah kode-golf , sehingga pengiriman terpendek yang valid (diukur dalam byte) menang.
- Anda dapat menggunakan karakter yang berbeda untuk
~
dan,
, jika Anda mau.
Uji Kasus
10~20 14 -> True
10~20 20 -> True
10~20 skip 14~18 17 -> False
~ skip 6 8 -> True
16,17 skip 16 16 -> True
(16,17) skip 16 16 -> False
~10,5~ 8 -> True
~10,5~ 4 -> True
6 skip 6,~ 6 -> True
sumber
~
dan,
, tetapi tidak untukskip
.6 skip 6,~
yang saya yakin telah saya artikan dengan benar. 2 jawaban lainnya sejauh ini tidak memuaskan (sekali lagi, dengan asumsi saya menafsirkan dengan benar). Jika saya salah paham, mohon perbaiki dan klarifikasi, tetapi dari pemahaman saya, itu harus cocok dengan apa pun (penyatuan set yang tidak cocok dengan set yang cocok dengan segalanya). Ini adalah jenis kasus yang saya bicarakan sebelumnya yang saya pikir dapat banyak membantu ketika menguji solusi kami.Jawaban:
PowerShell ,
189195 byte-100..100
sebagai nilaiPenjelasan
Saya menyadari sejak awal bahwa infinitas membuat ini tidak bisa digunakan untuk menghasilkan array dan menguji nilai-nilai.
Saya melihat ke dalam range tetapi di. Net mereka tidak memiliki range yang dibutuhkan ( panjang range terbatas pada integer yang ditandatangani (32 bit), jadi walaupun itu boleh saja membatasi range ke 32-bit yang sudah ditandatangani , Saya tidak akan mampu menangani semua rentang.
Jadi saya mulai berpikir tentang ini dalam hal mulai dan berakhir, dan akhirnya serangkaian tes boolean dan mulai membuat sekelompok pengganti regex untuk mengubah MPN menjadi ekspresi boolean yang dipahami PowerShell.
Saya pada dasarnya memecah ini menjadi beberapa aturan:
2~8
seperti mengatakann >=2 && n <=8
, tetapi ketika salah satu ujungnya hilang, tinggalkan&&
sisi yang hilang. Ketika keduanya hilang, saya awalnya hanya akan menggantinya dengan$true
. Apa yang akhirnya saya lakukan sebenarnya tidak menguji sisi yang hilang sama sekali, tetapi saya memastikan untuk memasukkan setiap nomor()
.()
dengan nilai input. Jadi, dalam kasus MPN seperti~8
dengan nilai input55
, ganti pertama akan menghasilkan(55-ge()-and55-le(8))
, maka ganti kedua datang untuk membuatnya(55-ge55-and55-le(8))
, pada dasarnya membatalkan bagian rentang tersebut.,
daftar yang dipisahkan koma , dan angka individual sebelum atau setelah askip
, jadi saya menggunakan pencarian jangka panjang yang tidak menyenangkan.skip
pada dasarnya sama dengan-and -not
jadi saya melakukan penggantian langsungskip
ke-and!
(menggunakan!
sebagai singkatan untuk-not
).-or
tetapi tidak memperhitungkan ekspresi selanjutnya jadi16,17 skip 16
menghasilkan kode seperti($n-eq16)-or($n-eq17) -and! ($n-eq16)
. Itu membutuhkan tanda kurung, tapi itu sepertinya tidak bisa dilakukan dengan penggantian yang lurus. Karena semua hal lain diganti kecuali koma, dan mereka memiliki prioritas terendah, saya hanya membagi seluruh string yang dihasilkan pada koma yang tersisa, kemudian membungkus setiap elemen dalam tanda kurung, dan bergabung kembali dengan-or
.Pada akhirnya kode yang dihasilkan hanya disalurkan ke
Invoke-Expression
(iex
) untuk dieksekusi dan kemudian kita mendapatkan hasil boolean ( Anda dapat melihat kode yang dihasilkan bukan hasil di sini ).Ini memakan waktu terlalu lama, dan saya yakin ada beberapa ruang untuk memeras beberapa byte lagi, tapi saya tidak bisa melihatnya lagi :-p
sumber
Perl,
99130 byteCobalah di Ideone.
Tidak Disatukan:
sumber
JavaScript (ES6),
221292287309274277278 byte(-5 byte terima kasih kepada Okx)
Wow. Ini tidak mudah karena semua kasus tepi, tetapi saya pikir saya melakukannya. Saya hanya berharap tidak ada kasus khusus yang dapat mematahkan ekspresi reguler yang digunakan. Saya akan bermain golf ini lebih banyak kapan saja saya bisa.
Cuplikan Tes
sumber
1/0
untukInfinity
.6
dengan ekspresi6 skip 6,~
yang saya percaya seharusnyatrue
tetapi kembalifalse
.false
sebagaimanaskip
berlaku untuk semua yang mengikutinya (6,~
dalam hal ini) selama tidak dibungkus dalam tanda kurung. Oleh karena itu, saya percaya itu harus kembalitrue
pada(6 skip 6),~
daripada6 skip 6,~
dengan masukan bilangan bulat6
.6 skip 6,~
cocok karena mewakili perbedaan antara set dan set .{6}
{6,-Infinity...Infinity}
Röda + bc, 183 byte
Ini mirip dengan jawaban PowerShell (atau saya pikir begitu, saya tidak mengerti PowerShell). Dibutuhkan angka sebagai argumen dan kode sebagai nilai dalam aliran input, seperti ini:
main { push("1~9") | f(5) }
.Saya pikir itu berhasil, setidaknya itu menyelesaikan semua kasus uji. Script di bawah ini dapat digunakan untuk memverifikasi ini.
Dan tesnya:
sumber