30 lines
1.0 KiB
Common Lisp
30 lines
1.0 KiB
Common Lisp
(defparameter *matrix* (read-matrix-from-file "0082_matrix.txt"))
|
|
|
|
(defparameter *directions* '((1 0)
|
|
(0 1)
|
|
(-1 0)))
|
|
|
|
(defun path-sum-three-ways ()
|
|
(let* ((dimensions (array-dimensions *matrix*))
|
|
(goal-column (1- (second dimensions)))
|
|
(states (loop for r from 0 below (first dimensions)
|
|
collect (cons (list r 0)
|
|
(aref *matrix* r 0))))
|
|
(visited (make-hash-table :test 'equal)))
|
|
(loop with sums = nil
|
|
for state = (pop states)
|
|
while state
|
|
do (destructuring-bind (position . sum) state
|
|
(setf (gethash position visited) t)
|
|
(when (= (second position) goal-column)
|
|
(push sum sums))
|
|
(loop for offset in *directions*
|
|
for new-position = (mapcar #'+ position offset)
|
|
when (and (every #'in-bounds-p new-position dimensions)
|
|
(not (gethash new-position visited)))
|
|
do (push (cons new-position
|
|
(+ sum (apply #'aref (cons *matrix* new-position))))
|
|
states))
|
|
(setf states (sort states #'< :key #'cdr)))
|
|
finally (return (apply #'min sums)))))
|