The Broken Weight Problem

broken-weight.lisp

;;;; Inspired by http://directed-procrastination.blogspot.com/2011/11/broken-weight-problem.html
;;;;
;;;; An example of using a generator to make your nondeterminism read nice.

(in-package :screamer-user)

(defun a-subset (set)
  "Non-deterministically returns all the subsets of SET, including the empty set NIL."
  (when set
    (either
      (list (car set))
      (cons (car set) (a-subset (cdr set)))
      (a-subset (cdr set)))))

(one-value
    (let* ((a (an-integer-between 1 39))
           (b (an-integer-between 1 39))
           (c (an-integer-between 1 39))
           (d (an-integer-between 1 39))
           (all (list a b c d)))
      (assert! (= 40 (+v a b c d)))
      (loop for weight from 1 upto 40
            do (let* ((left (a-subset all))
                      (right (a-subset (set-difference all left)))
                      (left-weight (apply #'+ left))
                      (right-weight (apply #'+ right)))
                 (assert! (or (= (+v weight left-weight) right-weight)
                              (= (+v weight right-weight) left-weight)))))
      all))