Skip to content

Latest commit

 

History

History
295 lines (287 loc) · 9.22 KB

2020.19.org

File metadata and controls

295 lines (287 loc) · 9.22 KB

Day 19

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

Input

(defun read-input (file)
  (iter (for line in-file file using #'read-line)
        (collect line)))
(defparameter *input*
  (read-input "input/19.txt"))

Part 1

The first part of the input is a list of rules. The second part is a list of messages. The question is: How many messages match rule 0.

Rules are of the form:

<number>: “<character>” –OR– <number>: <number>+ { | <number>+}

Checking my input, in the case of the rules presenting alternatives there are only 2, so that will help the processing. Since I’m no longer trying to compete on time, I’ll be taking it slow tonight.

The input has two segments: rules and messages. This function will divide the input into those two halves.

(defun split-input (lines)
  (let ((divider (position "" lines :test #'string=)))
    (list (subseq lines 0 divider)
          (subseq lines (1+ divider)))))
(defun parse-or-rule (parts)
  (loop for p in parts
     for rno = (parse-integer p :junk-allowed t)
     with stack = nil
     with rule = nil
     if (null rno)
     do (push (reverse stack) rule)
       (setf stack nil)
     if rno
     do (push rno stack)
     finally (push (reverse stack) rule)
       (return rule)))
(defun parse-rule (rule)
  (let* ((parts (cl-ppcre:split "\\s+" rule))
         (rno (parse-integer (pop parts) :junk-allowed t)))
    (cond ((parse-integer (first parts) :junk-allowed t)
           (list rno (parse-or-rule parts)))
          (t
           (list rno (char (first parts) 1))))))
(defun parse-rules (rules)
  (loop for rule in rules
     with table = (make-hash-table)
     finally (return table)
     for parsed = (parse-rule rule)
     do (setf (gethash (first parsed) table)
              (second parsed))))

So each rule is now in the hash table. I think I can convert this into a regex. I’m going to give it a shot.

(defun make-regex (rules &key (depth 200))
  (format nil "^~A$" (rules-to-regex rules :rno 0 :depth depth)))
(defun rules-to-regex (rules &key (rno 0) (depth 200))
  (cond ((zerop depth) "")
        (t
         (let ((rule (gethash rno rules)))
           (cond ((characterp rule)
                  (format nil "~A" rule))
                 ((= 1 (length rule))
                  (format nil "(~{~A~})" (loop for n in (car rule)
                                            collect (rules-to-regex rules :rno n :depth (1- depth)))))
                 (t
                  (format nil "(~{~A~}|~{~A~})"
                          (loop for n in (car rule)
                             collect (rules-to-regex rules :rno n :depth (1- depth)))
                          (loop for n in (cadr rule)
                             collect (rules-to-regex rules :rno n :depth (1- depth))))))))))

It worked, but the second part introduces two changes which make the above a bad idea (loops).

(defun solve-a (input)
  (let ((regex (make-regex (parse-rules (first (split-input input))))))
               (loop for line in (second (split-input input))
                  count (cl-ppcre:all-matches regex line))))
(defun problem-a () (format t "Problem 19 A: ~a~%" (solve-a *input*)))

Part 2

My brain isn’t working, it’s late, and I want to be done. I’m hacking the rules-to-regex function to take a depth parameter. This is decremented each time we recurse down.

Have to change two rules in the original:

8: 42 | 42 8 11: 42 31 | 42 11 31

(defun solve-b (input)
  (destructuring-bind (rules lines) (split-input input)
    (let ((rules (parse-rules rules)))
      (setf (gethash 8 rules) `((42) (42 8)))
      (setf (gethash 11 rules) `((42 31) (42 11 31)))
      (let* ((regex (make-regex rules :depth 50))
             (scanner (cl-ppcre:create-scanner regex)))
        (loop for line in lines
           count (cl-ppcre:all-matches scanner line))))))
(defun problem-b () (format t "Problem 19 B: ~a~%" (solve-b *input*)))

Putting it all together



<<read-input>>
<<input>>
<<split-input>>
<<parse-rules>>
<<apply-rules>>


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


Answer


Problem 19 A: 115
Problem 19 B: 237



Test Cases


(def-suite aoc.2020.19)
(in-suite aoc.2020.19)
(defparameter *test-input* '("0: 4 1 5"
                             "1: 2 3 | 3 2"
                             "2: 4 4 | 5 5"
                             "3: 4 5 | 5 4"
                             "4: \"a\""
                             "5: \"b\""
                             ""
                             "ababbb"
                             "bababa"
                             "abbbab"
                             "aaabbb"
                             "aaaabbb"))
(test count-matches
  (is (= 2 (loop with regex = (make-regex (parse-rules (first (split-input *test-input*))))
              for line in (second (split-input *test-input*))
                count (cl-ppcre:all-matches regex line)))))
(run! 'aoc.2020.19)


Test Results


Running test suite AOC.2020.19
 Running test COUNT-MATCHES .
 Did 1 check.
    Pass: 1 (100%)
    Skip: 0 ( 0%)
    Fail: 0 ( 0%)



Thoughts


Ada


Runner


Simple runner.


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


Specification


Specification for solution.


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


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.Day19 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 19");
      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.Day19;


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