;Shayna Rubin
;8'S PUZZLE

;;;The following puzzle configurations were used:
;;;(search a*-merge puzzle-a 8-extend 8-goal? 8-estimate 8-print)
;;;(search a*-merge puzzle-b 8-extend 8-goal? 8-estimate 8-print)
;;;(search a*-merge puzzle-c 8-extend 8-goal? 8-estimate 8-print)
;;;where-->
;;;puzzle-a is represented as '(1 0 3 4 2 5 6 7 8) [[one move]]
;;;puzzle-b is represented as '(0 2 3 1 7 5 4 6 8) [[four moves]]
;;;puzzle-c is represented as '(2 3 5 1 7 8 4 6 0) [[eight moves]]
;;;
;;;Acknowledgements:
;;;I talked to Troy Tricker about the four move procedures.


;;IS THE CURRENT STATE A GOAL STATE?
;;
;;This procedure takes a state which contains a current configuration of
;;the puzzle and returns a boolean if the current state is a goal state.
;;
;;Description:
;;Since the 8s puzzle has pieces numbered 1-8, this program uses an
;;accumulator (starting at 1) to check that the pieces are in their
;;correct location. Once a piece passes the test, the accumulator is
;;then increased by 1 in order to represent the next puzzle piece.

(define 8-goal?
  (lambda (state)
    (letrec ([helper
	      (lambda (ls acc)
		(cond
		 [(null? ls) #t]
		 [(zero? (car ls)) (helper (cdr ls) acc)]
		 [(equal? (car ls) acc) (helper (cdr ls) (add1 acc))]
		 [else #f]))])
      (helper (state-config state) 1))))


;;EXTEND
;;
;;This procedure takes a state as its argument, makes a list of all
;;possible moves in any direction, then filters out the bad moves.

(define 8-extend
  (lambda (state)
    (filter
     (list
      (move-up state)
      (move-down state)
      (move-left state)
      (move-right state)))))

;;FILTER
;;
;;This procedure takes a list of all states and removes all illegal states
;;from a list of all possible states.

(define filter
  (lambda (statels)
    (cond
     [(null? statels) '()]
     [(equal? #f (car statels)) (filter (cdr statels))]
     [else (cons (car statels) (filter (cdr statels)))])))

;;MOVE-UP
;;
;;This procedure takes a state as its argument and returns an updated
;;configuration when the blank space in the puzzle is moved up one place.
;;The procedure returns false if the move is impossible.  That is, if
;;the blank is at the top of the puzzle, it can not move up.  Indeces
;;are used to represent the placement of the pieces in the puzzle starting
;;with index 0.

(define move-up
  (lambda (state)
    (let ([blank (blank-loc (state-config state))])
      (cond
       ;;Test for illegal moves.
       [(<=? blank 2) #f]
       ;;Move is legal -- go on to rest of problem.
       [else (list
	      (add1 (state-distance state))
	      0
	      ;;When the blank is moved up, the new index will be 3
	      ;;less than the original index. (It moves 3 places back)
	      (swap blank (- blank 3) (state-config state)))]))))

;;MOVE-DOWN
;;
;;This procedure takes a state as its argument and returns an updated
;;configuration when the blank space in the puzzle is moved down one place.
;;It is similiar to the prior procedure in that impossible states return
;;false. (When the blank is on the bottom row)

(define move-down
  (lambda (state)
    (let ([blank (blank-loc (state-config state))])
      (cond
       ;;Test for illegal moves.
       [(>=? blank 6) #f]
       ;;Move is legal -- go on to rest of problem.
       [else (list (add1 (state-distance state))
		   0
		   ;;When the blank is moved down, the new index will be
		   ;;3 greater than the original index.
		   (swap blank (+ blank 3) (state-config state)))]))))

;;MOVE-LEFT
;;
;;This procedure takes a state as its argument and returns an updated
;;configuration when the blank space in the puzzle is moved left one
;;place.  Again, impossible states (those where the blank is on the
;;left side of the puzzle) return a false value.

(define move-left
  (lambda (state)
    (let ([blank (blank-loc (state-config state))])
      (cond
       ;;Test for illegal moves.
       [(zero? (mod blank 3)) #f]
       ;;Move is legal -- go on to rest of problem.
       [else (list (add1 (state-distance state))
		   0
		   ;;When the blank is moved left, the new index will be
		   ;;1 less than the original index.
		   (swap blank (- blank 1) (state-config state)))]))))

;;MOVE-RIGHT
;;
;;This procedure takes a state as its argument and returns an updated
;;configuration when the blank space in the puzzle is moved left one
;;place.  Again, impossible states (those where the blank is on the
;;right side of the puzzle) return a false value.

(define move-right
  (lambda (state)
    (let ([blank (blank-loc (state-config state))])
      (cond
       ;;Test for illegal moves.
       [(zero? (mod (add1 blank) 3)) #f]
       ;;Move is legal -- go on to rest of problem.
       [else (list (add1 (state-distance state))
		   0
		   ;;When the blank is moved right, the new index will be
		   ;;1 more than the original index.
		   (swap blank (add1 blank) (state-config state)))]))))

;;BLANK-LOC
;;
;;The location of the blank is represented as an index in the list starting
;;at index 0.

(define blank-loc
  (lambda (config)
    (letrec ([helper
	      (lambda (ls index)
		(cond
		 [(zero? (car ls)) index]
		 [else (helper (cdr ls) (add1 index))]))])
      (helper config 0))))


;;LIST-REF
;;
;;This procedure takes an index and a list as arguments and indicates
;;which puzzle piece is at a specified index.

(define list-ref
  (lambda (n ls)
    (if (zero? n)
	(car ls)
	(list-ref (sub1 n) (cdr ls)))))
	
;;SWAP
;;
;;This procedure takes 2 indeces and a list as arguments.  One of the 
;;indeces represents the blank.  The procedure then switches the blank 
;;with a specified puzzle piece.  This alters the state configuration.

(define swap
  (lambda (a b ls)
    (let ([piece-a (list-ref a ls)]
	  [piece-b (list-ref b ls)])
      (letrec ([helper
		(lambda (ls)
		  (cond
		   [(null? ls) '()]
                   [(equal? (car ls) piece-a)
	            (cons piece-b (helper (cdr ls)))]
                   [(equal? (car ls) piece-b)
	            (cons piece-a (helper (cdr ls)))]
		   [else (cons (car ls) (helper (cdr ls)))]))])
	(helper ls)))))


;;ESTIMATE
;;
;;This procedure takes a state as its argument and estimates the number
;;of moves remaining until the goal is reached.
;;This procedure takes the number of pieces that are in their correct
;;location and returns a number which indicates how many pieces are
;;NOT in their correct location--thus indicating how much further the
;;search must procede until the goal is reached.

(define 8-estimate
  (lambda (state)
    (letrec ([helper
	      (lambda (ls piece acc)
		(cond
		 ;;At the end of the list, how many pieces are left
		 ;;misplaced?
		 [(null? ls) (- 8 acc)]
		 ;;This disregards the blank as it would be anywhere.
		 [(zero? (car ls)) (helper (cdr ls) piece acc)]
		 ;;Checking for correct placement
		 [(equal? (car ls) piece)
		  (helper (cdr ls) (add1 piece) (add1 acc))]
		 ;;If misplaced piece...move on.
		 [else (helper (cdr ls) (add1 piece) acc)]))])
      (helper (state-config state) 1 0))))


;;PRINT
;;
;;This procedure takes an initial state as its argument and displays the
;;current state of the puzzle.

(define 8-print
  (lambda (state)
    (let ([blank (blank-loc (state-config state))])
      (letrec ([helper
	        (lambda (config index)
		  (cond
		   [(null? config) (printf "~n")]
		   [(zero? (mod (add1 index) 3))
		    (begin
		    (printf "~s ~n"
			    (car config))
		     (helper (cdr config) (add1 index)))]
		   [else
		    (begin
		    (printf "~s  "
			    (car config))
		    (helper (cdr config) (add1 index)))]))])
        (helper (state-config state) 0)))))