Test your Ada skills with our puzzle

2019-06-18

Produced by our software engineer Jack W for the Ada Europe 2019 event, below is a fiendishly tricky Ada code software puzzle.

/Begin Puzzle/

The following Ada code executes a procedure named insert_data with every integer value from 1 to 100. We expect insert_data to execute in approximately constant time, as it inserts elements of type t_packet into a Hashed_Set. Every element contains a different value, and we use CRC32 as part of the hash function.

with Ada.Unchecked_Conversion;
with GNAT.CRC32;
with Interfaces.C;
with Ada.Containers;
with Ada.Containers.Hashed_Sets;

package body puzzle is
  type t_color is (undefined, red, blue);
  type t_packet is record
    color : t_color := undefined;
    value : Natural := 0;
    text : String (1 .. 16);
  end record;

  function get_hash (packet : t_packet) return Ada.Containers.Hash_Type is
    use type Interfaces.C.size_t;
    subtype t_char_array is Interfaces.C.char_array (1 .. (t_packet'Size / 8));
    function to_char_array is new Ada.Unchecked_Conversion (t_packet, t_char_array);

    c : GNAT.CRC32.CRC32;
  begin
    GNAT.CRC32.Initialize (c);
    GNAT.CRC32.Update (c, Interfaces.C.To_Ada (to_char_array (packet)));
    return Ada.Containers.Hash_Type (GNAT.CRC32.Get_Value (c));
  end get_hash;
  package p_seen is new Ada.Containers.Hashed_Sets
    (Element_Type => t_packet, Hash => get_hash, Equivalent_Elements => "=");

  seen : p_seen.Set;

  procedure insert_data (value : Natural) is
    packet : t_packet;
  begin
    packet.value := value;
    packet.color := red;
    packet.text := " ada europe 2019";
    seen.Insert (packet);

    packet.value := value;
    packet.color := blue;
    packet.text := " rapita systems ";
    seen.Insert (packet);
  end insert_data;

  procedure run_test is
  begin
    seen.Reserve_Capacity (1000);
    for i in 1 .. 100 loop
      insert_data (i);
    end loop;
  end run_test;

end puzzle;