Liquid Nitrogen Blaster
Group: Ice Age Members
Posts: 157
Member No.: 532
Joined: 25-September 04
Ice Cubes: 11
|
The problem is, given an input file like:
Get the number of mines (*) surrounding each letter. - Start a new module named MineSweeper.
| CODE | | module MineSweeper where |
Import a few useful modules.
| CODE | import List
import IO
-- I realized this one isn't really necessary:
-- import Char
import Maybe |
Create a new data type called Square. Square can be represented by a Mine, a Safe spot, or a Letter representing some other character. Derive Show and Eq so they can be stringified for printing, and so that squares can be compared for equality.
| CODE | | data Square = Mine | Safe | Letter Char deriving (Show, Eq) |
Create type Row and type Grid, which are basically just type synonyms for lists of Squares and lists of lists of Squares.
| CODE | type Row = [Square]
type Grid = [Row] |
Get a grid given a FilePath (a String).
| CODE | | getGrid :: FilePath -> IO Grid |
To do this, read the file's contents, then use the "lines" function to split that content into lines. Let the first line be called "first" and the rest be called "others." Use parseGridDimensions to parse the first line and get the height and width of the grid. Use createGrid to process the other lines and turn characters into Mine, Safe, or Letter values. Then use trimGrid to remove anything outside the bounds of the dimensions parsed earlier.
| CODE | getGrid fileName = do
contents <- readFile fileName
let (first:others) = lines contents
let dimensions = parseGridDimensions first
return $ trimGrid dimensions $ createGrid others |
Generic parseGridDimensions function. Take a String and return two readable values. In this case Ints.
| CODE | | parseGridDimensions :: Read a => String -> (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.
| CODE | parseGridDimensions input = (n, m)
where
[(n, input')] = reads input
[(m, _) ] = reads input' |
Pretty simple. Takes a Char and converts it to a Square.
| CODE | | 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.
| CODE | charToSquare ch =
case ch of
'.' -> Safe
'*' -> Mine
n -> Letter n |
Process a list of Strings into a Grid.
| CODE | | 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 [Letter 'D', Safe, Mine, Safe].
| CODE | | createGrid = map (map charToSquare) |
Trim unnecessary rows and columns from the Grid.
| CODE | | 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.
| CODE | | 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).
| CODE | | 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.
| CODE | | 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 .
| CODE | | 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.
| CODE | 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.
| CODE | findLetters (n, m) ((_:xs):r) =
findLetters (n, m + 1) (xs:r) |
Find the Letters present in the Grid.
| CODE | | 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.
| CODE | | lettersPresent = fst . unzip . findLetters (0, 0) |
Find all coordinates adjacent to the input coordinates based on input dimensions for the grid.
| CODE | | 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.
| CODE | adjacentCoords s@(n, m) s'@(n', m') =
[(n'', m'') | n'' <- [n' - 1 .. n' + 1],
m'' <- [m' - 1 .. m' + 1],
(n'', m'') /= s' && inBounds s (n'', m'')] |
Get a Grid's dimensions.
| CODE | | getGridDimensions :: Grid -> (Int, Int) |
Get the height and width of a Grid by calculating its length and the length of it's first Row.
| CODE | | getGridDimensions grid@(x:_) = (length grid, length x) |
Collect all adjacent Squares to a set of target coordinates.
| CODE | | adjacentSquares :: (Int, Int) -> Grid -> [Square] |
First collect all adjacentCoords. Then, for each of those collect the Square located at them.
| CODE | adjacentSquares s@(n, m) grid =
map (`squareAt` grid) $ adjacentCoords (getGridDimensions grid) s |
Determine if a set of coordinates is within a set of bounds.
| CODE | | inBounds :: (Int, Int) -> (Int, Int) -> Bool |
Let n and m be the bounds of the Grid. Let n' and m' be the coordinates being tested. Pretty easy to understand.
| CODE | inBounds (n, m) (n', m') =
n' >= 0 && n' < n && m' >= 0 && m' < m |
Retrieve a Square at a particular set of coordinates within a Grid.
| CODE | | squareAt :: (Int, Int) -> Grid -> Square |
Use the !! operator to do this. Consider "grid !! n !! m" similar to "grid[n][m]" in some other languages.
| CODE | | squareAt (n, m) grid = grid !! n !! m |
Count adjacent Squares which are Mines.
| CODE | | countAdjacentMines :: (Int, Int) -> Grid -> Int |
Find all adjacentSquares, filter it down to just those that are Mines, then count the resulting list.
| CODE | 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.
| CODE | getAdjacentMineCounts :: FilePath -> IO [(Char, Int)]
getAdjacentMineCounts fileName = do
grid <- getGrid fileName
let letterMap = findLetters (0, 0) grid
let letters = lettersPresent grid
return [(l, countAdjacentMines (fromJust $ lookup l letterMap) grid) | l <- letters] |
This post has been edited by wtd on Mar 15 2005, 08:07 PM
|
IceTeks Forums -> Technology made cool -> Programming
Dissection of a Program
