Skip to content

Instantly share code, notes, and snippets.

@lkuper
Last active October 27, 2019 17:17
Show Gist options
  • Save lkuper/3beffacf93b1256e7b97799d753cae23 to your computer and use it in GitHub Desktop.
Save lkuper/3beffacf93b1256e7b97799d753cae23 to your computer and use it in GitHub Desktop.
;; 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!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment