#lang racket

(module+ test
  (require rackunit))

(define (intersperse el lst)
  (if (null? lst)
      (list (list el))
      (let [(smaller-intersperse (intersperse el (cdr lst)))
            (head (car lst))]
        (cons (cons el lst)
              (map (curry cons head) smaller-intersperse)))))

(define (permutations lst)
  (if (null? lst)
      (list '())
      (let [(smaller-permutations (permutations (cdr lst)))
            (head (car lst))]
        (apply append
               (map (curry intersperse head)
                    smaller-permutations)))))

(module+ test
  (check-equal? (list->set (permutations '(1 2 3)))
                (list->set '((1 2 3)
                             (2 1 3)
                             (2 3 1)
                             (1 3 2)
                             (3 1 2)
                             (3 2 1)))))

(struct bintree (label left right))

(define (evaluate tree decs)
  (match decs
    ['() tree]
    [(cons 0 t) (evaluate (bintree-left tree) t)]
    [(cons 1 t) (evaluate (bintree-right tree) t)]))

(module+ test
  (define bool-tree
    (bintree
     'x1
     (bintree
      'x2
      (bintree 'x3 1 0)
      (bintree 'x3 0 1))
     (bintree
      'x2
      (bintree 'x3 0 0)
      (bintree 'x3 1 1))))
  (check-equal? (evaluate bool-tree '(1 0 1)) 0)
  (check-equal? (evaluate bool-tree '(0 1 1)) 1))

(define (satisficing-evaluations tree [rev-path '()])
  (match tree
    [0 '()]
    [1 (list (reverse rev-path))]
    [(bintree lbl left right)
     (let [(left-paths
            (satisficing-evaluations
             left
             (cons (list lbl 0)
                   rev-path)))
           (right-paths
            (satisficing-evaluations
             right
             (cons (list lbl 1)
                   rev-path)))]
       (append left-paths right-paths))]))