depth first search

W

willmann817

I am given method signature that takes a square 2D Character Array (a matrix) that represents a board of a game called Go. The board has black piecesrepresented by a 'B' white pieces represented by a 'W' and empty spaces represented by '.' The board also has a padding to represent going off the board this padding on all sides is represented by the character '/'. A pieceis considered alive if it is horizontally or vertically next to an empty space and alive pieces are contagious to other alive pieces of the same color. Using depth first search how can I count the number of alive black pieces and alive white pieces? I only know how to use DFS on a graph data type not a 2D array.

B

Barb Knox

I am given method signature that takes a square 2D Character Array (a matrix)
that represents a board of a game called Go. The board has black pieces
represented by a 'B' white pieces represented by a 'W' and empty spaces
represented by '.' The board also has a padding to represent going off the
board this padding on all sides is represented by the character '/'. A piece
is considered alive if it is horizontally or vertically next to an empty
space and alive pieces are contagious to other alive pieces of the same
color. Using depth first search how can I count the number of alive black
pieces and alive white pieces?
I only know how to use DFS on a graph data type not a 2D array.

This sounds like homework, but I'll give you a hint: consider the 2D
array to be a graph, with the vertices being the array elements and the

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum videtur.
| BBB aa a r bbb |
-----------------------------

W

willmann817

Barb Knox wrote:

Indeed, and a more remarkably obtuse example of using DFS would be hard to

concoct.

Hmm...

Searching for the last character in a String ?

Returning the value of a static final integer field ??

-- chris

Thanks for your help! But I need to clarify a few things if it is not too much trouble. So what I gather from your post is that if I am starting off at (x,y) that I need to do a recursive call on (x-1,y) , (x+1,y) , (x, y+1) and (x,y-1). So for example:
/ / / / / / /
/ 00*11 /
/ *0000 /
/ 00111 /
/ 11100 /
/ 0010* /
/ / / / / / /

Imagine 0's are white and 1's are black and * is an empty space. Also image that the matrix also is a 7x7 and not a 5 by 5 where the above diagram issurrounded by '/' to make sure you don't get an index out of bounds error.So really my starting place will be (2,2) and I will search (1,2), (3,2) (2,1) and (2,3). So my idea was to change the 0's and 1's to some other character (but not the same character) if they are alive (this will tell me Ihave visited those spots) and dead spots I have visited will also be changed to a character to know I have visited them. But the problem is if i start at (2,2) above and mark that first spot dead I still need to come back and change it to alive after I have visited the spot below it or the spot 2 to the right of it. (Because liveness is contagious with similar colors). Can you maybe provide some more specific assistance. This is HW and I do not want the answer but I have been cracking away at this on scratch paper with pictures and diagrams but still am a little stuck.

I have a template for DFS but I do not know how to apply it to this situation:

DFS(Vertex){
if visited(vertex) = true{
return;
}
visited(vertex) = true;
Application SPecific Processing goes here
for each neighbor W of vertex,
DFS(W);

M

markspace

I am given method signature that takes a square 2D Character Array (a
matrix) that represents a board of a game called Go. The board has
black pieces represented by a 'B' white pieces represented by a 'W'
and empty spaces represented by '.' The board also has a padding to
represent going off the board this padding on all sides is
represented by the character '/'. A piece is considered alive if it
is horizontally or vertically next to an empty space and alive pieces
are contagious to other alive pieces of the same color. Using depth
first search how can I count the number of alive black pieces and
alive white pieces? I only know how to use DFS on a graph data type
not a 2D array.

I agree with the homework comment. However, if this is a personal
project of some sort, you might want to start with one of many computer
programs that play Go. They are likely to have algorithms like this

Here's one example:

<http://www.gnu.org/software/gnugo/>

M

markspace

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

A

Alex

So what I gather from your post is that if I am
starting off at (x,y) that I need to do a recursive call on (x-1,y) ,
(x+1,y) , (x, y+1) and (x,y-1).

Yes, that's what Barb was saying, and that corresponds to the line:

for each neighbor W of vertex

in your template below. But I think that should really be:

for each _unvisited_ neighbor W of vertex
/ / / / / / /
/ 0 0 * 1 1 /
/ * 0 0 0 0 /
/ 0 0 1 1 1 /
/ 1 1 1 0 0 /
/ 0 0 1 0 * /
/ / / / / / /
(FTFY)

So really my starting place will be (2,2)

Why? I don't understand what's special about that grid location.
and I will search (1,2), (3,2) (2,1) and (2,3). So my idea was to
change the 0's and 1's to some other character (but not the same
character) if they are alive (this will tell me I have visited those
spots) and dead spots I have visited will also be changed to a
character to know I have visited them. But the problem is if i start
at (2,2) above and mark that first spot dead I still need to come
back and change it to alive after I have visited the spot below it or
the spot 2 to the right of it. (Because liveness is contagious with
similar colors).

Your problem makes it sound like maybe you shouldn't actually change
the value of the piece at each location to determine whether or not a
square has been visited. You might consider maintaining a separate 2D
array of Boolean that helps you keep track of which squares have and
have not been visited as you do the depth-first traversal.
Can you maybe provide some more specific assistance.

Probably not, since I don't play Go and I don't really understand what
you're trying to do from your description. From Wikipedia, and as
Markspace has pointed out, it looks like what you really want to do is
find continguous chains of same-colored pieces. Using DFS for this is

for each unvisited, same-colored neighbor W of vertex

Meanwhile, it sounds like you'll need to keep track of the adjacent
unoccupied locations you come across as you traverse the group, but I
don't play Go, so I don't know how this information is used to
determine if a group is "alive" or "dead". Markspace suggests that as
long as there is any open adjacent location the group is alive, but
Wikipedia suggests that there needs to be at least two internal "eyes"
to make a group "alive", so I dunno. That sounds like the

Application SPecific Processing goes here

part of your template, though. During each visit, search for/count
adjacent unoccupied (and probably not previously counted) locations; or
check for an eye; or whatever application-specific processing is needed

Good luck.

Alex

M

markspace

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

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.length; j++ ) {
Stone stone = board[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.

{
nextGroup:
for( Group g : groups ) {
for( Stone s : g ) {
if( hasLiberties( s ) ) {
continue nextGroup;
}
}
}
}

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
x=7, y=10}], color=WHITE}
BUILD SUCCESSFUL (total time: 0 seconds)

L

Lew

... [snip] ...
Thanks for your help! But I need to clarify a few things if it is not too much trouble. So what I gather
from your post is that if I am starting off at (x,y) that I need to do a recursive call on (x-1,y) , (x+1,y) ,
(x, y+1) and (x,y-1). So for example:

/ / / / / / /
/ 00*11 /
/ *0000 /
/ 00111 /
/ 11100 /
/ 0010* /
/ / / / / / /

Be careful. The representation is not the model.
Imagine 0's are white and 1's are black and * is an empty space. Also image that the matrix also is a
7x7 and not a 5 by 5 where the above diagram is surrounded by '/' to make sure you don't get an
index out of bounds error. So really my starting place will be (2,2) and I will search (1,2), (3,2) (2,1)
and (2,3). So my idea was to change the 0's and 1's to some other character (but not the same
character) if they are alive (this will tell me I have visited those spots) and dead spots I have visited
will also be changed to a character to know I have visited them. But the problem is if i start at (2,2)
above and mark that first spot dead I still need to come back and change it to alive after I have visited
the spot below it or the spot 2 to the right of it. (Because liveness is contagious with similar colors).
Can you maybe provide some more specific assistance. This is HW and I do not want the answer but I
have been cracking away at this on scratch paper with pictures and diagrams but still am a little
stuck.

Advice #1: Let go of the name of a specific algorithm. If you don't know what "depth" is,
latching onto "depth-first" won't be of much use. Others have suggested a better algorithm.

Instead of imprinting on some magical algorithm label, think about the problem in its raw
structures. What is a 'Board'?

It's a collection of 19 by 19 labeled intersections, yes?

What do "characters" have to do with that model? Think in terms of the problem itself,
and not in terms of predetermined algorithms or representations.

Java has the power to directly express notions like 'Board' and 'Intersection', and the
attributes each type has, like 'Stone stone;', where 'Stone' is a type (hint: enum) with
two values, 'BLACK' and 'WHITE'. (You should know the naming conventions.)

