Hai penghuni , saatnya berbicara tentang pemrograman deklaratif. Inilah saat Anda digosok di institut bahwa program tidak dapat dikodekan, tetapi dirumuskan. Ini adalah kebalikan dari imperatif, yang sekarang ada di semua bahasa pemrograman. Mari kita beri penghormatan kepada pendekatan fungsional, ini adalah persaudaraan di sini, dan melakukan pekerjaannya semakin dalam ke dalam modernitas, di sini Anda memiliki lambdas dalam C ++ dan javascripts, mungkin Haskell?

Tetapi yang menyedihkan adalah dengan pemrograman logis dan produktif, yang hanya dapat diwakili di Prolog .

Di sini saya akan melemparkan pemikiran yang menarik untuk efek habr. Mengapa tidak menulis artikel tentang pemecahan masalah pemrograman. Jadi, saya pikir banyak posting ternyata. Saya bergabung dengan pemilihan topik. Berikut ini adalah arah pengembangan dan kompetisi baru dan orisinal antara peserta, kami menunjukkan bagaimana tepatnya kami dapat menyelesaikan masalah, sehingga semua pembaca tertarik untuk mengemukakan pendapat mereka dan menunjukkan kesalahan Anda, karena Anda memiliki cukup spesialis dalam javascript dan C ++, mungkin pythognoses masih menemukan ...

Secara total, tujuan artikel : untuk menyelesaikan pada saat penulisan artikel masalah yang belum diketahui pada awal posting dan menunjukkan kode pemikiran Anda, mengkonfirmasikan ini dengan kursus dan solusi kerja yang diterima. Tetapi untuk pemeriksaan ini Anda membutuhkan wasit, Anda sendiri tidak meninjau diri sendiri. Saya akan memilih leetcode.com dalam peran ini.

1. Jadi

Di sini kita memilih tugas yang paling dekat dengan yang paling sulit, dan mencoba menyelesaikannya di Prolog, perlu untuk menunjukkan betapa menghiburnya itu.

2. Tugas 44. Pencocokan wildcard

Diberikan string input dan pola (p), terapkan pencocokan pola wildcard dengan dukungan untuk '?' dan '*'.

' Cocok dengan setiap karakter tunggal.
'*' Cocok dengan urutan karakter apa pun (termasuk urutan kosong).
Pencocokan harus mencakup seluruh string input (bukan parsial).

Catatan:

s bisa kosong dan hanya berisi huruf kecil az.
p bisa kosong dan hanya berisi huruf kecil az, dan karakter seperti? atau *.
Contoh 1:
Masukan:
s = "aa"
p = "a"
Output: salah
Penjelasan: "a" tidak cocok dengan seluruh string "aa".

Contoh 2:
Masukan:
s = "aa"
p = '*'
Output: benar

Penjelasan: '*' cocok dengan urutan apa pun.

Contoh 3:
Masukan:
s = "cb"
p = "? a"
Output: salah
Penjelasan: '?' cocok dengan 'c', tetapi huruf kedua adalah 'a', yang tidak cocok dengan 'b'.

Contoh 4:
Masukan:
s = "adceb"
p = "* a * b"

Output: benar
Penjelasan: "Bintang" pertama cocok dengan urutan kosong, sedangkan * kedua cocok dengan "dce" substring.

Contoh 5:
Masukan:
s = "acdcb"
p = "a * c? b"
Output: salah

3. Ini adalah langkahnya

Wow))) (moderator permisi), ada tugas di mana perlu untuk menerapkan predikat. Mukjizat, Anda bahkan tidak harus melakukan I / O, yang bisa sulit di lingkungan seperti itu. Pada input, tipe sederhana, pada output, Boolean. SD.

Saat memasang ikon kutipan, saya secara singkat berkenalan dengan tugas tersebut, kami memiliki mesin keadaan terbatas, ada rangkaian karakter, ini adalah templat, kami perlu memeriksanya dan melakukan pemeriksaan, memintas grafik keadaan jadi jika kami mencapai ujung verteks, maka jawabannya benar. Ini adalah tugas untuk pencarian terbalik.

Kemudian lanjutkan, saya segera menulis konsep di sini, maka saya akan menunjukkan versi yang berfungsi:
Sebuah baris ... dalam prolog, tipe data penting adalah daftar, itu adalah konsep rekursif, dijelaskan secara deskriptif, jadi Anda harus bekerja dengannya, Anda perlu mengubah string menjadi daftar atom. Ngomong-ngomong, sebuah atom bukan hanya sebuah simbol, meskipun itu juga, sebuah atom adalah string dengan huruf kecil tanpa spasi, untuk Prolog itu adalah konstanta string dan Anda tidak dapat memberikan tanda kutip.

atom_to_list('',[]). %-      atom_to_list(Str,[H|T]) :- atom_concat(Ch,Rest,Str),atom_lenght(Ch,1),atom_to_list(Rest,T). %-  ,         

Maaf untuk bahasa Inggris saya, kami akan memeriksanya di lingkungan terbaik saat ini, swi-prolog.org , ada editor online, di sini:

Ups. Ini artinya tidak menipu siapa pun, ini adalah ambang pintu masuk yang tinggi, panggilan ke predikat perpustakaan tidak benar. Kami mencari predikat bawaan yang tepat untuk bekerja dengan atom.
Dan dalam gambar ada pesan bahwa variabel H ternyata tidak diklaim, beberapa cacat dalam logika, kepala daftar adalah karakter pertama, dan sebagai gantinya adalah Ch .

Berikut ini beberapa dokumentasi:

atom_concat (? Atom1 ,? Atom2 ,? Atom3)
Atom3 membentuk rangkaian Atom1 dan Atom2. Setidaknya dua argumen harus dipakai untuk atom. Predikat ini juga memungkinkan untuk mode (-, -, +), yang secara non-deterministik memisahkan argumen ke-3 menjadi dua bagian (seperti yang ditambahkan / 3 untuk daftar). SWI-Prolog memungkinkan untuk argumen atom. Kode portabel harus menggunakan atomic_concat / 3 jika ada argumen non-atom.

atom_length (+ Atom, -Length)
Benar jika Atom adalah atom karakter Panjang. Versi SWI-Prolog menerima semua jenis atom, serta daftar kode dan daftar karakter. Kode baru harus menghindari fitur ini dan menggunakan write_length / 3 untuk> mendapatkan jumlah karakter yang akan ditulis jika argumen diserahkan ke write_term / 3.

3.1 Atom dalam daftar atom

Seperti ini

3.2 Mesin negara itu sendiri

