13.md

This solution for Part II requires 128 bits integers to implement (A * B mod N), where A, B and N are 64-bits integers. It works on GCC 11 or GNAT Pro 21. Both of them are not awailable for Jupyter notebook for now. It works only for prime numbers for bus id. For datails you may look at The Art of Computer Programming 4.3.2. Modular Arithmetic and Euler's totient function for a prime power argument.

with Ada.Text_IO;
with Ada.Long_Integer_Text_IO;
with Ada.Strings.Fixed;
with Ada.Strings.Maps;
with Ada.Containers.Vectors;

procedure Main is

   type Bus is record
      Id     : Long_Integer;
      Offset : Long_Integer;
   end record;

   package Bus_Vectors is new Ada.Containers.Vectors (Positive, Bus);

   Comma : Ada.Strings.Maps.Character_Set :=
     Ada.Strings.Maps.To_Set (",");
   Input     : Ada.Text_IO.File_Type;
   Vector    : Bus_Vectors.Vector;
begin
   Ada.Text_IO.Open (Input, Ada.Text_IO.In_File, "/home/jovyan/md/13/input");

   declare
      Ignore : String := Ada.Text_IO.Get_Line (Input);
   begin
      null;
   end;

   declare
      Offset  : Long_Integer := 0;
      Schedule  : String := Ada.Text_IO.Get_Line (Input);
      First, Last : Natural := 0;
   begin
      while Last < Schedule'Last loop
         Ada.Strings.Fixed.Find_Token
           (Source => Schedule,
            Set    => Comma,
            From   => Last + 1,
            Test   => Ada.Strings.Outside,
            First  => First,
            Last   => Last);

         exit when First > Last;

         if Schedule (First .. Last) /= "x" then
            declare
               Bus_Id : Long_Integer;
            begin
               Ada.Long_Integer_Text_IO.Get
                 (From => Schedule (First .. Last),
                  Item => Bus_Id,
                  Last => First);
               Vector.Append ((Bus_Id, Offset));
            end;
         end if;
         Offset := Offset + 1;
      end loop;
   end;

   declare
      function Power_Mod (M, D, N : Long_Integer) return Long_Integer is
      --  A function to calculate (M ** D) mod N;

         function Is_Odd (X : Long_Integer) return Boolean is
           (X mod 2 /= 0);

         function Mult_Mod (A, B, N : Long_Integer) return Long_Integer is
            --  A function to calculate (M * D) mod N;
            type Int_128 is mod 2**128;
            AX : Int_128 := Int_128 (A);
            BX : Int_128 := Int_128 (B);
            NX : Int_128 := Int_128 (N);
         begin
            return Long_Integer ((AX * BX) mod NX);
         end Mult_Mod;

         Result : Long_Integer := 1;
         Exp    : Long_Integer := D;
         Mult   : Long_Integer := M mod N;
      begin
         while Exp /= 0 loop
            --  Loop invariant is Power_Mod'Result = Result * Mult**Exp mod N
            if Is_Odd (Exp) then
               Result := Mult_Mod (Result, Mult, N);
            end if;

            Mult := Mult_Mod (Mult, Mult, N);
            Exp := Exp / 2;
         end loop;

         return Result;
      end Power_Mod;

      M : Long_Integer := 1;
      S : Long_Integer := 0;
   begin
      for X of Vector loop
         M := M * X.Id;
      end loop;

      for X of Vector loop
         if X.Offset /= 0 then
            S := S + (X.Id - X.Offset) * Power_Mod (M / X.Id, X.Id - 1, M);
            S := S mod M;
         end if;
      end loop;

      Ada.Long_Integer_Text_IO.Put (S);
   end;
end Main;

---

Back to Table of Contents