arithmetic-puzzle-solver.rkt

#lang racket

;; A solver for the following puzzle:
;; Given 5 integers a, b, c, d, and e,
;; find an expression that combines a, b, c, and d with arithmetic operations (+, -, *, and /) to get e.

(require srfi/1)

(define ops '(+ - * /))

(define (combine4 n1 n2 n3 n4)
  (concatenate
   (map (lambda (op)
          (map (lambda (e) `(,op ,n4 ,e)) (combine3 n1 n2 n3)))
        ops)))

(define (combine3 n1 n2 n3)
  (concatenate
   (map (lambda (op)
          (map (lambda (e) `(,op ,n3 ,e)) (combine2 n1 n2)))
        ops)))

(define (combine2 n1 n2)
  (map (lambda (op) `(,op ,n1 ,n2)) ops))

(define (eval-expr e)
  (with-handlers ([exn:fail:contract:divide-by-zero?
                   (lambda (exn) +inf.0)])
    (eval e)))

(define solve
  (lambda (n1 n2 n3 n4 target)
    (let* ([perms (permutations `(,n1 ,n2 ,n3 ,n4))]
           [expr-lists (map (lambda (perm)
                              (combine4 (first perm)
                                        (second perm)
                                        (third perm)
                                        (fourth perm)))
                            perms)]
           [val-lists (map (lambda (expr-list)
                             (map eval-expr expr-list)) expr-lists)]
           ;; For each perm, see if there's a val in its val-list that is equal to target.
           ;; If so, hold on to the corresponding expr from its expr-list.
           [solutions (filter-map (lambda (perm expr-list val-list)
                                    (let ([idx (list-index (lambda (elem)
                                                             (equal? elem target)) val-list)])
                                      (if idx
                                          (list-ref expr-list idx)
                                          #f)))
                                  perms expr-lists val-lists)])
      (delete-duplicates solutions))))

;; Example: combine 6, 6, 5, and 2 with arithmetic operations to get 17:
;; > (solve 6 6 5 2 17)
;; '((* 6 (+ 2 (/ 5 6))))

;; 5 / 6 = 5/6
;;   + 2 = 17/6
;;   * 6 = 17