Depth First Search of a Char_Matrix?

Depth First Search of a Char_Matrix?

[Alex]

Below is Char_Matrix representation of the board game "Go".  A 'W' represents a white piece, a 'B' represents a black piece, and a '.' represents a empty space.  Each black or white piece can either be alive or dead.  A piece is Alive is if it horizontally or vertically next to a '.' OR if it is horizontally or vertically next to another piece that is alive. You can think of aliveness as being contagious.  How can I use depth first search to count the number of alive black pieces and alive white pieces?  

WW.BB
.WWWW
WWBBB
BBBWW
WWBW.


In this example there are 11 alive white piece and 2 alive black pieces.

Can anyone provide any insight into this problem?

Re: Depth First Search of a Char_Matrix?

[Shark8]

On Saturday, April 27, 2013 8:09:10 AM UTC-6, Alex wrote:
> Below is Char_Matrix representation of the board game "Go".  A 'W' represents a white piece, a 'B' represents a black piece, and a '.' represents a empty space.  Each black or white piece can either be alive or dead.  A piece is Alive is if it horizontally or vertically next to a '.' OR if it is horizontally or vertically next to another piece that is alive. You can think of aliveness as being contagious.  How can I use depth first search to count the number of alive black pieces and alive white pieces?  
> 
> 
> WW.BB
> .WWWW
> WWBBB
> BBBWW
> WWBW.
> 
> 
> In this example there are 11 alive white piece and 2 alive black pieces.
> 
> Can anyone provide any insight into this problem?

According to your definition though all of the pieces should be alive; you forgot to add in the condition that the alive piece next to them has to be the same color to transmit 'alive'.

Anyway, here's the basic layout for a DFS function on determining if they're alive... the solution is simple, instead of merely returning a boolean you want to increment a counter. Note that this is coded as you said about alive being transmitted via another alive piece sou you'll have to add that logic in, too. 
    
    Type Piece_Color is (Black, White);
    Type Piece is record
	Color : Piece_Color;
    end record;
    
    SubType Board_Range is Positive Range 1..5;
    Type Board_Type is Array(Board_Range,Board_Range) of Access Piece;

    Board : Board_Type:= (others => (others => Null));
    
    Function Is_Alive(	Board	: Board_Type;
			X, Y	: Board_Range
		      ) return Boolean is
	Use Type System.Address;
	Package Address_List_Package is New Ada.Containers.Indefinite_Vectors(
		Index_Type	=> Positive,
		Element_Type	=> System.Address);

	Address_List : Address_List_Package.Vector;
	Function Recursion(X,Y : Board_Range) Return Boolean is
	begin
	    if Board(X,Y) = null then
		Return True;
	    elsif Address_List.Contains( Board(x,Y)'Address ) then
		Return False;
	    else
		Address_List.Append( Board(X,Y).all'Address );
		Return Result : Boolean := False do
		    declare
			xs : Array (1..2) of Natural:= (x - 1, x + 1);
			ys : Array (1..2) of Natural:= (y - 1, y + 1);
		    begin
			for index_1 of ys loop
			    for index_2 of xs loop
				if index_1 in Board_Range and index_2 in Board_Range then
				    Result:= Recursion(index_2, index_1);
				end if;
				if Result then Return; end if;
			    end loop;
			end loop;
		    end;
		end return;
	    end if;
	end Recursion;
	  
    begin
	Return Recursion(x,y);
    End Is_Alive;

Re: Depth First Search of a Char_Matrix?

[Jeffrey Carter]

On 04/27/2013 08:35 AM, Shark8 wrote:
>
>      SubType Board_Range is Positive Range 1..5;
>      Type Board_Type is Array(Board_Range,Board_Range) of Access Piece;
>
>      Board : Board_Type:= (others => (others => Null));
>
>      Function Is_Alive(	Board	: Board_Type;
> 			X, Y	: Board_Range
> 		      ) return Boolean is
> 	Use Type System.Address;
> 	Package Address_List_Package is New Ada.Containers.Indefinite_Vectors(
> 		Index_Type	=> Positive,
> 		Element_Type	=> System.Address);

There is absolutely no reason to use access types (especially not anonymous 
access types) or addresses for this problem.

-- 
Jeff Carter
"Sheriff murdered, crops burned, stores looted,
people stampeded, and cattle raped."
Blazing Saddles
35

Re: Depth First Search of a Char_Matrix?

[Shark8]

On Saturday, April 27, 2013 11:25:57 AM UTC-6, Jeffrey Carter wrote:
> 
> There is absolutely no reason to use access types (especially not anonymous 
> access types) or addresses for this problem.

Sure, but there's no real reason not to: the illustration was simply a DFS on something that might-not-exist and so null/some-object map to that perfectly fine. (It's an error to ask "what color is the piece at X,Y?" when the element X,Y contains no piece; this situation must be addressed somewhere, and access/null works.)

Re: Depth First Search of a Char_Matrix?

[Dmitry A. Kazakov]

On Sat, 27 Apr 2013 11:16:34 -0700 (PDT), Shark8 wrote:

> On Saturday, April 27, 2013 11:25:57 AM UTC-6, Jeffrey Carter wrote:
>> 
>> There is absolutely no reason to use access types (especially not anonymous 
>> access types) or addresses for this problem.
> 
> Sure, but there's no real reason not to: the illustration was simply a DFS
> on something that might-not-exist and so null/some-object map to that
> perfectly fine.

No, you don't place a key into the map if there is no value for it.

> It's an error to ask "what color is the piece at X,Y?" when the element
> X,Y contains no piece;

Likely

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Depth First Search of a Char_Matrix?

[Shark8]

On Saturday, April 27, 2013 12:48:09 PM UTC-6, Dmitry A. Kazakov wrote:
> On Sat, 27 Apr 2013 11:16:34 -0700 (PDT), Shark8 wrote:
> 
> > On Saturday, April 27, 2013 11:25:57 AM UTC-6, Jeffrey Carter wrote:
> >> 
> >> There is absolutely no reason to use access types (especially not anonymous 
> >> access types) or addresses for this problem.
> > 
> > Sure, but there's no real reason not to: the illustration was simply a DFS
> > on something that might-not-exist and so null/some-object map to that
> > perfectly fine.
> 
> 
> No, you don't place a key into the map if there is no value for it.

And I don't -- as the algorithm shows, the only place that a new address is placed into the list is when it's been visited for the first time, this is after the cases of a null board-space and an already-visited node have been checked (which return out of the function).

{i.e. it's a list of already-visited nodes, so that the recursion is not infinite.}

> > It's an error to ask "what color is the piece at X,Y?" when the element
> > X,Y contains no piece;
> 
> Likely

Re: Depth First Search of a Char_Matrix?

[Dmitry A. Kazakov]

On Sat, 27 Apr 2013 11:58:57 -0700 (PDT), Shark8 wrote:

> On Saturday, April 27, 2013 12:48:09 PM UTC-6, Dmitry A. Kazakov wrote:
>> On Sat, 27 Apr 2013 11:16:34 -0700 (PDT), Shark8 wrote:
>> 
>>> On Saturday, April 27, 2013 11:25:57 AM UTC-6, Jeffrey Carter wrote:
>>>> 
>>>> There is absolutely no reason to use access types (especially not anonymous 
>>>> access types) or addresses for this problem.
>>> 
>>> Sure, but there's no real reason not to: the illustration was simply a DFS
>>> on something that might-not-exist and so null/some-object map to that
>>> perfectly fine.
>> 
>> No, you don't place a key into the map if there is no value for it.
> 
> And I don't

In which case it is never null => it need not to be an address.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Depth First Search of a Char_Matrix?

[Simon Wright]

Shark8 <onewingedshark@gmail.com> writes:

> On Saturday, April 27, 2013 11:25:57 AM UTC-6, Jeffrey Carter wrote:
>> 
>> There is absolutely no reason to use access types (especially not
>> anonymous access types) or addresses for this problem.
>
> Sure, but there's no real reason not to: the illustration was simply a
> DFS on something that might-not-exist and so null/some-object map to
> that perfectly fine. (It's an error to ask "what color is the piece at
> X,Y?" when the element X,Y contains no piece; this situation must be
> addressed somewhere, and access/null works.)

As a general rule of thumb it is a bad idea to use access types unless
you Absolutely Have To.

To solve this problem, a discriminated record would have done just fine:

   type Cell (Occupied : Boolean := False) is record
      case Occupied is
         when True =>
            Piece : Piece_Colour;
            Alive : Boolean;
         when False =>
            null;
      end case;
   end record;

And anonymous access types are worse, see the recent problems with
anonymous task access types.

Re: Depth First Search of a Char_Matrix?

[Shark8]

On Saturday, April 27, 2013 1:31:49 PM UTC-6, Simon Wright wrote:
> Shark8 writes:
> 
> > On Saturday, April 27, 2013 11:25:57 AM UTC-6, Jeffrey Carter wrote:
> >> 
> >> There is absolutely no reason to use access types (especially not
> >> anonymous access types) or addresses for this problem.
> >
> > Sure, but there's no real reason not to: the illustration was simply a
> > DFS on something that might-not-exist and so null/some-object map to
> > that perfectly fine. (It's an error to ask "what color is the piece at
> > X,Y?" when the element X,Y contains no piece; this situation must be
> > addressed somewhere, and access/null works.)
> 
> As a general rule of thumb it is a bad idea to use access types unless
> you Absolutely Have To.
> 
> To solve this problem, a discriminated record would have done just fine:
> 
>    type Cell (Occupied : Boolean := False) is record
>       case Occupied is
>          when True =>
>             Piece : Piece_Colour;
>             Alive : Boolean;
>          when False =>
>             null;
>       end case;
>    end record;

Doh! So obvious.

> 
> And anonymous access types are worse, see the recent problems with
> anonymous task access types.

I know; I was the one who started that thread -- and that's why I've been spending my recent time thinking about access types (which probably explains why that was what popped into my head first).

Re: Depth First Search of a Char_Matrix?

[Jeffrey Carter]

On 04/27/2013 11:16 AM, Shark8 wrote:
> On Saturday, April 27, 2013 11:25:57 AM UTC-6, Jeffrey Carter wrote:
>>
>> There is absolutely no reason to use access types (especially not
>> anonymous access types) or addresses for this problem.
>
> Sure, but there's no real reason not to: the illustration was simply a DFS on
> something that might-not-exist and so null/some-object map to that perfectly
> fine. (It's an error to ask "what color is the piece at X,Y?" when the
> element X,Y contains no piece; this situation must be addressed somewhere,
> and access/null works.)

Yes, there are very good reasons not to.

Zero/non-zero map to that perfectly fine, too, and don't carry with them all the
opportunities of error that the manual memory management of access types do. But
the fact is, this is a Boolean value and should be modeled as such.

To the OP:

Good Ada code never contains visible access types, nor non-visible access types
that aren't absolutely essential.

Addresses should never appear in code that doesn't absolutely have to be
non-portable.

-- 
Jeff Carter
"Sheriff murdered, crops burned, stores looted,
people stampeded, and cattle raped."
Blazing Saddles
35

Re: Depth First Search of a Char_Matrix?

[Alex]

On Saturday, April 27, 2013 10:09:10 AM UTC-4, Alex wrote:
> Below is Char_Matrix representation of the board game "Go".  A 'W' represents a white piece, a 'B' represents a black piece, and a '.' represents a empty space.  Each black or white piece can either be alive or dead.  A piece is Alive is if it horizontally or vertically next to a '.' OR if it is horizontally or vertically next to another piece that is alive. You can think of aliveness as being contagious.  How can I use depth first search to count the number of alive black pieces and alive white pieces?  
> 
> 
> 
> WW.BB
> 
> .WWWW
> 
> WWBBB
> 
> BBBWW
> 
> WWBW.
> 
> 
> 
> 
> 
> In this example there are 11 alive white piece and 2 alive black pieces.
> 
> 
> 
> Can anyone provide any insight into this problem?

Shark you are correct,  I forgot to include the fact that only like colors are contagious.  Thank you very much for your assistance.  Without providing the code how would I change it to reflect this piece of missing logic?

Re: Depth First Search of a Char_Matrix?

[Shark8]

On Saturday, April 27, 2013 10:27:23 AM UTC-6, Alex wrote:
> On Saturday, April 27, 2013 10:09:10 AM UTC-4, Alex wrote:
> 
> > Below is Char_Matrix representation of the board game "Go".  A 'W' represents a white piece, a 'B' represents a black piece, and a '.' represents a empty space.  Each black or white piece can either be alive or dead.  A piece is Alive is if it horizontally or vertically next to a '.' OR if it is horizontally or vertically next to another piece that is alive. You can think of aliveness as being contagious.  How can I use depth first search to count the number of alive black pieces and alive white pieces?  
> 
> > 
> 
> > 
> 
> > 
> 
> > WW.BB
> 
> > 
> 
> > .WWWW
> 
> > 
> 
> > WWBBB
> 
> > 
> 
> > BBBWW
> 
> > 
> 
> > WWBW.
> 
> > 
> 
> > 
> 
> > 
> 
> > 
> 
> > 
> 
> > In this example there are 11 alive white piece and 2 alive black pieces.
> 
> > 
> 
> > 
> 
> > 
> 
> > Can anyone provide any insight into this problem?
> 
> 
> 
> Shark you are correct,  I forgot to include the fact that only like colors are contagious.  Thank you very much for your assistance.  Without providing the code how would I change it to reflect this piece of missing logic?

Simple:
1 )  Add a local variable indicating the color to Is_Alive, that will be accessable to its nested functions.
2 )  After checking for null on (x,y) assign that to the variable before calling recursion.

You could also make that variable a constant and use a conditional expression [in Ada 2012] to set the initial value -- something like:
Color : Constant Piece_Color:= (if board(x,y) /= null then board(x,y).color else white); -- DEFAULT to white on NULL, otherwise set to the initial piece's color.

Re: Depth First Search of a Char_Matrix?

[Alex]

On Saturday, April 27, 2013 12:34:55 PM UTC-4, Shark8 wrote:
> On Saturday, April 27, 2013 10:27:23 AM UTC-6, Alex wrote:
> 
> > On Saturday, April 27, 2013 10:09:10 AM UTC-4, Alex wrote:
> 
> > 
> 
> > > Below is Char_Matrix representation of the board game "Go".  A 'W' represents a white piece, a 'B' represents a black piece, and a '.' represents a empty space.  Each black or white piece can either be alive or dead.  A piece is Alive is if it horizontally or vertically next to a '.' OR if it is horizontally or vertically next to another piece that is alive. You can think of aliveness as being contagious.  How can I use depth first search to count the number of alive black pieces and alive white pieces?  
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > WW.BB
> 
> > 
> 
> > > 
> 
> > 
> 
> > > .WWWW
> 
> > 
> 
> > > 
> 
> > 
> 
> > > WWBBB
> 
> > 
> 
> > > 
> 
> > 
> 
> > > BBBWW
> 
> > 
> 
> > > 
> 
> > 
> 
> > > WWBW.
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > In this example there are 11 alive white piece and 2 alive black pieces.
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > Can anyone provide any insight into this problem?
> 
> > 
> 
> > 
> 
> > 
> 
> > Shark you are correct,  I forgot to include the fact that only like colors are contagious.  Thank you very much for your assistance.  Without providing the code how would I change it to reflect this piece of missing logic?
> 
> 
> 
> Simple:
> 
> 1 )  Add a local variable indicating the color to Is_Alive, that will be accessable to its nested functions.
> 
> 2 )  After checking for null on (x,y) assign that to the variable before calling recursion.
> 
> 
> 
> You could also make that variable a constant and use a conditional expression [in Ada 2012] to set the initial value -- something like:
> 
> Color : Constant Piece_Color:= (if board(x,y) /= null then board(x,y).color else white); -- DEFAULT to white on NULL, otherwise set to the initial piece's color.

