主页 / coding / 问题 / 79268916
Accepted
lanf
Asked: 2024-12-11 00:04:01 +0800 CST

Haskell 中与 DFS 兼容的无坐标邻居

  • 772

我最近发现自己正在解决很多二维矩阵搜索问题。一种典型的方法如下图所示，它在二维数组中沿着 4 个方向连接的路径搜索单词：

data State = S { word :: String, coord :: Coord } deriving (Eq, Ord, Read, Show)
data Coord = C Int Int deriving (Eq, Ord, Read, Show)

dfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]
coordMap :: [[a]] -> Map Coord a
cardinals :: Coord -> [Coord]
neighbors :: Map Coord Char -> State -> [State]

solution :: [[Char]] -> String -> Bool
solution board w = any found . search . states w $ board
  where
    search = dfsOnN coord (neighbors vals)
    found  = (== "") . word
    vals   = coordMap board

带签名的DFS函数

dfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]

采用投影函数，将状态发送到适合访问集的表示，以及后继函数，计算图中的邻居。

我的麻烦在于后继函数。从 的类型签名可以看出neighbors，我通常将位置映射到值，并在相邻坐标上执行查找以获取后继。但我觉得这是一种非常迂回的做法。如果我们总是将矩阵作为列表列表给出，那么列表已经“知道”附近有什么内容，因为它是连续的。

在许多类似的问题中，我们将其转换为坐标/索引的唯一原因就是执行索引算法来获取邻居。坐标本身对于问题而言完全是多余的。我们还必须担心查找可能会失败，Maybe如果我们使用类似的东西，则需要进行处理Map Coord Char，但这也应该是不必要的。列表列表已经“知道”其边界在哪里，当我们将其转换为坐标时，我们会丢弃此信息。

问题：a -> [a]是否有一种简洁的方法来实现不使用坐标的二维矩阵问题的快速总邻域函数？

限制：

  • 简洁意味着包括类型签名在内的标记少于 100 个（我的坐标完整版本的粗略大小）
  • 欢迎采用适合相当流行/常见/规范的库的解决方案。（因此base，诸如containers、、、、等等。unordered-containers）fglheaps
  • 总计意味着没有诸如、、!!等部分函数。headmaximum
  • 快的意思O(log n)。

为什么要有特定的限制？很简单，因为我已经知道如何在没有这些限制的情况下解决问题。我感兴趣的是找到一种原则性的方法来解决这类问题，当不允许使用大型自定义模板库时，这种方法将非常适合竞技编程。

解决方案的想法：我想知道像2D 拉链这样的东西是否可以起作用。

注意：我问了一个标题与此处类似的问题，但这些问题完全不相关，因为类型[[NonEmpty a]]或类似的值与上述 DFS 函数不“兼容”。似乎没有很好的方法可以从单元格的邻居列表中获取值，然后在 O(1) 中依次获取其邻居，因为这需要我们在正确的位置重新索引列表，但我们在此表示中丢弃了有关位置的所有信息。

haskell

1 个回答

  1. Best Answer

    当然，只需使用neighbors这个大链接答案即可。然后你可以写

    neighborMap :: Ord a => [[a]] -> Map a [a]
neighborMap ss = M.fromListWith [(k, [v]) | (k, v) <- neighbors ss]
-- OR, to save 11 tokens at the cost of sanity
neighborMap = M.fromListWith . fmap (fmap pure) . neighbors

    我猜它可能无法满足您的“简洁”要求，如果包括类型签名，则大约需要 200 个标记。不过，我再次感到有点惊讶的是，您可以在 100 个标记中完成您所说的内容；我数了一下，仅在 、 、 、 的声明中以及您发布的代码中就有近 70 个标记State，Coord这coordMap在cardinals您neighbors开始编写函数实现之前就已经用完了您的大部分预算。

    您可以使用 来避免Maybe在查找中使用M.findWithDefault []。（我有时希望有一个newtype包装器Map可以更优雅地处理此类事情，例如fromList :: Monoid v => [(k, v)] -> MonoidMap k v和lookup :: Monoid v => k -> MonoidMap k v -> v。该total-map包使用 部分解决了这个问题(!)，但它的fromList类似物通常不如我想要的那么好。）

    • 2

相关问题