17.scm

;; This code is AWFUL and I'm sorry.

;; idea from http://stackoverflow.com/a/23718676/415518
;; This works after I added the `concat`!
(define permutations
  (lambda (ls)
    (cond
     [(null? ls) '(())]
     [(equal? (length ls) 1) `((,(car ls)))]
     [(equal? (length ls) 2)
      `((,(car ls) ,(cadr ls))
        (,(cadr ls) ,(car ls)))]
     [else
      ;; for every element in the list,
      (concat (map (lambda (elem)
                     ;; create a sublist with that element removed, and get
                     ;; all permutations of the sublist,
                     (let* [(sublist (remove-first-occurrence ls elem))
                            (perms (permutations sublist))]
                       ;; then re-add the removed element to each of those.
                       (map (lambda (l)
                              (cons elem l))
                            perms)))
                   ls))])))

(define concat
  (lambda (ls)
    (fold-right append '() ls)))

(define remove-first-occurrence
  (lambda (ls elem)
    (cond
     [(null? ls) '()]
     [(equal? (car ls) elem) (cdr ls)]
     [else (cons (car ls) (remove-first-occurrence (cdr ls) elem))])))

;; ugh so gross

(define combine-4
  (lambda (n1 n2 n3 n4)
    (append
     (map (lambda (e) `(,(cons '+ (car e)) . ,(+ n4 (cdr e)))) (combine-3 n1 n2 n3))
     (map (lambda (e) `(,(cons '- (car e)) . ,(- n4 (cdr e)))) (combine-3 n1 n2 n3))
     (map (lambda (e) `(,(cons '* (car e)) . ,(* n4 (cdr e)))) (combine-3 n1 n2 n3))
     (map (lambda (e) (if (not (zero? (cdr e)))
                          `(,(cons '/ (car e)) . ,(/ n4 (cdr e)))
                          `(,(cons 'div0 (car e)) . 0)))
          (combine-3 n1 n2 n3)))))

(define combine-3
  (lambda (n1 n2 n3)
    (append
     (map (lambda (e) `(,(cons '+ (car e)) . ,(+ n3 (cdr e)))) (combine-2 n1 n2))
     (map (lambda (e) `(,(cons '- (car e)) . ,(- n3 (cdr e)))) (combine-2 n1 n2))
     (map (lambda (e) `(,(cons '* (car e)) . ,(* n3 (cdr e)))) (combine-2 n1 n2))
     (map (lambda (e) (if (not (zero? (cdr e)))
                          `(,(cons '/ (car e)). ,(/ n3 (cdr e)))
                          `(,(cons 'div0 (car e)) . 0)))
          (combine-2 n1 n2)))))


;; produces a list of possible combinations of 2
(define combine-2
  (lambda (n1 n2)
    `((+ . ,(+ n1 n2))
      (- . ,(- n1 n2))
      (* . ,(* n1 n2))
      ,(if (not (zero? n2))
           `(/ . ,(/ n1 n2))
           `(div0 . 0)))))
  
(define zip (lambda (l1 l2) (map list l1 l2)))

;; answer format: ((+ + . +) . 19)
(define answer-match?
  (lambda (target-num ans)
    (equal? target-num (cdr ans))))

(define solve
  (lambda (n1 n2 n3 n4)
    (let* ([perms (permutations `(,n1 ,n2 ,n3 ,n4))]
           [answers (map (lambda (perm)
                                   (combine-4 (car perm)
                                              (cadr perm)
                                              (caddr perm)
                                              (cadddr perm)))
                         perms)]
           [candidates (zip perms answers)])

      (zip perms (map (lambda (y)
                        (filter (lambda (x)
                                  (answer-match? 17 x)) y)) answers)))))

;; > (solve 6 6 5 2)
;; (((6 6 5 2) ()) ((6 6 2 5) ()) ((6 5 6 2) ()) ((6 5 2 6) ())
;;  ((6 2 6 5) ()) ((6 2 5 6) ()) ((6 6 5 2) ()) ((6 6 2 5) ())
;;  ((6 5 6 2) ()) ((6 5 2 6) ()) ((6 2 6 5) ()) ((6 2 5 6) ())
;;  ((5 6 6 2) ()) ((5 6 2 6) (((* + . /) . 17))) ((5 6 6 2) ())
;;  ((5 6 2 6) (((* + . /) . 17))) ((5 2 6 6) ()) ((5 2 6 6) ())
;;  ((2 6 6 5) ()) ((2 6 5 6) ()) ((2 6 6 5) ()) ((2 6 5 6) ())
;;  ((2 5 6 6) ()) ((2 5 6 6) ()))

;; I know, I know, this is almost unreadable, but what it means is
;; that if you combine 5, 6, 2, and 6 with the operations listed (*,
;; +, /) in REVERSE order, you get 17.

;; 5 / 6 = 5/6
;;   + 2 = 17/6
;;   * 6 = 17.  Yay!