Флип

; read input
(defun read-input(p)
(cond
    ((null p) nil)
    (T (cons p (read-input (read nil nil))))
)
)

(defun readinput(i)
    (cdr (read-input 1))
)

(defun run-breadth (start goal moves)
  (declare (special *open*))
  (declare (special *closed*))
  (declare (special *goal*))
  (setq *open* (list (build-record start nil)))
  (setq *closed* nil)
  (setq *goal* goal)
  (breadth-first moves))

;;; These functions handle the creation and access of (state parent)
;;; pairs.

(defun build-record (state parent) (list state parent))

(defun get-state (state-tuple) (nth 0 state-tuple))

(defun get-parent (state-tuple) (nth 1 state-tuple))

(defun retrieve-by-state (state list)
  (cond ((null list) nil)
        ((equal state (get-state (car list))) (car list))
        (t (retrieve-by-state state (cdr list)))))



(defun breadth-first (moves)
  (declare (special *open*))
  (declare (special *closed*))
  (declare (special *goal*))
  (cond ((null *open*) nil)
        (t (let ((state (car *open*)))
             (setq *closed* (cons state *closed*))

             (cond
    ;;; found solution: print path to it
        ((equal (get-state state) *goal*) (reverse (build-solution *goal*)))

            ;;; try next child state
                (t (setq *open*
                            (append (cdr *open*)
                                    (generate-descendants (get-state state)
                                                          moves)))
                      (breadth-first moves)))))))

(defun generate-descendants (state moves)
  (declare (special *open*))
  (declare (special *closed*))
  (cond ((null moves) nil)
        (t (let ((child (funcall (car moves) state))
                 (rest (generate-descendants state (cdr moves))))
             (cond ((null child) rest)
                   ((retrieve-by-state child rest) rest)
                   ((retrieve-by-state child *open*) rest)
                   ((retrieve-by-state child *closed*) rest)
                   (t (cons (build-record child state) rest)))))))


(defun build-solution (state)
  (declare (special *closed*))
  (cond ((null state) nil)
        (t (cons state (build-solution
                        (get-parent
                         (retrieve-by-state state *closed*)))))))


(defvar *initial* (car (readinput nil)))
;--don't change above this line


; write your function(s) here
(defun make-state (a b c d e f g h i)
(list a b c d e f g h i)
)


(defun safeState (state)
(cond
((null state) t)
((or (< (nth 0 (car state)) 0)(> (nth 0 (car state)) 2)(> (nth 1 (car state)) 2)(< (nth 1 (car state)) 0)) nil)
(t (safeState (cdr state)))

)
)

(defun safe (state)
(cond
((safeState state) state)
(t nil)
)
)


(defun promeni (pole)
(cond
((eq (nth 2 pole) 0)(list (nth 0 pole)(nth 1 pole) 1))
((eq (nth 2 pole) 1)(list (nth 0 pole)(nth 1 pole) 0))
)
)

(defun goreLevo (state)
(safe (make-state (promeni (nth 0 state))(promeni (nth 1 state))(nth 2 state)(promeni (nth 3 state))(nth 4 state)(nth 5 state)(nth 6 state)(nth 7 state)(nth 8 state))
))
(defun goreGore (state)
(safe (make-state (promeni (nth 0 state))(promeni (nth 1 state))(promeni (nth 2 state))(nth 3 state)(promeni(nth 4 state))(nth 5 state)(nth 6 state)(nth 7 state)(nth 8 state))
))
(defun goreDesno (state)
(safe (make-state (nth 0 state) (promeni (nth 1 state)) (promeni (nth 2 state)) (nth 3 state) (nth 4 state) (promeni (nth 5 state)) (nth 6 state) (nth 7 state) (nth 8 state))))

(defun sredinaLevo (state)
(safe (make-state (promeni (nth 0 state)) (nth 1 state) (nth 2 state) (promeni (nth 3 state)) (promeni (nth 4 state)) (nth 5 state) (promeni (nth 6 state)) (nth 7 state) (nth 8 state)))
)

(defun sredinaSredina (state)
(safe (make-state (nth 0 state) (promeni (nth 1 state)) (nth 2 state) (promeni (nth 3 state)) (promeni (nth 4 state)) (promeni (nth 5 state)) (nth 6 state) (promeni (nth 7 state)) (nth 8 state)))
)

(defun sredinaDesno (state)
(safe (make-state (nth 0 state) (nth 1 state) (promeni (nth 2 state)) (nth 3 state) (promeni (nth 4 state)) (promeni (nth 5 state)) (nth 6 state) (nth 7 state) (promeni (nth 8 state))))
)

(defun doluLevo (state)
(safe (make-state (nth 0 state) (nth 1 state) (nth 2 state) (promeni (nth 3 state)) (nth 4 state) (nth 5 state) (promeni (nth 6 state)) (promeni (nth 7 state)) (nth 8 state)))
)

(defun doluDolu (state)
(safe (make-state (nth 0 state) (nth 1 state) (nth 2 state) (nth 3 state) (promeni (nth 4 state)) (nth 5 state) (promeni (nth 6 state)) (promeni (nth 7 state)) (promeni (nth 8 state))))
)

(defun doluDesno (state)
(safe (make-state (nth 0 state) (nth 1 state) (nth 2 state) (nth 3 state) (nth 4 state) (promeni (nth 5 state)) (nth 6 state) (promeni (nth 7 state)) (promeni (nth 8 state))))
)

(print (run-breadth *initial* '((0 0 1) (0 1 1) (0 2 1) (1 0 1) (1 1 1) (1 2 1) (2 0 1) (2 1 1) (2 2 1)) '(goreLevo goreGore goreDesno sredinaLevo sredinaSredina sredinaDesno doluLevo doluDolu doluDesno)))