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

Good to see other Go projects here. I'm currently just taking the easy route and using bucket fill to compute groups and their liberties. So far I'm just dealing with playing individual moves, and it runs acceptably for that; no scoring or boards large enough for this to matter yet. I'll probably switch to something like union-find eventually. That's a better idea and it sounds like you want something with good asymptotic performance, anyway. computeGroup here: http://khumba.net/git/?p=goatee.git;a=blob;f=src/Khumba/Goatee/Sgf/Board.hs;... Cheers, Bryan On Mon, 30 Jun 2014 20:23:50 -0700 Bob Ippolito wrote:

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

On Mon, Jun 30, 2014 at 8:17 PM, Steve Trout 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Go game editor :: http://khumba.net/projects/goatee :: AGPL, Haskell I: [pulseaudio] main.c: Fresh high-resolution timers available! Bon appetit!