Thanks! So I am given the function signature, not really a function body that looks like this

   function Count_Alive(Board : Char_Matrix) return Integer is
 	M : Char_Matrix := Board;  
	begin
      return -999;
   end Count_Alive;


So I understand much of your logic, but I am given a matrix of characters defined as such:

type Char_Matrix is array(Positive range <>, Positive range <>) of Character;

So could you give me like an algorithm in words on what I need to do instead of giving me the answer in code?

Re: Depth First Search of a Char_Matrix?

[Alex]

On Saturday, April 27, 2013 12:51:44 PM UTC-4, Alex wrote:
> On Saturday, April 27, 2013 12:34:55 PM UTC-4, Shark8 wrote:
> 
> > On Saturday, April 27, 2013 10:27:23 AM UTC-6, Alex wrote:
> 
> > 
> 
> > > On Saturday, April 27, 2013 10:09:10 AM UTC-4, Alex wrote:
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > Below is Char_Matrix representation of the board game "Go".  A 'W' represents a white piece, a 'B' represents a black piece, and a '.' represents a empty space.  Each black or white piece can either be alive or dead.  A piece is Alive is if it horizontally or vertically next to a '.' OR if it is horizontally or vertically next to another piece that is alive. You can think of aliveness as being contagious.  How can I use depth first search to count the number of alive black pieces and alive white pieces?  
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > WW.BB
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > .WWWW
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > WWBBB
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > BBBWW
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > WWBW.
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > In this example there are 11 alive white piece and 2 alive black pieces.
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > > Can anyone provide any insight into this problem?
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > 
> 
> > 
> 
> > > Shark you are correct,  I forgot to include the fact that only like colors are contagious.  Thank you very much for your assistance.  Without providing the code how would I change it to reflect this piece of missing logic?
> 
> > 
> 
> > 
> 
> > 
> 
> > Simple:
> 
> > 
> 
> > 1 )  Add a local variable indicating the color to Is_Alive, that will be accessable to its nested functions.
> 
> > 
> 
> > 2 )  After checking for null on (x,y) assign that to the variable before calling recursion.
> 
> > 
> 
> > 
> 
> > 
> 
> > You could also make that variable a constant and use a conditional expression [in Ada 2012] to set the initial value -- something like:
> 
> > 
> 
> > Color : Constant Piece_Color:= (if board(x,y) /= null then board(x,y).color else white); -- DEFAULT to white on NULL, otherwise set to the initial piece's color.
> 
> 
> 
> Thanks! So I am given the function signature, not really a function body that looks like this
> 
> 
> 
>    function Count_Alive(Board : Char_Matrix) return Integer is
> 
>  	M : Char_Matrix := Board;  
> 
> 	begin
> 
>       return -999;
> 
>    end Count_Alive;
> 
> 
> 
> 
> 
> So I understand much of your logic, but I am given a matrix of characters defined as such:
> 
> 
> 
> type Char_Matrix is array(Positive range <>, Positive range <>) of Character;
> 
> 
> 
> So could you give me like an algorithm in words on what I need to do instead of giving me the answer in code?

