Skip to content

Instantly share code, notes, and snippets.

@arademaker
Last active August 29, 2015 14:14
Show Gist options
  • Save arademaker/1717903c5ae196586721 to your computer and use it in GitHub Desktop.
Save arademaker/1717903c5ae196586721 to your computer and use it in GitHub Desktop.
chickens
;; utilities
(defun combinations (&rest lists)
(if (car lists)
(mapcan (lambda (inner-val)
(mapcar (lambda (outer-val)
(cons outer-val inner-val))
(car lists)))
(apply #'combinations (cdr lists)))
(list nil)))
(defmacro range (i j)
`(loop for x from ,i to ,j collect x))
(defmacro intersection-3 (a b c)
`(intersection ,a (intersection ,b ,c :test #'equal)
:test #'equal))
;; compute the candidates
(defun f (n)
(labels ((test (i p1 p2)
(and (> p1 p2)
(equal 3500 (+ (* i p1) (* (- n i) p2))))))
(loop with r = (range 1 400)
for v in (combinations (range 0 n) r r)
when (apply #'test v)
collect (subseq v 1))))
#|
The output:
cl-user> (time (intersection-3 (f 26) (f 10) (f 16)))
; cpu time (non-gc) 0.638612 sec user, 0.007279 sec system
; cpu time (gc) 0.116465 sec user, 0.001272 sec system
; cpu time (total) 0.755077 sec user, 0.008551 sec system
; cpu time (thread) 0.637792 sec user, 0.006627 sec system
; real time 0.770082 sec (99.16%)
; space allocation:
; 18,568,715 cons cells, 7,680 other bytes, 0 static bytes
; Page Faults: major: 0 (gc: 0), minor: 0 (gc: 0)
((375 125))
|#
@arademaker
Copy link
Author

This is the solution for http://goo.gl/i433b9. First price is 375 and the second price is 125. If the second price can be zero, then change (range 1 400) to (range 0 400)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment