扫雷板标签（初级）

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

这里需要的是"stencil convolution"。看这张图：

111
1x1
111

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

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

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

有用于此的高级设备，例如 comonads 和数组，但出于此目的 post 我会保持简单，所以我们将以最简单的类型手工起草所有内容。我我还将在代码中留下一些空白，这样 reader 就不会那么无聊了。如果你启用 -fdefer-typed-holes，你可以用 _wut 之类的东西代替 ... 和 ghc 会告诉你它认为洞的类型应该是什么。

我想处理数字，而不是字符：正如你指出的，字符不适合算法工作。转换应该是双向的，这样我们就可以显示我们的结果也是。

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

intsToChars :: [[Int]] -> [[Char]]
intsToChars = ...

嵌套列表不是一种非常适合使用的类型。我们将定义一些辅助函数让它更容易。我们肯定需要的操作是"indexing"，即访问一个元素的索引 - 如果它首先存在。

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

这个有用吗？

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

剩下要做的就是"map"雷区周围的模板。为此，我们在将生成一个板，其中每个点都写有它的坐标。我希望在某个地方你会明白为什么的方式。
```
indices :: [[a]] -> [[(Int, Int)]]
indices u = [ [ ... | ... ] | ... ]
```
这里的想法是我们给它一个任何东西的板，它创建一个坐标板大小一样。

考虑我们目前的类型：

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

所以，这是一个将坐标转换为这些周围地雷数量的函数坐标。如果我们将它映射到坐标板上会发生什么？

fill :: [[Int]] -> [[Int]]
fill u = (fmap.fmap) (... u) (... u)

λ intsToChars (fill (charsToInts sampleInput))
["1110000","1011110","1122110","0011221","2332110","2422011","4843000","2422000"]

看起来不错，不是吗？

只剩下小事情要做：给定两块字符板，将它们重叠。这在概述关于列表列表。 （我们收到了很多关于这个的问题有点晚了。从 Stack Overflow Haskell 教师助理向你的教授问好组队！）

最终解决方案！

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

一点都不难！

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

为板创建一个专门的类型，以便只能构建正确的板。
为该类型定义一个 comonad。
完全划掉类型并将代码推广到 Store comonad。
使用高效的数组处理。

但我们探索的想法会持续下去。

进一步阅读：

让我知道进展如何！

扫雷板标签（初级）

Minesweeper board labels (beginner level)

haskell

list

minesweeper