Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!mx05.eternal-september.org!.POSTED!not-for-mail
From: markspace <markspace@nospam.nospam>
Newsgroups: comp.lang.java.programmer
Subject: Re: depth first search
Date: Sun, 28 Apr 2013 16:21:26 -0700
Organization: A noiseless patient Spider
Lines: 85
Message-ID: <klkanl$gud$1@dont-email.me>
References: <77f5a380-09d9-4054-b26f-22b32424b504@googlegroups.com> <kljuag$8or$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 28 Apr 2013 23:18:13 +0000 (UTC)
Injection-Info: mx05.eternal-september.org; posting-host="fba3415ba68d85d643935af2f52f0b4b"; logging-data="17357"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+f+F/BXLrz2RxhKwUV+anCHiFkI2AtY7M="
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130328 Thunderbird/17.0.5
In-Reply-To: <kljuag$8or$1@dont-email.me>
Cancel-Lock: sha1:gObHTq/qK5lRf1aEGMk4YSsNGfk=
Xref: csiph.com comp.lang.java.programmer:23706

On 4/28/2013 12:49 PM, markspace wrote:
> On 4/27/2013 9:46 PM, willmann817@gmail.com wrote:
>> I am given method signature that takes a square 2D Character Array (a
>> matrix) that represents a board of a game called Go....  Using depth
>> first search how can I count the number of alive black pieces and
>> alive white pieces?
>
> I'm not sure what relevance breath-first vs depth-first has.  There's no
> search tree here that I can see.  You need to find all groups
> (contiguous collections of stones) on the board and then mark all those
> that have no liberties as "dead."  Any search will do that, I think.
> Heck you might be able to do with with a simple iteration over the board
> if you're clever about it.
>


Yup, just a simple linear scan of the board will locate all groups.


    private void scanGroups()
    {
       for( int i = 0; i < board.length; i++ ) {
          for( int j = 0; j < board[i].length; j++ ) {
             Stone stone = board[i][j];
             if( stone == null ) continue;
             addGroup( stone, stoneAbove( j, i ), stoneLeft( j, i) );
          }
       }
    }

stoneAbove and stoneLeft are pretty trivial.  addGroup is more 
complicated in that you have to check for existing groups and merge two 
groups if they are the same color as the stone under consideration.  But 
it's not that hard to work out either.

After that scanning for dead groups is also completely linear.  Just 
list all the groups, and for each stone, if it has any liberties, then 
the group is alive.  Otherwise you have a dead group.

    private void printDeadGroups()
    {
       nextGroup:
       for( Group g : groups ) {
          for( Stone s : g ) {
             if( hasLiberties( s ) ) {
                continue nextGroup;
             }
          }
          System.out.println( "Dead: "+ g );
       }
    }

Non-trivial, but not super hard.

Good luck.

run:
  1: W.W..BBB...B.B..WWB
  2: .W.BBBB.WB..BBBW..W
  3: ..W.W.B..B.....W.W.
  4: B..WWWWBWW.W.BW.W..
  5: ..WW..WB.B.WBBW.BWW
  6: BWW..WWW.WWW.W.WB..
  7: BW..WBWW.B..W...BW.
  8: WWB.W.WB..B....BB.B
  9: .B.WW.WBBBWBWW..WW.
10: W.BBWW.B..WW....WW.
11: ..BW.WBWB.W.BB..BBB
12: ..B.B.BWBBW.B.B....
13: B....B.BWB..WW.B...
14: WW.B.BBB.BWBBW..WWW
15: BWW..W.B...W....BWW
16: ..W.BBBWBB...W..B.W
17: WB.W.B.BWW....BBB.W
18: W...BB.W.B.BB.BB.BB
19: ...B..B.BW.W.B.W.BW
     ABCDEFGHJKLMNOPQRST
Total groups:101
Dead: Group{stones=[Stone{color=WHITE, x=7, y=15}], color=WHITE}
Dead: Group{stones=[Stone{color=WHITE, x=18, y=18}], color=WHITE}
Dead: Group{stones=[Stone{color=BLACK, x=18, y=0}], color=BLACK}
Dead: Group{stones=[Stone{color=WHITE, x=7, y=11}, Stone{color=WHITE, 
x=7, y=10}], color=WHITE}
BUILD SUCCESSFUL (total time: 0 seconds)