Haskell-デカルトグリッドで特定の最も近い隣人をグループ化する

debugcn 投稿 Dev

cmdv

私はこのパズルのいくつかの方向性を求めており、特定の最も近い隣人をグループ化する必要があります。

私の入力データは次のとおりです。

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×5グリッド（褐色土地、青水）のデータ表現これは私が使用している(Int,Int)ようにXYリストが持っていた方法は、グリッドデカルト座標上に螺旋状にされた（従って、その順序）が生成されるので、座標(0,0)ビーイングを起源。残りIntは0水で1..9あり土地である人口の大きさです。

Because of the ordering of my Map I've been struggling with finding a way I can traverse my data and return 4 grouped land items that are grouped due to each others connected proximity (including diagonal), so I'm looking for a result like bellow:

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

I've researched and tried various algorithm like BFS, Flood Fill but my input data never fit the structural requirements or my understanding of the subjects doesn't allow me to convert it to using coordinates.

Is there a way I can run an algorithm directly on the data, or should I be looking at another direction?

I'm sorry there is no code examples of what I have so far but I've not even been able to create anything remotely useful to use.

cmdv

FPスラックチャネルを介してChrisPennerによるこのソリューションを使用することになりました。これは、Union Find Algorithmを使用します（少し役立つようにコードにコメントを追加しました）。

-- | 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)

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]

編集2021-06-11

コメントを追加

サインイン

分類Dev

Related 関連記事

記事

Haskell-デカルトグリッドで特定の最も近い隣人をグループ化する

Haskell-デカルトグリッドで特定の最も近い隣人をグループ化する

Haskellのリストで隣接する値をグループ化する

haskellのリスト内の要素をグループ化する

Haskellを使用してリストの要素をグループ化する

Haskellでグループ化してカウントする方法は？

haskellのデバッグループ

Haskellで型クラスをグループ化する方法

Haskellの無限文字列のフィルタリングを最適化する

Haskellグレネードでオートエンコーダーをモデル化する

スタック-Haskellコーディングの模擬試験Q：文字列のリストで最も長い文字列を返します

次のようにリストの要素をグループ化する関数がHaskellにありますか？

Haskellツリーで整数引数に最も近いキーを見つける

haskellで作成されたデータ型のリストから要素をフィルタリングする

Haskellでシングルトンリストの内容をテストする最も効率的または慣用的な方法は？

それぞれの名前でいくつかのローカルバインディングを印刷/ダンプできる（テンプレート）Haskellライブラリはありますか？

リストのリストでタプルをフィルタリングする[Haskell]

haskell：特定の記号（例： '！'）で文字列をフィルタリングする リストに？

別のプログラムで使用できるHaskellのモジュールをリリースする方法は？

特定の要素の値に基づいてHaskellのリストをフィルタリングするにはどうすればよいですか？

Haskellの「リスト」インデックスを最適化する

Haskell。同じ隣人を取得する

Haskell のリスト内の特定のタプルを更新するにはどうすればよいですか?

Haskellデータ型で重複するフィールド名をリファクタリングするにはどうすればよいですか？

HaskellのデフォルトのIOバッファリング

グループが述語を満たすまでHaskellグループリスト

Haskellのコンストラクターによるデータ型のグループ化

Haskellで共通の整数について3つのリストをチェックする最も効率的な方法

Haskellのgraphvizパッケージを使用してグラフラベルをプロットする方法

pandas-カテゴリのグループ化を含む最も近い値のルックアップ

カフェ (pycaffe) での最も近い隣人アップサンプリング

haskell：特定の記号（例： '！'）で文字列をフィルタリングするリストに？