Skip to content

Instantly share code, notes, and snippets.

@swannodette
Last active July 5, 2022 13:32
Show Gist options
  • Save swannodette/4686830 to your computer and use it in GitHub Desktop.
Save swannodette/4686830 to your computer and use it in GitHub Desktop.
Generates lists of size M containing natural numbers which add up to N
;; list comprehensions are often used as a poor man's Prolog
;; consider the following, it has only one solution
;; [1 1 1 1 1 1 1 1 1 1] yet we actually consider 10^10 possibilities
(for [a (range 1 11)
b (range 1 11)
c (range 1 11)
d (range 1 11)
e (range 1 11)
f (range 1 11)
g (range 1 11)
h (range 1 11)
i (range 1 11)
j (range 1 11)
:when (= (+ a b c d e f g h i j) 10)]
[a b c d e f g h i j])
;; compare to, which returns instantly
(sum-list 10 10)
(defn sumo
([l n] (sumo l 0 n))
([l acc n]
(matche [l]
([[]] (fd/== acc n))
([[x . r]]
(fresh [nacc]
(fd/in x (fd/interval 1 n))
(fd/+ acc x nacc)
(sumo r nacc n))))))
(defn sum-list [m n]
(run* [q] (== q (lvars m)) (sumo q n)))
;; (every? #(and (= (count %) 5) (= (reduce + %) 10)) (sum-list 5 10)) => true
@swannodette
Copy link
Author

@drcabana thanks for adding that, a nice way to demonstrate pruning the search.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment