This is a part of my ongoing challenge of solving every Advent of Code puzzle in a different language.

The challenge we're tackling today is available here.

Universal Orbit Map

This task presents us with a fun tree-based challenge. We’re given a list of orbits. Bodies can orbit bodies that also orbit other bodies, much like in the real world. For the first part of the task, we are to find the total number of direct and indirect orbits in our system. This sounds straightforward - let’s gather all orbits into a map and trace their paths back to the root (the universal center of mass).

The Language

We don’t need much to complete the task so we can choose pretty much anything. I’ve decided to use the Ada programming language. Named after Ada Lovelace, Ada is used in many extremely safety-critical systems. While originally built specifically for the US Department of Defense, its users now are in all areas of software development that require extreme care, such as military, aerospace and medical applications. This is out of my alley - although I work in finance, we work in a high-level enough context (JVM) to not worry about buffer overflows and such problems day-to-day.

Ada does many very cool things, none of which we’re going to use in our implementation. I, however, want to take note of some of them here. Ada has first-class support for task-based concurrency. It has built-in support for defining formal contracts on the code (think pre-post conditions). It’s also got a really powerful type system, enabling things like range-checked arithmetic. Ada does not have a garbage collector, but it limits access to dynamic memory. This is done for determinism (garbage collectors are hard to predict).

I’m using the AdaCore GNAT community edition implementation of Ada. The toolchain has a lot of features but is a little bit unwieldy (a common theme for Ada itself), thankfully the gnatmake tool simplifies the whole process.

The Solution: Part 1

As usual, let’s start with the code and then dig in.

with Ada.Text_IO;
with Ada.Command_Line;
with Ada.Strings.Fixed;
with Ada.Strings.Unbounded;
with Ada.Strings.Hash_Case_Insensitive;
with Ada.Strings.Equal_Case_Insensitive;
with Ada.Containers.Indefinite_Hashed_Maps;

procedure Solution_1 is
    package IO renames Ada.Text_IO;
    package Strings renames Ada.Strings;

    package String_Maps is new Ada.Containers.Indefinite_Hashed_Maps
        (Key_Type => String,
         Element_Type => String,
         Hash => Ada.Strings.Hash_Case_Insensitive,
         Equivalent_Keys => Ada.Strings.Equal_Case_Insensitive);

    Center_Of_Mass : aliased constant String := "COM";

    function Parse_Orbits_From_File (Name: String) return String_Maps.Map is
        File: IO.File_Type;
        Orbits: String_Maps.Map;
    begin
        IO.Open (File => File, Mode => IO.In_File, Name => Name);
        While not IO.End_Of_File (File) Loop
            declare
                Line : String := IO.Get_Line (File);
                Paren_Index : Integer := Strings.Fixed.Index(Line, ")", 1);
                Orbit_Target : String := Line(Line'First..Line'First + Paren_Index - 2);
                Orbiter : String := Line(Line'First + Paren_Index..Line'Last);
            begin
                Orbits.Insert(Orbiter, Orbit_Target);
            end;
        end loop;
        IO.Close (File);
        return Orbits;
    end Parse_Orbits_From_File;

    function Path_Length (Orbits: String_Maps.Map; Source: String; Target: String) return Integer is
        package SU renames Ada.Strings.Unbounded;
        Steps : Integer := 1;
        Current_Node : SU.Unbounded_String := SU.To_Unbounded_String (Source);
    begin
        while SU.To_String (Current_Node) /= Target Loop
            Steps := Steps + 1;
            Current_Node := SU.To_Unbounded_String (Orbits.Element (SU.To_String (Current_Node)));
        end Loop;
        return Steps;
    end Path_Length;

    function Count_Orbits (Orbits: String_Maps.Map) return Integer is
        Orbit_Count : Integer := 0;
        Orbiter_Cursor : String_Maps.Cursor := String_Maps.First (Orbits);
    begin
        while String_Maps.Has_Element (Orbiter_Cursor) Loop
            declare
                Current_Orbiter : String := String_Maps.Element (Orbiter_Cursor);
                Orbits_From_Center : Integer := Path_Length
                    (Orbits => Orbits,
                     Source => Current_Orbiter,
                     Target => Center_Of_Mass);
            begin
                Orbit_Count := Orbit_Count + Orbits_From_Center;
                String_Maps.Next (Orbiter_Cursor);
            end;
        end Loop;
        return Orbit_Count;
    end Count_Orbits;
begin
    declare
        Orbits: String_Maps.Map := Parse_Orbits_From_File (Ada.Command_Line.Argument (1));
        Orbit_Count : Integer := Count_Orbits (Orbits);
    begin
        IO.Put_Line (Integer'Image (Orbit_Count));
    end;
end Solution_1;

The first thing to note is that Ada’s type-system is characterized as “extremely strong typing”. We’ll work a lot with types in this solution, but we won’t be using the interesting parts of Ada. We start by declaring a bunch of with statements, pulling different Ada standard library packages into our scope so we can use them later.

Then we declare our main procedure, Solution_1. Ada differentiates procedures and functions - functions work with and change data, procedures just run side effects and don’t return anything. In the main procedure, we first declare some aliases for packages by using the package ... renames form. Since we’ll use these packages a lot, we’re giving them a little shorter aliases here.

Next up we have an interesting line. We want to use a hash map in our solution, to store the mappings of orbits between bodies. For this, we build an entirely new hash map package out of the given Ada Hashed_Maps primitive. We specify the types, hash and comparison function we’ll use here. Since we’re just mapping strings to strings we can just use built-in functions for this. Take note however of us using Indefinite_Hashed_Maps and not just Hashed_Maps. In Ada, strings are fixed-length arrays. This means you can’t change the length of a string after you’ve created it. We, for convenience, want strings with different lengths. To make this simpler, we’re going to use the little bit slower but more convenient Indefinite_Hashed_Maps. This enables storing dynamically-sized strings. Interesting to note here how Ada allows tuning a lot of what goes on underneath the hood, quite conveniently.

Then we define a constant, "COM", which we’ll use later to identify the center of mass, aka the root node.

Now we get to our first actual code, in Parse_Orbits_From_File. In this function, we want to parse an input file and return the orbits parsed from it. We start with the signature, taking a single String denoting the filename, and returning a Map out of the new map type package we just created. In Ada, all variables must be declared before use, but they must be declared in special blocks. Before we hit begin in this function, we declare two variables. One to be the input file and the second to be the actual orbits we parse.

Once we get to the function body, we start by opening the given file. Take note of the named parameters we use here. You can use these for any function. Then we loop through the file until the end. In the body of the loop, we run a declare block as we want to use some more variables. Something to note here is the weird way we slice the string. In Ada, strings are not 0 indexed. They’re not even 1-indexed. They’re whatever-indexed. This means you always have to start from the index of the first element, instead of the index being absolute. Also, note the interesting property access syntax - Line'First.

Side note: I’m not sure what the Ada casing conventions are, but when looking online for documentation, most resources I found were underscore-case along with capitals on every word, so I’m following that.

Let’s skip over to the second function, Path_Length. Here, we take the orbit map, a source, and a target, and we want to return the number of steps we have to take until we reach the target from the source. The implementation is pretty straightforward, except for the constant munging between Unbounded_String and To_String. This is because we want to hold strings of different lengths in Current_Node and the map stores fixed strings. Thus, we have to manually convert between Unbounded and Fixed.

Next up, we have Count_Orbits, which adds up all the orbits of all the nodes in the tree using the Path_Length function we defined earlier. To note here is the cursor construction used to iterate through the elements of the map.

Finally, we get to the actual procedure itself, which parses and counts the orbits using the functions we declare earlier. It then casts the number to a string and prints it out, ending the first part of the solution.

The Solution: Part 2

In part 2, we’re also given the location of your spaceship and Santa. Both of those orbit some other bodies. We’re given the task of finding out the minimum amount of orbital transfer we have to do to reach the body Santa is orbiting from the body you are orbiting. We can solve this in two parts. First, we find the closest intersection of the paths from the respective bodies to the root node. We’ll have to transfer through this intersection. Then we’ll take how many hops it takes from both sides to reach this intersection and add those together.

Here’s the code.

with Ada.Text_IO;
with Ada.Command_Line;
with Ada.Strings.Fixed;
with Ada.Strings.Unbounded;
with Ada.Strings.Hash_Case_Insensitive;
with Ada.Strings.Equal_Case_Insensitive;
with Ada.Containers.Indefinite_Hashed_Maps;
with Ada.Containers.Indefinite_Vectors;

procedure Solution_2 is
    package IO renames Ada.Text_IO;
    package Strings renames Ada.Strings;

    package String_Maps is new Ada.Containers.Indefinite_Hashed_Maps
        (Key_Type => String,
         Element_Type => String,
         Hash => Ada.Strings.Hash_Case_Insensitive,
         Equivalent_Keys => Ada.Strings.Equal_Case_Insensitive);

    package String_Vectors is new Ada.Containers.Indefinite_Vectors
        (Index_Type => Natural,
         Element_Type => String);

    Center_Of_Mass : aliased constant String := "COM";
    You : aliased constant String := "YOU";
    Santa : aliased constant String := "SAN";
    Not_Found : exception;

    function Parse_Orbits_From_File (Name: String) return String_Maps.Map is
        File: IO.File_Type;
        Orbits: String_Maps.Map;
    begin
        IO.Open (File => File, Mode => IO.In_File, Name => Name);
        While not IO.End_Of_File (File) Loop
            declare
                Line : String := IO.Get_Line (File);
                Paren_Index : Integer := Strings.Fixed.Index(Line, ")", 1);
                Orbit_Target : String := Line(Line'First..Line'First + Paren_Index - 2);
                Orbiter : String := Line(Line'First + Paren_Index..Line'Last);
            begin
                Orbits.Insert(Orbiter, Orbit_Target);
            end;
        end loop;
        IO.Close (File);
        return Orbits;
    end Parse_Orbits_From_File;

    function Build_Steps (Orbits: String_Maps.Map; Source: String; Target: String) return String_Vectors.Vector is
        package SU renames Ada.Strings.Unbounded;
        Current_Node : SU.Unbounded_String := SU.To_Unbounded_String (Source);
        Steps : String_Vectors.Vector;
    begin
        while SU.To_String (Current_Node) /= Target Loop
            Current_Node := SU.To_Unbounded_String (Orbits.Element (SU.To_String (Current_Node)));
            Steps.Append(SU.To_String (Current_Node));
        end Loop;
        return Steps;
    end Build_Steps;

    function Find_First_Intersection (First_Vector: String_Vectors.Vector; Second_Vector: String_Vectors.Vector) return String is
        Cursor : String_Vectors.Cursor := String_Vectors.First (First_Vector);
    begin
        while String_Vectors.Has_Element (Cursor) loop
            declare
                Element : String := String_Vectors.Element (Cursor);
                Index_In_Second : Integer := Second_Vector.Find_Index (Element);
            begin
                if Index_In_Second /= String_Vectors.No_Index then
                    return Element;
                end if;
                String_Vectors.Next (Cursor);
            end;
        end loop;
        raise Not_Found;
    end Find_First_Intersection;
begin
    declare
        Orbits: String_Maps.Map := Parse_Orbits_From_File (Ada.Command_Line.Argument (1));
        You_Steps : String_Vectors.Vector := Build_Steps (Orbits, You, Center_Of_Mass);
        Santa_Steps : String_Vectors.Vector := Build_Steps (Orbits, Santa, Center_Of_Mass);
        Intersection : String := Find_First_Intersection (You_Steps, Santa_Steps);
        You_Intersection_Index : Integer := You_Steps.Find_Index (Intersection);
        Santa_Intersection_Index : Integer := Santa_Steps.Find_Index (Intersection);
    begin
        IO.Put_Line (Integer'Image (You_Intersection_Index + Santa_Intersection_Index));
    end;
end Solution_2;

The first change you’ll notice is that we also build a package for vectors (array lists) of strings. We have two new functions that use these. The first one, Build_Steps works similarly to Path_Length, but instead of giving us a length, it will build a vector of the path to the root element. We use this path in Find_First_Intersection, where we find the first intersection of two vectors by brute force using ordered sets here would net better performance, but performance isn’t a problem for this task. Finally, in the end, we put these functions together, finding the first intersection of both Santa’s and your path to the root node. We find the answer by adding up the indexes of the intersection from both paths.

That’s it.

Retro

Although we didn’t use any of the really useful parts of Ada, we already got some interesting experience. I wonder why Ada hasn’t taken off massively. I feel it may be that the safety comes at such a cost of verbosity, writing software in Ada didn’t feel super productive. It’s not bad for a 40-year-old language, though. I think the modern equivalent to Ada might be Rust (it also focuses on safety), but it focuses on a different kind of safety. Rust is more about safe memory management, pointers, and ownership while Ada is more about correct maths and contracts.

If you want to look at the code in full, I’m putting all of the Advent of Code solutions on github.