扫雷板标签（初学者级别）

Question

我们得到了一项作业，在其中得到了一个类似于扫雷的样板，带有空格而不是数字（板为[String]形式）并且已经放置了地雷。我们需要创建一个函数，该函数将所有空格替换为等于相邻地雷数量的数字。

我无法取得任何实际进展，除了删除所有带有零的空格外，这可能根本没有用。我还遇到了一个问题，即零是Char类型，这使我无法为其添加例如+1。如果可以在没有高级功能的情况下解决此问题，那就太好了，所以我可以理解，但是任何解决方案或至少是解决方案的想法都可以。

这是代码开头的样子。

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

结果应该是这个

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

我为任何指导感到非常高兴，因为我没有任何实际进展。

Answer 1

您在这里需要的称为“模板卷积”。看这张照片：

111
1x1
111

这是您的模具。在游戏板上挑选一块瓷砖，然后将模板放在该瓷砖的顶部。有多少1个覆盖地雷，我们应该在此图块中显示该数字。例如：

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

一旦将这一操作应用到整个板上，我们就基本完成了。

[为此，有一些高级设备，例如comonads和数组，但出于本文的目的我将使事情保持简单，因此我们将以最简单的类型手工起草所有内容。一世我还将在代码中留一些空白，以免使读者感到无聊。如果你启用-fdefer-typed-holes，您可以将-fdefer-typed-holes之类的内容替换为_wut和...会告诉您对孔类型的看法。

---

1. 我想处理数字而不是字符：如您所指出的，字符不适合进行算法工作。转换应该是两种方式，以便我们可以显示结果。

   ghc

2. 嵌套列表不是一个非常舒适的类型。我们将定义一些辅助函数使它更容易。我们肯定需要执行的操作是“ indexing”]，即访问元素的索引号-如果它排在首位。

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

3. [[现在，到有趣的东西—模具应用。

   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 = ...
           | ...                     = ...

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

4. 剩下要做的就是在雷场周围的所有模板上

   “ map”。为此，我们将生成一个板，在每个板上都写入其坐标。我希望在某个地方您将看到原因的方式。

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

   这里的想法是，我们给它任何东西，它创建一个坐标为相同的大小。

5. 考虑到目前为止的类型：

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

   因此，这是一个将坐标转换为围绕这些地雷的数量的函数坐标。如果将其映射到坐标板上会发生什么？
   λ :type applyStencil (charsToInts sampleInput) 
   applyStencil (charsToInts sampleInput) :: (Int, Int) -> Int
   

   看起来不错，不是吗？

6. 只剩下小事了：给定两个字符板，将它们覆盖。这是概述

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

   关于列表列表。

   （我们对此有很多疑问有点晚。向Stack Overflow Haskell老师的助手打招呼团队！）

7. 最终解决方案！

   an answer to another question

   一点也不难！

---

有一些方法可以改进此代码：

为板创建专用类型，以便只能构造正确的板。
1. 为该类型定义一个comonad。
2. 完全擦除类型并将代码概括为商店的通用代码。
3. 使用有效的数组处理。

但是我们探索的想法将持续到最后。

一些进一步的阅读：

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

The basics of stencil convolution.

The use of standard comonad types.

让我知道怎么回事！