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

[Bryan Gardiner]

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;hb=HEAD

Cheers,
Bryan


On Mon, 30 Jun 2014 20:23:50 -0700
Bob Ippolito <bob at redivi.com> wrote:

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



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