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
@kingtim
Copy link

kingtim commented Jan 31, 2013

Nice.

It should be

(defn sum-list [m n]
  (run* [q] (== q (lvars m)) (sumo q n)))

right? Or am I missing something?

@mrb
Copy link

mrb commented Feb 1, 2013

@kingtim Confirmed!

@swannodette
Copy link
Author

@kingtim @mrb, fixed thanks!

@drcabana
Copy link

drcabana commented Feb 2, 2013

In fairness to the list comprehension approach, it can be made much faster:

(for [a (range 1 11)
      b (range 1 (- 11 a))
      c (range 1 (- 11 a b))
      d (range 1 (- 11 a b c ))
      e (range 1 (- 11 a b c d))
      f (range 1 (- 11 a b c d e))
      g (range 1 (- 11 a b c d e f))
      h (range 1 (- 11 a b c d e f g))
      i (range 1 (- 11 a b c d e f g h))
      j (range 1 (- 11 a b c d e f g h i))
      :when (= (+ a b c d e f g h i j) 10)]
  [a b c d e f g h i j])

@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