-----------------------------------

wtd

Tue Mar 15, 2005 2:47 am


For templest :)

-----------------------------------

To find the numbers of mines adjacent to letters on a map.  :)

module MineSweeper where

import List
import IO
import Char
import Maybe

data Square = Mine | Safe | Letter Char  deriving (Show, Eq)
type Row = [Square]
type Grid = [Row]

getGrid :: FilePath -> IO Grid
getGrid fileName = do
  contents  String -> (a, a)
parseGridDimensions input = (n, m)
  where
    [(n, input')] = reads input
    [(m, _)     ] = reads input'

charToSquare :: Char -> Square
charToSquare ch = 
  case ch of
    '.' -> Safe
    '*' -> Mine
    n   -> Letter n 

createGrid :: [String] -> Grid
createGrid = map (map charToSquare)

trimGrid :: (Int, Int) -> Grid -> Grid
trimGrid (n, m) = map (take m) . take n

findLetters :: (Int, Int) -> Grid -> [(Char, (Int, Int))]
findLetters (_,_) [] = []
findLetters (n, m) ([]:r) = findLetters (n + 1, 0) r
findLetters coords@(n, m) ((x:xs):r) = 
  case x of
    Letter ch -> (ch, coords) : findLetters (n, m + 1) (xs:r)
    _         -> findLetters (n, m + 1) (xs:r)

lettersPresent :: Grid -> [Char]
lettersPresent = fst . unzip . findLetters (0, 0)

adjacentCoords :: (Int, Int) -> (Int, Int) -> [(Int, Int)]
adjacentCoords s@(n, m) s'@(n', m') = 
  [(n'', m'') | n''  Grid -> [Square]
adjacentSquares s@(n, m) grid = 
  map (`squareAt` grid) $ adjacentCoords (getGridDimensions grid) s

inBounds :: (Int, Int) -> (Int, Int) -> Bool
inBounds (n, m) (n', m') = 
  n' >= 0 && n' < n && m' >= 0 && m' < m
    
squareAt :: (Int, Int) -> Grid -> Square
squareAt (n, m) grid = grid !! n !! m

countAdjacentMines :: (Int, Int) -> Grid -> Int
countAdjacentMines coords = 
  length . filter (Mine ==) . adjacentSquares coords

getAdjacentMineCounts :: FilePath -> IO [(Char, Int)]
getAdjacentMineCounts fileName = do
  grid  (a, a)

The reads function parses the desired Int from the input String.  We parse once, then parse the String remaining after the first parse.

parseGridDimensions input = (n, m)
  where
    [(n, input')] = reads input
    [(m, _)     ] = reads input'

Pretty simple.  Takes a Char and converts it to a Square.

charToSquare :: Char -> Square

If ch is '.' return Safe.  If ch is '*' then we get Mine.  Otherwise we get a Letter value storing the input Char.

charToSquare ch =
  case ch of
    '.' -> Safe
    '*' -> Mine
    n   -> Letter n

Process a list of Strings into a Grid.

createGrid :: [String] -> Grid

Do this by mapping "map toSquare" to each String.  "map toSquare" applies toSquare to each Char in a String and collects the result.

The result of running this on "D.*." would be createGrid = map (map charToSquare)

Trim unnecessary rows and columns from the Grid.

trimGrid :: (Int, Int) -> Grid -> Grid

Do this by first "take n", which grabs the first n rows from the Grid.  Then, for each of those Rows, "take m", which grabs the first m elements in each Row.

trimGrid (n, m) = map (take m) . take n

Find all of the letters in the grid and the coordinates at which they're located, starting from some initial set of coordinates (0, 0).

findLetters :: (Int, Int) -> Grid -> [(Char, (Int, Int))]

If the grid to search is empty, then we don't care about the coordinates.  Clearly there can be no Letters within.

findLetters (_,_) [] = []

If the first Row in the Grid is empty, continue searching with the remaining Rows.  Increment n by 1 and set m to zero to indicates starting again one row down at .

findLetters (n, m) ([]:r) = findLetters (n + 1, 0) r

If the first element in the current Row is a Letter, then append the Char it contains and the current coordinates to the result of finding the latters in the remaining Rows.  Increment the column (m) by 1.

findLetters coords@(n, m) (((Letter ch):xs):r) =
  (ch, coords) : findLetters (n, m + 1) (xs:r)

If the first element in the current grid is anything other than a letter, find the Letters in the remaining part of the Grid, incrementing the column count by 1.

findLetters (n, m) ((_:xs):r) =
  findLetters (n, m + 1) (xs:r)

Find the Letters present in the Grid.

lettersPresent :: Grid -> [Char]

To do this, first use the above findLetters function to find all of the letters and their coordinates.  Then unzip that list, meaning you get two lists: one containing the Letters,and the other containing the coordinates.  Use fst to just get the first list.

lettersPresent = fst . unzip . findLetters (0, 0)

Find all coordinates adjacent to the input coordinates based on input dimensions for the grid.

adjacentCoords :: (Int, Int) -> (Int, Int) -> [(Int, Int)]

Let n and m be the bounds of the Grid.  Let n' and m' be the coordinates of the target.  n'' and m'' are each coordinate between n' - 1 and n' + 1 and m' - 1 and m' + 1.  Coordinates are only accepted if they do not match the target exactly, and are within the bounds of the Grid. 

adjacentCoords s@(n, m) s'@(n', m') =
  [(n'', m'') | n'' = 0 && n' < n && m' >= 0 && m' < m

Retrieve a Square at a particular set of coordinates within a Grid. 
   
squareAt :: (Int, Int) -> Grid -> Square

Use the !! operator to do this.  Consider "grid !! n !! m" similar to "gridsquareAt (n, m) grid = grid !! n !! m

Count adjacent Squares which are Mines.

countAdjacentMines :: (Int, Int) -> Grid -> Int

Find all adjacentSquares, filter it down to just those that are Mines, then count the resulting list.

countAdjacentMines coords =
  length . filter (Mine ==) . adjacentSquares coords

Bundle all of it up together to read a file, get the Grid it represents, find the letters within it, then count the mines adjacent to those letters.

getAdjacentMineCounts :: FilePath -> IO [(Char, Int)]
getAdjacentMineCounts fileName = do
  grid