Hallo Anwohner , es ist Zeit, über deklarative Programmierung zu sprechen. Dies ist, wenn sie Sie am Institut gerieben haben, dass Programme nicht codiert, sondern formuliert werden können. Dies ist das Gegenteil von Imperativ, das jetzt in allen Programmiersprachen verfügbar ist. Lassen Sie uns dem funktionalen Ansatz Tribut zollen, er ist hier brüderlich und macht seine Arbeit immer tiefer in der Moderne. Hier haben Sie Lambdas in C ++ und Javascripts, vielleicht einen Haskell?

Das Traurige ist jedoch die logische, produktive Programmierung, die nur auf Prolog dargestellt werden kann .

Hier werde ich einen interessanten Gedanken für den Habr-Effekt werfen. Warum nicht einen Artikel über die Lösung eines Programmierproblems schreiben? Ich denke, es haben sich viele Beiträge herausgestellt. Ich schließe mich der Themenauswahl an. Hier ist eine originelle, neue Richtung der Entwicklung und des Wettbewerbs zwischen den Teilnehmern. Wir zeigen, wie genau wir Probleme lösen können, damit alle Leser daran interessiert sind, ihre Meinung zu äußern und auf Ihre Fehler hinzuweisen, weil Sie genügend Spezialisten für Javascript und C ++ haben. Vielleicht stoßen Pythognosen immer noch auf ...

Insgesamt ist der Zweck des Artikels : zum Zeitpunkt des Schreibens des Artikels ein Problem zu lösen, das zu Beginn des Beitrags noch nicht bekannt war, und Ihren Gedankencode zu zeigen, dies mit dem Kurs und der erhaltenen Arbeitslösung zu bestätigen. Für diese Prüfung benötigen Sie jedoch einen Schiedsrichter, den Sie selbst nicht überprüfen. Ich werde leetcode.com in dieser Rolle wählen .

1. Also

Hier wählen wir die Aufgabe aus, die den schwierigsten am nächsten kommt, und versuchen, sie in Prolog zu lösen. Wir müssen zeigen, wie unterhaltsam sie ist.

2. Aufgabe 44. Wildcard-Matching

Implementieren Sie anhand einer Eingabezeichenfolge (n) und eines Musters (p) einen Platzhaltermusterabgleich mit Unterstützung für '?' und '*'.

'?' Entspricht einem einzelnen Zeichen.
'*' Entspricht einer beliebigen Zeichenfolge (einschließlich der leeren Folge).
Der Abgleich sollte die gesamte Eingabezeichenfolge abdecken (nicht teilweise).

Hinweis:

s könnte leer sein und enthält nur Kleinbuchstaben az.
p könnte leer sein und enthält nur Kleinbuchstaben az und Zeichen wie? oder *.
Beispiel 1:
Eingabe:
s = "aa"
p = "a"
Ausgabe: false
Erläuterung: "a" stimmt nicht mit der gesamten Zeichenfolge "aa" überein.

Beispiel 2:
Eingabe:
s = "aa"
p = '*'
Ausgabe: wahr

Erläuterung: '*' entspricht einer beliebigen Sequenz.

Beispiel 3:
Eingabe:
s = "cb"
p = "? a"
Ausgabe: false
Erklärung: '?' entspricht 'c', aber der zweite Buchstabe ist 'a', was nicht mit 'b' übereinstimmt.

Beispiel 4:
Eingabe:
s = "adceb"
p = "* a * b"

Ausgabe: wahr
Erläuterung: Der erste "Stern" entspricht der leeren Sequenz, während der zweite * der Teilzeichenfolge "dce" entspricht.

Beispiel 5:
Eingabe:
s = "acdcb"
p = "a * c? b"
Ausgabe: false

3. Dies ist der Zug

Wow))) (Moderatoren entschuldigen mich), es gab eine Aufgabe, bei der es notwendig ist, ein Prädikat zu implementieren. Wunder, Sie müssen nicht einmal E / A ausführen, was in einer solchen Umgebung schwierig sein kann. Am Eingang einfache Typen, am Ausgang Boolean. Grundstufe.

Beim Aufstellen von Zitiersymbolen habe ich mich kurz mit der Aufgabe vertraut gemacht. Wir haben eine endliche Zustandsmaschine. Es gibt eine Kette von Zeichen. Es handelt sich um eine Vorlage. Wir müssen sie überprüfen und das Zustandsdiagramm umgehen. Wenn wir also das Ende des Scheitelpunkts erreichen, ist die Antwort wahr. Dies ist die Aufgabe für die umgekehrte Suche.

