Sweeping Mines… Functionally

Mr. GeekRaver and I were walking between buildings and, for some reason, talking about how silly it is that good ol’ Minesweeper was “glossed up” for Vista. He said he had written it for DOS in some tiny amount of C code (http://www.bradygirl.com/Work/mine.c).

His explanation of little tricks to make the implementation simple (e.g. a traverse() function that walks the board applying a passed in function to each cell) sounded like FP to me. So, here it is in about 40 lines of F# (plus another 50 for UI). Now, my challenge to him is to beat that using Python (his current kick) this time...

// Minesweeper (in 90 lines)

open System
open System.Drawing
open System.Windows.Forms

let w = 9  // width of mine field
let h = 9  // height
let d = 10 // 1:10 mine density

type State = Unknown | Flag | Expose
type mines = (bool * State)[,]

let randomField = // init field w/randomly placed mines
let r = new Random(int DateTime.Now.Ticks)
Array2D.init w h (fun _ _ -> (r.Next(d) = 0), Unknown) // note _

let adjacentCoordinates x y = [ // list of adjacent x,y pairs
for i in x - 1 .. x + 1 do
for j in y - 1 .. y + 1 do
if (i <> x || j <> y) && // not including x,y itself
i >= 0 && i < w && j >= 0 && j < h // not off edges
then yield (i, j) ]

let adjacentCells (m : mines) = // list of adjacent cells
List.map (fun (x, y) -> m.[x, y]) // note (x, y) and curried xy

let countMines m = Seq.sumBy (function (true, _) -> 1 | _ -> 0) m // given Seq of cells
let countFlags m = Seq.sumBy (function (_, Flag) -> 1 | _ -> 0) m

let setCell f m x y = // apply f to snd of cell x,y of m

Array2D.mapi (fun i j (cx, cy as c) ->

if i = x && j = y then (cx, f cy) else c) m

let setFlag m = // toggle Flag, but leave already Exposed as is

setCell (function Unknown -> Flag | Flag -> Unknown | Expose -> Expose) m

let setExpose m = setCell (function Flag -> Flag | _ -> Expose) m // leaved Flagged as is

// automatically expose safe cells based on exposed mines and flags
let rec autoExpose (m : mines) = function // x, y
| [] -> m
| (x, y) :: t ->
if (snd m.[x, y]) = Unknown then
let n = setExpose m x y
let a = adjacentCoordinates x y
let c = adjacentCells n a
autoExpose n (if countFlags c >= countMines c then (a @ t) else t)
else autoExpose m t // already Exposed or Flagged

// that's it, the rest is UI:
let form =
let field = ref randomField
let s = 60 // grid size

let paintField (g : Graphics) =
let paintCell (g : Graphics) x y c =
let i = x * s // x-coordinate
let j = y * s // y-coordinate
let l = i + 1 // left (with 1 pix inset)
let t = j + 1 // top
let (r : int) = i + s - 1 // right
let b = j + s - 1 // bottom
let i = s - 1 // inner size
let f = new Font(FontFamily.GenericSansSerif, 24.0f, FontStyle.Bold)
match c with
| (_, Unknown) -> // "embossed"-looking highlights
g.DrawLine(Pens.DarkGray, r, t, r, b)
g.DrawLine(Pens.DarkGray, l, b, r, b)
g.DrawLine(Pens.White,    l, t, r, t)
g.DrawLine(Pens.White,    l, t, l, b)
| (   _, Flag)   -> g.FillRectangle(Brushes.Green, l, t, i, i)
| (true, Expose) -> g.FillRectangle(Brushes.Red,   l, t, i, i)
| (   _, Expose) ->
g.FillRectangle(Brushes.Gray, l, t, i, i)
let n = (countMines (adjacentCells !field (adjacentCoordinates x y))).ToString()
if n <> "0" then
let b = match n with
| "1" -> Brushes.LightBlue
| "2" -> Brushes.LightGreen
| "3" -> Brushes.LightCoral
| _   -> Brushes.White
let m = g.MeasureString(n, f)
g.DrawString(n, f, b,
float32 l + (float32 s - m.Width)  / 2.0f,
float32 t + (float32 s - m.Height) / 2.0f)
g.Clear(Color.Gainsboro)
Array2D.iteri (paintCell g) !field // note: use of currying paintCell

let f = new Form(Text = "Mines", ClientSize = new Size(w * s, h * s), Visible = true)
f.Paint.Add(fun a -> paintField a.Graphics)
fun a -> let i = a.X / s
let j = a.Y / s
field := if a.Button = MouseButtons.Left
then autoExpose !field [(i, j)]
else setFlag !field i j
let m, s = (!field).[i, j] // m, s
if m && s = Expose then // exposed a mine?!
field := Array2D.map (fun (m, _) -> (m, Expose)) !field // expose everything
f.Refresh()
MessageBox.Show("Boooooom!\nTry again.") |> ignore
field := randomField // start over
f.Refresh())
f

Application.Run(form)

Tags