Memecahkan Notasi Masalah Matematika

14

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 , 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
Buah Esolanging
sumber
Apakah mungkin menggunakan karakter lain untuk mewakili operator?. Misalnya menggunakan # bukannya ~
rahnema1
1
@ rahnema1 Untuk ~dan ,, tetapi tidak untuk skip.
Buah Esolanging
3
Mengapa ~ 10,5 ~ salah untuk 4? Karena itu adalah penyatuan-infinity ke 10 dan 5 hingga infinity, yang pertama termasuk 4
ev3commander
@ ev3commander Diedit. Saya selalu mengacaukan test case saya. Saya yakin tantangan saya akan lebih jelas jika saya tidak menambahkannya: P
Esolanging Fruit
1
@ Challenger5 Saya telah menambahkan test case 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.
briantist

Jawaban:

3

PowerShell , 189 195 byte

param($m,$q)('$m',"'(\d*)~(\d*)','($q-ge(`$1)-and$q-le(`$2))'","'\(\)',$q","'((?<=,|skip )\d+|\d+(?=,| skip))','($q-eq`$1)'","'skip','-and!'"-join'-replace'|iex|% Sp* ','|%{"($_)"})-join'-or'|iex

Penjelasan

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:

  • Ranges lebih mudah untuk dikerjakan terlebih dahulu karena mereka tidak bisa menjadi ekspresi di kedua ujungnya, tetapi keterbukaannya terasa sulit untuk diimplementasikan segera. Premisnya 2~8seperti mengatakan n >=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 ().
  • dan kemudian lakukan substitusi langsung yang menggantikan tanda kurung kosong ()dengan nilai input. Jadi, dalam kasus MPN seperti ~8dengan nilai input 55, 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.
  • Selanjutnya saya harus berurusan dengan nomor individual di MPN, tetapi harus berhati-hati untuk tidak mengacaukan dengan yang saya masukkan sebelumnya. Ini benar-benar hanya angka dalam ,daftar yang dipisahkan koma , dan angka individual sebelum atau setelah a skip, jadi saya menggunakan pencarian jangka panjang yang tidak menyenangkan.
  • skippada dasarnya sama dengan -and -notjadi saya melakukan penggantian langsung skipke -and!(menggunakan !sebagai singkatan untuk -not).
  • Hal rumit berikutnya adalah urutan prioritas rendah untuk koma yang tersisa. Saya awalnya hanya menggantinya dengan -ortetapi tidak memperhitungkan ekspresi selanjutnya jadi 16,17 skip 16menghasilkan 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

briantis
sumber
2

Perl, 99 130 byte

sub f{($_,$n)=@_;s/(-?\d+)?~(-?\d+)?|(-?\d+)/!(defined$3?$n!=$3:length$1&&$1>$n||length$2&&$n>$2)+0/ge;s/skip/&&!/g;s/,/||/g;eval}

Cobalah di Ideone.

Tidak Disatukan:

sub f {
    my ($e, $n) = @_;

    $e =~ s/(-?\d+)?~(-?\d+)?|(-?\d+)/ (defined($3) ? $n == $3 : (!length($1) || $n >= $1) && (!length($2) || $n <= $2)) + 0 /ge;
    $e =~ s/skip/ && ! /g;
    $e =~ s/,/ || /g;

    return eval($e);
}
Denis Ibaev
sumber
1
Gagal untuk ~ -2 untuk input -2. Juga saat memasukkan -? sebelum ketiga \ d *
Kjetil S.
@KjetilS. Diperbaiki untuk angka negatif dan nol.
Denis Ibaev
kode yang bagus (tata bahasa penuh sesak nafas sering tidak diperlukan, regex lebih mudah)
Kjetil S.
1

JavaScript (ES6), 221 292 287 309 274 277 278 byte

(-5 byte terima kasih kepada Okx)

(j,v,m=1/0,Z=/(skip)([^,]+)/g)=>eval(j[M='replace'](/(-?\d*)~(-?\d*)/g,(e,a,b)=>(a[M]('-','#')||-m)+'<='+(T=v[M]('-','#'))+'&&'+T+'<='+(b[M]('-','#')||m))[M](Z,i=o=>o.match(Z)?i(o[M](Z,'&&!($2)')):o)[M](/,/g,'||')[M](/(^|[^=&#\d])(\d+)([^<\d]|$)/g,'$1$2=='+v+'$3')[M](/#/g,'-'))

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

D=(j,v,m=1/0,Z=/(skip)([^,]+)/g)=>eval(j[M='replace'](/(-?\d*)~(-?\d*)/g,(e,a,b)=>(a[M]('-','#')||-m)+'<='+(T=v[M]('-','#'))+'&&'+T+'<='+(b[M]('-','#')||m))[M](Z,i=o=>o.match(Z)?i(o[M](Z,'&&!($2)')):o)[M](/,/g,'||')[M](/(^|[^=&#\d])(\d+)([^<\d]|$)/g,'$1$2=='+v+'$3')[M](/#/g,'-'))
MPN Expression:<input type="text" value="1~9 skip (2~8 skip (3~7 skip (4~6 skip 5)))" id="MPN"></input>
<br>
Integer:<input type="number" id="INT" value=6></input>
<input type="button" value="Submit" onclick="T=r=>document.getElementById(r).value;console.log(D(T('MPN'),T('INT')))"></input>

R. Kap
sumber
@AriaAx Ini seharusnya berfungsi sekarang.
R. Kap
@ R.Kap bisa Anda gunakan 1/0untuk Infinity.
Okx
@ R.Kap saya mencoba nilai 6dengan ekspresi 6 skip 6,~yang saya percaya seharusnya truetetapi kembali false.
briantist
@ Briantist Sebenarnya, saya percaya bahwa harus kembali falsesebagaimana skipberlaku untuk semua yang mengikutinya ( 6,~dalam hal ini) selama tidak dibungkus dalam tanda kurung. Oleh karena itu, saya percaya itu harus kembali truepada (6 skip 6),~daripada 6 skip 6,~dengan masukan bilangan bulat 6.
R. Kap
@ briantist Dengan kata lain, tidak ada yang6 skip 6,~ cocok karena mewakili perbedaan antara set dan set . {6}{6,-Infinity...Infinity}
R. Kap
0

Röda + bc, 183 byte

f x{{["x=",x,"\n"];replace" ","",",","||","skip\\(","&&!","skip([0-9~]+)","&&!($1)","(?<!~|\\d)(\\d+)(?!~|\\d)","x==$1","(\\d*)~(\\d*)","x>=($1)&&x<=($2)","\\(\\)",x;["\n"]}|exec"bc"}

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.

main {
    readLines("/tmp/tests.txt") | split(sep=";") | for code, num, ans do
        push(code, " -> ")
        print(code) | replace" ","",",","||","skip\\(","&&!","skip([0-9~]+)","&&!($1)","(?<!~|\\d)(\\d+)(?!~|\\d)","x==$1","(\\d*)~(\\d*)","x>=($1)&&x<=($2)","\\(\\)",num
        a := push(code) | f(num) | head()
        result := push("OK") if [ (a = "0" and ans = "False") or (a = "1" and ans = "True") ] else push("FAIL")
        print code, " ; ", num, " -> ", a, " ", ans, " (", result, ")\n"
    done
}

Dan tesnya:

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
fergusq
sumber