Haskell - 在笛卡尔网格中对特定的最近邻居进行分组

Question

我在这个难题中寻求一些方向，我需要将特定的最近邻居分组在一起。

我的输入数据是：

myList :: Map (Int, Int) Int
myList =
  fromList
    [((-2,-2),0),((-2,-1),0),((-2,0),2),((-2,1),0),((-2,2),0)
    ,((-1,-2),1),((-1,-1),3),((-1,0),0),((-1,1),0),((-1,2),1)
    ,((0,-2),0),((0,-1),0),((0,0),0),((0,1),0),((0,2),0)
    ,((1,-2),0),((1,-1),0),((1,0),0),((1,1),2),((1,2),1)
    ,((2,-2),0),((2,-1),2),((2,0),0),((2,1),0),((2,2),0)]

这是这个 5 x 5 网格（棕色土地，蓝色水）的数据表示： 我使用(Int,Int)作为XY坐标，因为必须生成列表的方式（因此其顺序）是在(0,0)作为原点的笛卡尔坐标网格上的螺旋中。剩下的Int就是人口规模0，即水、1..9土地。

由于我的排序，Map我一直在努力寻找一种方法来遍历我的数据并返回4分组的土地项目，这些土地项目由于彼此连接的接近度（包括对角线）而分组，所以我正在寻找如下结果：

[ [(-1 , 2)]
, [(1, 2),(1,1)]
, [(-2, -0),(-1,-1),(-1,-2)]
, [(2, -1)]]

我研究并尝试了各种算法，如 BFS、Flood Fill，但我的输入数据永远不符合结构要求，或者我对主题的理解不允许我将其转换为使用坐标。

有没有办法可以直接在数据上运行算法，或者我应该寻找另一个方向？

很抱歉，到目前为止我还没有代码示例，但我什至无法创建任何远程有用的东西。

Answer 1

我最终通过 FP slack 频道采用了 Chris Penner 的解决方案，它使用并集查找算法（我在代码中添加了注释以提供一点帮助）：

-- | Take Map of land coordinates and return list of grouped land items forming islands
-- | Using Union find algorythm
findIslands ::  M.Map Coordinate Coordinate -> IO [[Coordinate]]
findIslands land = do
  -- create fresh point map
  pointMap <- traverse U.fresh land
  -- traverse each point checking for neighbours
  void . flip M.traverseWithKey pointMap $ \(x, y) point ->
      for_ (catMaybes (flip M.lookup pointMap <$> [(x + 1, y), (x, y + 1),(x +1, y +1), (x - 1, y + 1)]))
          $ \neighbourPoint ->
              U.union point neighbourPoint
  -- traverse ppintMap and representative and their descriptors
  withUnionKey :: (M.Map Coordinate Coordinate) <- for pointMap (U.repr >=> U.descriptor)
  -- swap cordinates arround
  let unionKeyToCoord :: [(Coordinate, Coordinate)] = (swap <$> M.toList withUnionKey)
      -- combine coordinates to create islands
      results :: M.Map Coordinate [Coordinate] = M.fromListWith (<>) (fmap (:[]) <$> unionKeyToCoord)
  -- return just the elements from the Map
  return (M.elems results)

convertTolandGrid :: [Coordinate] -> M.Map Coordinate Coordinate
convertTolandGrid = M.fromList . fmap (id &&& id)