Implement a faster algorithm

Question

I have been stuck on this question for days. Apparently I need to write a better algorithm to win the algorithm below. The below code is implemented from the famous Aima file. Is there any expert here who could guide me on how to win the algorithm?

(defun find-closest (list)
    (x (car (array-dimensions list)))
        (y (cadr (array-dimensions list)))
            (let ((elems (aref list x y)))
                (dolist (e elems)
                    (when (eq (type-of e) type)
                        (return-from find-closest (list x y)))) nil))

I tried implementing a DFS but failed and I do not quite know why. Below is my code.

 (defun find-closest (list)
   (let ((open (list list)) 
    (closed (list))
    (steps 0)
    (expanded 0)
    (stored 0))
    (loop while open do
      (let ((x (pop open))) 
        (when (finished? x)
          (return (format nil "Found ~a in ~a steps.
Expanded ~a nodes, stored a maximum of ~a nodes." x steps expanded stored)))
        (incf steps)
        (pushnew x closed :test #'equal)
        (let ((successors (successors x)))
          (incf expanded (length successors))
          (setq successors
            (delete-if (lambda (a)
                 (or (find a open :test #'equal)
                     (find a closed :test #'equal)))
                   successors))
          (setq open (append open successors))
          (setq stored (max stored (length open))))))))

Answer 1

Looking at the code, the function find-some-in-grid returns the first found thing of type. This will, essentially, give you O(n * m) time for an n * m world (imagine a world, where you have one dirt on each line, alternating between "left-most" and "right-most".

Since you can pull out a list of all dirt locations, you can build a shortest traversal, or at least a shorter-than-dump traversal, by instead of picking whatever dirt you happen to find first you pick the closest (for some distance metric, from the code it looks like you have Manhattan distances (that is, you can only move along the X xor the Y axis, not both at the same time). That should give you a robot that is at least as good as the dumb-traversal robot and frequently better, even if it's not optimal.

With the provision that I do NOT have the book and base implementation purely on what's in your question, something like this might work:

(defun find-closest-in-grid (radar type pos-x pos-y)
  (labels ((distance (x y) 
              (+ (abs (- x pos-x)) 
                 (abs (- y pos-y)))))
     (destructuring-bind (width height) 
         (array-dimensions radar)
       (let ((best nil)
            ((best-distance (+ width height))))
         (loop for x from 0 below width
           do (loop for y from 0 below height
                 do (loop for element in (aref radar x y)
                       do (when (eql (type-of element) type)
                             (when (<= (distance x y) best-distance)
                                (setf best (list x y))
                                (setf best-distance (distance x y))))))))
         best)))