Anonymous user
Maximum triangle path sum: Difference between revisions
Added Ada version
(Added racket implementation) |
(Added Ada version) |
||
Line 34:
This task is derived from the [http://projecteuler.net/problem=18 Euler Problem #18].
=={{header|Ada}}==
<lang ada>with Ada.Text_Io; use Ada.Text_Io;
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;
with Ada.Containers.Vectors;
procedure Max_Sum is
package Integer_Vectors is new Ada.Containers.Vectors
(Positive, Integer);
Triangle : Integer_Vectors.Vector;
Data : String :=
" 55"&
" 94 48"&
" 95 30 96"&
" 77 71 26 67"&
" 97 13 76 38 45"&
" 07 36 79 16 37 68"&
" 48 07 09 18 70 26 06"&
" 18 72 79 46 59 79 29 90"&
" 20 76 87 11 32 07 07 49 18"&
" 27 83 58 35 71 11 25 57 29 85"&
" 14 64 36 96 27 11 58 56 92 18 55"&
" 02 90 03 60 48 49 41 46 33 36 47 23"&
" 92 50 48 02 36 59 42 79 72 20 82 77 42"&
" 56 78 38 80 39 75 02 71 66 66 01 03 55 72"&
" 44 25 67 84 71 67 11 61 40 57 58 89 40 56 36"&
" 85 32 25 85 57 48 84 35 47 62 17 01 01 99 89 52"&
" 06 71 28 75 94 48 37 10 23 51 06 48 53 18 74 98 15"&
" 27 02 92 23 08 71 76 84 15 52 92 63 81 10 44 10 69 93";
Num : Integer;
Last : Integer;
Index : Positive;
Tn : Integer := 1;
begin
Index := Data'First;
while Index < Data'Last loop
Get(Data(Index..Data'Last), Num, Last);
Triangle.Append(Num);
Index := Last+1;
end loop;
Last := Integer(Triangle.Length);
while (Tn * (Tn + 1) / 2) < Last loop
Tn := Tn + 1;
end loop;
for N in reverse 2 .. Tn loop
for I in 2 .. N loop
Triangle.Replace_Element
(Last - N, Triangle.Element(Last -N) +
Integer'Max(Triangle.Element(Last-1), Triangle.Element(Last)));
Last := Last - 1;
end loop;
Last := Last - 1;
end loop;
Put_Line(Integer'Image(Triangle.Element(1)));
end Max_Sum;
</lang>
Output:
<pre> 1320
</pre>
=={{header|D}}==
<lang d>void main() {
| |||