So forget using dumb old characters to mean something other than "character".

There are lots of ways to express collections of things like "rows" and "collections", and
"arrays of rows" and "collections of rows", for example, or even just
"collections/arrays of 'Intersection'".

One 'Intersection' instance can know an awful lot about itself. For example, it can know
the indexes (0 through 18, inclusive) of the row and column of each of its neighbors, as
well as its own.

It can have a type to represent its liveness or connectedness state. For example, a type
'Liveness' (hint: enum) can represent states of 'LIVE', 'DEAD' or 'UNKNOWN'. (You could also
represent 'UNKNOWN' by having 'null' for an instance value of 'Liveness'.)

So please answer to this group with a type design for 'public class Intersection'.

You can use constant variables (not actually a contradiction in Java) to hold things like
board size. So to give you a boost, actually maybe too much, here's the sort of thing I have
in mind (using 'class' instead of 'interface', though the latter could be better):

public class Board
{
public static final int BOARD_SIZE = 19;

final Intersection [] [] intersections = new Intersection [BOARD_SIZE] [BOARD_SIZE];

/**
* Constructor.
*/
public Board()
{
for (int row = 0; row < intersections.length; ++row)
{
for (int column = 0; column < row.length; ++column)
{
intersections [row] [column] = new Intersection();
}
}
}

// etc.
}

Looking forward to your ideas for 'Intersection'.

B

Barb Knox

Lew said:
... [snip] ...
Thanks for your help! But I need to clarify a few things if it is not too
much trouble. So what I gather
from your post is that if I am starting off at (x,y) that I need to do a
recursive call on (x-1,y) , (x+1,y) ,
(x, y+1) and (x,y-1). So for example:

/ / / / / / /
/ 00*11 /
/ *0000 /
/ 00111 /
/ 11100 /
/ 0010* /
/ / / / / / /

Be careful. The representation is not the model.
[SNIP]

Looking forward to your ideas for 'Intersection'.

I heartily endorse all of Lew's points. If you don't understand some
point he makes please ask for clarification. You will lean much more
about being a competent programmer from understanding his points than
from just hacking out some solution to your immediate homework problem.

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum videtur.
| BBB aa a r bbb |
-----------------------------

L

Lew

Alex said:
Meanwhile, it sounds like you'll need to keep track of the adjacent
unoccupied locations you come across as you traverse the group, but I
don't play Go, so I don't know how this information is used to
determine if a group is "alive" or "dead". Markspace suggests that as
long as there is any open adjacent location the group is alive, but
Wikipedia suggests that there needs to be at least two internal "eyes"
to make a group "alive", so I dunno.

You point to the fundamental way to model the game. You mention terms of art
in the domain being modeled, in this case the game of Go, and work to define them
precisely within the model, i.e., to describe their attributes and/or behaviors.
In terms of each other.

If you start out modeling "liveness" as characters, several things go wrong. As your
domain knowledge grows (does "alive" mean "has two or more Eyes in the Group"?)
you add more arbitrary character-to-meaning associations. Now '1' means "has liberty" and '2' means "is alive" and '3' means "is dead", and '4' means "not yet determined" - no wait, couldn't a "group"
both "have a liberty" and be "not yet determined", or "alive", or "dead"? Drat, now I need
'5' to mean "has liberty" and "not yet dead", no wait, "not yet determined", or did I mean "dead"?

So you write types that semantically match the language that you're modeling.

You might give a 'Group' type an attribute 'hasLiberty' (modeled with methods 'hasLiberty()' and
'setLiberty()'). You could give it a separate 'alive' attribute of type 'Boolean', where 'TRUE' means
"alive", 'FALSE' means "dead", and 'null' means "not yet determined". then you can code
logic that makes sense, such as

You won't get lost trying to remember what '2' means.

J

Joshua Cranmer ðŸ§

I am given method signature that takes a square 2D Character Array (a
matrix) that represents a board of a game called Go. The board has
black pieces represented by a 'B' white pieces represented by a 'W'
and empty spaces represented by '.' The board also has a padding to
represent going off the board this padding on all sides is
represented by the character '/'. A piece is considered alive if it
is horizontally or vertically next to an empty space and alive pieces
are contagious to other alive pieces of the same color. Using depth
first search how can I count the number of alive black pieces and
alive white pieces? I only know how to use DFS on a graph data type
not a 2D array.

