[2015-08-28] Challenge #229 [Hard] Divisible by 7

lucky7s.lisp

; https://www.reddit.com/r/dailyprogrammer/comments/3irzsi/20150828_challenge_229_hard_divisible_by_7/

(defun lucky7s (n &aux
                  (nx0 (floor (+ n 2) 3))
                  (ny0 (floor (+ n 1) 3))
                  (nz0 (floor n       3))
                  (cache (make-hash-table :test 'equal)))
  (labels ((nt (k m &aux (n 0) (t0 0) nsub tsub)
             (cond ((zerop m)
                    (values (if (zerop k) 1 0) 0))
                   ((gethash (list k m) cache)
                    (values-list (gethash (list k m) cache)))
                   (t
                    (loop for a below 10
                          for ksub = (mod (if (oddp m) (- k a) (+ k a)) 7) do
                          (setf (values nsub tsub) (nt ksub (1- m)))
                          (incf n nsub)
                          (incf t0 (+ tsub (* a (expt 1000 (1- m)) nsub))))
                    (setf (gethash (list k m) cache) (list n t0))
                    (values n t0)))))
    (loop for x below 7
          for y = (mod (- x) 7)
          for z = x
          for (nx tx) = (multiple-value-list (nt x nx0))
          for (ny ty) = (multiple-value-list (nt y ny0))
          for (nz tz) = (multiple-value-list (nt z nz0))
          sum (+ (* tx ny nz) (* 10 nx ty nz) (* 100 nx ny tz)))))