# Lesson 9

Write a lisp program solving the search problem beneath using depth first search. (A simplified version of the farmer, goat etc. problem, use "OR", but no need for "SAFE")
```      S ---> A ---> B
|      |
|      |
v      v
C ---> D ---> G

```
Solution:
```      S ---> A ---> B                   >(depth 's nil)
|      |                           1> (DEPTH S NIL)
|      |                             2> (RIGHT S)
v      v                             <2 (RIGHT A)
C ---> D ---> G                      2> (DEPTH A (S))
3> (RIGHT A)
(defun right (state)                         <3 (RIGHT B)
(cond ((equal state 's) 'a)                  3> (DEPTH B (A S))
((equal state 'a) 'b)                    4> (RIGHT B)
((equal state 'c) 'd)                    <4 (RIGHT NIL)
((equal state 'd) 'g)                    4> (DEPTH NIL (B A S))
(t nil)))                                <4 (DEPTH NIL)
4> (DOWN B)
(defun down (state)                            <4 (DOWN NIL)
(cond ((equal state 's) 'c)                    4> (DEPTH NIL (B A S))
((equal state 'a) 'd)                    <4 (DEPTH NIL)
(t nil)))                              <3 (DEPTH NIL)
3> (DOWN A)
(defun depth (s p)                           <3 (DOWN D)
(cond ((null s) nil)                       3> (DEPTH D (A S))
((equal s 'g)
(reverse (cons s p)))               4> (RIGHT D)
((member s p) nil)                     <4 (RIGHT G)
(t (or (depth (right s)
(cons s p))              4> (DEPTH G (D A S))
(depth (down s)
(cons s p))))))          <4 (DEPTH (S A D G))
<3 (DEPTH (S A D G))
<2 (DEPTH (S A D G))
<1 (DEPTH (S A D G))
(S A D G)
```
Search problems from page 9 in the handout, sorry they are in Swedish!