The characters are just like the original example: either a 'B' a 'W' or a '.'  ('.' is empty space, not null)

Re: Depth First Search of a Char_Matrix?

[Shark8]

On Saturday, April 27, 2013 10:51:44 AM UTC-6, Alex wrote:
> 
> Thanks! So I am given the function signature, not really a function body that looks like this
> 
>    function Count_Alive(Board : Char_Matrix) return Integer is
>  	M : Char_Matrix := Board;  
> 	begin
>       return -999;
>    end Count_Alive;
> 
> 
> So I understand much of your logic, but I am given a matrix of characters defined as such:
> 
> type Char_Matrix is array(Positive range <>, Positive range <>) of Character;
> 
> So could you give me like an algorithm in words on what I need to do instead of giving me the answer in code?

The algorithm is much the same, just substitute a "Piece'(Color=>Black)" for 'B', "Piece'(Color=>White)" for 'W', and the space/'.'/whatever for the null. (Your handling of null and such will have to change, but it's the same idea as in the code already given: there's a board-position that might have a piece, if it does that piece is either black or white and either alive or dead.)

Re: Depth First Search of a Char_Matrix?

[Alex]

On Saturday, April 27, 2013 3:05:30 PM UTC-4, Shark8 wrote:
> On Saturday, April 27, 2013 10:51:44 AM UTC-6, Alex wrote:
> 
> > 
> 
> > Thanks! So I am given the function signature, not really a function body that looks like this
> 
> > 
> 
> >    function Count_Alive(Board : Char_Matrix) return Integer is
> 
> >  	M : Char_Matrix := Board;  
> 
> > 	begin
> 
> >       return -999;
> 
> >    end Count_Alive;
> 
> > 
> 
> > 
> 
> > So I understand much of your logic, but I am given a matrix of characters defined as such:
> 
> > 
> 
> > type Char_Matrix is array(Positive range <>, Positive range <>) of Character;
> 
> > 
> 
> > So could you give me like an algorithm in words on what I need to do instead of giving me the answer in code?
> 
> 
> 
> The algorithm is much the same, just substitute a "Piece'(Color=>Black)" for 'B', "Piece'(Color=>White)" for 'W', and the space/'.'/whatever for the null. (Your handling of null and such will have to change, but it's the same idea as in the code already given: there's a board-position that might have a piece, if it does that piece is either black or white and either alive or dead.)

