Advent of Code 2024

Today, I'll be using Pascal, perhaps the archetypal old-school procedural language. Pascal is rather stiff in general, but I'll amp up the effect by using a more standard 70s style, although Turbo Pascal and Delphi have many useful extensions.

Part 1

The first task today is to find all of the trailheads in a topographic map, and sum their scores.

• The topographic map is a grid of digits from 0-9 indicating altitude.
• A trailhead is any position that starts one or more hiking trails.
• The score of a trailhead is the number of 9's on the topographic map that are reachable from that trailhead.
• A hiking trail is any path that begins at altitude 0, ends at altitude 9, and always increase in altitude by 1 each step. Trails can only progress left, right, up, or down; not diagonally.

We can find the hiking trails from a trailhead by keeping a set of spots we're looking at, which we'll initialise with the trailhead 0 we're currently scoring, and then repeatedly calculates a new set of all the neighbouring cells that have 1 more than the cell's value. We'll assume a cell_set type, a function empty_cell_set that creates an empty set of coordinates, a next_steps function that finds neighbours of the cells in a set that continue the hiking trail, and a set_length function that reports the number of elements in a set.

In a Pascal function, we need to declare all the local variables in a special var block before the function body. C used to have a similar requirement for declaring variables at the top of scopes--it's a bad idea!

Another charming quirk of Pascal is that you return a value by assigning to the name of the function. It's kind of a good way to think of function names, although I think parameters often matter enough to the phrasing that it doesn't quite work. Maybe that's just a reason that phrasings like that should be avoided, though; another is that it looks worse when using them as higher-order functions.

function score(x, y : integer): integer;

var
   next_cell : integer;
   steps     : cell_set;

begin
   steps := empty_cell_set();
   steps[x, y] := true;

   for next_cell := 1 to 9 do
      begin
         steps := next_steps(steps);
         if set_length(steps) = 0 then
            break;
      end;

   score := set_length(steps);
end;

Pascal natively supports sets, but they won't work for our purposes, as they can only have a maximum of 255 elements (they're primarily designed for combinations of flags). We'll use the same lazy solution we did with assembler, and just define a large array that we can index into with booleans. Pascal supports multi-dimensional arrays, and we can define type aliases in a type block. In Pascal, we have to define the dimensions of our array explicitly, so we can choose 0- or 1-indexing as we please. I'll use 1-indexing today, partly just to show it off, and partly because it does allow for cleaner code for what we need to do right now. A const block allows us to define constants:

const
   width   = 57;
   height  = 57;

type
   cell_set = array [1..width, 1..height] of boolean;

Then we can define empty_cell_set and set_length pretty easily:

function empty_cell_set(): cell_set;

var
   x, y : integer;

begin
   for x := 1 to width do
      for y := 1 to height do
         empty_cell_set[x, y] := false;
end;

function set_length(s : cell_set): integer;

var
   x, y : integer;

begin
   set_length := 0;

   for x := 1 to width do
      for y := 1 to height do
         if s[x, y] then
            inc(set_length);
end;

Finding the next steps from a set of starting cells is a little more involved. We'll begin with an empty set, and then loop over every cell in grid, which will hold the entire topographic map. If a cell is not in sources, we ignore it, but otherwise we check each neighbour cell in turn, and if it's 1 more than cell, we add it to the result set. Note that in Pascal, booleans combined with and and or must be parenthesised:

function next_steps(sources : cell_set): cell_set;

var
   x, y, cell : integer;

begin
   next_steps := empty_cell_set();

   for x := 1 to width do
      for y := 1 to height do
      begin
         if not sources[x, y] then
            continue;

         cell := grid[x, y];

         if (x + 1 <= width) and (grid[x + 1, y] = cell + 1) then
            next_steps[x + 1, y] := true;
         if (x - 1 > 0) and (grid[x - 1, y] = cell + 1) then
            next_steps[x - 1, y] := true;
         if (y + 1 <= height) and (grid[x, y + 1] = cell + 1) then
            next_steps[x, y + 1] := true;
         if (y - 1 > 0) and (grid[x, y - 1] = cell + 1) then
            next_steps[x, y - 1] := true;
      end;
end;

Finally, we add a function that reads the input into grid, and add the main code that ties all the pieces together. In Pascal, the program itself is wrapped in a program block with its own const, type, var, and begin/end blocks, as well as function and procedure definitions, which can themselves have the first kinds of blocks (but not nested functions or procedures). Procedures are like functions, except that they don't return a value.

The code is mostly straightforward, although the file-reading code is a little unusual. We have to first use assign to associate the file variable with a file on disk, and then use reset to actually open it for reading.

