The Advent of Code in Ada

This is of necessity long, and may not interest most people — or really anyone aside from me.

Introduction

I lurk on a few websites related to computer programming, and sometimes participate. Every year, one or more of them will pop up a discussion about Advent of Code, an annual programming puzzle contest. It’s like an Advent calendar, where on each day you open a compartment to find a goodie — only instead of a chocolate treat, you get two programming puzzles.

True to its name, the Advent of Code competitions start at midnight EST on December 1st, and continue through the 25th.

I doubt most participants intend to win. Many probably start off thinking they’ll do well, but before long one realizes that he doesn’t stand a chance against seasoned, “professional” competitors. He may even wonder how on earth the professionals manage to complete many of the puzzles so quickly! I certainly did.

Many participate as a purely social event, as an excuse to chat on their favorite programming-related forums. Some companies have their employees participate as a way of building skills; and some people do it to learn a programming language.

Last November I joined the latter group, with the intent of learning the Ada programming language.

Why Ada?

I first heard of Ada in my youth, probably among the computer books I read voraciously. That was the age of the “home computer”, which has since been replaced by the age of the “Personal Computers”.✝“Impersonal” would be a better description, but I suppose that’s a discussion for another day. My father, an engineer who worked for a NASA contractor, once said that Ada interested him greatly, though I don’t think he ever acquired much experience with it.

Quite a few people harbor negative opinions of Ada. One of my undergaduate professors derided it as a product of the military; she was much more impressed with C++. Too many people take one look at it and say, “Nah; I’m more of a ‘curly brackets’ person.” 
with Ada.Text_IO;

procedure Test_Out is
   package ATIO renames Ada.Text_IO;
begin
   ATIO.Put_Line("Hello, world!");
end Test_Out;
Early in its lifetime, Ada picked up a reputation for being a very complicated language, and this is one of the reasons it didn’t take off. Some people still say that.

As it happens, I had pretty much no exposure to Ada until about 2017 or 2018, when I took a course on compiler construction. We had an end-of-term team assignment to research and present on several computer languages, and when I saw that Pascal and Ada were two of the options, I signed my name next to those.

I put a lot of work into studying Ada for that project, enough that by the end of the semester I ported the toy compiler we were working on to Ada, and added multitasking facilities for COBEGIN and COEND that made use of Ada’s task mechanism. I also learned about the SPARK dialect, which helps produce “provably formally correct code”.

After decades of struggling with C++’s complexities and inconsistencies, Ada didn’t seem half bad. I enjoyed the experience enough to sign up for the GNAT Academic Program.

A toy compiler is OK, but I didn’t have much cause to use Ada again for a while, and by late 2020 I knew I had forgotten most of what I’d learned. The Advent of Code seemed like a good time to re-acquaint myself with Ada.

Advent of Code 2020

The first puzzle opens,
After saving Christmas five years in a row…
Hmm. You must have me confused with someone else.

I pressed on.

My experience

I successfully completed every puzzle!

…sadly, not always on my own. On several occasions I looked at other people’s solutions to obtain ideas. I generally attributed those participants when I did. On some occasions I did not: these are instances where I already had the right idea, but my implementation wasn’t working. After exhausting my brain, I would visit Reddit, read what people were saying, see if someone was following my approach, and if so, download the code and see if I could run it and see where its intermediate computations diverged from mine. These un-attributed people were writing in other languages; I particularly remember using solutions written in Java and Rust, the latter of which I’ve never used before, but I had briefly studied it, and besides it’s essentially an imperative language like most mainstream languages, so I deciphered enough to insert print statements in the right places.

One charming aspect of the 2020 puzzles was the alliterative names: Report Repair, Toboggan Trajectory, etc. Only Combo Breaker, the final puzzle, didn’t at least try, and that’s a shame, since “Hotel Hacker” would have worked great.

The puzzles themselves range from very easy to insanely difficult. Even the easiest ones took me at least 45 minutes, but those occurred on the first few days, and I console myself that it was due to reacquainting myself with Ada.

Other puzzles took hours. I stayed up all night on more than one occasion, until I came to grips with reality and accepted that I might as well get a good night’s sleep and attack the puzzles with a fresh mind in the morning. Alas, that’s also round about the insanely hard puzzles’s advent, which meant I ended up squandering before a screen much of the holiday time I had meant to spend with family. Awareness of the tradeoff didn’t help lessen my frustration at those times.

I got the T-shirt! …well, kind of

There was a payoff to completing the competition: this pleasant animated ASCII art that incorporates many of the puzzles.

Flush with the pleasure of having completed the Advent of Code — many who start do not finish — I decided to buy the T-shirt. It looks cool, and I thought it would be awesome to sport it around.

Sadly, I’m the kind of idiot savant who forgets to select the size, so I ended up buying the default size (Small) instead of one that fits me (Large).

My elder daughter is very happy with her new T-shirt.

Advent of Code 2019

In an interview somewhere online, Eric Wastl mentions the number of people who have completed all the puzzles for all the years. It’s not a big number, as I recall: roughly 400, I think. Without thinking how much time it had taken to complete quite a few of the puzzles, I decided to try my hand at Advent of Code 2019, also in Ada.

My experience

I completed that one, too!

…also, alas, not entirely on my own. In fact, for some reason I found it a much, much bigger challenge. Two or three of the problems seemed much harder than any of 2020’s problems, I might even say that they seemed unreasonably hard for a “simple” competition. I’d have kept this opinion to myself, but a few comments on Reddit also expressed dissatisfaction at the difficulty in 2019, which I don’t remember from the 2020 competition. I probably didn’t look hard enough, and I discuss this disappointment below, so don’t judge me too harshly yet.

These difficult problems did have something in common: circumventing algorithmic complexity seemed a much bigger deal in 2019’s puzzles than it had been in 2020’s. A couple of puzzles related to this ground me down so much that after completing them I would go a couple of weeks or more without even thinking about it. Because of this, I finished the 2019 competition in April, despite starting in January.

All that said, it’s Mr. Wastl’s competition, so what makes it “reasonable” is really up to him. Unlike me, Mr. Wastl works in the industry, so he would have a better conception.

One part of the 2019 competition that I really enjoyed were the Intcode puzzles. That gave me practice building and assembling an Ada package, which is both something the 2020 competition didn’t quite afford me, and also one of my favorite activities. Reusable code gives one a sense of satisfaction that a one-off puzzle doesn’t quite accomplish.

Hands down, I most enjoyed the final puzzle, a text adventure game in the old style (“old” = 1980s), programmed in Intcode, which is pretty impressive in itself, and required a bit of ingenuity to work through the main puzzle. The game takes its inspiration from the old 1980s games in more than one way by making reference to at least one creature from Zork.

Not quite the T-shirt

I got my payoff!

Unlike the 2020 animation, there really aren’t any particular puzzle items visible in this animation. It “just” depicts the general storyline:
Santa has become stranded at the edge of the Solar System while delivering presents to other planets! To accurately calculate his position in space, safely align his warp drive, and return to Earth in time to save Christmas, he needs you to bring him measurements from fifty stars.
You’ll notice a dot that moves from Earth to each of the other planets, innermost first, until it ends up beyond Pluto, then returns to Earth.

Also unlike the 2020 competition, there was no special T-shirt for the occasion. ✣If you’re wondering, my younger daughter does not seem particularly disappointed.

Was it a good idea?

Yes. I have a decent grasp on Ada, though I’d not be foolish enough to pretend that I’m an expert.

Is Ada suitable for Advent of Code?

To win?

Not unless you come really well prepared.

To be fair, that applies to just about any programming language. The top competitors are using whatever tool they have at hand, which from what I hear includes things like spreadsheets and prepared programs that work in many situations. They have a lot of experience at tying their tools together. That’s impressive, but it means that someone like me, who comes to each day’s puzzles with a blank slate (more or less) has little hope of writing an Ada program that solves both puzzles within, say, 2-3 minutes.

To learn?

I wanted to learn Ada, and for that purpose it worked well. There were times that I struggled with the Ada language itself when I might not have struggled with a different language. That’s not necessarily a bad thing: I was learning Ada, and in cases where the struggles were not due to the learning, the restrictions Ada imposes may well be a guarantee for a good result.

To break a compiler?

Gautier de Montmollin, who maintains the HAC Ada Compiler, remarked in comp.lang.ada that the Advent of Code helped him test, improve, and debug HAC.

I likewise discovered several bugs in the GNAT Ada compiler and reported them to AdaCore. AdaCore confirmed the bugs and said they would be fixed in the next release. Alas, they didn’t send me an advance copy of the fixed compiler as a reward. ;-)

