;; dfs search for a number
;;
;; 
;; This code is similar to dfs.scm, the difference is that
;;  this version keeps track of the path from the start state to
;;  the goal


;; 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)
      (list goal)))

   ((= 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
			;; display where we are (the state about to be explored)
			(genspaces (- 10 maxdepth))
			(show "state: " (car states) "\n")
			;; run dfs on the subtree rooted at the first state
			;; in the (remaining) list of successors
			(let ((result (dfs (car states) goal (- maxdepth 1))))
			  (if (not result)
				  ;; if we did not find the goal, search the rest of
				  ;; the list of successors
				  (dfs-helper (cdr states))

				  ;; we found the goal state. result is a list of the
				  ;; states visited to reach the goal. Put this state
				  ;; at the beginning of this list and return the result
				  (cons startnum result))))
		  ;; all successors have been checked, report failure
		  #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)
(dfs 0 -3 5)