Dann fahren Sie fort, ich schreibe sofort einen Entwurf hier, dann werde ich eine Arbeitsversion zeigen:
Eine Zeile ... im Prolog ist ein wichtiger Datentyp eine Liste, ein rekursives Konzept, das deklarativ beschrieben wird. Sie müssen also damit arbeiten und Zeichenfolgen in Listen von Atomen umwandeln. Ein Atom ist übrigens nicht nur ein Symbol, obwohl es auch ein String mit einem kleinen Buchstaben ohne Leerzeichen ist. Für Prolog sind es String-Konstanten, und Sie können keine Anführungszeichen setzen.

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

Entschuldigung für mein Englisch, wir werden es derzeit in der besten Umgebung überprüfen, swi-prolog.org . Hier gibt es einen Online-Editor:

Ups. Dies ist, was es bedeutet, niemanden zu täuschen, es ist eine hohe Eintrittsschwelle, Aufrufe von Bibliotheksprädikaten sind nicht korrekt. Wir suchen nach den richtigen eingebauten Prädikaten für die Arbeit mit Atomen.
Und auf dem Bild gibt es eine Meldung, dass die Variable H nicht beansprucht wurde, ein Fehler in der Logik, der Kopf der Liste ist das erste Zeichen und an seiner Stelle sollte Ch stehen .

Hier ist eine Dokumentation:

atom_concat (? Atom1 ,? Atom2 ,? Atom3)
Atom3 bildet die Verkettung von Atom1 und Atom2. Mindestens zwei der Argumente müssen zu Atomen instanziiert werden. Dieses Prädikat ermöglicht auch den Modus (-, -, +), bei dem das dritte Argument nicht deterministisch in zwei Teile aufgeteilt wird (wie in Anhang / 3 für Listen). SWI-Prolog erlaubt atomare Argumente. Portabler Code muss atomic_concat / 3 verwenden, wenn Nicht-Atom-Argumente beteiligt sind.

atom_length (+ Atom, -Length)
True, wenn Atom ein Atom mit Längenzeichen ist. Die SWI-Prolog-Version akzeptiert alle Atomtypen sowie Codelisten und Zeichenlisten. Neuer Code sollte diese Funktion vermeiden und write_length / 3 verwenden, um> die Anzahl der Zeichen zu ermitteln, die geschrieben würden, wenn das Argument an write_term / 3 übergeben würde.

3.1 Atom in der Liste der Atome

So

3.2 Die Zustandsmaschine selbst

Stellen Sie sich ein Diagramm vor, das Zeichen aus einer Vorlage liest und die Übereinstimmung mit den Zeichen in der Eingabezeile überprüft. Lösungsentwurf:

 %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). 

Machen wir die endgültige Schnittstelle:
isMatch (S, P): - atom_to_list (S, SL), atom_to_list (P, PL),!, test_pattrn (SL, PL),!.

Hier sind alle Beispiele aus der Erklärung des Problems:

4. Schiedsrichter

Es scheint, dass die Entscheidung fertig ist, jetzt schalten wir den Schiedsrichter ein. Auf der Website leetcode.com (ja, ja, wir lösen das Problem Nr. 44) erhalten wir Tests und versuchen, diese nacheinander mit unserer Implementierung auszuführen. Ein Pech, sie akzeptieren keine Programme auf Prolog .

Nichts, wir werden alle Aufgaben einzeln erledigen:

 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 

Hier ist eine Liste von Tests, die jemand versucht hat, indem er eine solche Checkliste für dieses Problem eingeführt hat.

Und das sind nicht alle Tests, bis wir aufhören:

Hier ist das fertige Programm sowie einige Tests:

 %-      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). 

Hier sind die Testergebnisse:

 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. Fazit

Prolog ist wie ein Training für den Geist. Es ist lustig, Probleme darauf zu lösen, obwohl diese Lösung keine Optimierung hatte. Das manuelle Durchführen komplexerer Tests erwies sich als sehr mühsam, so dass die Vollständigkeit der Lösung bisher nicht nachgewiesen werden konnte. Und es scheint mir, dass ich bereits die Größe eines Habr-Artikels erreicht habe.

An welchem ​​Beispiel scheitert diese Entscheidung?

Wie gefällt dir mein Anruf, die Einwohner von Habr?

Sie können konkurrieren, indem Sie Ihr Gehirn dazu bringen, Probleme zu lösen und interessante Lösungen zu zeigen, denn Programmieren ist ein kreativer Prozess.