Minesweeper board labels (beginner level)

Question

We were given a homework, where we get a sample minesweeper-like board, with blank spaces instead of numbers (board is in [String] form) and already placed mines. What we need is to create a function, that replaces all blank spaces with numbers, which are equal to number of adjecent mines.

I was unable of making any real progress, except for removing all spaces with zeroes, which is probably not even useful in any way. I also had a problem with zeroes being of Char type, which made me unable to add for example +1 to it. It would be great if this could be solved without advanced functions, so I can understand it, but any solution or at least idea of solution will do.

This is what the beginning of the code should look like.

import Data.Char

type Result = [String]

pp :: Result -> IO ()
pp x = putStr (concat (map (++"\n") x)) --prints strings in a column.


sampleInput = ["       ",
               " *     ",
               "    *  ",
               "   *   ",
               "      *",
               "***    ",
               "* *    ",
               "***    "]

minesweeper :: Result -> Result

And result should be this

Prelude>pp(minesweeper sampleInput)
1110000
1*11110
1122*10
001*221
233211*
***2011
*8*3000
***2000

I'm incredibly glad for any guidance as I'm unable of any real progress.

Update: Did a bit different yet similar solution. You can check related question here

Answer 1

What you need here is called "stencil convolution". Look at this picture:

111
1x1
111

This is your stencil. Pick a tile on the playing board and place the stencil on top of that tile. How many 1s overlay mines, that number we should display in this tile. For example:

       .....   .....
111    .*...   .....
1x1  + ..x*. = ..3..
111    ...*.   .....
       .....   .....

Once we apply this operation to the whole board, we are basically done.

There are advanced devices for this, such as comonads and arrays, but for the purpose of this post I will keep things simple, so we are going to draft everything by hand, in the simplest types. I am also going to leave some blanks in the code, so that it is less boring for the reader. If you enable -fdefer-typed-holes, you can put things like _wut in place of ... and ghc will tell you what it thinks the type of the hole should be.

---

1. I should like to deal with numbers, rather than characters: as you point out, characters are ill-suited for algorithmic work. Conversion should be two way, so that we can display our result as well.

   charsToInts :: [[Char]] -> [[Int]]
   charsToInts = (fmap . fmap) charToInt
     where
       charToInt '*' = ...
       charToInt ... = ...
   
   intsToChars :: [[Int]] -> [[Char]]
   intsToChars = ...
   

2. A nested list is not a very comfortable type to work with. We will define some helper functions to make it easier. The operation that we will surely need is "indexing", that is, accessing an element by its index — if it is there in the first place.

   lookup2DMaybe :: [[a]] -> (Int, Int) -> Maybe a
   lookup2DMaybe u (i, j) = do
       xs' <- lookupMaybe xs  i
       x   <- ...
       return x
     where
       lookupMaybe :: [a] -> Int -> Maybe a
       lookupMaybe xs i
           | 0 <= i && i < length xs = ...
           | ...                     = ...
   

3. Now, to interesting stuff — stencil application.

   applyStencil :: [[Int]] -> (Int, Int) -> Int
   applyStencil u = sum . Data.Maybe.catMaybes . fmap (... u) . stencil
     where
       stencil :: (Int, Int) -> [(Int, Int)]
       stencil (i, j) = [ (i + di, ...) | di <- ..., dj <- ..., (di, dj) /= ... ]
   

   Does this work?

   λ applyStencil (charsToInts sampleInput) (3, 5)
   2
   λ applyStencil (charsToInts sampleInput) (6, 1)
   8
   

4. All that is left to do is to "map" the stencil all around the minefield. To this end, we are going to generate a board where at every point its coordinates are written. I hope somewhere along the way you will see why.

   indices :: [[a]] -> [[(Int, Int)]]
   indices u = [ [ ... | ... ] | ... ]
   

   The idea here is that we give it a board of anything, and it creates a board of coordinates of the same size.

5. Consider the type we have so far:

   λ :type applyStencil (charsToInts sampleInput) 
   applyStencil (charsToInts sampleInput) :: (Int, Int) -> Int
   

   So, this is a function that converts coordinates to the number of mines around these coordinates. What happens if we map it over a board of coordinates?

   fill :: [[Int]] -> [[Int]]
   fill u = (fmap.fmap) (... u) (... u)
   
   λ intsToChars (fill (charsToInts sampleInput))
   ["1110000","1011110","1122110","0011221","2332110","2422011","4843000","2422000"]
   

   Looks about right, does it not?

6. Only small things left to do: given two boards of characters, overlay them. This is outlined in an answer to another question about lists of lists. (We get a lot of of questions of this kind of late. Say hi to your professor from the Stack Overflow Haskell Teacher's Assistants Team!)

7. Final solution!

   minesweeper x = overlay x (intsToChars . fill . charsToInts $ x)
   

   Not hard at all!

---

There are some ways to improve this code:

1. Create a specialized type for the board, such that only correct boards can be constructed.
2. Define a comonad for that type.
3. Scratch the type altogether and generalize the code to the Store comonad.
4. Use efficient array processing.

But the ideas we explored are there to last.

Some further reading:

1. The basics of stencil convolution.
2. The use of standard comonad types.
3. Advanced optimization of stencil convolution.

 

Let me know how it goes!