29 lines
1016 B
Common Lisp
29 lines
1016 B
Common Lisp
(defparameter *matrix* (read-matrix-from-file "0083_matrix.txt"))
|
|
|
|
(defparameter *directions* '((1 0)
|
|
(0 1)
|
|
(-1 0)
|
|
(0 -1)))
|
|
|
|
(defun path-sum-four-ways ()
|
|
(let* ((dimensions (array-dimensions *matrix*))
|
|
(goal-position (mapcar #'1- dimensions))
|
|
(states (list (cons (list 0 0) (aref *matrix* 0 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 (every #'= position goal-position)
|
|
(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)))))
|