I am just still a little confused.  I know how to do a DFS if I actually have a Graph Data Type with nodes and edges but I do not have that.  I am given the following

type Char_Matrix is array(Positive range <>, Positive range <>) of Character;

and

   function Count_Alive(Board : Char_Matrix) return Integer is
   begin
      return -999;
   end Count_Alive; 

The Char_Matrix will look something like this:

///////
/WW.BB/
/.WWWW/
/WWBBB/
/BBBWW/
/WWBW./
///////

A '/' is off the board, a 'W' is a white piece, a 'B' is a black piece and a '.' is an empty space on the board.  A piece is alive if it is next to an empty space ('.') or if it is next to an alive piece of the same color. What are the nodes and edges and how do you traverse this using DFS to count the number of Alive pieces and number of Dead pieces?  

Re: Depth First Search of a Char_Matrix?

[Alex]

On Saturday, April 27, 2013 3:05:30 PM UTC-4, Shark8 wrote:
> On Saturday, April 27, 2013 10:51:44 AM UTC-6, Alex wrote:
> 
> > 
> 
> > Thanks! So I am given the function signature, not really a function body that looks like this
> 
> > 
> 
> >    function Count_Alive(Board : Char_Matrix) return Integer is
> 
> >  	M : Char_Matrix := Board;  
> 
> > 	begin
> 
> >       return -999;
> 
> >    end Count_Alive;
> 
> > 
> 
> > 
> 
> > So I understand much of your logic, but I am given a matrix of characters defined as such:
> 
> > 
> 
> > type Char_Matrix is array(Positive range <>, Positive range <>) of Character;
> 
> > 
> 
> > So could you give me like an algorithm in words on what I need to do instead of giving me the answer in code?
> 
> 
> 
> The algorithm is much the same, just substitute a "Piece'(Color=>Black)" for 'B', "Piece'(Color=>White)" for 'W', and the space/'.'/whatever for the null. (Your handling of null and such will have to change, but it's the same idea as in the code already given: there's a board-position that might have a piece, if it does that piece is either black or white and either alive or dead.)

I am just still a little confused.  I know how to do a DFS if I actually have a Graph Data Type with nodes and edges but I do not have that.  I am given the following

type Char_Matrix is array(Positive range <>, Positive range <>) of Character;

and

   function Count_Alive(Board : Char_Matrix) return Integer is
   begin
      return -999;
   end Count_Alive;

The Char_Matrix will look something like this:


WW.BB
.WWWW
WWBBB
BBBWW
WWBW.


