Skip to content

Latest commit

 

History

History
459 lines (437 loc) · 13.9 KB

2021.08.org

File metadata and controls

459 lines (437 loc) · 13.9 KB

Day 08

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-08)
  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-08
  (:use :common-lisp
        :parseq
        :fiveam)
  (:export :problem-a
           :problem-b))
(in-package :aoc-2021-08)

Input

(defun read-input (file)
  (with-open-file (in file)
    (loop
       for line = (read-line in nil)
       while line
       collect (cl-ppcre:split " \\| " line))))
(defparameter *input*
  (read-input "input/08.txt"))

Part 1

(defun count-1-4-7-8 (lines)
  (loop
     for (nil output) in lines
     sum (loop
            for display in (cl-ppcre:split " " output)
            for n = (length display)
            count (or (= n 2) (= n 3) (= n 4) (= n 7)))))
(defun problem-a () (format t "Problem 08 A: ~a~%" (count-1-4-7-8 *input*)))

Part 2

Ok, after reading it over a couple times I finally grok it. But that doesn’t help me code it any quicker.

The official designations for each segment are from this table:

Ok, taking a moment to think, there has got to be a better way. So here’s my thought, each pattern can be turned into a 7-bit number. The order doesn’t actually matter. Using this, 1, 4, 7, and 8 can be readily identified using part 1, logcount can be used to count the number of bits and give me the same result as I had before.

(defun pattern-to-number (pattern)
  (loop for ch across pattern
       sum (expt 2 (- (char-code ch) (char-code #\a)))))

(defun translate (numbers output)
  (loop
     for d in output
     with result = 0
     finally (return result)
     do
       (setf result (* 10 result))
       (incf result (position d numbers))))

(defun decode-line (codes output)
  (let ((codes (mapcar #'pattern-to-number codes))
        (output (mapcar #'pattern-to-number output))
        (numbers (make-array 10)))
    ;; set 1
    (setf (aref numbers 1)
          (find-if (lambda (n) (= (logcount n) 2)) codes))
    (setf codes (remove (aref numbers 1) codes))
    ;; set 4
    (setf (aref numbers 4)
          (find-if (lambda  (n) (= (logcount n) 4)) codes))
    (setf codes (remove (aref numbers 4) codes))
    ;; set 7
    (setf (aref numbers 7)
          (find-if (lambda (n) (= (logcount n) 3)) codes))
    (setf codes (remove (aref numbers 7) codes))
    ;; set 8
    (setf (aref numbers 8)
          (find-if (lambda (n) (= (logcount n) 7)) codes))
    (setf codes (remove (aref numbers 8) codes))
    ;; 9 ^ (7 | 4) will have one bit
    (setf (aref numbers 9)
          (find-if (lambda (n)
                     (= (logcount (logxor n (logior (aref numbers 7) (aref numbers 4)))) 1))
                   codes))
    (setf codes (remove (aref numbers 9) codes))
    ;; 3 & 1 = 1
    (setf (aref numbers 3)
          (find-if (lambda (n)
                     (and (= (logcount n) 5)
                          (= (aref numbers 1) (logand (aref numbers 1) n))))
                   codes))
    (setf codes (remove (aref numbers 3) codes))
    ;; 6 | 1 = 8
    (setf (aref numbers 6)
          (find-if (lambda (n)
                     (= (aref numbers 8) (logior (aref numbers 1) n)))
                   codes))
    (setf codes (remove (aref numbers 6) codes))
    ;; 0 is the last 6-bit value
    (setf (aref numbers 0)
          (find-if (lambda (n)
                     (= 6 (logcount n)))
                   codes))
    (setf codes (remove (aref numbers 0) codes))
    ;; 6 or 5 = 6
    (setf (aref numbers 5)
          (find-if (lambda (n)
                     (= (aref numbers 6) (logior (aref numbers 6) n)))
                   codes))
    (setf codes (remove (aref numbers 5) codes))
    ;; 2 is last
    (setf (aref numbers 2) (first codes))
    (translate numbers output)))

(defun decode-all-lines (lines)
  (loop
     for (codes output) in lines
     sum (decode-line (cl-ppcre:split " " codes) (cl-ppcre:split " " output))))
(defun problem-b () (format t "Problem 08 B: ~a~%" (decode-all-lines *input*)))

Putting it all together



<<read-input>>
<<input>>
<<part-1>>
<<decoder-ring>>


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


Answer


Problem 08 A: 421
Problem 08 B: 986163



Test Cases


(def-suite aoc.2021.08)
(in-suite aoc.2021.08)
(defparameter *small-test*
  '("acedgfb cdfbe gcdfa fbcad dab cefabd cdfgeb eafb cagedb ab"
    "cdfeb fcadb cdfeb cdbaf"))
(defparameter *big-test*
  (read-input "test/08.txt"))
(run! 'aoc.2021.08)


Test Results


Thoughts


Ada


Runner


Simple runner.


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


Specification


Specification for solution.


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


Packages


with GNAT.Regpat; use GNAT.Regpat;
with Text_IO; use Text_IO;


Types and generics




Implementation


Actual implementation body.


<<ada-packages>>
package body AOC2021.Day08 is
   -- represents the signals as a bolean array
   type Encoded is array (Character range 'a'..'g') of Boolean
   with Default_Component_Value => False;
   Empty : constant Encoded := (others => False);
   type Code_Array is array (1..10) of Encoded;
   type Display_Array is array (1..4) of Encoded;

   -- Straight forward procedure to convert a string of [a-g]+ into a
   -- boolean array.
   procedure Encode (Code : in out Encoded; Input : String) is
   begin
      for C of Input loop
         Code(C) := True;
      end loop;
   end Encode;

   procedure Parse_Line (Line : String; Codes : out Code_Array; Display : out Display_Array; Count : in out Integer) is
      Pattern : constant String :=
        "([a-g]+) ([a-g]+) ([a-g]+) ([a-g]+) ([a-g]+) ([a-g]+) ([a-g]+) ([a-g]+) ([a-g]+) ([a-g]+) \| ([a-g]+) ([a-g]+) ([a-g]+) ([a-g]+)";
      Re : constant Pattern_Matcher := Compile(Pattern);
      Matches : Match_Array (0..Paren_Count(Re));

   begin
      Match(Re, Line, Matches);
      for I in 1..10 loop
         Encode(Codes (I), Line(Matches(I).First..Matches(I).Last));
      end loop;
      for I in 1..4 loop
         if 1 = (Matches (I+10).Last - Matches (I+10).First)
           or 2 = (Matches (I+10).Last - Matches (I+10).First)
           or 3 = (Matches (I+10).Last - Matches (I+10).First)
           or 6 = (Matches (I+10).Last - Matches (I+10).First)
         then
            Count := Count + 1;
         end if;
         Encode(Display (I), Line(Matches(I+10).First..Matches(I+10).Last));
      end loop;
   end Parse_Line;

   -- I couldn't find a "popcount" function in the Ada spec so here it is
   function Popcount (Code : Encoded) return Natural is
      Count : Natural := 0;
   begin
      for B of Code loop
         Count := Count + (if B then 1 else 0);
      end loop;
      return Count;
   end Popcount;

   procedure Decode_Display (Codes : in out Code_Array; Display : Display_Array; Sum : in out Integer) is
      Decoder_Ring : array (0..9) of Encoded;
      Result : Natural := 0;
   begin
      Decoder_Ring (8) := (others => True);
      -- Remove "8"
      for I in Codes'Range loop
         if Codes(I) = Decoder_Ring (8)
         then
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      -- Find "1"
      for I in Codes'Range loop
         if 2 = Popcount (Codes(I))
         then
            Decoder_Ring (1) := Codes(I);
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      -- Find "7"
      for I in Codes'Range loop
         if 3 = Popcount (Codes(I))
         then
            Decoder_Ring (7) := Codes(I);
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      -- Find "4"
      for I in Codes'Range loop
         if 4 = Popcount (Codes(I))
         then
            Decoder_Ring (4) := Codes(I);
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      -- Find "9": 1 = Popcount (9 xor (7 or 4))
      for I in Codes'Range loop
         if 1 = Popcount (Codes(I) xor (Decoder_Ring(7) or Decoder_Ring(4)))
           and Popcount (Codes(I)) = 6
         then
            Decoder_Ring (9) := Codes(I);
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      -- Find "0": Popcount 0 = 6
      for I in Codes'Range loop
         if Popcount (Codes(I)) = 6
           and Decoder_Ring (1) = (Decoder_Ring (1) and Codes (I))
         then
            Decoder_Ring (0) := Codes (I);
            Codes (I) := Empty;
         end if;
      end loop;
      -- Find "6": 8 = 6 or 1
      for I in Codes'Range loop
         if Popcount (Codes(I)) = 6
         then
            Decoder_Ring (6) := Codes(I);
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      -- Find "5": 6 = 5 or 6
      for I in Codes'Range loop
         if Decoder_Ring (9) = (Codes(I) or Decoder_Ring (1))
         then
            Decoder_Ring (5) := Codes(I);
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      -- Find "3": 3 or 1 = 3 & Popcount 3 = 5
      for I in Codes'Range loop
         if Codes(I) = (Codes(I) or Decoder_Ring (1))
           and Popcount (Codes(I)) = 5
         then
            Decoder_Ring (3) := Codes(I);
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      -- Find "2": 2 or 3 = 2 or 1
      for I in Codes'Range loop
         if Codes(I) /= Empty
         then
            Decoder_Ring (2) := Codes(I);
            Codes(I) := Empty;
            exit;
         end if;
      end loop;
      for Code of Display loop
         Result := Result * 10;
         for I in Decoder_Ring'Range loop
            if Code = Decoder_Ring (I)
            then
               Result := Result + I;
               exit;
            end if;
         end loop;
      end loop;
      Sum := Sum + Result;
   end Decode_Display;

   procedure Solve (Filename : String; Count : in out Integer; Sum : in out Integer) is
      Input_File : File_Type;
   begin
      Open (Input_File, In_File, Filename);
      while not End_Of_File (Input_File) loop
         declare
            Line : String := Get_Line (Input_File);
            Codes : Code_Array;
            Display : Display_Array;
         begin
            Parse_Line (Line, Codes, Display, Count);
            Decode_Display (Codes, Display, Sum);
         end;
      end loop;
      Close (Input_File);
   end Solve;

   procedure Run is
      Count : Integer := 0;
      Sum : Integer := 0;
   begin

      Solve ("../input/08.txt", Count, Sum);

      Put_Line("Advent of Code 2021 - Day 08");
      Put_Line("The result for Part 1 is " & Integer'Image(Count));
      Put_Line("The result for Part 2 is " & Integer'Image(Sum)); 
  end Run;
end AOC2021.Day08;


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 day08
./day08