Quellcode Porno

[1unitedpower]

Habt ihr mal versucht ein Programm zu schreiben, das Sudoku-Puzzle lösen kan? Dann versucht euch mal daran zu erinnern, wie umfangreich der entstandende Quellcode dafür geworden ist, oder nehmt euch jetzt die Zeit darüber nachzudenken, auf wieviele Zeilen ihr es in der Programmiersprache eurer Wahl wohl bringen würdet.

Ich habe heute Abend bei einer Fingerübung ein solches Programm in Prolog geschrieben, danach habe ich mich nach anderen Prolog-Lösungen umgesehen und bin auf diesen genialen 15-Zeiler gestoßen. Das haut mich aus den Socken.

[alt]

Tja Alter,

da kannste mal sehen, wie dumm so Sprüche sind wie Gibts alles schon, Du erfindest das Rad neu. Btw., auf DeinerRöhre gibts 'zig Videos, wo in jeweils über einer Stunde erklärt wird, wie ein Chat mit WebSocket funktioniert incl. PHP Code.

Ich erkläre es Dir in fünf Minuten mit einem Code der lässig auf eine DIN A 4 Seite passt :)

Schönes Wochenende,

[Karl Kartoffel]

bin auf diesen genialen 15-Zeiler gestoßen. Das haut mich aus den Socken.

Das Programm benutzt eine Bibliothek, die, der Beschreibung nach, nicht einmal zum Standardumfang von Prolog gehört. Ich kann das nicht im Detail bewerten, aber worauf ich hinaus will: Ich baue dir einen Sudoku-Löser in einem Einzeiler, indem ich den ganzen Code in eine Bibliothek stecke.

Dein "genial" und Aus-den-Socken-Hauen täte ich insofern streichen und widme mich lieber dem Stotterschreib im Betreff.

[1unitedpower]

bin auf diesen genialen 15-Zeiler gestoßen. Das haut mich aus den Socken.

Das Programm benutzt eine Bibliothek, die, der Beschreibung nach, nicht einmal zum Standardumfang von Prolog gehört. Ich kann das nicht im Detail bewerten, aber worauf ich hinaus will: Ich baue dir einen Sudoku-Löser in einem Einzeiler, indem ich den ganzen Code in eine Bibliothek stecke.

Berechtigte Kritik, ich möchte das mit zwei Vergleichen einschätzen: Die Funktionen trim() und array_map() aus PHP gehören nicht zum Sprachkern, sondern werden in den String- und Array-Erweiterung respektive definiert. Das DOM gehört nicht zum JavaScript-Kern, es ist trotzdem eine Standard-API in allen Browsern, oder in Spec-Sprech: document ist kein built-in object sondern ein standard object. Auf vergleichbare Art gehört Constraint Logic Programming over Finite Domains nicht zum Prolog-Kern, ist aber Teil von SWI Prolog.

[seth]

gudn tach!

Habt ihr mal versucht ein Programm zu schreiben, das Sudoku-Puzzle lösen kan?

ja, alter hut. schwieriger und interessanter ist es, automatisch zufaellige sudokus zu erstellen, die dann ein mensch loesen koennen soll.

Dann versucht euch mal daran zu erinnern, wie umfangreich der entstandende Quellcode dafür geworden ist, oder nehmt euch jetzt die Zeit darüber nachzudenken, auf wieviele Zeilen ihr es in der Programmiersprache eurer Wahl wohl bringen würdet.

in perl geht's mit ca. 2 zeilen, siehe da oder auch dort.

prost

seth

[1unitedpower]

ja, alter hut. schwieriger und interessanter ist es, automatisch zufaellige sudokus zu erstellen, die dann ein mensch loesen koennen soll.

Jedes wohldefinierte Sudoku-Spielfeld ist im Grunde auch vom Menschen lösbar. Eine Schwierigkeit, die ich beim Menschen vermute, ist es, Spiele zu lösen, die mehrere zulässige Lösungen besitzen. Das sind also Spiele, die durch die vorgegebenen Zahlen nicht bereits eindeutig bestimmt sind.

