Created
August 9, 2012 12:04
-
-
Save rf/3303640 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defn lookup | |
"Lookup a variable in the model. Respects inversion of the variable if it is | |
specified with a - symbol. Returns nil if the variable is unset." | |
[model v] | |
(if (= (get v 0) \-) ; If the first character is '-' | |
(if-let [[k v] (find model (subs v 1))] ; If v is defined in the map get it | |
(not v) ; return not v if we found it | |
nil) ; otherwise return nil | |
(get model v))) ; If it isn't inverted simply get it | |
(def foobar {"A" false, "B" true}) | |
(println "should return false:" (lookup foobar "A")) | |
(println "should return false:" (lookup foobar "-B")) | |
(println "should return true:" (lookup foobar "B")) | |
(println "should return nil:" (lookup foobar "-C")) | |
(defn satisfiable? | |
"Checks to see if a given clause is satisfiable given a model." | |
[model, clause] | |
(let [lookups (map #(lookup model %) clause)] | |
(cond | |
(some true? lookups) true ; if some var is true the clause is true | |
(every? false? lookups) false ; if every var is false the clause is false | |
:otherwise nil))) ; otherwise we don't know what it is | |
(def barbaz '("A" "-B")) | |
(def buzfuz '("-A" "-B")) | |
(def sprangadang '("A" "-B" "C")) | |
(println "should return false:" (satisfiable? foobar barbaz)) | |
(println "should return true:" (satisfiable? foobar buzfuz)) | |
(println "should return nil:" (satisfiable? foobar sprangadang)) | |
(defn solve | |
"Solves some set of clauses recursively, given some model and some list of | |
variables present in the clauses." | |
[variables, clauses, model] | |
(let [results (map #(satisfiable? model %) clauses)] | |
(cond | |
; If some clause can't be satisfied, this model doesn't work. | |
(some false? results) false | |
; If every clause can be satisfied, this model works. | |
(every? true? results) model | |
:otherwise ; recurse | |
; Choose the first variable that is not yet defined .. | |
(if-let [[choice] (filter #(nil? (get model %)) variables)] | |
; And try setting it to true; if that doesn't work, try false. | |
(or | |
(solve variables clauses (assoc model choice true)) | |
(solve variables clauses (assoc model choice false))) | |
false)))) | |
(def rock '(("A" "-B") ("-A" "-B"))) | |
(def paper '(("A" "-B") ("-A" "-B") ("A" "B" "C"))) | |
(def scissors '(("-A" "B") ("-B") ("A"))) | |
(println "should return a model:" (solve '("A" "B") rock {})) | |
(println "should return a model:" (solve '("A" "B" "C") paper {})) | |
(println "should return false:" (solve '("A" "B") scissors {})) |
ohpauleez
commented
Aug 9, 2012
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment