Skip to content

Latest commit

 

History

History
331 lines (314 loc) · 9.77 KB

2021.09.org

File metadata and controls

331 lines (314 loc) · 9.77 KB

Day 09

Executing this code

If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:

  1. Starting slime (M-x slime)
  2. Typing C-c C-c in the block initialize.
  3. In the repl type (in-package :aoc-2021-09)
  4. Typing C-c C-c in the block answers

Initial stuffs

Packages to load

(unless (find-package :cl-ppcre)
  (ql:quickload "cl-ppcre"))
(unless (find-package :iterate)
  (ql:quickload "iterate"))
(unless (find-package :parseq)
  (ql:quickload "parseq"))
(unless (find-package :lparallel)
  (ql:quickload "lparallel"))
(unless (find-package :fiveam)
  (ql:quickload "fiveam"))
(unless (find-package :series)
  (ql:quickload "series"))
(unless (find-package :cl-permutation)
  (ql:quickload "cl-permutation"))
(unless (find-package :bordeaux-threads)
  (ql:quickload "bordeaux-threads"))

Create package for this day

<<packages>>
(defpackage :aoc-2021-09
  (:use :common-lisp
        :parseq
        :fiveam)
  (:export :problem-a
           :problem-b))
(in-package :aoc-2021-09)

Input

(defun read-input (file)
  (with-open-file (in file)
    (loop
       for line = (read-line in nil)
       while line
       collect line)))
(defparameter *input*
  (read-input "input/09.txt"))

Part 1

(defun make-grid (lines)
  (loop
     with grid = (make-hash-table)
     for line in lines
     for i from 0
     finally (return grid)
     do (loop
           for c across line
           for j from 0
           do (setf (gethash (complex i j) grid) (- (char-code c) (char-code #\0))))))

(defun score-grid (grid)
  (loop
     with score = 0
     for pos being the hash-keys of grid using (hash-value v)
     finally (return score)
     if (loop
           for offset in '(#C(0 1) #C(0 -1) #C(1 0) #C(-1 0))
           always (< v (gethash (+ offset pos) grid 10)))
     do (incf score (1+ v))))
(defun problem-a () (format t "Problem 09 A: ~a~%" (score-grid (make-grid *input*))))

Part 2

Now instead of finding the low point, we need to find all “basins” basins are unique areas, below 9, that all flow to a common low point.

If I understand the example correctly, basins are always surrounded by 9s. What I’ll do is find each low point, and search outward.

(defun low-point-p (grid pos)
  (loop
     with v = (gethash pos grid)
     for offset in '(#C(0 1) #C(0 -1) #C(1 0) #C(-1 0))
     always (< v (gethash (+ offset pos) grid 10))))

(defun neighbors (pos)
  (loop for offset in '(#C(0 1) #C(0 -1) #C(1 0) #C(-1 0))
     collect (+ pos offset)))

(defun get-basin-size (grid pos)
  (loop
     with visited = (list pos)
     with basin = (list pos)
     with next = (neighbors pos)
     finally (return (length basin))
     for current = (pop next)
     for height = (gethash current grid 9)
     do (push current visited)
     if (< height 9)
     do
       (push current basin)
       (let ((neighbors (neighbors current)))
         (loop for n in neighbors
              unless (member n visited)
              do (pushnew n next)))
     while next))

(defun find-basin-sizes (grid)
  (loop
     with basins = nil
     for pos being the hash-keys of grid
     if (low-point-p grid pos)
     do (push (get-basin-size grid pos) basins)
     finally (return (subseq (sort basins #'>) 0 3))))
(defun problem-b () (format t "Problem 09 B: ~a~%" (apply #'* (find-basin-sizes (make-grid *input*)))))

Putting it all together



<<read-input>>
<<input>>
<<chars-to-grid>>
<<basins>>


<<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)


Answer


Problem 09 A: 417
Problem 09 B: 1148965



Test Cases


(def-suite aoc.2021.09)
(in-suite aoc.2021.09)

(run! 'aoc.2021.09)


Test Results


Thoughts


Ada


Runner


Simple runner.


with AOC2021.Day09;
procedure Day09 is
begin
  AOC2021.Day09.Run;
end Day09;


Specification


Specification for solution.


package AOC2021.Day09 is
   procedure Run;
end AOC2021.Day09;


Packages


with Text_IO; use Text_IO;
with Ada.Containers.Vectors;
with Ada.Containers; use Ada.Containers;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Strings.Unbounded.Text_IO; use Ada.Strings.Unbounded.Text_IO;


Types and generics


package String_Vectors is new Ada.Containers.Vectors
  (Element_Type => Unbounded_String, Index_Type => Positive);
use String_Vectors;
type Height_Type is new Integer range 0..9;
type Height_Map_Array is array(Natural range <>, Natural range <>) of Height_Type;


Implementation


<<ada-packages>>
package body AOC2021.Day09 is
   <<types-and-generics>>

   function Is_Lowest_Point(I, J: Natural; Height_Map: Height_Map_Array) return Boolean is
     (for all X in -1..1 => X = 0 or
        (Height_Map(I,J) < Height_Map(I + X, J)
           and Height_Map(I,J) < Height_Map(I, J + X)));

   function Part_1(Height_Map: Height_Map_Array) return Integer is
      Count : Integer := 0;
   begin
      for I in 1..(Height_Map'Last(1)-1) loop
         for J in 1..(Height_Map'Last(2)-1) loop
            if Is_Lowest_Point(I, J, Height_Map) then
               Count := Count + 1 + Integer(Height_Map(I,J));
            end if;
         end loop;
      end loop;
      return Count;
   end Part_1;

   function Basin_Crawl (I, J: Natural; Height_Map: in out Height_Map_Array) return Integer is
      Total : Integer := 0;
   begin
      if Height_Map(I, J) = 9
      then
         return 0;
      end if;
      Height_Map(I, J) := 9;
      Total := Total + Basin_Crawl(I + 1, J, Height_Map);
      Total := Total + Basin_Crawl(I - 1, J, Height_Map);
      Total := Total + Basin_Crawl(I, J + 1, Height_Map);
      Total := Total + Basin_Crawl(I, J - 1, Height_Map);
      return Total + 1;
   end Basin_Crawl;

   function Part_2(Height_Map: in out Height_Map_Array) return Integer is
      Biggest : array (1..3) of Integer := (others => 0);
      Temp : Integer := 0;
      Current_Basin : Integer := 0;
   begin
      for I in 1..(Height_Map'Last(1)-1) loop
         for J in 1..(Height_Map'Last(2)-1) loop
            if Is_Lowest_Point(I, J, Height_Map) then
               Current_Basin := Basin_Crawl(I, J, Height_Map);
               for I in 1..3 loop
                  if Biggest(I) < Current_Basin then
                     Temp := Biggest(I);
                     Biggest(I) := Current_Basin;
                     Current_Basin := Temp;
                  end if;
               end loop;
            end if;
         end loop;
      end loop;
      return Biggest(1) * Biggest(2) * Biggest(3);
   end Part_2;

   function Make_Map (Lines: String_Vectors.Vector) return Height_Map_Array is
      Height_Map : Height_Map_Array(0..(Natural(Lines.Length)+1),
                                      0..(Length(Lines(1)) + 1))
           := (others => (others => 9));

   begin
      for I in 1..Natural(Lines.Length) loop
         declare
            Line : Unbounded_String := Lines(I);
         begin
            for J in 1..Length(Lines(1)) loop
               Height_Map(I, J) := Height_Type'Value(Slice(Line,J,J));
            end loop;
         end;
      end loop;
      return Height_Map;
   end Make_Map;

   procedure Read_File (Filename: String; Lines: out String_Vectors.Vector) is
      File : File_Type;
      Line : Unbounded_String;
   begin
      Open (File, In_File, Filename);
      while not End_Of_File (File) loop
         Get_Line(File, Line);
         Lines.Append(Line);
      end loop;
      Close (File);
      null;
   end Read_File;

   procedure Run is
      Lines: String_Vectors.Vector;
      P1 : Integer := 0;
      P2 : Integer := 0;
   begin
      Read_File ("../input/09.txt", Lines);
      declare
         Height_Map : Height_Map_Array := Make_Map(Lines);
      begin
         P1 := Part_1(Height_Map);
         P2 := Part_2(Height_Map);
      end;
      Put_Line("Advent of Code 2021 - Day 09");
      Put_Line("The result for Part 1 is " & Integer'Image(P1));
      Put_Line("The result for Part 2 is " & Integer'Image(p2));
   end Run;
end AOC2021.Day09;


Run the program


In order to run this you have to “tangle” the code first using C-c
  C-v C-t.


cd ada
gnatmake day09
./day09


Advent of Code 2021 - Day 09
The result for Part 1 is  417
The result for Part 2 is  1148965