;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; CSCI 4150 Introduction to Artificial Intelligence, Fall 2000
; Assignment 3 testing code
;
; Copyright (c) 2000 Wesley H. Huang.  All rights reserved.
;
; This file contains:
;
; * A few procedures that you can use to make testing your heuristics
;   on the A* algorithm easier
;
; * Information on using the testing procedure
;
; Note that the code for the A* algorithm and the testing procedure is
; contained in the (compiled) scheme file a3code.com.  You can load
; this with the command (load "a3code").  (For version 7.3, you may
; need to specify the ".com".)
;
; Also note that you'll need to write the ep-children function before
; you can start testing your 8 puzzle heuristics using the A*
; procedure.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; A basic procedure that calls the A* algorithm with your ep-children
; and allows you to specify the start, goal, and heuristic
;
(define (run-heuristic start-state goal-state heuristic)
  (display "; ****************************************\n")
  (display "; START STATE: ")
  (display start-state)
  (display "\n; GOAL STATE:  ")
  (display goal-state)
  (display "\n;\n")
  (astar start-state goal-state ep-children heuristic))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; below are a number of specific tests.  You can just give these test
; procedures your heuristic function, and it will run A*
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;
; This is an easy one --- the zero heuristic finds this after evaluating
; 297 states.  The manhattan heuristic only evaluates 16 states!
; 
(define	(test1 heuristic)
  (let ((ss '(space 1 2 3 4 5 6 7 8))      ; start state
	(gs '(space 4 2 1 5 8 3 6 7)))     ; goal state
    (run-heuristic ss gs heuristic)))

;
; Here's another easy one --- the zero heuristic evaluates 5342 states, the
; manhattan heuristic 52 states.
;
(define (test2 heuristic)
  (let ((ss '(8 3 5 2 1 6 4 7 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))

;
; Here's a more difficult one --- manhattan evaluates 396 states, 
; the zero-heuristic evaluates a lot of states...  (i didn't wait!)
;
(define (test3 heuristic)
  (let ((ss  '(8 5 1 7 4 3 2 6 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))

;
; This starts to be moderately difficult --- the manhattan heuristic 
; evaluates almost 2900 nodes
; 
(define (test4 heuristic)
  (let ((ss '(3 2 7 5 4 8 1 6 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))

;
; a tough one!
;
(define (test5 heuristic)
  (let ((ss '(8 7 6 5 4 3 2 1 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))
	
;
; By the way, it's easy to make up these test cases --- just take an
; 8 puzzle, start at the goal configuration, and start moving pieces around.  
; The fewer moves you make, the easier it will be.
;
; You can also generate random states with the MIT Scheme "random" function.
; (And some list manipulation...)  See the MIT Scheme reference manual for
; details on the random function.
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Testing your code
;
; to use the code testing procedure i've included in the a3code.com
; file, do the following:
;
; 1. start a fresh scheme (not the one you've been working in)
; 2. load this file (a3tests.scm)  This loads the variables below
; 3. call the test function and give it the filename of your code:
;
;      (test "mycode.scm")
;
; For some reason, this program is now CRASHING after it finishes
; testing your code.  I don't know why, but it only happens for the
; compiled version of the code I'm giving you.  At least you get to
; test your code!
;
; Remember, that this is not an extensive test of your code!  in
; particular, it does not run the A* algorithm on your heuristic
; (which we will do for the actual grading).  You can make it more
; extensive by creating a real set of test inputs and outputs for the
; variables below.
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Below are variables that you can change to provide a real set of
; test inputs for the test function to give your code.  I've provided
; a few simple test cases below just to get you started.
;
(define ep-children-inputs
  '((;first input
     (1 2 3 4 5 6 7 8 space))
    (;second input
     (1 3 2 4 5 6 7 8 space))))
(define ep-children-outputs
  '(;first output (order of children does not matter)
    ((1 2 3 4 5 space 7 8 6) (1 2 3 4 5 6 7 space 8))
    ;second output
    ((1 3 2 4 5 space 7 8 6) (1 3 2 4 5 6 7 space 8))))


(define ep-manhattan-inputs
  '((;first input
     (1 2 3 4 5 6 7 8 space) (1 2 3 4 5 space 7 8 6))
    (;second input
     (1 3 2 4 5 6 7 8 space) (1 3 2 4 5 space 7 8 6))))
(define ep-manhattan-outputs
  '(;first output
    1
    ;second output
    1))

(define ep-heuristic-inputs
  '((;first input
     (1 2 3 4 5 6 7 8 space) (1 2 3 4 5 space 7 8 6))
    (;second input
     (1 3 2 4 5 6 7 8 space) (1 3 2 4 5 space 7 8 6))))
;
; There is no ep-heuristic-outputs because the test function only
; checks to see that your function returns a nonnegative real number.
; For the real testing, we'll actually run your ep-heuristic with the
; A* algorithm, so be sure to try it out!
;