Skip to content

Instantly share code, notes, and snippets.

@lkuper
Last active November 18, 2020 19:56
Show Gist options
  • Save lkuper/fdb9670a4b4dc180eb9e9239f786412d to your computer and use it in GitHub Desktop.
Save lkuper/fdb9670a4b4dc180eb9e9239f786412d to your computer and use it in GitHub Desktop.
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment