LS-Game

°ú¸ñ: Programming Language
±³¼ö: ÇÑ»ó¿µ
Á¦ÃâÀÏ: 6-Nov-97
Á¦ÃâÀÚ: ±è±â¿ë, 93208-002, Áö¸®Çаú

;
; lsgame.lisp
;
;   Programming Languages Assignment #3
;
;   created by: Kim, Ki-Yong, 93208-002, Dept. of Geography
;  

(defun init ()
  (setf board_size 5)
  (setf n_scramble 50)
  (setf optimizing_method 'opt1_and_opt2))


(defun createLine (size)
  (let ((line nil))
    (dotimes (x size line)
      (setf line (cons 'L line)))))


(defun createBoard (size)
  (let ((matrix ()))
    (dotimes (y size matrix)
      (setf matrix (cons (createLine size) matrix)))))


(defun getXY (board x y)
  (nth x (nth y board)))


(defun reverseXY (board x y)
  (setf (nth x (nth y board))
    (if (eq (getXY board x y) 'L) 'S 'L)))


(defun isOdd (num)
  (let ((flag nil))
    (multiple-value-bind
      (quotient remainder)
      (truncate num 2)
      (setf result (= remainder 1)))))


(defun copyBoard (board)
  (let ((copy (createBoard board_size)))
    (dotimes (y board_size copy)
      (dotimes (x board_size copy)
        (setf (nth x (nth y copy)) (getXY board x y))))))


(defun setEvenXY (board x y)
  (dotimes (i board_size)
    (reverseXY board x i)
    (if (= i x) 'X (reverseXY board i y))))


(defun copyForEven (board)
  (let ((copy (createBoard board_size)))
    (dotimes (y board_size copy)
      (dotimes ( x board_size copy)
        (when (eq (getXY board x y) 'S)
          (setEvenXY copy x y))))))


(defun pressXY (board x y)
  (dotimes (i board_size)
    (reverseXY board x i)
    (if (= x i) 'X (reverseXY board i y))))


(defun getCross (board x y)
  (let ((count 0))
    (dotimes (i board_size count)
     (setf count (if (eq (getXY board x i) 'L) count (+ count 1)))
     (setf count (if (or (= x i)
                         (eq (getXY board i y) 'L)
                     ) count (+ count 1))
      )
    )
  )
)


(defun getParallel (board i1 i2 type)
  (let ((count 0) (x 0) (y 0))
    (dotimes (i board_size count)
      (setf x (if (eq type 'HORZ) i i1))
      (setf y (if (eq type 'HORZ) i1 i))
      (setf count (if (eq (getXY board x y) 'L) count (+ count 1)))
      (setf x (if (eq type 'HORZ) i i2))
      (setf y (if (eq type 'HORZ) i2 i))
      (setf count (if (eq (getXY board x y) 'L) count (+ count 1)))
    )
  )
)


(defun reverseCross (board x y)
  (pressXY board x y)
  (reverseXY board x y))


(defun reverseParallel (board i1 i2 type)
  (let ((x 0) (y 0))
    (dotimes (i board_size)
      (setf x (if (eq type 'HORZ) i i1))
      (setf y (if (eq type 'HORZ) i1 i))
      (reverseXY board x y)
      (setf x (if (eq type 'HORZ) i i2))
      (setf y (if (eq type 'HORZ) i2 i))
      (reverseXY board x y)
    )
  )
)


(defun optimize1 (board)
  (loop
    (let ((nCross 0) (nMaxCross 0) (xMax 0) (yMax 0))
      (dotimes (y board_size)
        (dotimes (x board_size)
          (setf nCross (getCross board x y))
          (when (< nMaxCross nCross)
            (setf nMaxCross nCross)
            (setf xMax x)
            (setf yMax y))))
      (when (<= nMaxCross board_size) (return NIL))
      (reverseCross board xMax yMax))))


(defun optimize2 (board)
  (loop
    (let ((typeMax 'HORZ) (nPara 0) (nMaxPara 0) (i1Max 0) (i2Max 0))
      (dotimes (i1 (- board_size 1))
        (dotimes (i2 board_size)
          (when (< i1 i2)
            (dolist (type (list 'HORZ 'VERT))
              (setf nPara (getParallel board i1 i2 type))
              (when (< nMaxPara nPara)
                (setf nMaxPara nPara)
                (setf i1Max i1)
                (setf i2Max i2)
                (setf typeMax type))))))
      (when (<= nMaxPara board_size) (return NIL))
      (reverseParallel board i1Max i2Max typeMax)
    )
  )
)


(defun scramble (board times randomstate)
  (let ((x 0) (y 0))
    (dotimes (i times board)
      (setf x (random board_size randomstate))
      (setf y (random board_size randomstate))
      (format t "~%Pressing #~a, (~a, ~a)..."
                (+ i 1) x y)
      (pressXY board x y)
      (print_board board))))


(defun print_board (board)
  (dolist (line board)
    (print line))
  (print '------))


(defun solve (board copy)
  (print 'Solving...)
  (let ((nSolve 0))
    (dotimes (y board_size)
      (dotimes (x board_size)
        (when (eq (getXY copy x y) 'S)
              (pressXY board x y)
              (setf nSolve (+ nSolve 1))
              (format t "~%Solving #~a, (~a, ~a)..."
                        nSolve x y)
              (print_board board))
      )
    )
  )
)
         

(defun LSGame ()
  (init)
  (setf rs (make-random-state t))
  (setf board (scramble (createBoard board_size) n_scramble rs))

  (setf copy (if (isOdd board_size)
                 (copyBoard board)
                 (copyForEven board)))
  (print "Before Optimizing")
  (print_board copy)
  (when (isOdd board_size)
    (when (or (eq optimizing_method 'opt1_only)
              (eq optimizing_method 'opt1_and_opt2))
          (optimize1 copy))
    (when (or (eq optimizing_method 'opt2_only)
              (eq optimizing_method 'opt1_and_opt2))
          (optimize2 copy)))

  (print "After Optimizing")
  (print_board copy)
  (solve board copy)
)

(LSGame)

 



#clisp -q < lsgame.lisp

INIT
CREATELINE
CREATEBOARD
GETXY
REVERSEXY
ISODD
COPYBOARD
SETEVENXY
COPYFOREVEN
PRESSXY
GETCROSS
GETPARALLEL
REVERSECROSS
REVERSEPARALLEL
OPTIMIZE1
OPTIMIZE2
SCRAMBLE
PRINT_BOARD
SOLVE
LSGAME
Pressing #1, (2, 3)...
(L L S L L) 
(L L S L L) 
(L L S L L) 
(S S S S S) 
(L L S L L) 
------ 
Pressing #2, (4, 1)...
(L L S L S) 
(S S L S S) 
(L L S L S) 
(S S S S L) 
(L L S L S) 
------ 
Pressing #3, (3, 4)...
(L L S S S) 
(S S L L S) 
(L L S S S) 
(S S S L L) 
(S S L S L) 
------ 
Pressing #4, (4, 1)...
(L L S S L) 
(L L S S L) 
(L L S S L) 
(S S S L S) 
(S S L S S) 
------ 
Pressing #5, (3, 0)...
(S S L L S) 
(L L S L L) 
(L L S L L) 
(S S S S S) 
(S S L L S) 
------ 
Pressing #6, (3, 3)...
(S S L S S) 
(L L S S L) 
(L L S S L) 
(L L L L L) 
(S S L S S) 
------ 
Pressing #7, (2, 1)...
(S S S S S) 
(S S L L S) 
(L L L S L) 
(L L S L L) 
(S S S S S) 
------ 
Pressing #8, (2, 2)...
(S S L S S) 
(S S S L S) 
(S S S L S) 
(L L L L L) 
(S S L S S) 
------ 
Pressing #9, (4, 0)...
(L L S L L) 
(S S S L L) 
(S S S L L) 
(L L L L S) 
(S S L S L) 
------ 
Pressing #10, (2, 2)...
(L L L L L) 
(S S L L L) 
(L L L S S) 
(L L S L S) 
(S S S S L) 
------ 
Pressing #11, (2, 0)...
(S S S S S) 
(S S S L L) 
(L L S S S) 
(L L L L S) 
(S S L S L) 
------ 
Pressing #12, (2, 3)...
(S S L S S) 
(S S L L L) 
(L L L S S) 
(S S S S L) 
(S S S S L) 
------ 
Pressing #13, (4, 1)...
(S S L S L) 
(L L S S S) 
(L L L S L) 
(S S S S S) 
(S S S S S) 
------ 
Pressing #14, (0, 0)...
(L L S L S) 
(S L S S S) 
(S L L S L) 
(L S S S S) 
(L S S S S) 
------ 
Pressing #15, (2, 0)...
(S S L S L) 
(S L L S S) 
(S L S S L) 
(L S L S S) 
(L S L S S) 
------ 
Pressing #16, (2, 0)...
(L L S L S) 
(S L S S S) 
(S L L S L) 
(L S S S S) 
(L S S S S) 
------ 
Pressing #17, (4, 0)...
(S S L S L) 
(S L S S L) 
(S L L S S) 
(L S S S L) 
(L S S S L) 
------ 
Pressing #18, (1, 3)...
(S L L S L) 
(S S S S L) 
(S S L S S) 
(S L L L S) 
(L L S S L) 
------ 
Pressing #19, (0, 2)...
(L L L S L) 
(L S S S L) 
(L L S L L) 
(L L L L S) 
(S L S S L) 
------ 
Pressing #20, (3, 2)...
(L L L L L) 
(L S S L L) 
(S S L S S) 
(L L L S S) 
(S L S L L) 
------ 
Pressing #21, (1, 1)...
(L S L L L) 
(S L L S S) 
(S L L S S) 
(L S L S S) 
(S S S L L) 
------ 
Pressing #22, (3, 0)...
(S L S S S) 
(S L L L S) 
(S L L L S) 
(L S L L S) 
(S S S S L) 
------ 
Pressing #23, (4, 1)...
(S L S S L) 
(L S S S L) 
(S L L L L) 
(L S L L L) 
(S S S S S) 
------ 
Pressing #24, (4, 3)...
(S L S S S) 
(L S S S S) 
(S L L L S) 
(S L S S S) 
(S S S S L) 
------ 
Pressing #25, (2, 3)...
(S L L S S) 
(L S L S S) 
(S L S L S) 
(L S L L L) 
(S S L S L) 
------ 
Pressing #26, (4, 4)...
(S L L S L) 
(L S L S L) 
(S L S L L) 
(L S L L S) 
(L L S L S) 
------ 
Pressing #27, (1, 1)...
(S S L S L) 
(S L S L S) 
(S S S L L) 
(L L L L S) 
(L S S L S) 
------ 
Pressing #28, (3, 0)...
(L L S L S) 
(S L S S S) 
(S S S S L) 
(L L L S S) 
(L S S S S) 
------ 
Pressing #29, (0, 4)...
(S L S L S) 
(L L S S S) 
(L S S S L) 
(S L L S S) 
(S L L L L) 
------ 
Pressing #30, (2, 0)...
(L S L S L) 
(L L L S S) 
(L S L S L) 
(S L S S S) 
(S L S L L) 
------ 
Pressing #31, (4, 3)...
(L S L S S) 
(L L L S L) 
(L S L S S) 
(L S L L L) 
(S L S L S) 
------ 
Pressing #32, (0, 3)...
(S S L S S) 
(S L L S L) 
(S S L S S) 
(S L S S S) 
(L L S L S) 
------ 
Pressing #33, (1, 2)...
(S L L S S) 
(S S L S L) 
(L L S L L) 
(S S S S S) 
(L S S L S) 
------ 
Pressing #34, (4, 2)...
(S L L S L) 
(S S L S S) 
(S S L S S) 
(S S S S L) 
(L S S L L) 
------ 
Pressing #35, (1, 3)...
(S S L S L) 
(S L L S S) 
(S L L S S) 
(L L L L S) 
(L L S L L) 
------ 
Pressing #36, (4, 1)...
(S S L S S) 
(L S S L L) 
(S L L S L) 
(L L L L L) 
(L L S L S) 
------ 
Pressing #37, (1, 2)...
(S L L S S) 
(L L S L L) 
(L S S L S) 
(L S L L L) 
(L S S L S) 
------ 
Pressing #38, (2, 2)...
(S L S S S) 
(L L L L L) 
(S L L S L) 
(L S S L L) 
(L S L L S) 
------ 
Pressing #39, (4, 1)...
(S L S S L) 
(S S S S S) 
(S L L S S) 
(L S S L S) 
(L S L L L) 
------ 
Pressing #40, (3, 2)...
(S L S L L) 
(S S S L S) 
(L S S L L) 
(L S S S S) 
(L S L S L) 
------ 
Pressing #41, (1, 1)...
(S S S L L) 
(L L L S L) 
(L L S L L) 
(L L S S S) 
(L L L S L) 
------ 
Pressing #42, (0, 1)...
(L S S L L) 
(S S S L S) 
(S L S L L) 
(S L S S S) 
(S L L S L) 
------ 
Pressing #43, (4, 2)...
(L S S L S) 
(S S S L L) 
(L S L S S) 
(S L S S L) 
(S L L S S) 
------ 
Pressing #44, (2, 3)...
(L S L L S) 
(S S L L L) 
(L S S S S) 
(L S L L S) 
(S L S S S) 
------ 
Pressing #45, (4, 2)...
(L S L L L) 
(S S L L S) 
(S L L L L) 
(L S L L L) 
(S L S S L) 
------ 
Pressing #46, (2, 0)...
(S L S S S) 
(S S S L S) 
(S L S L L) 
(L S S L L) 
(S L L S L) 
------ 
Pressing #47, (4, 0)...
(L S L L L) 
(S S S L L) 
(S L S L S) 
(L S S L S) 
(S L L S S) 
------ 
Pressing #48, (1, 2)...
(L L L L L) 
(S L S L L) 
(L S L S L) 
(L L S L S) 
(S S L S S) 
------ 
Pressing #49, (1, 2)...
(L S L L L) 
(S S S L L) 
(S L S L S) 
(L S S L S) 
(S L L S S) 
------ 
Pressing #50, (2, 2)...
(L S S L L) 
(S S L L L) 
(L S L S L) 
(L S L L S) 
(S L S S S) 
------ 
"Before Optimizing" 
(L S S L L) 
(S S L L L) 
(L S L S L) 
(L S L L S) 
(S L S S S) 
------ 
"After Optimizing" 
(L L S L L) 
(S L L L L) 
(L L L S L) 
(L L L L S) 
(L L L L L) 
------ 
SOLVING... 
Solving #1, (2, 0)...
(S L L S S) 
(S S S L L) 
(L S S S L) 
(L S S L S) 
(S L L S S) 
------ 
Solving #2, (0, 1)...
(L L L S S) 
(L L L S S) 
(S S S S L) 
(S S S L S) 
(L L L S S) 
------ 
Solving #3, (3, 2)...
(L L L L S) 
(L L L L S) 
(L L L L S) 
(S S S S S) 
(L L L L S) 
------ 
Solving #4, (4, 3)...
(L L L L L) 
(L L L L L) 
(L L L L L) 
(L L L L L) 
(L L L L L) 
------ 
NIL