09.md

Day 9

Firstly, we need some standard packages to read the text file and a vector to keep state of calculation.

with Ada.Text_IO;
with Ada.Long_Integer_Text_IO;
with Ada.Containers.Vectors;

Let's solve Part II. Here is result of Part I:

Part_I_Result : constant Long_Integer := 552655238;

My idea is to keep result of partial sum calculation in a record. I keep Min, Max and rest of the sum.

type Partial_Sum is record
   Min, Max : Long_Integer;
   Left : Long_Integer;
end record;

On each new number I will calculate several Partial_Sum in parallel. Let's keep sums in a vector.

package Partial_Sum_Vectors is new Ada.Containers.Vectors (Positive, Partial_Sum);

On each new number Next, I will call a procedure to update each parial sum in the vector. If a partial sum exceed the target, it will be removed. If the procedure found a target, then it will return Max + Min in Found argument.

procedure Update_Sums
  (Sums  : in out Partial_Sum_Vectors.Vector;
   Next  : Long_Integer;
   Found : out Long_Integer);
--  Update Sums with new value. Return Found = Min+Max or zero if not found.

procedure Update_Sums
  (Sums  : in out Partial_Sum_Vectors.Vector;
   Next  : Long_Integer;
   Found : out Long_Integer)
is
   Index : Positive := Sums.First_Index;
begin
   Found := 0;
      
   while Index <= Sums.Last_Index loop
      if Sums (Index).Left < Next then
         --  Move to the end of vector and shrink it.
         Sums.Swap (Index, Sums.Last_Index);
         Sums.Delete_Last;
      else
         declare
            Item : Partial_Sum renames Sums (Index);
         begin
            Item.Left := Item.Left - Next;
            Item.Min := Long_Integer'Min (Item.Min, Next);
            Item.Max := Long_Integer'Max (Item.Max, Next);
               
            if Item.Left = 0 then
               Found := Item.Min + Item.Max;
               exit;
            end if;
               
            Index := Index + 1;
         end;
      end if;
   end loop;
end Update_Sums;

To create new item in the vector I need two numbers. That's why I keep previous value in Prev. The Input if an input file.

Sums  : Partial_Sum_Vectors.Vector;
Prev  : Long_Integer;
Input : Ada.Text_IO.File_Type;

Let's do initialization: open the file and read the first number into Prev.

Ada.Text_IO.Open (Input, Ada.Text_IO.In_File, "/home/jovyan/md/09/input");
Ada.Long_Integer_Text_IO.Get (Input, Prev);

Now loop over the rest of numbers.

while not Ada.Text_IO.End_Of_File (Input) loop
   declare
      Next  : Long_Integer;
      Found : Long_Integer;
   begin
      Ada.Long_Integer_Text_IO.Get (Input, Next);

      Update_Sums (Sums, Next, Found);
         
      if Found > 0 then
         Ada.Long_Integer_Text_IO.Put (Found);
         exit;
      elsif Prev + Next < Part_I_Result then
         Sums.Append
           ((Min => Long_Integer'Min (Prev, Next),
             Max => Long_Integer'Max (Prev, Next),
             Left => Part_I_Result - Prev - Next));
      end if;
         
      Prev := Next;
   end;
end loop;

            70672245

Well, the maximum vector length over the run was 482 items.

---

Back to Table of Contents