To compare languages?

It’s hard not to look at this Python code, taken from Lucas Alegre’s solution to Day 1 of the 2019 competition: 
from math import floor


def mass_to_fuel(mass):
    return floor(mass/3) - 2


if __name__ == '__main__':

    with open('day01.txt') as f:
        mass = [int(x) for x in f.readlines()]

    # Part1: 
    # print(sum(map(mass_to_fuel, mass)))

    # Part 2:
    c = 0
    for m in mass:
        while m > 0:
            m = max(0, mass_to_fuel(m))
            c += m
    print(c)
…and not feel at least a bit of envy when I have to write this: 
-- Advent of Code 2019, Day 1
--
-- John Perry
--
-- Tyranny of the Rocket Equation
--
-- part 1: apply a simple formula to input sequence
--
-- part 2: compound the formula on itself
--

with Ada.Text_IO;
use Ada.Text_IO;

with Ada.Integer_Text_IO;
use Ada.Integer_Text_IO;

procedure Main is

   -- SECTION
   -- input-related

   F: File_Type; -- input file

   Testing: constant Boolean := False;

   Filename: constant String
         := (
             if Testing then "/Users/user/common/Ada/AoC2019/Day1/example.txt"
             else "/Users/user/common/Ada/AoC2019/Day1/input.txt"
            );

   -- SECTION
   -- computing fuel requirements

   function Estimate_Fuel(Mass: Natural) return Natural is
   -- returns an estimate of the fuel mass necessary for Mass
   ( ( Mass - Mass mod 3 ) / 3 -2 );

begin

   -- SECTION
   -- parts 1 and 2 together

   Open(F, In_File, Filename);

   declare

      Value, Partial_Sum, Intermediate_Sum: Natural;
      Sum, Total_Sum: Natural := 0;

   begin

      while not End_Of_File(F) loop

         Get(F, Value);

         Partial_Sum := Estimate_Fuel(Value);
         Sum := Sum + Partial_Sum;

         -- now accumulate the fuel for the fuel
         -- only need to do this for Partial_Sum > 8;
         -- otherwise estimate is 0 or negtive

         Intermediate_Sum := Partial_Sum;

         while Partial_Sum > 8 loop
            Partial_Sum := Estimate_Fuel(Partial_Sum);
            Intermediate_Sum := Intermediate_Sum + Partial_Sum;
         end loop;

         Total_Sum := Total_Sum + Intermediate_Sum;

      end loop;

      Put("sum of fuel requirements: "); Put(Sum, 0); New_Line;
      Put("total sum of fuel requirements: "); Put(Total_Sum, 0); New_Line;

   end;

   Close(F);

end Main;
To be perfectly fair, there may well be a nice, elegant way of writing this in Ada; I don’t know that I’d have thought of writing that style of Python code myself. I don’t have that much experience with the use of “mappings”, an admittedly nice technique, but not one I often think of offhand. As the competition progressed, I did learn more. However, something simple like this Python code: 
    with open('day01.txt') as f:
        mass = [int(x) for x in f.readlines()]
…will nevertheless require some with and use or renames clauses in Ada that come “free” in Python.

Specifications, or the lack thereof

One recurrent frustration I had with the puzzles is that they often don’t specify parameters that I thought ought to be specified.

One example would be 2019’s Intcode problems. What size should one set aside for the Intcode programs? How much data will they need? What’s the maximum size an Intcode value can take? The puzzles never say. Ada’s kind of particular about types, for good reason; overflow bugs can be pretty hard to track down.

Arguably, this particular example illustrates how a package evolves as you find more needs for it, and I was quite pleased at how little restructuring my Intcode package needed. But on more than one occasion I encountered problems simply because I didn’t have the right amount of data set aside, the right stack size, and/or the right type chosen for an Intcode. Eventually I needed to use Long_Long_Integer, which uses a 64-bit integer, but shouldn’t that be specified from the start?

Will I do another?

It can be immensely rewarding to complete a puzzle, especially when you’ve figured it out on your own, but it takes a lot of time and energy, and I do have other obligations. A while back I was thinking I might complete all the old puzzles, as well as participate in the 2021 competition, but to be honest, I’d rather spend the time and energy doing something else.

So, I don’t know.

Well, maybe if there’s another custom T-shirt. ;-)