Dann versucht euch mal daran zu erinnern, wie umfangreich der entstandende Quellcode dafür geworden ist, oder nehmt euch jetzt die Zeit darüber nachzudenken, auf wieviele Zeilen ihr es in der Programmiersprache eurer Wahl wohl bringen würdet.

in perl geht's mit ca. 2 zeilen, siehe da oder auch dort.

Definitiv auch cool, ich hätte mir noch gewünscht, dass zu jedem komprmierten Beispiel auch der ursprüngliche Algorithmus in lesbarer Form existierte. So fällt es schwer die Implementierngen zu vergleichen, zum Beispiel bzgl. Laufzeit oder ob die Algorithmen jeweils genau eine Lösung oder alle finden.

[Der Martin]

Hallo,

Jedes wohldefinierte Sudoku-Spielfeld ist im Grunde auch vom Menschen lösbar. Eine Schwierigkeit, die ich beim Menschen vermute, ist es, Spiele zu lösen, die mehrere zulässige Lösungen besitzen. Das sind also Spiele, die durch die vorgegebenen Zahlen nicht bereits eindeutig bestimmt sind.

ich vermute die Haupt-Schwierigkeit woanders, nämlich darin, mehrere Schritte vorauszudenken. Aus demselben Grund gibt es IMO auch viele Menschen, die Schach spielen "können", d.h. die Figuren korrekt nach den Regeln setzen, denen aber der strategische Weitblick fehlt (ich zähle mich da auch dazu).

Beim Sudoku ist es am Anfang oft so, dass mehrere Etappenlösungen möglich sind, aber nur eine davon auch bis zum Schluss ohne Widersprüche bleibt. Man muss sich also oft für einen Ansatz entscheiden: "Nehmen wir mal an, hier müsste die 4 stehen." Ein paar Züge weiter führt das in einen Widerspruch, und man muss einige Schritte zurückgehen. Aber wie weit? Und welche Kombinationen hatte man schon, welche noch nicht? Hier den Überblick zu behalten, sehe ich als die eigentliche Herausforderung, und damit tun sich manche Leute sehr schwer.

Disclaimer: Ich weiß zwar theoretisch, wie Sudoku geht, habe aber keinen Spaß daran.

So long,
 Martin

[1unitedpower]

Beim Sudoku ist es am Anfang oft so, dass mehrere Etappenlösungen möglich sind, aber nur eine davon auch bis zum Schluss ohne Widersprüche bleibt. Man muss sich also oft für einen Ansatz entscheiden: "Nehmen wir mal an, hier müsste die 4 stehen." Ein paar Züge weiter führt das in einen Widerspruch, und man muss einige Schritte zurückgehen. Aber wie weit? Und welche Kombinationen hatte man schon, welche noch nicht? Hier den Überblick zu behalten, sehe ich als die eigentliche Herausforderung, und damit tun sich manche Leute sehr schwer.

Stimmt, das beansprucht unsere kognitiven Fähigkeiten noch viel mehr.

Disclaimer: Ich weiß zwar theoretisch, wie Sudoku geht, habe aber keinen Spaß daran.

Ach du jemine, Sudoku ist auch für mich ein Spiel für die finsterste Langeweile, wenn sämtliche Alternativen ausgeschöpft sind, einschließlich Nichtstun und den Kopf vor die Wand schlagen. Es ist aber wegen seiner Einfachheit eine schöne Programmieraufgabe.

[seth]

gudn tach!

schwieriger und interessanter ist es, automatisch zufaellige sudokus zu erstellen, die dann ein mensch loesen koennen soll.

Jedes wohldefinierte Sudoku-Spielfeld ist im Grunde auch vom Menschen lösbar. Eine Schwierigkeit, die ich beim Menschen vermute, ist es, Spiele zu lösen, die mehrere zulässige Lösungen besitzen. Das sind also Spiele, die durch die vorgegebenen Zahlen nicht bereits eindeutig bestimmt sind.

ein sudoku ist normalerweise loesbar und die loesung ist eindeutig (sonst ist es schwierig, eine musterloesung anzugeben). zudem gibt es verschiedene schwierigkeitsgrade. das alles zu beruecksichtigen, ist gar nicht so leicht. in der wikipedia stehen ein bissl was zur erstellung.

prost

seth

[seth]

