cmpsc441-hw2-2

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                         JACOB GALLUCCI                ;;;
;;;                         jag6248@psu.edu                               ;;;
;;;                         Dr. Chang                     ;;;
;;;                         CMPSC441 - Assignment 2 - search.ss           ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; CMPSC441               Artificial Intelligence              Fall 2018 ;;;
;;;                                                                       ;;;
;;;                                                                       ;;;
;;; SIMPLE SEARCH PROCEDURE                                               ;;;
;;;                                                                       ;;;
;;;   - Startup Code for homework 2                                       ;;;
;;;                                                                       ;;;
;;;   - Note that you don't have use this code                            ;;;
;;;     if you really want to dig in and write your own.                  ;;;
;;;                                                                       ;;;
;;;                                                                       ;;;
;;; Report bugs to sukmoon@psu.edu                                        ;;;
;;;                                                                       ;;;
;;; THANK YOU!                                                            ;;;
;;;                                                                       ;;;
;;;                                                                       ;;;
;;; Sukmoon Chang                                      September 25, 2018 ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;
;;; SEARCH:
;;;   -- Non-curried version of generic search algorithm
;;;   -- Can be customized for depth-first and breadth-first search
;;;   -- You must convert it to a curried version so that
;;;      - the function accepts 1 algorithm specific parameter and returns a function
;;;      - that accepts 3 problem-specific parameters and returns a function
;;;      - that accepths 1 instance specific parameter and performs the search
;;;   -- The 5 parameters are described below
;;;
;;; Input:
;;;   merge-queue
;;;     -- algorithm specific
;;;     -- procedure that takes a list of new paths and a queue
;;;        and returns a new queue
;;;   extend
;;;     -- problem-specific
;;;     -- procedure that takes a state and a list of visited states,
;;;        and returns a list of states that are reachable in one move
;;;        from the given state
;;;   goal?
;;;     -- problem-specific
;;;     -- predicate that takes a state and returns true if the
;;;        state is a goal state, false otherwise
;;;   print-path
;;;     -- problem-specific
;;;     -- procedure that takes a state and prints out a state nicely
;;;   init-state
;;;     -- problem instance-specific
;;;     -- an initial state to start the search from
;;;
;;; OUTPUT:
;;;   -- When succeeded, a path from the initial state to a goal state
;;;   -- When failed, #f
;;;


(module hw2 racket

  ;; only the following 2 procedures will be provided
  (provide depth-first-search breadth-first-search)

  ;; generic search algorithm


  (define search
    (lambda (merge-queue)
      (lambda (extend goal? print-path)
        (lambda (init-state)
        (letrec
            ((search-helper
              (lambda (queue visited)
                (cond
                  ((null? queue) #f)
                  ((goal? (caar queue))
                   (begin
                     (print-path (car queue))
                     (car queue)))
                  (else
                   (let ((successors (extend (caar queue) visited)))
                     (cond
                       ((null? successors)
                        (search-helper (cdr queue) visited))
                       (else
                        (let ((new-paths (extend-path successors (car queue))))
                          (search-helper
                           (merge-queue queue new-paths)
                           (append successors visited)))))))))))
          (search-helper
           (list (list init-state))   ; initial queue
           (list init-state)))))))      ; initial visited


  (define extend-path
    (lambda (successors path)
      (if (null? successors)
          '()
          (cons (cons (car successors) path)
            (extend-path (cdr successors) path)))))



  ;; merge new extended paths to queue for depth first search
  ;; - uncomment and define your merge for depth first search

  (define depth-first-merge
    (lambda (queue new-paths)
      (cond
        ((null? new-paths) (append '() queue))
        (else (append new-paths queue)))))



  ;; merge new extended paths to queue for breadth first search
  ;; - uncomment and define your merge for breadth first search

  (define breadth-first-merge
    (lambda (queue new-paths)
      (cond
        ((null? new-paths) (append queue '()))
        (else (append queue new-paths)))))

  ;; customize the generic search for depth first search
  ;; - uncomment and define your depth-first-search in terms of your
  ;;   curried version of search and depth-first-merge

  (define depth-first-search
    (lambda (extend goal? print-path)
      (lambda (init-state)
        (((search depth-first-merge) extend goal? print-path) init-state))))

  ;; customize the generic search for breadth first search
  ;; - uncomment and define your breadth-first-search in terms of your
  ;;   curried version of search and breadth-first-merge

  (define breadth-first-search
    (lambda (extend goal? print-path)
      (lambda (init-state)
        (((search breadth-first-merge) extend goal? print-path) init-state))))


  ;;;; DO NOT REMOVE THE FOLLOWING LINE
  )