I have not depicted it in the picture above but a '/' is off the board and the perimeter of the char_matrix is made up of a bunch of '/', a 'W' is a white piece, a 'B' is a black piece and a '.' is an empty space on the board.  A piece is alive if it is next to an empty space ('.') or if it is next to an alive piece of the same color. What are the nodes and edges and how do you traverse this using DFS to count the number of Alive pieces and number of Dead pieces?  

Re: Depth First Search of a Char_Matrix?

[Shark8]

When you print the array out you have a representation of nodes (and implicitly edges), just displayed in a tabular ASCII format.

Is a very real sense (1,1), (1,2),...,(5,5) are merely addresses/locations of a node, wherein 'B', 'W' and '.'/' ' denote that node's state the edges, then, ar nothing more than the relationship of what is adjacent in the horizontal/vertical.

-------------------------------------------
[Non-DFS method]
You could count the dead pieces as follows:
if there are no empty locations all are dead, otherwise
(1) make two lists of nodes A & B,
(2) add all the empty nodes to A,
(3) for each node of A, add its neighbors to B if they are occupied,
(4) clear A
(5) for each of those nodes in B, add only its neighbors containing a piece of the same color to A
(6) merge A into B
(7) repeat #4/#5/#6 until the sizes B is the same as it was in #4.

At this point the system is stable and you have all the live pieces in your list, anything not in your list is then dead. -- This would be a horrible way to do things on any large sized board because of the reiterations... but it's already given you the secret of how to do it with DFS.

Re: Depth First Search of a Char_Matrix?

[Alex]

On Saturday, April 27, 2013 7:34:51 PM UTC-4, Shark8 wrote:
> When you print the array out you have a representation of nodes (and implicitly edges), just displayed in a tabular ASCII format.
> 
> 
> 
> Is a very real sense (1,1), (1,2),...,(5,5) are merely addresses/locations of a node, wherein 'B', 'W' and '.'/' ' denote that node's state the edges, then, ar nothing more than the relationship of what is adjacent in the horizontal/vertical.
> 
> 
> 
> -------------------------------------------
> 
> [Non-DFS method]
> 
> You could count the dead pieces as follows:
> 
> if there are no empty locations all are dead, otherwise
> 
> (1) make two lists of nodes A & B,
> 
> (2) add all the empty nodes to A,
> 
> (3) for each node of A, add its neighbors to B if they are occupied,
> 
> (4) clear A
> 
> (5) for each of those nodes in B, add only its neighbors containing a piece of the same color to A
> 
> (6) merge A into B
> 
> (7) repeat #4/#5/#6 until the sizes B is the same as it was in #4.
> 
> 
> 
> At this point the system is stable and you have all the live pieces in your list, anything not in your list is then dead. -- This would be a horrible way to do things on any large sized board because of the reiterations... but it's already given you the secret of how to do it with DFS.

Ok that makes a lot more sense and yes that set of steps has provided much more insight into the DFS way to do things.  Thanks!

Re: Depth First Search of a Char_Matrix?

[Alex]

On Saturday, April 27, 2013 7:34:51 PM UTC-4, Shark8 wrote:
> When you print the array out you have a representation of nodes (and implicitly edges), just displayed in a tabular ASCII format.
> 
> 
> 
> Is a very real sense (1,1), (1,2),...,(5,5) are merely addresses/locations of a node, wherein 'B', 'W' and '.'/' ' denote that node's state the edges, then, ar nothing more than the relationship of what is adjacent in the horizontal/vertical.
> 
> 
> 
> -------------------------------------------
> 
> [Non-DFS method]
> 
> You could count the dead pieces as follows:
> 
> if there are no empty locations all are dead, otherwise
> 
> (1) make two lists of nodes A & B,
> 
> (2) add all the empty nodes to A,
> 
> (3) for each node of A, add its neighbors to B if they are occupied,
> 
> (4) clear A
> 
> (5) for each of those nodes in B, add only its neighbors containing a piece of the same color to A
> 
> (6) merge A into B
> 
> (7) repeat #4/#5/#6 until the sizes B is the same as it was in #4.
> 
> 
> 
> At this point the system is stable and you have all the live pieces in your list, anything not in your list is then dead. -- This would be a horrible way to do things on any large sized board because of the reiterations... but it's already given you the secret of how to do it with DFS.

