Wheres-waldo function in LISP

Question

I am trying to solve problems on LISP and I am stuck with this problem for many days.

"Write a function, called wheres-waldo, that takes a lisp object (i.e., a data structure built from conses) as argument and returns a Lisp expression that extracts the symbol waldo from this object, if it is present"

For example,

E.g: (wheres-waldo '(emerson ralph waldo)) =

OUTPUT: (FIRST (REST (REST '(EMERSON RALPH WALDO))))

E.g: (wheres-waldo '(mentor (ralph waldo emerson) (henry david thoreau))) =

OUTPUT: (FIRST (REST (FIRST (REST 
                 '(MENTOR (RALPH WALDO EMERSON)
                          (HENRY DAVID THOREAU))))))

I have written some recursion for example,

(defun wheres-waldo(lispOBJ)
    (cond ((null lispOBJ) nil)
    (equalp (first lispOBJ) waldo)
    ( t (***stuck here how to write recursion for this***))
)

I found this question from http://ai.eecs.umich.edu/people/wellman/courses/eecs492/f94/MP1.html wheres-waldo. Any help would be appreciated. Thank you.

Answer 1

You need to loop over a list, and if an element is a list, recurse into the sublist, exactly as you would implement a deep search. The only difference is that, in order to produce the required output, you need to carry on the s-expression retracing the functions you used to get there.

Here is one possible implementation. Note that I have used the more traditional car and cdr instead of first and rest - they are equivalent.

(defun whereis (who obj &optional (sexp (list 'quote obj)))
  (cond
   ; we found the object - return the s-expr
   ((eq obj who) sexp)
   ; try car and the cdr
   ((and obj (listp obj)) 
    (or (whereis who (car obj) (list 'car sexp))
        (whereis who (cdr obj) (list 'cdr sexp))))))

then:

? (whereis 'waldo '(emerson ralph waldo))
(CAR (CDR (CDR '(EMERSON RALPH WALDO))))

? (whereis 'waldo '(mentor (ralph waldo emerson) (henry david thoreau)))
(CAR (CDR (CAR (CDR '(MENTOR (RALPH WALDO EMERSON) (HENRY DAVID THOREAU))))))

? (whereis 'thoreau '(mentor (ralph waldo emerson) (henry david thoreau)))
(CAR (CDR (CDR (CAR (CDR (CDR '(MENTOR (RALPH WALDO EMERSON) (HENRY DAVID THOREAU))))))))

? (whereis 'scotty '(beam me up . scotty))
(CDR (CDR (CDR '(BEAM ME UP . SCOTTY))))

? (whereis 'waldo '(emerson ralph))
NIL

If your element can appear more than once, you could also build a list of results:

? (whereis 'c '(a b c d c b a))
((CAR (CDR (CDR '(A B C D C B A)))) (CAR (CDR (CDR (CDR (CDR '(A B C D C B A)))))))

with this code:

(defun whereis (who obj)
  (let ((res nil)) ; the final result
    (labels
        ; sub-function: walks the whole list recursively
        ((sub (obj sexp)
           ; found it - add to result list
           (when (eq obj who) (setf res (cons sexp res)))
           ; try car and cdr
           (when (and obj (listp obj))
             (sub (cdr obj) (list 'cdr sexp))
             (sub (car obj) (list 'car sexp)))))
      ; call sub-function
      (sub obj (list 'quote obj)))
    res))

Answer 2

The main problem with your approach is that if first elements equals waldo, how are you suppose to generate the answer? There may be many possible paths waldo might be in so we need a way to indicate in the iteration what path we are on and we need to backtrack if we are at a dead end.

(defun wheres-waldo (o)
  (labels                                          ; labels is to make local functions 
   ((aux (cur acc)                                 ; define loacl function aux with args cur and acc
      (or                                          ; or stops at the first non NIL value
       (and (eq cur 'waldo) acc)                   ; if (eq cur 'waldo) we return acc 
       (and (consp cur)                            ; (else) if object is a cons 
            (or                                    ; then one of the followin
             (aux (car cur) (list 'first acc))     ; answer might be in the car
             (aux (cdr cur) (list 'rest acc))))))) ; or the cdr of the cons 
    (aux o (list 'quote o))))                      ; call aux with original object and the same object quoted. (list 'quote x) ==> 'x (as data)

As you see, main work is done by aux that has an object and an accumuolator idicating the path and the quotes data. If you find waldo then the result is the accumulator.

If waldo exists in several locations it always do car first so not necessarily the shortest answer but the first it finds.

I use and/or here. These are similar to if except it's the value of the expression that gets returned. Eg (and (eq cur 'waldo) acc) will make sure we return acc if cur is waldo since and evaluates to the last true value. If there is one NIL value it becomes the result of the form. For or it will evaluate to the first true value (everything not NIL) or NIL if all expressions mounts to NIL. In Exercise 2 of your link you were to rewrite a function in a similar way.