Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #23706

Re: depth first search

Show all headers | View raw

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)

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

depth first search willmann817@gmail.com - 2013-04-27 21:46 -0700
  Re: depth first search Barb Knox <see@sig.below> - 2013-04-28 21:06 +1200
    Re: depth first search "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2013-04-28 11:40 +0100
      Re: depth first search willmann817@gmail.com - 2013-04-28 07:22 -0700
        Re: depth first search "Alex" <foo@email.invalid> - 2013-04-28 20:25 +0000
          Re: depth first search Lew <lewbloch@gmail.com> - 2013-04-28 19:01 -0700
        Re: depth first search Lew <lewbloch@gmail.com> - 2013-04-28 18:42 -0700
          Re: depth first search Barb Knox <see@sig.below> - 2013-04-29 13:59 +1200
            Re: depth first search lipska the kat <"nospam at neversurrender dot co dot uk"> - 2013-04-29 11:21 +0100
              Re: depth first search Barb Knox <see@sig.below> - 2013-05-02 16:02 +1200
  Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 12:22 -0700
  Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 12:49 -0700
    Re: depth first search markspace <markspace@nospam.nospam> - 2013-04-28 16:21 -0700
  Re: depth first search Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2013-04-28 21:43 -0500
    Re: depth first search willmann817@gmail.com - 2013-04-29 08:46 -0700

csiph-web