The purpose of Lisp Quiz is similar to Ruby Quiz--it's all for your own enjoyment and to help you learn to program in Lisp. There are no winners and no losers, only learners. You compete only against yourself and your own abilities. In trying to solve the problems yourself and in reviewing the answers submitted by your peers, you're sure to learn something that you didn't know before.
I'd like to follow a similar format for completing each of the quizzes as was used with Ruby Quiz. Each quiz will be announced periodically, as I get time. Immediately following the posting, please don't post any substantial discussion or solutions about the quiz before the 48-hour No-Spoiler Period has elapsed. This should give people some time to consider their own solutions to the stated problem before everybody jumps in with their own answers. After the No-Spoiler Period, please feel free to discuss solutions, post your own solutions as replies to the original quiz thread on LispForum.com (this thread right here). During the No-Spoiler Period, please feel free to post clarifying questions or (gak!) corrections to the original problem statement. The intent isn't to silence all questions or comments, but rather to keep from influencing others who are trying to solve things their own way.
I'll try to come up with interesting challenges that will lead you into interestings parts of the Common Lisp spec without being so large as to consume months of your time coming up with individual solutions. That's difficult, however, and I'm fairly busy with a job and family. Thus, the schedule for new quizzes will be somewhat sporadic, particular if I have to do some programming to set things up.
To help out, you can suggest your own challenges. If you have an idea for an interesting Lisp Quiz challenge, send me an email via LispForum (findinglisp) and we can figure out how to best get it out for people to work on.
Lisp Quiz #1: Minesweeper
When I bought my first PC in 1992, I found that Windows 3.1 had a couple of games that came with it. Minesweeper was simple but tremendously addicting. I always wondered what it would take to build a simple algorithm that could solve Minesweeper. In particular, I wondered what would be the best way to navigate through those sticky situations where you can't quite reason out which of the neighboring board positions has the mine and you have to guess.
Your challenge is to write a program that can play Minesweeper. Rather than write the whole game, I have supplied a simple Minesweeper engine. It resides in the MINESWEEPER package. You can have your program play the game by creating an instance of the GAME class. The :WIDTH and :HEIGHT parameters control the size of the game board. The :MINE-COUNT parameter sets the number of mines in the board.
Each time you select a position on the board, call the REVEAL method with the (X, Y) position of the position. REVEAL returns either :BOOM-GAME-OVER if you select a position with a mine, the number of mines in surrounding locations (0 to 8), or :YOU-WIN when you select the last position without a mine.
Here's a REPL transcript so you can see this in action:
Code: Select all
CL-USER> (defvar *game* (make-instance 'minesweeper:game :width 10 :height 10 :mine-count 20))
*GAME*
CL-USER> (minesweeper:reveal *game* 0 0)
0
CL-USER> (minesweeper:reveal *game* 0 1)
1
CL-USER> (minesweeper:reveal *game* 1 0)
0
CL-USER> (minesweeper:reveal *game* 1 1)
1
CL-USER> (minesweeper:reveal *game* 2 0)
0
CL-USER> (minesweeper:reveal *game* 2 1)
1
CL-USER> (minesweeper:reveal *game* 2 2)
1
CL-USER> (minesweeper:reveal *game* 2 3)
3
CL-USER> (minesweeper:reveal *game* 2 4)
3
CL-USER> (minesweeper:reveal *game* 2 5)
4
CL-USER> (minesweeper:reveal *game* 2 6)
3
CL-USER> (minesweeper:reveal *game* 2 7)
:BOOM-GAME-OVER
CL-USER>
Your task is to use a superior algorithm to consistently win the game. Note that you cannot generate a perfect algorithm that wins all the time because at least the initial selection must be done at random, with no knowledge of where the mines might be; sometimes you will select a space with a mine on your first guess.
The game engine doesn't keep track of anything it doesn't have to for its own use. In particular, it has no user interface of any sort. Using the publicly exported methods of the MINESWEEPER package, you can only create instances of the GAME class and ask it to REVEAL a location on the board. If you need more than that (and you will), you'll have to keep track of everything else yourself.
There are other methods in the MINESWEEPER package that are not exported. You might find some of them useful to help you debug your own code. For instance, see PRINT-BOARD and PRINT-REVEALED.
Here's the MINESWEEPER package:
Code: Select all
(defpackage #:minesweeper
(:use #:cl)
(:export #:game
#:reveal))
(in-package #:minesweeper)
(defclass game ()
((board :accessor board-of :initarg :board)
(revealed :accessor revealed-of :initarg :revealed)
(mine-count :accessor mine-count-of :initarg :mine-count :initform 20)
(width :accessor width-of :initarg :width :initform 10)
(height :accessor height-of :initarg :height :initform 10)
(game-over :accessor game-over-of :initarg :game-over :initform nil)))
(defun print-matrix (array width printer
&optional (stream *standard-output*))
"Print an ARRAY as a matrix with the specified WIDTH. Use the
specified PRINTER to output each array object to the STREAM."
(loop
for index from 0 below (length array)
for value = (aref array index)
do (funcall printer value stream)
when (= 0 (mod (1+ index) width))
do (terpri stream)))
(defgeneric print-revealed (game &optional stream)
(:documentation "Print out the matrix of revealed locations to the
specified STREAM."))
(defmethod print-revealed ((game game) &optional (stream *standard-output*))
(with-slots (revealed width)
game
(print-matrix revealed width
#'(lambda (value stream)
(princ (if value 1 0) stream))
stream)))
(defgeneric print-board (game &optional stream)
(:documentation "Print out the game board on the specified STREAM."))
(defmethod print-board ((game game) &optional (stream *standard-output*))
(with-slots (board width)
game
(print-matrix board width
#'(lambda (value stream)
(if (eql value :mine)
(princ #\M stream)
(princ value stream)))
stream)))
(defgeneric linear-to-xy (game index)
(:documentation "Converts a linear index of board position into
an (X,Y) coordinate, returned as multiple values."))
(defmethod linear-to-xy ((game game) index)
(with-slots (width)
game
(let ((y (truncate (/ index width)))
(x (mod index width)))
(values x y))))
(defgeneric xy-to-linear (game x y)
(:documentation "Convert an (X,Y) coordinate to a linear position in
the board array. Returns the zero-based linear index or NIL if
the (X,Y) position is out of bounds."))
(defmethod xy-to-linear ((game game) x y)
(with-slots (height width)
game
(if (or (< x 0) ; check if out of bounds
(>= x width)
(< y 0)
(>= y height))
NIL
(+ (* y (width-of game)) x))))
(defgeneric count-a-mine (game x y)
(:documentation "Return 1 if the specified location, (X,Y), contains
a mine, or 0 otherwise. If X or Y is out of range of the board,
return 0."))
(defmethod count-a-mine ((game game) x y)
(with-slots (board)
game
(let ((index (xy-to-linear game x y)))
(if index
(if (eql (aref board index) :mine)
1
0)
0)))) ; out of bounds, so return 0
(defgeneric count-surrounding-mines (game index)
(:documentation "Return a count of the mines surrounding a given
position, INDEX, on the board."))
(defmethod count-surrounding-mines ((game game) index)
(with-slots (height width)
game
;; Convert the linear index to (X,Y) so that we can more easily
;; deal with the edges of the board and COUNT-A-MINE can detect
;; out-of-bounds values.
(multiple-value-bind (x y)
(linear-to-xy game index)
(+ (count-a-mine game (1- x) (1- y))
(count-a-mine game x (1- y))
(count-a-mine game (1+ x) (1- y))
(count-a-mine game (1- x) y)
(count-a-mine game (1+ x) y)
(count-a-mine game (1- x) (1+ y))
(count-a-mine game x (1+ y))
(count-a-mine game (1+ x) (1+ y))))))
(defmethod initialize-instance :after ((game game) &key)
(with-slots (board revealed mine-count width height game-over)
game
(let ((board-length (* width height)))
(setf board (make-array board-length ))
(setf revealed (make-array board-length :initial-element nil))
(let* ((clearspots (make-array board-length))
(clear-length board-length))
(dotimes (i board-length)
(setf (aref clearspots i) i))
(dotimes (i mine-count)
(let* ((choice-index (random clear-length))
(choice (aref clearspots choice-index)))
(setf (aref board choice) :mine)
(setf (aref revealed choice) t) ; mark mine locations as
; already revealed. This
; makes all-revealed-p
; simpler.
(decf clear-length)
(setf (aref clearspots choice-index)
(aref clearspots clear-length)))))
(dotimes (i board-length)
(unless (eql (aref board i) :mine)
(setf (aref board i) (count-surrounding-mines game i)))))))
(defgeneric location (game x y)
(:documentation "Returns the contents of the board at the
specified (X,Y) location. This can either be :MINE if there is a
mine present, or the number of surrounding mines (0 - 8) if there is
nothing at that location."))
(defmethod location ((game game) x y)
(aref (board-of game) (xy-to-linear game x y)))
(defgeneric mine-p (game x y)
(:documentation "Returns NIL if there is not a mine at the
specified (X,Y) location."))
(defmethod mine-p ((game game) x y)
(eql :mine (location game x y)))
(defgeneric mark-revealed (game x y)
(:documentation "Mark that the user has seen this particular (X,Y)
position."))
(defmethod mark-revealed ((game game) x y)
(with-slots (revealed)
game
(let ((position (xy-to-linear game x y)))
(setf (aref revealed position) t))))
(defgeneric all-revealed-p (game)
(:documentation "Return true if every board position has been
revealed; NIL otherwise. The user wins when every board position has
been revealed without him selecting a position with a mine. This is
the case because the positions with mines are marked as being
revealed in INITIALIZE-INSTANCE."))
(defmethod all-revealed-p ((game game))
(every #'identity (revealed-of game)))
(defgeneric reveal (game x y)
(:documentation "Reveals the content of the game board location
specified by X and Y. Returns the number of mines surrounding the
location if the location does not contain a mine, or :BOOM-GAME-OVER
if the location contains a mine. If the user selects all the free
spaces on the board, the function returns :YOU-WIN instead of the
number of surrounding mines."))
(defmethod reveal ((game game) x y)
(when (game-over-of game)
(error "This game is already over."))
(if (mine-p game x y)
(progn
(setf (game-over-of game) t)
:boom-game-over)
(progn
(mark-revealed game x y)
(if (all-revealed-p game)
(progn
(setf (game-over-of game) t)
:you-win)
(location game x y)))))