We call the main code's x and y variables root_x and root_y to avoid name collisions. Pascal does support shadowing properly, so each function and procedure could use the same names as the main code's variables, but because the main code's variables are essentially globals in this program, forgetting to declare a local x or y variable could introduce confusing bugs by accidentally overwriting the top-level one.

Here's the complete program:

program Day10Part1;

const
   width   = 57;
   height  = 57;

type
   cells    = array [1..width, 1..height] of integer;
   cell_set = array [1..width, 1..height] of boolean;

var
   grid           : cells;
   root_x, root_y : integer;
   total_score    : integer;


procedure read_grid;

var
   input : text;
   c     : char;
   x, y  : integer;

begin
   assign(input, '2024/input/day-10.txt');
   reset(input);

   for y := 1 to height do
   begin
      for x := 1 to width do
      begin
         read(input, c);
         grid[x, y] := ord(c) - ord('0');
      end;

      read(input, c); (* discard newline *)
   end;

   close(input);
end;


function empty_cell_set(): cell_set;

var
   x, y : integer;

begin
   for x := 1 to width do
      for y := 1 to height do
         empty_cell_set[x, y] := false;
end;


function set_length(s : cell_set): integer;

var
   x, y : integer;

begin
   set_length := 0;

   for x := 1 to width do
      for y := 1 to height do
         if s[x, y] then
            inc(set_length);
end;


function next_steps(sources : cell_set): cell_set;

var
   x, y, cell : integer;

begin
   next_steps := empty_cell_set();

   for x := 1 to width do
      for y := 1 to height do
      begin
         if not sources[x, y] then
            continue;

         cell := grid[x, y];

         if (x + 1 <= width) and (grid[x + 1, y] = cell + 1) then
            next_steps[x + 1, y] := true;
         if (x - 1 > 0) and (grid[x - 1, y] = cell + 1) then
            next_steps[x - 1, y] := true;
         if (y + 1 <= height) and (grid[x, y + 1] = cell + 1) then
            next_steps[x, y + 1] := true;
         if (y - 1 > 0) and (grid[x, y - 1] = cell + 1) then
            next_steps[x, y - 1] := true;
      end;
end;


function score(x, y : integer): integer;

var
   next_cell : integer;
   steps     : cell_set;

begin
   steps := empty_cell_set();
   steps[x, y] := true;

   for next_cell := 1 to 9 do
      begin
         steps := next_steps(steps);
         if set_length(steps) = 0 then
            break;
      end;

   score := set_length(steps);
end;


begin
   read_grid;

   total_score := 0;

   for root_x := 1 to width do
      for root_y := 1 to height do
         if grid[root_x, root_y] = 0 then
            inc(total_score, score(root_x, root_y));

   write(total_score);
   writeln;
end.

Part 2

For part 2, instead of summing the unique 9s reachable from a trailhead, we want to sum the number of unique hiking trails. I think this problem is actually easier (it's how I originally interpreted part 1, as well). Rather than needing to keep track of a set of cells under consideration, we can simply use a recursive function that sums the result of calling itself on each neighbour.

• If that neighbour is not the next cell or is out of bounds, it returns 0.
• If that neighbour is the next cell and is a 9, it returns 1.
• If that neighbour is the next cell and is not a 9, it calls itself recursively on each neighbour and sums their results.

We can just delete a lot of our code, and score now follows the algorithm given above very directly. Here's the completed code:

program Day10Part2;

const
   width   = 57;
   height  = 57;

type
   cells = array [1..width, 1..height] of integer;

var
   grid           : cells;
   root_x, root_y : integer;
   total_score    : integer;


procedure read_grid;

var
   input : text;
   c     : char;
   x, y  : integer;

begin
   assign(input, '2024/input/day-10.txt');
   reset(input);

   for y := 1 to height do
   begin
      for x := 1 to width do
      begin
         read(input, c);
         grid[x, y] := ord(c) - ord('0');
      end;

      read(input, c); (* discard newline *)
   end;

   close(input);
end;


function score(x, y, prev : integer): integer;

var
   cell : integer;

begin
   if (x < 1) or (y < 1) or (x > width) or (y > height) then
      score := 0
   else
   begin
      cell := grid[x, y];

      if cell <> prev + 1 then
         score := 0
      else if cell = 9 then
         score := 1
      else
         score := (
            score(x + 1, y, cell) +
            score(x - 1, y, cell) +
            score(x, y + 1, cell) +
            score(x, y - 1, cell)
         );
   end;
end;


begin
   read_grid;

   total_score := 0;

   for root_x := 1 to width do
      for root_y := 1 to height do
         if grid[root_x, root_y] = 0 then
            inc(total_score, score(root_x, root_y, -1));

   write(total_score);
   writeln;
end.