* Ada95 Help 2D arrays
@ 2012-04-20 11:46 Will
2012-04-20 16:27 ` Niklas Holsti
` (2 more replies)
0 siblings, 3 replies; 5+ messages in thread
From: Will @ 2012-04-20 11:46 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Ada95 Help 2D arrays
2012-04-20 11:46 Ada95 Help 2D arrays Will
@ 2012-04-20 16:27 ` Niklas Holsti
2012-04-20 16:55 ` Will
2012-04-20 17:33 ` Will
2 siblings, 0 replies; 5+ messages in thread
From: Niklas Holsti @ 2012-04-20 16:27 UTC (permalink / raw)
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
. @ .
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Ada95 Help 2D arrays
2012-04-20 11:46 Ada95 Help 2D arrays Will
2012-04-20 16:27 ` Niklas Holsti
@ 2012-04-20 16:55 ` Will
2012-04-20 17:33 ` Will
2 siblings, 0 replies; 5+ messages in thread
From: Will @ 2012-04-20 16:55 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Ada95 Help 2D arrays
2012-04-20 11:46 Ada95 Help 2D arrays Will
2012-04-20 16:27 ` Niklas Holsti
2012-04-20 16:55 ` Will
@ 2012-04-20 17:33 ` Will
2012-04-20 18:12 ` Niklas Holsti
2 siblings, 1 reply; 5+ messages in thread
From: Will @ 2012-04-20 17:33 UTC (permalink / raw)
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;
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Ada95 Help 2D arrays
2012-04-20 17:33 ` Will
@ 2012-04-20 18:12 ` Niklas Holsti
0 siblings, 0 replies; 5+ messages in thread
From: Niklas Holsti @ 2012-04-20 18:12 UTC (permalink / raw)
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
. @ .
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2012-04-20 18:12 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-04-20 11:46 Ada95 Help 2D arrays Will
2012-04-20 16:27 ` Niklas Holsti
2012-04-20 16:55 ` Will
2012-04-20 17:33 ` Will
2012-04-20 18:12 ` Niklas Holsti
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox