PasteRack.org
Paste # 29105
2016-07-13 04:40:08

Fork as a new paste.

Paste viewed 227 times.


Embed:

  1. #lang racket
  2.  
  3. ;; A solver for the following puzzle:
  4. ;; Given 5 integers a, b, c, d, and e,
  5. ;; find an expression that combines a, b, c, and d with arithmetic operations (+, -, *, and /) to get e.
  6.  
  7. (require srfi/1)
  8. (require racket/generator)
  9.  
  10. (define ops '(+ - * /))
  11.  
  12. (define (splits l)
  13.   (for/list ([i (in-range 1 (length l))])
  14.     (cons (take l i) (drop l i))))
  15.  
  16. ;; produces a sequence (usually lazy) of all possible combinations of `nums'
  17. ;; using operators in `ops'.
  18. (define (combine nums)
  19.   (match nums
  20.     ['() (error "impossible")]
  21.     [(list x) (list x)]
  22.     [_ (in-generator
  23.         (for* ([halves (splits nums)]
  24.                [left   (combine (car halves))]
  25.                [right  (combine (cdr halves))]
  26.                [op     ops])
  27.           (yield `(,op ,left ,right))))]))
  28.  
  29. (define (eval-expr e)
  30.   (with-handlers ([exn:fail:contract:divide-by-zero?
  31.                    (lambda (exn) +inf.0)])
  32.     (eval e)))
  33.  
  34. (define (solve n1 n2 n3 n4 target)
  35.   (delete-duplicates
  36.    (for*/list ([p (permutations (list n1 n2 n3 n4))]
  37.                [l (combine p)]
  38.                #:when (= target (eval-expr l)))
  39.      l)))
  40.  
  41. ;; Example: combine 6, 6, 5, and 2 with arithmetic operations to get 17:
  42. ;; > (solve 6 6 5 2 17)
  43. ;; '((* 6 (+ (/ 5 6) 2))
  44. ;;   (* (+ (/ 5 6) 2) 6)
  45. ;;   (* 6 (+ 2 (/ 5 6)))
  46. ;;   (* (+ 2 (/ 5 6)) 6))
  47.  
  48. ;; 5 / 6 = 5/6
  49. ;;   + 2 = 17/6
  50. ;;   * 6 = 17
  51.  
  52. (pretty-print (solve 6 6 5 2 17))

=>

'((* 6 (+ (/ 5 6) 2))

  (* (+ (/ 5 6) 2) 6)

  (* 6 (+ 2 (/ 5 6)))

  (* (+ 2 (/ 5 6)) 6))