Logicals PROLOG vs Python

[ALSO]

Ich programmiere gerade in Prolog ein Programm, das aus gegebenen Verknüfungen z.B. A= 4, B=23, X=5 usw. aus diesen Angaben dann Fragen beantworten kann wie z.B welche Nummer hat D etc.

Einsteinrätsel und Alphametiken sind in Prolog schnell zu machen aber wie sieht es mit Python aus?
Wie aufwendig ist sowas in Python und wie würde so ein Ansatz aussehen, wo finde ich ähnliches Material. Ich habe es versucht , aber in Prolog scheint es kürzer und schneller zu gehen.
Trotzdem glaube ich es geht auch in Python und will es probieren. Danke für die HiIfe VG

[nezzcarth]

Nach meinem Kenntnisstand verwenden Prolog Implementationen dazu Backtracking, d. h. im Prinzip eine Tiefensuche auf einem Suchbaum, bei der man alle möglichen Lösungskandidaten systematisch durchprobiert und ggf. zurückspringt (vom Konzept her; im Detail dürften heutige Implementationen diverse Optimierungen aufweisen). Das kann man in Python nach programmieren. Der Unterschied ist halt, dass dieser Mechanismus bei Prolog Teil der Sprache ist.

[__blackjack__]

@ALSO: Du suchst eventuell etwas in dieser Richtung: https://pypi.org/project/python-constraint/

[pillmuncher]

Vor ein paar Jahren hab ich zum Spaß eine EDSL für Prolog-Programmierung in Python geschrieben. Du kannst sie gerne ausprobieren.

https://github.com/pillmuncher/hornet

Sag bescheid, ob es funktioniert. Doku gibt es keine, nur einige Beispiele zur Verwendung, deswegen Nachfragen gerne hier oder als PM.

[ALSO]

Hi, danke. für die links.
Ich wollte eher fragen wie ihr dieses Problem in Python löst, um es vergleichen zu können:
Von B, F, I kann jeder 6, 10 oder 3 sein und analog gilt noch:
A C D E H 2 1 9 8 4
A E F H J 5 810 4 2
D E H I J 6 4 2 5 9

Was ist C E G H J ? C=1; G=7 ;J=5 ; E/H=2/4; (B=3 I=6 F=10 A=8 D=9)

[pillmuncher]

@ALSO: Die 810 sollen 8 und 0 sein, oder?

[pillmuncher]

@ALSO: Egal. Ich hab noch eine andere Prolog-in-Python-Lib geschrieben, allerdings ohne Cut. Hier: https://github.com/pillmuncher/yogic
Beispielcode für dein Problem:

Code: Alles auswählen

from itertools import permutations
from lib.yogic import *

def equate(letters, numbers):
    return alt(*[unify(letters, list(permutated_numbers))
                for permutated_numbers in permutations(numbers)])

# ----8<---------8<---------8<---------8<---------8<---------8<---------8<-----

a = var()
b = var()
c = var()
d = var()
e = var()
f = var()
h = var()
i = var()
j = var()

equation = seq(
        equate([b, f, i], [6, 10, 3]),
        equate([a, c, d, e, h], [2, 1, 9, 8, 4]),
        equate([d, e, h, i, j], [6, 4, 2, 5, 9]),
)

for n, each in enumerate(resolve(equation)):
    print('Ergebnis', n, '----------------------------------------------')
    print('a', each[a])
    print('b', each[b])
    print('c', each[c])
    print('d', each[d])
    print('e', each[e])
    print('f', each[f])
    print('h', each[h])
    print('i', each[i])
    print('j', each[j])
    print()
print()

Ergebnis:

Code: Alles auswählen

Ergebnis 0 ----------------------------------------------
a 1
b 10
c 8
d 2
e 9
f 3
h 4
i 6
j 5

Ergebnis 1 ----------------------------------------------
a 1
b 10
c 8
d 2
e 4
f 3
h 9
i 6
j 5

Ergebnis 2 ----------------------------------------------
a 1
b 10
c 8
d 9
e 2
f 3
h 4
i 6
j 5

Ergebnis 3 ----------------------------------------------
...
Ergebnis 23 ----------------------------------------------
a 8
b 3
c 1
d 4
e 9
f 10
h 2
i 6
j 5

Die Zeile mit der 810 in deinen Vorgaben produziert kein Ergebnis, also hab ich sie weggelassen.

[ALSO]

Sorry meine Schuld, es ist nicht 810 sondern 8,10
Von B, F, I kann jeder 6, 10 oder 3 sein und analog gilt noch:
A,C, D, E, H 2, 1, 9, 8, 4
A, E, F, H, J 5, 8,10, 4, 2
D, E, H, I, J 6, 4, 2, 5, 9

Was ist C E G H J ? C=1; G=7 ;J=5 ; E/H=2/4; (B=3 I=6 F=10 A=8 D=9)

[ALSO]

Vielen Dank - echt super mit der fehlenden Zeile müsste es eindeutig sein

[ALSO]

Habe die Zeile ergänzt - wo finde ich das lib.yogic - ich habe anaconda




equation = seq(
equate([b, f, i], [6, 10, 3]),
equate([a, c, d, e, h], [2, 1, 9, 8, 4]),
equate([a, e, f, h, j], [5, 8, 10, 4, 2]),
equate([d, e, h, i, j], [6, 4, 2, 5, 9]),
)

[pillmuncher]

Habe die Zeile ergänzt - wo finde ich das lib.yogic - ich habe anaconda

Hier: https://github.com/pillmuncher/yogic

Es ist aber nur ein Spielzeug. Ich bastel mir alle paar Jahre ein neues Prolog-in-Python als Übungsprojekt.

[ALSO]

ich finde es super

[pillmuncher]

@ALSO: Danke, freut mich, dass es für jemanden nützlich ist. Übrigens habe ich gerade gesehen, dass ich doch einen Cut eingebaut hatte.

Ein paar Anmerkungen:

• Es ist wirklich nur ein Spielzeug. Es gibt nicht mal Dokumentation.
• backtracking.py implementiert die Backtracking-Monade (Dont fear the Monad: https://www.youtube.com/watch?v=ZhuHCtR3xq8).
• Monaden sind letztlich nur eine bequeme und formalisierte Art, Continuation Passing Style zu verwenden, ohne das jedesmal explizit programmieren zu müssen. Die Mutter aller Monaden ist deswegen die Continuation-Monade, mit der sich alle anderen Monaden bauen lassen. Prolog-in-Python lässt sich un-monadisch ebenfalls leicht bauen, wenn man nur Continuations verwendet, wie hier: https://www.ps.uni-saarland.de/~duchier ... tions.html
• Python hat standardmäßig Strict Evaluation (https://wiki.c2.com/?StrictEvaluation). Damit trotzdem rekursive Aufrufe wie in Prolog möglich werden, gibt es einen @recursive Decorator (https://www.python.org/dev/peps/pep-0318).
• Es gibt in yogic zwei Arten, Prädikate zu bauen: Entweder man gibt aus einer Funktion aus bereits bestehenden Prädikaten zusammengesetzte Werte zurück, z.B. mittels alt() ("oder") bzw. seq() ("und"), oder man deklariert mittels @predicate eine Funktion als Prädikat und gibt dann einzelne Auswertungs-Ergebnisse mittels yield zurück, die damit implizit als Werte in einem seq() interpretiert werden.
• Sofern man beide Dekoratoren verwendet, muss @recursive immer vor @predicate stehen.
• tailcalls.py wurde gar nicht verwendet, deswegen habe ich es jetzt rausgenommen.
• Der Name yogic ist nur ein Witz. Er setzt sich zusammen aus dem y in Python und dem ogic in Logic, und bezieht sich auf das Yogische Fliegen:

[ALSO]

Ah ok - ich schaue das durch.

wie ist es mit der Rechenzeit bei komplexeren Aufgaben?
z.B.

[ALSO]

Läuft irgendwie nicht - syntax? - modul?

Code: Alles auswählen

from itertools import permutations
from lib.yogic import *

def equate(letters, numbers):
    return alt(*[unify(letters, list(permutated_numbers))
                for permutated_numbers in permutations(numbers)])

# ----8<---------8<---------8<---------8<---------8<---------8<---------8<-----

a = var()
b = var()
c = var()
d = var()
e = var()
f = var()
g = var()
h = var()
i = var()
j = var()
k = var()
l = var()

equation = seq(
        equate([a, d, e, f, j, k, l], [2, 8, 6, 9, 1, 7, 4]),
        equate([a, b, c, e, h, i, j], [11, 1, 12, 8, 4, 5, 10]),
        equate([b, c, d, e, f, g, h], [5, 2, 9, 8, 11, 3, 10]),
        equate([a, d, f, g, i, j, k], [4, 6, 12, 1, 2, 9, 3]),
        equate([b, c, g, h, j, l], [3, 4, 7, 11, 5, 10]),                      
)

for n, each in enumerate(resolve(equation)):
    print('Ergebnis', n, '----------------------------------------------')
    print('a', each[a])
    print('b', each[b])
    print('c', each[c])
    print('d', each[d])
    print('e', each[e])
    print('f', each[f])
    print('g', each[g])
    print('h', each[h])
    print('i', each[i])
    print('j', each[j])
    print('k', each[k])
    print('l', each[l])     
    print()
print()

[ALSO]

Läuft nicht wegen modul?

[pillmuncher]

@ALSO: Entweder wir kommunizieren öffentlich oder über PMs. Bitte entscheide dich. Und ich weiß nicht, was du mit Modul meinst. Yogic? Oder dein Modul?

[pillmuncher]

Hier ist noch eine Lösung, ganz ohne Prolog:

Code: Alles auswählen

from pprint import pprint

def find_solutions(candidates, solution, tally):
    if not candidates:
        yield solution
    else:
        variable, numbers = candidates.popitem()
        for number in numbers - tally:
            solution[variable] = number
            tally.add(number)
            yield from find_solutions(candidates, solution, tally)
            tally.remove(number)
        candidates[variable] = numbers

def solutions(equations):
    candidates = {}
    for variables, numbers in equations:
        for variable in variables:
            if variable not in candidates:
                candidates[variable] = set(numbers)
            else:
                candidates[variable].intersection_update(numbers)
    return find_solutions(candidates, {}, set())

def main():
    equations = ([
        (['a', 'd', 'e', 'f', 'j', 'k', 'l'], [2, 8, 6, 9, 1, 7, 4]),
        (['a', 'b', 'c', 'e', 'h', 'i', 'j'], [11, 1, 12, 8, 4, 5, 10]),
        (['b', 'c', 'd', 'e', 'f', 'g', 'h'], [5, 2, 9, 8, 11, 3, 10]),
        (['a', 'd', 'f', 'g', 'i', 'j', 'k'], [4, 6, 12, 1, 2, 9, 3]),
        (['b', 'c', 'g', 'h', 'j', 'l'], [3, 4, 7, 11, 5, 10]),
    ])
    for each in solutions(equations):
        print()
        pprint(list(sorted(each.items())))

if __name__ == '__main__':
    main()

[ALSO]

Super. Liefert aber alle Permutationen als output -ein bisschen umständlich aber eigentlich vollständig - wie könnte man nur die Zahlen für jeden Buchtabe ausgeben , statt "each.items" sort verwenden?