This is what I have so far but I am going out of Bounds and I am not sure why??

   function Count_Alive(Board : Char_Matrix) return Integer is
	M : Char_Matrix := Board; 
	V : Bool_Matrix(2..Board'Length-1, 2..Board'Length-1) := (others => (others => False));	
	WhiteCount, BlackCount : Integer := 0;
		procedure DFS(X,Y:Integer; Char : Character) is
		current : Character:= Char;	
		begin
			Put_Line("X = " & X & " Y = " & Y);
			if V(X,Y) = True or M(X,Y) = '/' or M(X,Y) /= current  then
				null;
			else
				V(X,Y) := True;
				if current = 'W' then
					WhiteCount := WhiteCount + 1;
				end if;
				
				if current = 'B' then
					BlackCount := BlackCount + 1;
				end if;
			end if;
				
				DFS(X,Y-1,current);
				DFS(X+1,Y,current);
				DFS(X-1,Y,current);
				DFS(X,Y+1,current);
				
		end DFS;

	begin
		for R in 2..M'Length(1)-1 loop
			for C in 2..M'Length(2)-1 loop
				if M(R,C) = '.' then
					DFS(R,C-1,'W');
					DFS(R+1,C,'W');
					DFS(R-1,C,'W');
					DFS(R,C+1,'W');
					
					DFS(R,C-1,'B');
					DFS(R+1,C,'B');
					DFS(R-1,C,'B');
					DFS(R,C+1,'B');
				end if;
			end loop;
		end loop;
      return (1000*BlackCount)+WhiteCount;
   end Count_Alive;

Re: Depth First Search of a Char_Matrix?

[Jeffrey Carter]

On 04/29/2013 01:55 PM, Alex wrote:
>
> 	begin
> 		for R in 2..M'Length(1)-1 loop
> 			for C in 2..M'Length(2)-1 loop
> 				if M(R,C) = '.' then
> 					DFS(R,C-1,'W');

If M (2, 2) = '.' then here you call DFS with X => 2 and Y => 1.

 > 		procedure DFS(X,Y:Integer; Char : Character) is
 > 		   current : Character:= Char;	
 > 		begin
 > 			Put_Line("X = " & X & " Y = " & Y);
 > 			if V(X,Y) = True or M(X,Y) = '/' or M(X,Y) /= current  then

And here you index V with (2, 1).

-- 
Jeff Carter
"Sir Robin the not-quite-so-brave-as-Sir-Lancelot,
who had nearly fought the Dragon of Angnor,
who nearly stood up to the vicious Chicken of Bristol,
and who had personally wet himself at the
Battle of Badon Hill."
Monty Python & the Holy Grail
68

Re: Depth First Search of a Char_Matrix?

[AdaMagica]

On Monday, April 29, 2013 10:55:46 PM UTC+2, Alex wrote:
> This is what I have so far but I am going out of Bounds and I am not sure why??

No wonder. This is written in a terrible style.
One character names M, V, which don't tell you anything about the meaning.
Counts as Integer - a count is Natural, or do you have negative numbers of pieces?
Parameters X, Y as Integer, equally bad.

Think about good subtypes for your problem.

Re: Depth First Search of a Char_Matrix?

[AdaMagica]

> WW.BB
> .WWWW
> WWBBB
> BBBWW
> WWBW.

I do not really understand the status of your Go board. This configuration would only be possible after a move of black.
Let's see: This could be the previous config. All pieces are alive. It's blacks turn.

WW.BB
.WWWW
WWBBB
BBBWW
WW.W.
  |
Black places a piece on the last row thus killing the first two white pieces (leading to the config you give), which are then removed.

Thus after black's move, only the liveliness of the white pieces has to be checked. The statement that the black pieces in the last three rows are dead is utter nonsense.