;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Lightz-Out problem
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; The important functions in this implementation are:
;   lightz-h     - The heuristic function
;   lightz-goalp - The goal predicate (all lights off)
;   ligthz-succ  - The successor function
;
; Utility functions:
;   lightz-activate - Activate a given square in the lightz problem.
;   lightz-draw-state - Draw a given state on the screen (for debugging).
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; The size of the problem
(defparameter *lightz-size* 5) 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; INTERNAL FUNCTIONS
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defparameter *lightz-succ-list* nil) 
                             
(defmacro invert (l y x) 
 `(setf ,l (logxor ,l (ash 1 (+ (* *lightz-size* ,y) ,x)))))
 
(dotimes (y *lightz-size*)
 (dotimes (x *lightz-size*)
  (let ((temp-state 0))
   (invert temp-state x y)
   (when (> x 0)                  (invert temp-state (1- x) y))
   (when (< x (1- *lightz-size*)) (invert temp-state (1+ x) y))
   (when (> y 0)                  (invert temp-state x (1- y)))
   (when (< y (1- *lightz-size*)) (invert temp-state x (1+ y)))
   (setf *lightz-succ-list* (cons temp-state *lightz-succ-list*)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; INTERFACE FUNCTIONS
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; This function draws an state as a 2D bit array of lights
(defun lightz-draw-state (state)
 (dotimes (x *lightz-size*)
  (dotimes (y *lightz-size*)
   (princ (mod state 2)) (setf state (ash state -1)))
   (format t "~%")) (format t "~%"))

; The heurisitic function counts the number of lights "on" in a given state
(defun lightz-h (state) (logcount state))

; The goal predicate - checks if all lights are off in a given state
(defun lightz-goalp (state) (zerop state))

; The successors function for the lightz problem.
; Parameter: A state of the lightz problem.
; Returns:   A list of states reachable directly from the given state.
(defun lightz-succ (state)
 (mapcar #'(lambda (s) (logxor s state)) *lightz-succ-list*))

; Utility function to activate the nth location from a given state
; Flips n and surrounding squares.
;
; Parameters:
;  state - Original state to change
;  n     - Square number (from 0 to size^2 - 1) to activate in state.
;
; Returns: state after activation of square n.
(defun lightz-activate (state n)
  (logxor (nth n *lightz-succ-list*) state))