in perl geht's mit ca. 2 zeilen, siehe da oder auch dort.

Definitiv auch cool, ich hätte mir noch gewünscht, dass zu jedem komprmierten Beispiel auch der ursprüngliche Algorithmus in lesbarer Form existierte.

zu dem perl-beispiel (genauer: dem vorlaeufer des dort genannten) gibt's ne erklaerung.

prost

seth

[Camping_RIDER]

Aloha ;)

Ich habe heute Abend bei einer Fingerübung ein solches Programm in Prolog geschrieben, danach habe ich mich nach anderen Prolog-Lösungen umgesehen und bin auf diesen genialen 15-Zeiler gestoßen. Das haut mich aus den Socken.

Ja, nicht schlecht. Bezogen auf die anderen Antworten mag es zwar nicht die kürzeste Lösung sein, hat aber im Vergleich zu noch kürzeren Lösungen noch eine gewisse Lesbarkeit. Das zeigt eben auf, dass das Lösen eines Logikrätsels ein Heimspiel für Prolog ist - denn sowas ist einfach die Kernanwendung deklarativer Programmierung.

Die Fingerübung steht mir übrigens auch in Kürze bevor; im Sinne der Prüfungsvorbereitung bezüglich Haskell, Prolog und CHR ;)

Grüße,

RIDER

[1unitedpower]

Ja, nicht schlecht. Bezogen auf die anderen Antworten mag es zwar nicht die kürzeste Lösung sein, hat aber im Vergleich zu noch kürzeren Lösungen noch eine gewisse Lesbarkeit. Das zeigt eben auf, dass das Lösen eines Logikrätsels ein Heimspiel für Prolog ist - denn sowas ist einfach die Kernanwendung deklarativer Programmierung.

Schöner Beitrag, allerdings finde ich den Zusammenhang nicht ganz so offensichtlich. Die Bezeichnung stammt ja nicht von den Anwendungsgebieten, die die Entwickler von Prolog im Hinterkopf hatten, sondern von einem Implementierungs-Detail logischer Programmiersprachen, der SLD-Resolution für prädikatenlogische Hornformeln (die übrigens auch nicht rein deklarativ ist). Ebenso erhalten funktionale Programmiersprachen ja nicht ihre Existenzberechtigung, weil in der Welt so viele algebraische Probleme in Funktionsräumen existieren, die man lösen muss, sondern weil die für die Interpreter und Compiler zugrunde liegenden mathematischen Modelle auf dem Lambda-Kalkül aufbauen. Die Anwendungsdomänen erstrecken sich weit darüber hinaus. Aber das ist ideologisches Genörgel und im Grunde gebe ich dir recht, dass Sudoku ein Heimspiel für Prolog ist.

Die Fingerübung steht mir übrigens auch in Kürze bevor; im Sinne der Prüfungsvorbereitung bezüglich Haskell, Prolog und CHR ;)

Ich hatte die Klausur vor einem Monat und versuche jetzt mein Prolog-Wissen frisch zu haten, weil so viel Eleganz in dem Entwurf steckt. Wenn du noch gutes Lernmaterial gebrauchen kannst, kann ich das Skript meines Professors Jürgen Giesl empfehlen. Die ersten 4 Kapitel beschäftigen sich nur mit den mathematischen Grundlagen, Kapitel 5 von handelt von konzeptionellen Eigenschaften Prologs und Kapitel 6 behandelt Logikprogrammierung mit Constraints. http://verify.rwth-aachen.de/lp15/skript.pdf

[Camping_RIDER]

Aloha ;)

Ich hatte die Klausur vor einem Monat und versuche jetzt mein Prolog-Wissen frisch zu haten, weil so viel Eleganz in dem Entwurf steckt. Wenn du noch gutes Lernmaterial gebrauchen kannst, kann ich das Skript meines Professors Jürgen Giesl empfehlen. Die ersten 4 Kapitel beschäftigen sich nur mit den mathematischen Grundlagen, Kapitel 5 von handelt von konzeptionellen Eigenschaften Prologs und Kapitel 6 behandelt Logikprogrammierung mit Constraints. http://verify.rwth-aachen.de/lp15/skript.pdf