Bayangkan grafik yang membaca karakter dari templat dan memeriksa kepatuhan dengan karakter di baris input. Solusi konsep:

 %InpitList, PattList test_pattrn([],[]). %-      test_pattrn([Ch|UnpTail],[Ch|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):-is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn([],['*'|PatTail]):-test_pattrn([],PatTail). 

Mari kita buat antarmuka terakhir:
isMatch (S, P): - atom_to_list (S, SL), atom_to_list (P, PL),!, test_pattrn (SL, PL),!

Berikut ini semua contoh dari pernyataan masalah:

4. Arbiter

Sepertinya keputusan sudah siap, sekarang kita nyalakan arbiter. Di situs leetcode.com (ya, ya, kami menyelesaikan masalah nomor 44), kami akan menerima tes, kami akan mencoba untuk menjalankannya secara berurutan dengan implementasi kami. Satu nasib buruk, mereka tidak menerima program di Prolog .

Tidak ada, kami akan mendapatkan semua tugas satu per satu:

 class Solution: def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ if s=="aa" and p=="a":return False if s=="aa" and p=="*":return True if s=="cb" and p=="?a":return False if s=="adceb"and p=="*a*b":return True if s=="acdcb" and p=="a*c?b":return False if s=="aab" and p=="c*a*b":return False if s=="mississippi" and p=="m??*ss*?i*pi":return False if s=="aa" and p=="aa":return True if s=="aaa" and p=="aa":return False if s=="aa" and p=="a*":return True if s=="ab" and p=="?*":return True if s=="a" and p=="a":return True if s=="a" and p=="aa":return False if s=="aa" and p=="aaa":return False if s=="abefcdgiescdfimde" and p=="ab*cd?i*de":return True if s=="zacabz" and p=="*a?b*":return False if s=="leetcode" and p=="*e*t?d*":return False if s=="missingtest" and p=="mi*ing?s*t":return False if s=="aaaa" and p=="***a":return True if s=="" and p=="":return True if s=="" and p=="*":return True if s=="" and p=="a":return False if s=="" and p=="?":return False if s=="a" and p=="":return False if s=="a" and p=="a*":return True if s=="a" and p=="?*":return True if s=="a" and p=="*":return True if s=="b" and p=="?":return True if s=="b" and p=="??":return False if s=="bc" and p=="??":return True if s=="bcd" and p=="??":return False if s=="b" and p=="?*?":return False if s=="b" and p=="*?*?":return False if s=="b" and p=="*?*?*":return False if s=="c" and p=="*?*":return True if s=="cd" and p=="*?":return False if s=="cd" and p=="?":return False if s=="de" and p=="??":return True if s=="fg" and p=="???":return False if s=="hi" and p=="*?":return True if s=="ab" and p=="*a":return False if s=="aa" and p=="*a":return True if s=="cab" and p=="*ab":return True if s=="ab" and p=="*ab":return True if s=="ac" and p=="*ab":return False if s=="abc" and p=="*ab":return False if s=="cabab" and p=="ab*":return True if s=="cabab" and p=="*ab":return True if s=="ab" and p=="ab":return True if s=="ab" and p=="*?*?*":return True if s=="ac" and p=="ab":return False if s=="a" and p=="ab":return False if s=="abc" and p=="ab":return False if s=="" and p=="ab*":return False if s=="a" and p=="ab*":return False if s=="ab" and p=="ab*":return True if s=="ac" and p=="ab*":return False if s=="abc" and p=="ab*":return True if s=="" and p=="*a*":return False if s=="a" and p=="*a*":return True if s=="b" and p=="*a*":return True 

Berikut adalah daftar tes, seseorang berusaha keras dengan memperkenalkan daftar periksa untuk masalah ini.

Dan ini belum semua tes, sampai kita berhenti:

Ini adalah program yang sudah selesai, ditambah beberapa tes:

 %-      atom_to_list('',[]). %-  ,         atom_to_list(Str,[Ch|T]) :- atom_concat(Ch,Rest,Str),atom_length(Ch,1), atom_to_list(Rest,T). is_letter(X):-X@>=a, X@=<z. %InpitList, PattList test_pattrn([],[]). %-      test_pattrn([Ch|UnpTail],[Ch|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'?' Matches any single character. test_pattrn([Ch|UnpTail],['?'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,PatTail). %'*' Matches any sequence of characters (including the empty sequence). test_pattrn([Ch|UnpTail],['*'|PatTail]):- is_letter(Ch),test_pattrn(UnpTail,['*'|PatTail]). test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail). isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!, test_pattrn(SL,PL),!. %unit-tests framework assert_are_equal(Goal, false):-not(Goal),!,writeln(Goal->ok). assert_are_equal(Goal, true):-Goal,!,writeln(Goal->ok). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %main goal :-assert_are_equal(isMatch(aa,a),false). :-assert_are_equal(isMatch(aa,'*'),true). :-assert_are_equal(isMatch(cb,'?a'),false). :-assert_are_equal(isMatch(adceb,'*a*b'),true). :-assert_are_equal(isMatch(acdcb,'a*c?b'),false). :-assert_are_equal(isMatch(aab,'c*a*b'),false). :-assert_are_equal(isMatch(mississippi,'m??*ss*?i*pi'),false). :-assert_are_equal(isMatch(abefcdgiescdfimde,'ab*cd?i*de'),true). :-assert_are_equal(isMatch(zacabz,'*a?b*'),false). :-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false). :-assert_are_equal(isMatch(aaaa,'***a'),true). :-assert_are_equal(isMatch(b,'*?*?*'),false). 

Inilah hasil tesnya:

 isMatch(aa, *)->ok isMatch(cb, ?a)->ok isMatch(adceb, *a*b)->ok isMatch(acdcb, a*c?b)->ok isMatch(aab, c*a*b)->ok isMatch(mississippi, m??*ss*?i*pi)->ok isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok isMatch(zacabz, *a?b*)->ok isMatch(leetcode, *e*t?d*)->ok isMatch(aaaa, ***a)->ok isMatch(b, *?*?*)->ok true 

5. Kesimpulan

Prolog seperti latihan untuk pikiran. Lucu untuk menyelesaikan masalah di atasnya, meskipun solusi ini tidak memiliki optimasi. Secara manual mendapatkan tes yang lebih kompleks ternyata sangat melelahkan, sejauh ini tidak mungkin untuk membuktikan kelengkapan solusi. Dan menurut saya, saya sudah sampai pada ukuran artikel habr.

Pada contoh apa keputusan ini gagal?

Bagaimana Anda menyukai panggilan saya, penduduk Habr?

Anda dapat bersaing dengan membuat otak Anda memecahkan masalah dan menunjukkan solusi yang menarik, karena pemrograman adalah proses kreatif.