[Haskell-cafe] Algorithm for labeling same-colored regions in a 2D array?

[Bob Ippolito]

I've done this before with a data structure inspired by Union-Find
https://github.com/etrepum/exercism-exercises/blob/master/haskell/go-counting/Counting.hs


On Mon, Jun 30, 2014 at 8:17 PM, Steve Trout <steve.trout at gmail.com> wrote:

> (Apparently joining the list through the Google Groups interface doesn't
> work, but the post still shows up there. Sorry if you see this twice!)
>
> For fun, I'm writing a rules engine for the board game Go (in Haskell
> obviously). I have a board, which is a grid of spaces that can contain a
> black piece, a white piece, or nothing. Part of what i need to do is to
> detect regions of the same "color" (black, white, or empty) and get
> information about them like their size, the color of the bordering spaces,
> etc. Regions are bounded by other colors or the board edges in cardinal
> directions. I'm just starting on this so I haven't picked my data
> structures yet, but Vector (Vector _) or Map (Int, Int) _ are what I've
> toyed with.
>
> I have a vague idea of how I would go about this in an imperative language
> with mutation. I'd iterate over the board, keeping lists of points
> contained in the same region, combining (relabeling) regions if they happen
> to connect later on. (I realize there are probably better algorithms in
> those languages, but that would be my first attempt.) I know i could cobble
> something like this together in the State monad, but I have a feeling that
> there ought to be a better (more "Haskellish"/pure-functional) way.
>
> What would a Haskellish algorithm for this kind of thing look like? I
> wouldn't mind a complete answer or just a nudge in the right direction.
>
> Thanks,
> -Steve
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140630/d123bcb1/attachment.html>