Ich hab da mehr so das Gesamtpaket abzuliefern; d.h. Haskell, Prolog und CHR/Constraints in einer Vorlesung (2 SWS), also verhältnismäßig knapp (mir übrigens zu knapp, zumal das im Bachelorstudium die einzige nennenswerte Berührung mit nicht-imperativer Programmierung ist). Werde mir das aber gerne mal ansehen ;)

Prolog ist sowieso sehr kurz gekommen; die Hälfte des Semesters hatte Haskell für sich und die andere Semesterhälfte teilen sich Prolog und CHR (Constraint Handling Rules, falls das kein Begriff ist - keine Ahnung wie weit das konkret verbreitet ist) - und da unser Prof. der Erfinder von CHR ist, ist der Prolog-Teil eben doch recht kurz gekommen.

Die größte Schwierigkeit ist also, bezogen auf die Prüfung, dass man zwei (beziehungsweise drei) doch sehr unterschiedliche Sprachen hat, die über unterschiedliche Möglichkeiten / built-ins verfügen. Das Umdenken innerhalb einer Prüfung könnte problematisch sein, auch wenn mir Prolog/CHR und Haskell sonst eigentlich ganz gut liegen.

Grüße,

RIDER

[1unitedpower]

Prolog ist sowieso sehr kurz gekommen; die Hälfte des Semesters hatte Haskell für sich und die andere Semesterhälfte teilen sich Prolog und CHR (Constraint Handling Rules, falls das kein Begriff ist - keine Ahnung wie weit das konkret verbreitet ist) - und da unser Prof. der Erfinder von CHR ist, ist der Prolog-Teil eben doch recht kurz gekommen.

CHR war mir bis jetzt kein Begriff, es sieht aber interessant aus und erinnert mich zumindest syntaktisch an lineare Programmierung.

[Camping_RIDER]

Aloha ;)

Prolog ist sowieso sehr kurz gekommen; die Hälfte des Semesters hatte Haskell für sich und die andere Semesterhälfte teilen sich Prolog und CHR (Constraint Handling Rules, falls das kein Begriff ist - keine Ahnung wie weit das konkret verbreitet ist) - und da unser Prof. der Erfinder von CHR ist, ist der Prolog-Teil eben doch recht kurz gekommen.

CHR war mir bis jetzt kein Begriff, es sieht aber interessant aus und erinnert mich zumindest syntaktisch an lineare Programmierung.

Grundsätzlich ist CHR keine eigenständig lauffähige Sprache, sondern eine Art "Sprache in der Sprache", d.h. CHR bedient sich einer beliebigen Hostsprache (es gibt Implementierungen für verschiedenste Sprachen).

Das Grundkonzept an CHR ist ein dynamischer Constraint-Speicher und der Zustand des Programms bemisst sich dann am Vorhandensein oder nicht-vorhandensein bestimmter Constraints in diesem Speicher. Die elementarste Operation in CHR ist damit das Ablegen eines Constraints im Constraint-Speicher.

Die Programmierung findet mithilfe von drei Arten von Regeln statt (die Regeln haben jeweils eine id und können noch Bedingungen, also ein Guard-Statement, haben):

Simplifizierungsregel

"<=>"

Falls bestimmte constraints im Constraint-Speicher liegen, ersetze diese durch andere Constraints

Prolog-Pseudocode: Regel-ID @ Head-wegwerfen <=> Guard | Body

Propagierungsregel

"==>"

Falls bestimmte constraints im Constraint-Speicher liegen, füge diesem weitere Constraints hinzu

Prolog-Pseudocode: Regel-ID @ Head-behalten ==> Guard | Body

Simpagationsregel

Mischung aus "<=>" und "==>"

Falls bestimmte constraints im Constraint-Speicher liegen, entferne einen Teil von diesen constraints und füge dafür neue constraints hinzu

Prolog-Pseudocode: Regel-ID @ Head-behalten \ Head-wegwerfen <=> Guard | Body

Die Regeln werden alle nacheinander linear angewandt; jedesmal wenn sich der constraint-Speicher verändert werden nochmal alle Regeln angewandt, bis der constraint-Speicher sich nicht mehr verändert (Programmende).

