;;****************************************************************
;; Part 3
;; - modify your search to accept advice on which coin to try first
;; - modify your search to do a feasibility test before proceeding
;; - modify your search to do a direct-solution test 
;; 
;; (reject) is a feasibility test
;; (direct-answer3) is a direct-solution test
;;


(define (search-with-direct num-coins val-coins solution)
  (begin
    (set! guesses (+ guesses 1))
    (if (and (= num-coins 0) (= val-coins 0))
        solution
        (if (not (reject num-coins val-coins))
	    (let ((dir (direct-answer3 num-coins val-coins)))
	      (or
	       (if dir
		   (search-with-direct
		    (- num-coins 1)
		    (- val-coins dir)
		    (cons dir solution))
		   (set! dir -1))
	       (if (not (= dir 25))
		   (search-with-direct
		    (- num-coins 1)
		    (- val-coins 25)
		    (cons 25 solution))
		   #f)
	       (if (not (= dir 10))
		   (search-with-direct
		    (- num-coins 1)
		    (- val-coins 10)
		    (cons 10 solution))
		   #f)
	       (if (not (= dir 5))
		   (search-with-direct
		    (- num-coins 1)
		    (- val-coins 5)
		    (cons 5 solution))
		   #f)
	       (if (not (= dir 1))
		   (search-with-direct
		    (- num-coins 1)
		    (- val-coins 1)
		    (cons 1 solution))
		   #f)
	       #f))
            #f))))




;; Show some problems running with and without your heuristics
;; (define c '((20 308) (19 231) (17 127) (15 143) (20 176) (18 206)
;; (19 163) (10 62) (11 176) (11 75)))
;;
;; I define the test functions below, but they just show how many guesses
;;  each problem takes
;; (guesses-without-direct c)
;; Value 200: (45 1140 8731 44 112 1139 59 34 34 207)
;; (guesses-without-tree c)
;; Value 254: (21 20 4866 16 21 19 20 11 12 12)
;;
;; notice that the latter (with direct) does much better
;;
;;