hw2-cmpsc441-1

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   JACOB GALLUCCI                                                        ;;
;;   [email protected]                                                       ;;
;;   CMPSC441 - Assignment 2                                               ;;
;;   farmers.ss                                                            ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; CMPSC441               Artificial Intelligence              Fall 2018 ;;;
;;;                                                                       ;;;
;;;                                                                       ;;;
;;; PROBLEM-SPECIFIC CODE FOR FARMER'S PROBLEM                            ;;;
;;;                                                                       ;;;
;;;   - Write your code for farmer's problem here                         ;;;
;;;                                                                       ;;;
;;; Report bugs to [email protected]                                        ;;;
;;;                                                                       ;;;
;;; THANK YOU!                                                            ;;;
;;;                                                                       ;;;
;;;                                                                       ;;;
;;; Sukmoon Chang                                      September 25, 2018 ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;; DO NOT MODIFY NEXT 2 LINES
#lang mzscheme
(require "search.ss")


;;; Problem specific code for solving the farmer's problem
;;; using the curried version of the simple search procedure.
;;; The farmer's problem was discussed in the lecture.
;;;
;;; To solve the problem, load this file and run
;;;    (farmer-depth-first)
;;; or
;;;    (farmer-breadth-first)
;;;
;;; Here, a state is represented as follows:
;;;       (farmer (grain chicken fox))
;;; where #t represents the left bay
;;;       #f represents the right bay
;;; For example
;;;         (#f (#t #f #t))
;;; says
;;;         grain and fox are on the left bay
;;;         farmer and chicken are on the right bay
;;;
;;; So, the initial state is
;;;         (#t (#t #t #t))
;;; and the final state is
;;;         (#f (#f #f #f))



;;; For consistency, 2 procedures for outputting
;;; the current path are provided below


;; pretty-print a path
(define pretty-print-path
  (lambda (path)
    (letrec
        ((helper
           (lambda (path)
             (cond
               ((null? path) (printf "~%"))
               (else
                 (begin
                   (pretty-print-state (car path))
                   (printf "~%")
                   (helper (cdr path))))))))
      (helper (reverse path)))))


(define pretty-print-state
  (lambda (state)
    (let ((farmer (car state))
          (grain   (car (cadr state)))
          (chicken (cadr (cadr state)))
          (fox     (caddr (cadr state))))
      (if farmer
          (printf " Farmer |=>    |~%")
          (printf "        |    <=| Farmer~%"))
      (if grain
          (printf " Grain  |      |~%")
          (printf "        |      | Grain~%"))
      (if chicken
          (printf "Chicken |      |~%")
          (printf "        |      | Chicken~%"))
      (if fox
          (printf "    Fox |      |~%")
          (printf "        |      | Fox~%")))))


;;; Rest of your code goes here

;; initial state
(define init-state '(#t (#t #t #t)))

;; determine if a state is invalid
; returns #f if an element is on the same side as another element that will eat it w/o farmer
;            or if the state has already been visited, Otherwise returns #t
(define good-config?
  (lambda (config visited)
    (cond
      ((visited? visited config) #f)
      ((and (eq? (car (cadr config)) (cadr (cadr config)))
            (not (eq? (car (cadr config)) (car config)))) #f)
      ((and (eq? (cadr (cadr config)) (caddr (cadr config)))
            (not (eq? (cadr (cadr config)) (car config)))) #f)
      (else #t))))

;; Flip functions [used in cross functs] - used to easily flip the value for extend
; changes value of G, C or F to #t -> #f or visa versa
(define flip-grain
  (lambda (grain-chicken-fox)
    (cons (not (car grain-chicken-fox)) (cdr grain-chicken-fox))))
(define flip-chicken
  (lambda (grain-chicken-fox)
    (cons (car grain-chicken-fox)
          (cons (not (cadr grain-chicken-fox))
                (cddr grain-chicken-fox)))))
(define flip-fox
  (lambda (grain-chicken-fox)
    (reverse (flip-grain (reverse grain-chicken-fox)))))

;; Same Side [used in cross functs] - Checks if the farmer is on the same side of river as G,C or F
; returns #t or #f depending on if the farmer is on the correct side
(define same-side-grain?
  (lambda (state)
    (cond
      ((eq? (car (cadr state)) (car state)) #t)
      (else #f))))
(define same-side-chicken?
  (lambda (state)
    (cond
      ((eq? (cadr (cadr state)) (car state)) #t)
      (else #f))))
(define same-side-fox?
  (lambda (state)
    (cond
      ((eq? (caddr (cadr state )) (car state)) #t)
      (else #f))))

;; Cross [used in extend] - Makes state of farmer moving across river (with or without element)
; Crosses the farmer and the related element (switches #t -> #f or visa versa) and returns state
; If the farmer is not on the same side as the related element, returns empty list as state
(define cross-grain
  (lambda (state)
    (cond
      ((same-side-grain? state)
       (cons (not (car state)) (list (flip-grain (cadr state)))))
      (else '()))))
(define cross-chicken
  (lambda (state)
    (cond
      ((same-side-chicken? state)
       (cons (not (car state)) (list (flip-chicken (cadr state)))))
      (else '()))))
(define cross-fox
  (lambda (state)
    (cond
      ((same-side-fox? state)
       (cons (not (car state)) (list (flip-fox (cadr state)))))
      (else '()))))
(define cross-farmer
  (lambda (state)
    (cons (not (car state)) (cdr state))))

;; Extend - gets children of a state
; Makes a list of all possible movements then filters out Invalid movements
; (Empty lists made by cross functs OR movements where something gets eaten)
; Then it returns the filtered list (valid children of the current state)
(define extend
  (lambda (state visited)
    (letrec ([filter-pre
             (lambda (pre-extend visited)
               (cond
                 ((null? pre-extend) '())
                 ((null? (car pre-extend)) (filter-pre (cdr pre-extend) visited))
                 ((good-config? (car pre-extend) visited)
                  (cons (car pre-extend) (filter-pre (cdr pre-extend) visited)))
                 (else (filter-pre (cdr pre-extend) visited))))])
      (define pre-extend
        (cons (cross-grain state)
              (cons (cross-chicken state)
                    (cons (cross-fox state)
                          (list (cross-farmer state))))))
      (filter-pre pre-extend visited))))

;; Goal - Checks if the current state is a goal, returns #t if goal
(define goal?
  (lambda (state)
    (cond
      ((null? state) #t)
      ((list? (car state)) (goal? (car state)))
      ((not (car state)) (goal? (cdr state)))
      (else #f))))

;; Visited [used in good-config]- determine if a state is visited
(define visited?
  (lambda (visited current-move)
    (cond
      ((null? visited) #f)
      ((equal? (car visited) current-move) #t)
      (else (visited? (cdr visited) current-move)))))

;; Searches - Depth first and Breadth first - run searches using these
(define farmer-depth-first
  (lambda ()
    ((depth-first-search extend goal? pretty-print-path) init-state)))
(define farmer-breadth-first
  (lambda ()
    ((breadth-first-search extend goal? pretty-print-path) init-state)))