;; dfs search for a number
;;
;; This procedure makes it easy to generate
;; output...
(define show 
  (lambda x
	(map display x)))


;; successor states of a state numbered x are x-1 and x+1

(define (successor x)
  (list (- x 1) (+ x 1)))

;; depth first seach example. Uses a DFS to search for a number (goal)
;; in search tree rooted at startnum. The successor function is used to
;; generate a list of child states.
;;
;; This procedure generates a trace of what it is doing, and
;; indents each line of output to show the level (in the search tree).
;; Note that if maxdepth is greater than 10 the indentation won't work!
;;
;; dfs calls itself for each state returned by the successor function.
;;  This function uses a named let to recursive over the list of
;;  successor states (could also use a do loop here).

(define (dfs startnum goal maxdepth)
  (cond
   ((equal? goal startnum)
    (begin
      (show "GOAL FOUND: " startnum)
      #t))

   ((= maxdepth 0) #f)

   (else 
    ;; named let. initialize states with list of
    ;; all successor states. We will recurse over this
    ;; list using the named let.
    (let dfs-helper ((states (successor startnum)))
      (if (not (null? states))
	  (begin
	    (genspaces (- 10 maxdepth))
	    (show "state: " (car states) "\n")
	    (if (not (dfs (car states) goal (- maxdepth 1)))
		(dfs-helper (cdr states))
		#t))
	   #f)))))


;; used to generate indentation
(define (genspaces cnt)
  (if (not (= 0 cnt))
      (begin
	(display "   ")
	(genspaces (- cnt 1)))))

;; here is a sample call:
;;   start at 0, find the number 3 and limit depth to 4.
(dfs 0 3 4)