Beispiel für ein CHR-Kuchenteigrezept in der Hostsprache Prolog (in swi-prolog lauffähig):

% CHR-Library einbinden

:- use_module(library(chr)).

% Deklaration der Constraints mit Anzahl möglicher Parameter

:- chr_constraint ei/0,eigelb/0,eiweiss/0,butter/1,puderzucker/1,mehl/1,vanillezucker,teig/1.

% Küchenwerkzeug: Eitrenner - entfernt Ei aus dem Speicher und fügt dafür eigelb und eiweiss hinzu (Simplifizierungsregel)

eitrenner @ ei <=> eigelb,eiweiss.

% Küchenwerkzeug: Küchenmaschine - wenn alle Zutaten in ausreichender Menge vorhanden sind, wird daraus der Teig gemischt (Simplifizierungsregel mit Guard)

kuechenmaschine @ butter(B),puderzucker(P),mehl(M),vanillezucker,eigelb <=> B >= 200, P >= 100, M >= 300 | M1 is M - 300, B1 is B - 200, P1 is P - 100, butter(B1),puderzucker(P1),mehl(M1),teig(620).

% Küchenwerkzeug: große Schüssel - darin kann der Teig zusammengefügt werden, wenn er nicht auf einmal in die Küchenmaschine gepasst hat ;) (Simplifizierungsregel)

grosse_schuessel @ teig(X),teig(Y) <=> Z is Y + X, teig(Z).

Im SWIPL kann das dann z.B. folgendermaßen gestartet werden / ergibt folgende Ausgabe:

% Eingabe - Anfangs-Constraints abspeichern
?- butter(500), puderzucker(800), mehl(600), vanillezucker,vanillezucker, ei, eigelb.
eiweiss

% Ausgabe - Inhalt des Constraint-Speichers nach Programmende
butter(100)
puderzucker(600)
mehl(0)
teig(1240)
true ;
false.

Das ist natürlich quasi ein sinnlos-Programm, veranschaulicht aber die Wirkungsweise der Simplifizierungsregel und des Constraint-Speichers ganz gut (und Propagierungsregeln sind ziemlich trivial und Simpagation ist lediglich eine Mischung von beidem).

Falls das nicht schon too much war - die Einführung in CHR fand bei uns mit Hilfe einer einzelnen PPP statt, ich war mal so frech und hab die bei mir ge-up-t.

Grüße,

RIDER

[1unitedpower]

Da hab ich mich von der syntaktischen Ähnlichkeit zur linearen Programmierung ja ordentlich hinters Licht führen lassen, denn semantisch lassen sich kaum Gemeinsamkeiten festellen. Zusammen mit den Folien hat mir deine Erklärung aber einen guten ersten Eindruck vermittelt, hört sich an, als wären CHR vor allem für künstliche Intelligenzen eine hervorrande Modellierungsmöglichkeit, lieg ich damit richtig?

[Camping_RIDER]

Aloha ;)

Da hab ich mich von der syntaktischen Ähnlichkeit zur linearen Programmierung ja ordentlich hinters Licht führen lassen, denn semantisch lassen sich kaum Gemeinsamkeiten festellen. Zusammen mit den Folien hat mir deine Erklärung aber einen guten ersten Eindruck vermittelt, hört sich an, als wären CHR vor allem für künstliche Intelligenzen eine hervorrande Modellierungsmöglichkeit, lieg ich damit richtig?

So wie ich es sehe, ja. Insofern haben CHR und Prolog (bzw. Logikprogrammierung im Allgemeinen) schon per se eine gewisse gemeinsame Basis in ihrer Ausrichtung (die Prolog-Implementierung ist auch die "ursprüngliche" Form von CHR). Vorteile von CHR sehe ich vor allem darin, dass man CHR in vielen verschiedenen Hostsprachen nutzen kann und dass die Grundlagen so überschaubar sind. Die Anwendungsmöglichkeiten und Eigenschaften von CHR in verschiedenen Anwendungen sind aber auch aktuelles Forschungsthema; insbesondere auch bei uns in Ulm.

Grüße,

RIDER

[Tabellenkalk]

Hallo,

Prolog-Wissen frisch zu haten,

schöner freudscher Verschreiber!

Gruß
Kalk