The algorithm you are looking for is more properly called the "flood
fill" algorithm; the name is derived from the notion that filling the region

Note that a 2-D grid is itself a graph; the adjacency lists are just
implicit in the definition. Consider:

o-o-o-o
| | | |
o-o-o-o
| | | |
o-o-o-o
| | | |
o-o-o-o

[Note that you need fixed-width fonts for the above diagram to make any
sense.]

If that still isn't enough for you, consider that you want to find the
connected components of a graph where edges between differently-colored
nodes are deleted, e.g.:

B-B W-W
| | |
B W-W-W
|
B * B-B
| |
B *-*-*

W

willmann817

I am given method signature that takes a square 2D Character Array (a
matrix) that represents a board of a game called Go. The board has
black pieces represented by a 'B' white pieces represented by a 'W'
and empty spaces represented by '.' The board also has a padding to
represent going off the board this padding on all sides is
represented by the character '/'. A piece is considered alive if it
is horizontally or vertically next to an empty space and alive pieces
are contagious to other alive pieces of the same color. Using depth
first search how can I count the number of alive black pieces and
alive white pieces? I only know how to use DFS on a graph data type
not a 2D array.

The algorithm you are looking for is more properly called the "flood

fill" algorithm; the name is derived from the notion that filling the region

Note that a 2-D grid is itself a graph; the adjacency lists are just

implicit in the definition. Consider:

o-o-o-o

| | | |

o-o-o-o

| | | |

o-o-o-o

| | | |

o-o-o-o

[Note that you need fixed-width fonts for the above diagram to make any

sense.]

If that still isn't enough for you, consider that you want to find the

connected components of a graph where edges between differently-colored

nodes are deleted, e.g.:

B-B W-W

| | |

B W-W-W

|

B * B-B

| |

B *-*-*

--

Beware of bugs in the above code; I have only proved it correct, not

tried it. -- Donald E. Knuth

Joshua, That makes a ton of sense. I appreciate it. Best answer yet!

B

Barb Knox

lipska the kat said:
Lew said:
... [snip] ...
Thanks for your help! But I need to clarify a few things if it is not too
much trouble. So what I gather
from your post is that if I am starting off at (x,y) that I need to do a
recursive call on (x-1,y) , (x+1,y) ,
(x, y+1) and (x,y-1). So for example:

/ / / / / / /
/ 00*11 /
/ *0000 /
/ 00111 /
/ 11100 /
/ 0010* /
/ / / / / / /

Be careful. The representation is not the model.
[SNIP]

Looking forward to your ideas for 'Intersection'.

I heartily endorse all of Lew's points.

Do you?, why?

For the reason I gave: The OP will learn much more about being a
competent programmer from understanding Lew's points than from just
hacking out some solution to the immediate homework problem.
The original statement of requirements is quite clear

Who can say? We are not given the original statement but rather the
OP's paraphrase of it. But I agree that the paraphrase is clear enough.
"I am given method signature that takes a square 2D Character Array (a
matrix) that represents a board of a game called Go"

later

"Using depth first search how can I count the number of alive black
pieces and alive white pieces"

It's all very well suggesting all these ways of doing it differently,
Don't you think that we should be helping to answer the question instead?

Lew did not suggest doing it differently from the given requirements.
However it's done there will need to be some representation additional
to the given array of "B", "W", ".", and "/" characters, to keep track
of which cells have already been visited.

The OP's initial idea for additional representation was to use somew
other character(s) in the character array. Lew's suggestion for
additional representation is (IMO) much better, but plausibly not more
useful for someone who just wants to hack out a passing homework answer.

(In case it's not clear, the given concrete input representation of the
problem would be read and converted into Lew's OO representation.)

It is also plausibly over the OP's head at this stage (assuming it's a
first programming class), but maybe it helps the OP think some useful
thoughts.
It's just a thought.

And a criticism.
I don't know the game of GO so it's difficult to provide a possible
solution, it's got me thinking though

Thinking is good.

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum videtur.
| BBB aa a r bbb |
-----------------------------