Ada95 Help 2D arrays

Ada95 Help 2D arrays

[Will]

I really need help with the problem below... any ideas?  I was thinking about passing each row and column into their own arrays or something but I am not even sure how to go about doing that.  Please send me your ideas if you can help.  Thanks again,

willmann817


Many people across America participate in Superbowl pools. Your pool is run a little differently from most. Instead of buying individual squares from a grid, you purchase a row and a column. After painstaking research, you have assigned an integer score to each square representing the probability of that event occurring. You want to buy the row and column with the maximum combined score, calculated by adding all the individual scores in that row and column.

For example, consider the following grid:

   10 20 30 40

   20 30 20 20

   30 20 10 10

   40 20 10 40


Your best option is to choose the first row and the first column, giving you a combined score of 190.


Write a function Best_Combined_Score(Grid) that takes an Int_Matrix and returns the maximum combined score, as described above. You can assume that the grid is square, and that it contains only positive integers.

Re: Ada95 Help 2D arrays

[Niklas Holsti]

On 12-04-20 14:46 , Will wrote:
> I really need help with the problem below... any ideas?  I was
> thinking about passing each row and column into their own arrays or
> something but I am not even sure how to go about doing that.

Before trying to write the solution in Ada, perhaps you should write 
down the algorithm in English, and show it here on the newsgroup. We can 
then suggest how to express it in Ada.

> Many people across America participate in Superbowl pools. Your pool
> is run a little differently from most. Instead of buying individual
> squares from a grid, you purchase a row and a column. After
> painstaking research, you have assigned an integer score to each
> square representing the probability of that event occurring. You want
> to buy the row and column with the maximum combined score, calculated
> by adding all the individual scores in that row and column.

It is not clearly said here, but it seems that the element at the 
intersection of the row and column should be counted only *once* in the 
combined score of this (row,column) combination. Otherwise, you could 
pick the best row and the best column independently of each other.

> Write a function Best_Combined_Score(Grid) that takes an Int_Matrix

Is the type Int_Matrix already defined somewhere? That would be a 
starting point.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Ada95 Help 2D arrays

[Will]

You are

On Friday, April 20, 2012 7:46:35 AM UTC-4, Will wrote:
> I really need help with the problem below... any ideas?  I was thinking about passing each row and column into their own arrays or something but I am not even sure how to go about doing that.  Please send me your ideas if you can help.  Thanks again,
> 
> willmann817
> 
> 
> Many people across America participate in Superbowl pools. Your pool is run a little differently from most. Instead of buying individual squares from a grid, you purchase a row and a column. After painstaking research, you have assigned an integer score to each square representing the probability of that event occurring. You want to buy the row and column with the maximum combined score, calculated by adding all the individual scores in that row and column.
> 
> For example, consider the following grid:
> 
>    10 20 30 40
> 
>    20 30 20 20
> 
>    30 20 10 10
> 
>    40 20 10 40
> 
> 
> Your best option is to choose the first row and the first column, giving you a combined score of 190.
> 
> 
> Write a function Best_Combined_Score(Grid) that takes an Int_Matrix and returns the maximum combined score, as described above. You can assume that the grid is square, and that it contains only positive integers.

You are correct about Int_Matrix being defined already in another body and spec file. And the intersection should only be counted once as you said.  I will see what I can do about the algorithm.  Thanks a bunch

-willmann817

Re: Ada95 Help 2D arrays

[Will]

Here is my solution and no doubt it does work!  

type Int_Array is array(Positive range <>) of Integer;
   type Int_Matrix is array(Positive range <>, Positive range <>) of Integer;
	

   function Best_Combined_Score(Grid : Int_Matrix) return Integer is  
   Total : integer := 0;
	RowTotal : integer := 0;
	ColumnTotal : integer :=0;
	Sum : Integer := 0;
	begin	 
	
	   
	
	for R in Grid'Range(1)loop
	RowTotal := 0;
		for C in Grid'Range(2) loop
			Rowtotal := Rowtotal +Grid(R,C);
		end loop;
		
	for Column in Grid'Range(2) loop
	ColumnTotal := 0;
		for Row in Grid'Range(1)loop
	 	ColumnTotal := ColumnTotal + Grid(Row,Column);      
	   end loop;                                          
		                                                 		
	Total := RowTotal + ColumnTotal - Grid(R, Column);
		
		if Total > Sum then 
		 Sum := Total;
		end if;
		
		end loop;
		end loop;
		
		
     return Sum;
   end Best_Combined_Score;

Re: Ada95 Help 2D arrays

[Niklas Holsti]

On 12-04-20 20:33 , Will wrote:
> Here is my solution and no doubt it does work!

Looks pretty good to me. I have taken the liberty of cleaning up the 
formatting a bit, replacing the TABs with spaces. I have added some remarks.

> type Int_Array is array(Positive range<>) of Integer;
> type Int_Matrix is array(Positive range<>, Positive range<>) of Integer;
>
>
> function Best_Combined_Score(Grid : Int_Matrix) return Integer is

The problem statement said that the numbers in the Grid are positive 
integers. I would therefore use the type Natural instead of Integer for 
the function return type and the local variables.

>    Total       : integer := 0;
>    RowTotal    : integer := 0;
>    ColumnTotal : integer := 0;

The initializations of Total, RowTotal, and ColumnTotal are unnecessary: 
the variables are initialized below before being used.

>    Sum         : Integer := 0;
> begin	
> 	
>    for R in Grid'Range(1) loop

IMO it would be more balanced to call this (outermost) row index "Row", 
since it plays the same role as the "Column" index below, and use the 
identifier "R" in the inner loop over row indices.

>       RowTotal := 0;
>       for C in Grid'Range(2) loop
>          Rowtotal := Rowtotal +Grid(R,C);
>       end loop;
>
>       for Column in Grid'Range(2) loop
>          ColumnTotal := 0;
>          for Row in Grid'Range(1)loop
>             ColumnTotal := ColumnTotal + Grid(Row,Column);
>          end loop;
> 		                                                 		
>          Total := RowTotal + ColumnTotal - Grid(R, Column);
>
>          if Total > Sum then
>             Sum := Total;
>          end if;
>
>       end loop;
>    end loop;
> 		
>    return Sum;
> end Best_Combined_Score;

I think it works. But it is a cubic-complexity algorithm (loops nested 
three deep). A quadratic-complexity algorithm (loops nested two deep) 
would be more efficient for large grids. Of course, premature 
optimization is the root of much evil, but the quadratic algorithm is 
not much more difficult and demonstrates some nice aspects of local 
array variables in Ada.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .