9 files changed, 521 insertions, 0 deletions
diff --git a/users/tazjin/aoc2020/default.nix b/users/tazjin/aoc2020/default.nix
new file mode 100644
index 0000000000..cd89da7de4
--- /dev/null
+++ b/users/tazjin/aoc2020/default.nix
@@ -0,0 +1,26 @@
+# Solutions for Advent of Code 2020, written in Emacs Lisp.
+#
+# For each day a new file is created as "solution-day$n.el".
+{ depot, pkgs, ... }:
+
+let
+  inherit (builtins) attrNames filter head listToAttrs match readDir;
+  dir = readDir ./.;
+  matchSolution = match "solution-(.*)\.el";
+  isSolution = f: (matchSolution f) != null;
+  getDay = f: head (matchSolution f);
+
+  solutionFiles = filter (e: dir."${e}" == "regular" && isSolution e) (attrNames dir);
+  solutions = map
+    (f:
+      let day = getDay f; in depot.nix.writeElispBin {
+        name = day;
+        deps = p: with p; [ dash s ht p.f ];
+        src = ./. + ("/" + f);
+      })
+    solutionFiles;
+in
+pkgs.symlinkJoin {
+  name = "aoc2020";
+  paths = solutions;
+}
diff --git a/users/tazjin/aoc2020/solution-day1.el b/users/tazjin/aoc2020/solution-day1.el
new file mode 100644
index 0000000000..a04f43d151
--- /dev/null
+++ b/users/tazjin/aoc2020/solution-day1.el
@@ -0,0 +1,44 @@
+;; Advent of Code 2020 - Day 1
+(require 'cl)
+(require 'ht)
+(require 'dash)
+
+(defmacro hash-set (&rest elements)
+  "Define a hash-table with empty values, for use as a set."
+  (cons 'ht (-map (lambda (x) (list x nil)) elements)))
+
+;; Puzzle 1:
+
+(defvar day1/input
+  (hash-set 1645 1995 1658 1062 1472 1710 1424 1823 1518 1656 1811 1511 1320 1521 1395
+            1996 1724 1666 1637 1504 1766 534 1738 1791 1372 1225 1690 1949 1495 1436 1166
+            1686 1861 1889 1887 997 1202 1478 833 1497 1459 1717 1272 1047 1751 1549 1204
+            1230 1260 1611 1506 1648 1354 1415 1615 1327 1622 1592 1807 1601 1026 1757 1376
+            1707 1514 1905 1660 1578 1963 1292 390 1898 1019 1580 1499 1830 1801 1881 1764
+            1442 1838 1088 1087 1040 1349 1644 1908 1697 1115 1178 1224 1810 1445 1594 1894
+            1287 1676 1435 1294 1796 1350 1685 1118 1488 1726 1696 1190 1538 1780 1806 1207
+            1346 1705 983 1249 1455 2002 1466 1723 1227 1390 1281 1715 1603 1862 1744 1774
+            1385 1312 1654 1872 1142 1273 1508 1639 1827 1461 1795 1533 1304 1417 1984 28
+            1693 1951 1391 1931 1179 1278 1400 1361 1369 1343 1416 1426 314 1510 1933 1239
+            1218 1918 1797 1255 1399 1229 723 1992 1595 1191 1916 1525 1605 1524 1869 1652
+            1874 1756 1246 1310 1219 1482 1429 1244 1554 1575 1123 1194 1408 1917 1613 1773
+            1809 1987 1733 1844 1423 1718 1714 1923 1503))
+
+(message "Solution to day1/1: %s"
+         (cl-loop for first being the hash-keys of day1/input
+                  for second = (- 2020 first)
+                  when (ht-contains? day1/input second)
+                  return (* first second)))
+
+;; Puzzle 2:
+
+(message "Solution to day1/1: %s"
+         (cl-loop for first being the hash-keys of day1/input
+                  for result =
+                  (cl-loop
+                   for second being the elements of (-drop 1 (ht-keys day1/input))
+                   for third = (- 2020 first second)
+                   when (ht-contains? day1/input third)
+                   return (* first second third))
+
+                  when result return result))
diff --git a/users/tazjin/aoc2020/solution-day2.el b/users/tazjin/aoc2020/solution-day2.el
new file mode 100644
index 0000000000..5993bf3407
--- /dev/null
+++ b/users/tazjin/aoc2020/solution-day2.el
@@ -0,0 +1,54 @@
+;; Advent of Code 2020 - Day 2
+
+(require 'cl-lib)
+(require 'f)
+(require 'ht)
+(require 's)
+(require 'seq)
+
+(defvar day2/input
+  ;; This one was too large to inline.
+  (s-lines (f-read "/tmp/aoc/day2.txt")))
+
+(defun day2/count-letters (password)
+  (let ((table (ht-create)))
+    (cl-loop for char across password
+             for current = (ht-get table char)
+             do (ht-set table char
+                        (if current (+ 1 current) 1)))
+    table))
+
+(defun day2/parse (input)
+  (let* ((split (s-split " " input))
+         (range (s-split "-" (car split))))
+    (list (string-to-number (car range))
+          (string-to-number (cadr range))
+          (string-to-char (cadr split))
+          (caddr split))))
+
+(defun day2/count-with-validation (func)
+  (length (-filter
+           (lambda (password)
+             (and (not (seq-empty-p password))
+                  (apply func (day2/parse password))))
+           day2/input)))
+
+;; Puzzle 1
+
+(defun day2/validate-oldjob (min max char password)
+  (let ((count (ht-get (day2/count-letters password) char)))
+    (when count
+      (and (>= count min)
+           (<= count max)))))
+
+(message "Solution to day2/1: %s"
+         (day2/count-with-validation #'day2/validate-oldjob))
+
+;; Puzzle 2
+
+(defun day2/validate-toboggan (pos1 pos2 char password)
+  (xor (= char (aref password (- pos1 1)))
+       (= char (aref password (- pos2 1)))))
+
+(message "Solution to day2/2: %s"
+         (day2/count-with-validation #'day2/validate-toboggan))
diff --git a/users/tazjin/aoc2020/solution-day3.el b/users/tazjin/aoc2020/solution-day3.el
new file mode 100644
index 0000000000..80ea4a2264
--- /dev/null
+++ b/users/tazjin/aoc2020/solution-day3.el
@@ -0,0 +1,43 @@
+;; Advent of Code 2020 - Day 3
+
+(require 'cl-lib)
+(require 'dash)
+(require 'f)
+(require 's)
+(require 'seq)
+
+(setq day3/input
+      (-filter (lambda (s) (not (seq-empty-p s)))
+         (s-lines (f-read "/tmp/aoc/day3.txt"))))
+
+(setq day3/input-width (length (elt day3/input 0)))
+(setq day3/input-height (length day3/input))
+
+(defun day3/thing-at-point (x y)
+  "Pun intentional."
+  (when (>= day3/input-height y)
+    (let ((x-repeated (mod (- x 1) day3/input-width)))
+      (elt (elt day3/input (- y 1)) x-repeated))))
+
+(defun day3/slope (x-steps y-steps)
+  "Produce the objects encountered through this slope until the
+  bottom of the map."
+  (cl-loop for x from 1 by x-steps
+           for y from 1 to day3/input-height by y-steps
+           collect (day3/thing-at-point x y)))
+
+;; Puzzle 1
+
+(defun day3/count-trees (x-steps y-steps)
+  (cl-loop for thing being the elements of (day3/slope x-steps y-steps)
+           count (= thing ?#)))
+
+(message "Solution to day3/1: One encounters %s trees" (day3/count-trees 3 1))
+
+;; Puzzle 2
+
+(message "Solution to day3/2 %s" (* (day3/count-trees 1 1)
+                                    (day3/count-trees 3 1)
+                                    (day3/count-trees 5 1)
+                                    (day3/count-trees 7 1)
+                                    (day3/count-trees 1 2)))
diff --git a/users/tazjin/aoc2020/solution-day4.el b/users/tazjin/aoc2020/solution-day4.el
new file mode 100644
index 0000000000..034a40a955
--- /dev/null
+++ b/users/tazjin/aoc2020/solution-day4.el
@@ -0,0 +1,98 @@
+;; Advent of Code 2020 - Day 4
+
+(require 'cl-lib)
+(require 's)
+(require 'dash)
+(require 'f)
+
+(cl-defstruct day4/passport
+  byr ;; Birth Year
+  iyr ;; Issue Year
+  eyr ;; Expiration Year
+  hgt ;; Height
+  hcl ;; Hair Color
+  ecl ;; Eye Color
+  pid ;; Passport ID
+  cid ;; Country ID
+  )
+
+(defun day4/parse-passport (input)
+  (let* ((pairs (s-split " " (s-replace "\n" " " input) t))
+         (slots
+          (-map
+           (lambda (pair)
+             (pcase-let ((`(,key ,value) (s-split ":" (s-trim pair))))
+               (list (intern (format ":%s" key)) value)))
+           pairs)))
+    (apply #'make-day4/passport (-flatten slots))))
+
+(defun day4/parse-passports (input)
+  (-map #'day4/parse-passport (s-split "\n\n" input t)))
+
+(setq day4/input (day4/parse-passports (f-read "/tmp/aoc/day4.txt")))
+
+;; Puzzle 1
+
+(defun day4/validate (passport)
+  "Check that all fields except CID are present."
+  (cl-check-type passport day4/passport)
+  (and (day4/passport-byr passport)
+       (day4/passport-iyr passport)
+       (day4/passport-eyr passport)
+       (day4/passport-hgt passport)
+       (day4/passport-hcl passport)
+       (day4/passport-ecl passport)
+       (day4/passport-pid passport)))
+
+(message "Solution to day4/1: %s" (cl-loop for passport being the elements of day4/input
+                                           count (day4/validate passport)))
+
+;; Puzzle 2
+
+(defun day4/year-bound (min max value)
+  (and
+   (s-matches? (rx (= 4 digit)) value)
+   (<= min (string-to-number value) max)))
+
+(defun day4/check-unit (unit min max value)
+  (and
+   (string-match (rx (group (+? digit)) (literal unit)) value)
+   (<= min (string-to-number (match-string 1 value)) max)))
+
+(defun day4/properly-validate (passport)
+  "Opting for readable rather than clever here."
+  (and
+   (day4/validate passport)
+
+   ;; byr (Birth Year) - four digits; at least 1920 and at most 2002.
+   (day4/year-bound 1920 2002 (day4/passport-byr passport))
+
+   ;; iyr (Issue Year) - four digits; at least 2010 and at most 2020.
+   (day4/year-bound 2010 2020 (day4/passport-iyr passport))
+
+   ;; eyr (Expiration Year) - four digits; at least 2020 and at most 2030.
+   (day4/year-bound 2020 2030 (day4/passport-eyr passport))
+
+   ;; hgt (Height) - a number followed by either cm or in:
+   ;; If cm, the number must be at least 150 and at most 193.
+   ;; If in, the number must be at least 59 and at most 76.
+   (or (day4/check-unit "cm" 150 193 (day4/passport-hgt passport))
+       (day4/check-unit "in" 59 76 (day4/passport-hgt passport)))
+
+   ;; hcl (Hair Color) - a # followed by exactly six characters 0-9 or a-f.
+   (s-matches? (rx ?# (= 6 hex)) (day4/passport-hcl passport))
+
+   ;; ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.
+   (-contains? '("amb" "blu" "brn" "gry" "grn" "hzl" "oth")
+               (day4/passport-ecl passport))
+
+   ;; pid (Passport ID) - a nine-digit number, including leading zeroes.
+   (s-matches? (rx line-start (= 9 digit) line-end)
+               (day4/passport-pid passport))
+
+   ;; cid (Country ID) - ignored, missing or not.
+   ))
+
+(message "Solution to day4/2: %s"
+         (cl-loop for passport being the elements of day4/input
+                  count (day4/properly-validate passport)))
diff --git a/users/tazjin/aoc2020/solution-day5.el b/users/tazjin/aoc2020/solution-day5.el
new file mode 100644
index 0000000000..9bba322902
--- /dev/null
+++ b/users/tazjin/aoc2020/solution-day5.el
@@ -0,0 +1,61 @@
+;; Advent of Code 2020 - Day 5
+
+(require 'cl-lib)
+(require 'dash)
+(require 'f)
+(require 'ht)
+(require 's)
+(require 'seq)
+
+(defvar day5/input
+  (-filter (lambda (s) (not (seq-empty-p s)))
+           (s-lines (f-read "/tmp/aoc/day5.txt"))))
+
+(defun day5/lower (sequence)
+  (seq-subseq sequence 0 (/ (length sequence) 2)))
+
+(defun day5/upper (sequence)
+  (seq-subseq sequence (/ (length sequence) 2)))
+
+(defun day5/seat-id (column row)
+  (+ column (* 8 row)))
+
+(defun day5/find-seat (boarding-pass)
+  (let ((rows (number-sequence 0 127))
+        (columns (number-sequence 0 7)))
+    (cl-loop for char across boarding-pass
+             do (pcase char
+                  (?F (setq rows (day5/lower rows)))
+                  (?B (setq rows (day5/upper rows)))
+                  (?R (setq columns (day5/upper columns)))
+                  (?L (setq columns (day5/lower columns))))
+             finally return (day5/seat-id (car columns) (car rows)))))
+
+;; Puzzle 1
+
+(message "Solution to day5/1: %s"
+         (cl-loop for boarding-pass in day5/input
+                  maximize (day5/find-seat boarding-pass)))
+
+;; Puzzle 2
+
+(defun day5/all-seats-in (row)
+  (-map (lambda (column) (day5/seat-id column row))
+        (number-sequence 0 7)))
+
+(message "Solution to day5/2: %s"
+         (let ((all-seats (ht-create)))
+           (-each (-mapcat #'day5/all-seats-in (number-sequence 1 126))
+             (lambda (seat) (ht-set all-seats seat nil)))
+
+           (cl-loop for boarding-pass in day5/input
+                    do (ht-remove all-seats (day5/find-seat boarding-pass))
+
+                    ;; Remove seats that lack adjacent entries, those
+                    ;; are missing on the plane.
+                    finally return
+                    (car
+                     (-filter (lambda (seat)
+                                (and (not (ht-contains? all-seats (- seat 1)))
+                                     (not (ht-contains? all-seats (+ seat 1)))))
+                              (ht-keys all-seats))))))
diff --git a/users/tazjin/aoc2020/solution-day6.el b/users/tazjin/aoc2020/solution-day6.el
new file mode 100644
index 0000000000..8179c79af2
--- /dev/null
+++ b/users/tazjin/aoc2020/solution-day6.el
@@ -0,0 +1,40 @@
+;; Advent of Code 2020 - Day 6
+
+(require 'cl-lib)
+(require 'dash)
+(require 'f)
+(require 'ht)
+(require 's)
+
+(defvar day6/input (s-split "\n\n" (f-read "/tmp/aoc/day6.txt") t)
+  "Input, split into groups (with people in each group still distinct)")
+
+;; Puzzle 1
+
+(defun day6/count-answers (group-answers)
+  "I suspect doing it this way will be useful in puzzle 2."
+  (let ((table (ht-create)))
+    (-each group-answers
+      (lambda (answer)
+        (cl-loop for char across answer
+                 do (ht-set table char (+ 1 (or (ht-get table char)
+                                                0))))))
+    table))
+
+(message "Solution to day6/1: %s"
+         (cl-loop for group being the elements of day6/input
+                  sum (length
+                       (ht-keys
+                        (day6/count-answers (s-lines group))))))
+
+;; Puzzle 2
+
+(defun day6/count-unanimous-answers (answers)
+  (ht-reject (lambda (_key value) (not (= value (length answers))))
+             (day6/count-answers answers)))
+
+(message "Solution to day6/2: %s"
+         (cl-loop for group being the elements of day6/input
+                  sum (length
+                       (ht-keys
+                        (day6/count-unanimous-answers (s-split "\n" group t))))))
diff --git a/users/tazjin/aoc2020/solution-day7.el b/users/tazjin/aoc2020/solution-day7.el
new file mode 100644
index 0000000000..251a85fede
--- /dev/null
+++ b/users/tazjin/aoc2020/solution-day7.el
@@ -0,0 +1,92 @@
+;; Advent of Code 2020 - Day 7
+
+(require 'cl-lib)
+(require 'dash)
+(require 'f)
+(require 's)
+(require 'ht)
+
+(defvar day7/input
+  (s-lines (s-chomp (f-read "/tmp/aoc/day7.txt"))))
+
+(defun day7/parse-bag (input)
+  (string-match (rx line-start
+                    (group (one-or-more (or letter space)))
+                    "s contain "
+                    (group (one-or-more anything))
+                    "." line-end)
+                input)
+  (cons (match-string 1 input)
+        (-map
+         (lambda (content)
+           (unless (equal content "no other bags")
+             (progn
+               (string-match
+                (rx (group (one-or-more digit))
+                    space
+                    (group (one-or-more anything) "bag"))
+                content)
+               (cons (match-string 2 content)
+                     (string-to-number (match-string 1 content))))))
+         (s-split ", " (match-string 2 input)))))
+
+(defun day7/id-or-next (table bag-type)
+  (unless (ht-contains? table bag-type)
+    (ht-set table bag-type (length (ht-keys table))))
+  (ht-get table bag-type))
+
+(defun day7/build-graph (input &optional flip)
+  "Represent graph mappings directionally using an adjacency
+  matrix, because that's probably easiest.
+
+  By default an edge means 'contains', with optional argument
+  FLIP edges are inverted and mean 'contained by'."
+
+  (let ((bag-mapping (ht-create))
+        (graph (let ((length (length input)))
+                 (apply #'vector
+                        (-map (lambda (_) (make-vector length 0)) input)))))
+    (cl-loop for bag in (-map #'day7/parse-bag input)
+             for bag-id = (day7/id-or-next bag-mapping (car bag))
+             do (-each (-filter #'identity (cdr bag))
+                  (pcase-lambda (`(,contained-type . ,count))
+                    (let ((contained-id (day7/id-or-next bag-mapping contained-type)))
+                      (if flip
+                          (aset (aref graph contained-id) bag-id count)
+                        (aset (aref graph bag-id) contained-id count))))))
+    (cons bag-mapping graph)))
+
+;; Puzzle 1
+
+(defun day7/find-ancestors (visited graph start)
+  (ht-set visited start t)
+  (cl-loop for bag-count being the elements of (aref graph start)
+           using (index bag-id)
+           when (and (> bag-count 0)
+                     (not (ht-contains? visited bag-id)))
+           do (day7/find-ancestors visited graph bag-id)))
+
+(message
+ "Solution to day7/1: %s"
+ (pcase-let* ((`(,mapping . ,graph) (day7/build-graph day7/input t))
+              (shiny-gold-id (ht-get mapping "shiny gold bag"))
+              (visited (ht-create)))
+   (day7/find-ancestors visited graph shiny-gold-id)
+   (- (length (ht-keys visited)) 1)))
+
+;; Puzzle 2
+
+(defun ht-find-by-value (table value)
+  (ht-find (lambda (_key item-value) (equal item-value value)) table))
+
+(defun day7/count-contained-bags (mapping graph start)
+  (cl-loop for bag-count being the elements of (aref graph start)
+           using (index bag-id)
+           when (> bag-count 0)
+           sum (+ bag-count
+                  (* bag-count (day7/count-contained-bags mapping graph bag-id)))))
+
+(message "Solution to day7/2: %s"
+         (pcase-let* ((`(,mapping . ,graph) (day7/build-graph day7/input))
+                      (shiny-gold-id (ht-get mapping "shiny gold bag")))
+           (day7/count-contained-bags mapping graph shiny-gold-id)))
diff --git a/users/tazjin/aoc2020/solution-day8.el b/users/tazjin/aoc2020/solution-day8.el
new file mode 100644
index 0000000000..591a07fbf3
--- /dev/null
+++ b/users/tazjin/aoc2020/solution-day8.el
@@ -0,0 +1,63 @@
+;; Advent of Code 2020 - Day
+
+(require 'cl-lib)
+(require 'dash)
+(require 'f)
+(require 's)
+
+(setq day8/input
+      (apply #'vector
+             (-map (lambda (s)
+                     (pcase-let ((`(,op ,val) (s-split " " s t)))
+                       (cons (intern op) (string-to-number val))))
+                   (s-lines (s-chomp (f-read "/tmp/aoc/day8.txt"))))))
+
+(defun day8/step (code position acc)
+  (if (>= position (length code))
+      (cons 'final acc)
+
+    (let ((current (aref code position)))
+      (aset code position :done)
+      (pcase current
+        (:done (cons 'loop acc))
+        (`(nop . ,val) (cons (+ position 1) acc))
+        (`(acc . ,val) (cons (+ position 1) (+ acc val)))
+        (`(jmp . ,val) (cons (+ position val) acc))))))
+
+;; Puzzle 1
+
+(message "Solution to day8/1: %s"
+         (let ((code (copy-sequence day8/input))
+               (position 0)
+               (acc 0))
+           (cl-loop for next = (day8/step code position acc)
+                    when (equal 'loop (car next)) return (cdr next)
+                    do (setq position (car next))
+                    do (setq acc (cdr next)))))
+
+;; Puzzle 2
+
+(defun day8/flip-at (code pos)
+  (pcase (aref code pos)
+    (`(nop . ,val) (aset code pos `(jmp . ,val)))
+    (`(jmp . ,val) (aset code pos `(nop . ,val)))
+    (other (error "Unexpected flip op: %s" other))))
+
+(defun day8/try-flip (flip-at code position acc)
+  (day8/flip-at code flip-at)
+  (cl-loop for next = (day8/step code position acc)
+           when (equal 'loop (car next)) return nil
+           when (equal 'final (car next)) return (cdr next)
+           do (setq position (car next))
+           do (setq acc (cdr next))))
+
+(message "Solution to day8/2: %s"
+         (let ((flip-options (cl-loop for op being the elements of day8/input
+                                      using (index idx)
+                                      for opcode = (car op)
+                                      when (or (equal 'nop opcode)
+                                               (equal 'jmp opcode))
+                                      collect idx)))
+           (cl-loop for flip-at in flip-options
+                    for result = (day8/try-flip flip-at (copy-sequence day8/input) 0 0)
+                    when result return result)))