Skip to content

Latest commit

 

History

History
310 lines (301 loc) · 9.33 KB

2020.16.org

File metadata and controls

310 lines (301 loc) · 9.33 KB

Day 16

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

Input

(defun parse-ticket (line)
  (mapcar #'parse-integer (cl-ppcre:all-matches-as-strings "\\d+" line)))
(defun parse-field (line)
  (let ((parts (cl-ppcre:split ":" line)))
    (cons (first parts)
          (mapcar #'parse-integer (cl-ppcre:all-matches-as-strings "\\d+" (second parts))))))
(defun read-input (file)
  (let (ranges ticket tickets)
    (with-open-file (in file)
      (setf ranges
            (loop for line = (read-line in nil)
               until (zerop (length line))
               collect (parse-field line)))
      (read-line in)
      (setf ticket (parse-ticket (read-line in)))
      (read-line in) (read-line in)
      (setf tickets
            (loop for line = (read-line in nil)
               while line
               collect (parse-ticket line))))
    (list ranges ticket tickets)))


(defparameter *input*
  (read-input "input/16.txt"))

Part 1

Count invalid tickets. A ticket is invalid if it contains a number which none of the ranges apply to.

(defun valid-value (ranges value)
  (loop for (name a b c d) in ranges
     if (or (<= a value b)
            (<= c value d))
     do (return t)))
(defun invalid-values (ranges ticket)
  (loop for i in ticket
     if (not (valid-value ranges i))
     sum i))
(defun count-invalid (ranges tickets)
  (loop for ticket in tickets
     sum (invalid-values ranges ticket)))
(defun problem-a () (format t "Problem 16 A: ~a~%" (count-invalid (first *input*) (third *input*))))

Part 2

Now discard all the invalid tickets. Using the remaining ones, determine which ticket index corresponds to which field.

(defun valid-ticket (ranges ticket)
  (loop for i in ticket
     if (not (valid-value ranges i))
     do (return-from valid-ticket nil))
  t)
(defun discard-invalid (ranges tickets)
  (loop for ticket in tickets
     if (valid-ticket ranges ticket)
     collect ticket))
(defun viable-field-indexes (ranges tickets)
  (let ((field-indexes (make-hash-table :test 'equal)))
    (loop for (name a b c d) in ranges
       do (loop named find-index
             for index from 0 below (length (first tickets))
             if (every (lambda (ticket)
                         (let ((n (nth index ticket)))
                           (or (<= a n b)
                               (<= c n d))))
                       tickets)
             do (push index (gethash name field-indexes))))
    field-indexes))
(defun find-fields (ranges tickets)
  (let ((field-indexes (viable-field-indexes ranges tickets))
        (indexes (make-hash-table :test 'equal)))
    (labels ((one-each ()
               (loop for v being the hash-values in field-indexes
                  if (< 1 (length v))
                  do (return-from one-each nil))
               t)
             (remove-from-others (index field)
               (loop for k being the hash-keys of field-indexes using (hash-value v)
                  do (unless (string= k field)
                       (setf (gethash k field-indexes)
                             (remove index v))))))
      (loop
         until (one-each)
         do (loop named inner
               for k being the hash-keys in field-indexes using (hash-value v)
               if (= 1 (length v))
               do (remove-from-others (first v) k)
                 (remhash k field-indexes)
                 (setf (gethash k indexes) (first v))
                 (return-from inner)))
      indexes)))
(defun solve-b (input)
  (let ((fields (find-fields (first input) (discard-invalid (first input) (third input))))
        (product 1))
    (loop for k being the hash-keys of fields using (hash-value v)
       if (search "departure" k)
       do (setf product (* product (nth v (second *input*)))))
    product))

The above returns a set of viable indexes for each field. The second function will reduce it to just one option per field. I’m confident the above is correct, but I’m getting an incorrect answer.

I had a stupid mistake that was causing me to not filter anything. A lot of hacking around finally got me to the answer. The above is not pretty, but it is functional.

(defun problem-b () (format t "Problem 16 B: ~a~%" (solve-b *input*)))

Putting it all together



<<parse-ticket>>
<<read-input>>
<<input>>
<<count-invalid>>
<<discard-invalid>>
<<find-fields>>


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


Answer


Problem 16 A: 20048
Problem 16 B: 4810284647569



Test Cases


(def-suite aoc.2020.16)
(in-suite aoc.2020.16)
(defparameter *test-string*
"class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50

your ticket:
7,1,14

nearby tickets:
7,3,47
40,4,50
55,2,20
38,6,12")
(defparameter *test-input-1*
  '((("class" 1 3 5 7) ("row" 6 11 33 44) ("seat" 13 40 45 50))
    (7 1 14)
    ((7 3 47)
     (40 4 50)
     (55 2 20)
     (38 6 12))))
(defparameter *test-input-2*
  '((("class" 0 1 4 19) ("row" 0 5 8 19) ("seat" 0 13 16 19))
    (11 12 13)
    ((3 9 18)
     (15 1 5)
     (5 14 9))))
(run! 'aoc.2020.16)


Test Results


Running test suite AOC.2020.16
 Didn't run anything...huh?



Thoughts


Ada


Runner


Simple runner.


with AOC2020.Day16;
procedure Day16 is
begin
  AOC2020.Day16.Run;
end Day16;


Specification


Specification for solution.


package AOC2020.Day16 is
   procedure Run;
end AOC2020.Day16;


Packages


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


Types and generics




Implementation


Actual implementation body.


<<ada-packages>>
package body AOC2020.Day16 is
   <<types-and-generics>>
   -- Used as an example of matching regular expressions
   procedure Parse_Line (Line : Unbounded_String; P : out Password) is
      Pattern : constant String := "(\d+)-(\d+) ([a-z]): ([a-z]+)";
      Re : constant Pattern_Matcher := Compile(Pattern);
      Matches : Match_Array (0..4);
      Pass : Unbounded_String;
      P0, P1 : Positive;
      C : Character;
   begin
      Match(Re, To_String(Line), Matches);
      P0 := Integer'Value(Slice(Line, Matches(1).First, Matches(1).Last));
      P1 := Integer'Value(Slice(Line, Matches(2).First, Matches(2).Last));
      C := Element(Line, Matches(3).First);
      Pass := To_Unbounded_String(Slice(Line, Matches(4).First, Matches(4).Last));
      P := (Min_Or_Pos => P0,
            Max_Or_Pos => P1,
            C => C,
            P => Pass);
   end Parse_Line;
   procedure Run is
   begin
      Put_Line("Advent of Code 2020 - Day 16");
      Put_Line("The result for Part 1 is " & Integer'Image(0));
      Put_Line("The result for Part 2 is " & Integer'Image(0));
   end Run;
end AOC2020.Day16;


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