advent-of-code-2020

0.11.0


Advent of Code 2020

dependencies

org.clojure/clojure
1.10.1
org.clojure/math.combinatorics
0.1.6
shams/priority-queue
0.1.2
criterium
0.4.6
instaparse
1.4.10
org.clojure/core.logic
1.0.0
aysylu/loom
1.0.2
com.climate/claypoole
1.1.4



(this space intentionally left almost blank)
 
(ns advent-of-code-2020.day-10
  (:require [clojure.test :refer [deftest testing is]]
            [clojure.string :refer [split-lines]]
            [clojure.java.io :as io]))

Day 10: Adapter Array

Adapters have different voltanges and can be chained together. Adapters can only cope with differences between 1 and 3 volts. Initial output voltage is 0, final output voltage is max + 3.

(def example-adapters
  [16 10 15 5 1 11 7 19 6 12 4])
(def example-adapters-2
  [28 33 18 42 31 14 46 20 48 47 24 23 49 45 19 38 39 11 1 32 25 35 8 17 7 9 4 2 34 10 3])
(def output-voltage 0)

Final device output is 3 plus the max of your adapters.

(defn device-voltage
  [adapters]
  (+ 3 (reduce max adapters)))

You have to use all adapters, in which case the only solution is just a sorted list.

(defn voltage-differences
  [adapters]
  (->> (conj adapters output-voltage (device-voltage adapters))
       sort
       (partition 2 1)
       (map #(- (second %) (first %)))))
(deftest voltage-differences-tests
  (is (= {1 7 3 5} (frequencies (voltage-differences example-adapters))))
  (is (= {1 22 3 10} (frequencies (voltage-differences example-adapters-2)))))

Part one answer relies on the product of two counts from frequencies.

(defn product
  [diffs]
  (apply * (vals (select-keys (frequencies diffs) [1 3]))))

Get the list of numbers.

(defn load-input
  []
  (->> "input/day_10.txt"
       io/resource
       slurp
       split-lines
       (map read-string)))
(deftest product-differences-tests
  (is (= 2070 (-> (load-input) voltage-differences product))))

Part 2

Count the number of possible chains of adapters between the input and your device, bearing in mind adapters can only support 1 to 3 volt differences.

So this is either extremely dumb or showing off. The intuition here is very simple: you can't avoid traversing differences of 3 volts, so you're not actually interested in them because there's no branching. All you're interested in are runs of 1 volt differences (input data only seems to have 1 and 3, fortunately).

Turns out there's a very simple trick here, which is to use this sequence.

That is, the number of n-tosses having a run of 3 or more heads - heads in this case are gaps in the adapter chain of n adapters. These runs are invalid so if we subtract them from 2^n (which would be the world in which all adapters could plug into all others), we get the right answer.

(defonce tribonacci
  (memoize (fn [n]
             (case n
               0 0
               1 0
               2 1
               3 3
               (- (* 3 (tribonacci (- n 1)))
                  (tribonacci (- n 2))
                  (tribonacci (- n 3))
                  (* 2 (tribonacci (- n 4))))))))

Counts the number of valid chains in adapters.

(defn count-chains
  [adapters]
  (->> adapters
       voltage-differences
       (partition-by identity) ;; get runs of the same difference
       (filter (comp #{1} first)) ;; we only care about 1s
       (map count) ;; count the length of the runs
       (map #(- (Math/pow 2 (dec %)) ;; possible combinations
                (tribonacci (max 0 (- % 2))))) ;; invalid combinations
       (map biginteger) ;; result overflows int
       (reduce *)))
(deftest count-chains-test
  (is (= 1 (count-chains [1])))
  (is (= 2 (count-chains [1 2])))
  (is (= 4 (count-chains [1 2 3])))
  (is (= 7 (count-chains [1 2 3 4])))
  (is (= 13 (count-chains [1 2 3 4 5])))
  (is (= 24 (count-chains [1 2 3 4 5 6])))
  (is (= 44 (count-chains [1 2 3 4 5 6 7])))
  (is (= 81 (count-chains [1 2 3 4 5 6 7 8])))
  (is (= 1 (count-chains [1 4 5])))
  (is (= 2 (count-chains [1 2 5])))
  (is (= 1 (count-chains [3 4 7])))
  (is (= 4 (count-chains [1 2 5 6 7])))
  (is (= 16 (count-chains [1 2 3 5 6 7 8])))
  (is (= 8 (count-chains example-adapters)))
  (is (= 19208 (count-chains example-adapters-2)))
  (is (= 24179327893504 (count-chains (load-input)))))
 
(ns advent-of-code-2020.day-11
  (:require [clojure.test :refer [with-test is deftest]]
            [clojure.string :refer [split]]
            [com.climate.claypoole :as cp]
            [clojure.java.io :as io]))

Day 11: Seating System

(def example-layout
  "L.LL.LL.LL
LLLLLLL.LL
L.L.L..L..
LLLL.LL.LL
L.LL.LL.LL
L.LLLLL.LL
..L.L.....
LLLLLLLLLL
L.LLLLLL.L
L.LLLLL.LL")

Read layout as a string into a two-dimensional grid of chars with the first dimension addressing the row, the second the column.

(with-test
  (defn initial-layout
    [layout]
    (mapv vec (split layout #"\n")))
  (is (= \L (-> example-layout initial-layout (get-in [0 0]))))
  (is (= \. (-> example-layout initial-layout (get-in [0 1]))))
  (is (= \L (-> "LLL" initial-layout (get-in [0 2])))))

Retrieve the contents of the grid at row,col.

(with-test
  (defn seat
    [layout row col]
    (get-in layout [row col] nil))
  (is (= \. (-> example-layout initial-layout (seat 6 0))))
  (is (= \. (-> example-layout initial-layout (seat 6 1)))))

Returns a sequence containing the contents of cells adjacent to row,col.

(with-test
  (def adjacent-seats
    (memoize
     (fn [layout row col]
       (for [drow [-1 0 1]
             dcol [-1 0 1]
             :when (not= drow dcol 0)
             :let [seat (seat layout (+ row drow) (+ col dcol))]
             :when seat]
         seat))))
  (let [layout (initial-layout "#L#\nL.L\n#L#")]
    (is (= (seq "LL.") (-> layout (adjacent-seats 0 0))))
    (is (= (seq "#L#LL#L#") (-> layout (adjacent-seats 1 1))))))

Is this seat occupied?

(defn occupied?
  [seat]
  (= \# seat))

Does this seat have four or more adjacent occupied seats?

(defn crowded?
  [neighbours]
  (->> neighbours
       (filter occupied?)
       (take 4)
       (count)
       (= 4)))

Does this seat only have unoccupied adjacent seats?

(defn quiet?
  [neighbours]
  (every? (complement occupied?) neighbours))

Is this seat empty?

(defn free?
  [seat]
  (= \L seat))

Returns a vector [row col new-value] indicating that the seat at the specified row and col should be updated to new-value.

(with-test
  (defn change-seat
    [layout row col]
    (let [seat (seat layout row col)
          neighbours (adjacent-seats layout row col)]
      (cond
        (and (free? seat)
             (quiet? neighbours)) [row col \#]
        (and (occupied? seat)
             (crowded? neighbours)) [row col \L])))
  (let [quiet (initial-layout "LLL\nLLL\nLLL")
        busy (initial-layout "###\n###\n###")]
    (is (= [1 1 \#] (change-seat quiet 1 1)))
    (is (= [1 1 \L] (change-seat busy 1 1)))
    (is (nil? (change-seat busy 0 0)))))
(def example-rounds
  [example-layout
   "#.##.##.##
#######.##
#.#.#..#..
####.##.##
#.##.##.##
#.#####.##
..#.#.....
##########
#.######.#
#.#####.##"
   "#.LL.L#.##
#LLLLLL.L#
L.L.L..L..
#LLL.LL.L#
#.LL.LL.LL
#.LLLL#.##
..L.L.....
#LLLLLLLL#
#.LLLLLL.L
#.#LLLL.##"
   "#.##.L#.##
#L###LL.L#
L.#.#..#..
#L##.##.L#
#.##.LL.LL
#.###L#.##
..#.#.....
#L######L#
#.LL###L.L
#.#L###.##"
   "#.#L.L#.##
#LLL#LL.L#
L.L.L..#..
#LLL.##.L#
#.LL.LL.LL
#.LL#L#.##
..L.L.....
#L#LLLL#L#
#.LLLLLL.L
#.#L#L#.##"
   "#.#L.L#.##
#LLL#LL.L#
L.#.L..#..
#L##.##.L#
#.#L.LL.LL
#.#L#L#.##
..L.L.....
#L#L##L#L#
#.LLLLLL.L
#.#L#L#.##"])
(def cpu-pool (cp/threadpool (cp/ncpus)))

Update all seats in layout for one round.

(with-test
  (defn all-change
    [layout]
    (->> (cp/upfor cpu-pool
                   [row (range 0 (count layout))
                    col (range 0 (count (first layout)))]
                   (change-seat layout row col))
         (filter some?)
         (reduce (fn [new-layout [row col change]]
                   (assoc-in new-layout [row col] change))
                 layout)))
  (dotimes [i (dec (count example-rounds))]
    (is (= (initial-layout (example-rounds (inc i)))
           (all-change (initial-layout (example-rounds i)))))))

Iteratively call all-change on layout until the result converges.

(with-test
  (defn converge
    [layout]
    (reduce (fn [prev-layout layout]
              (if (= prev-layout layout)
                (reduced layout)
                layout))
            (iterate all-change layout)))
  (is (= (initial-layout (last example-rounds))
         (converge (initial-layout example-layout)))))

Get the input layout.

(defn load-input
  []
  (slurp (io/resource "input/day_11.txt")))
(with-test
  (defn eventual-occupants
    [layout]
    (->> layout
         (initial-layout)
         (converge)
         (flatten)
         (filter occupied?)
         count))
  (is (= 37 (eventual-occupants example-layout)))
  (is (= 0 (eventual-occupants (load-input)))))
 
(ns advent-of-code-2020.day-1
  (:require [clojure.test :refer [deftest testing is]]
            [clojure.math.combinatorics :refer [combinations]]
            [criterium.core :refer [quick-bench]]))

Day 1: Report Repair (https://adventofcode.com/2020/day/1)

Find two entries in the input that sum to 2020, and multiply those numbers together.

Puzzle inputs vary by user so you have to be authenticated and can't just fetch them on demand, so let's just cut and paste.

(def input
  [1822 1917 1642 1617 1941 1740 1529 1896 1880 568 1897 1521 1832 1936 611 1475 1950 1895 1532 1721 1498 1905 1770 1845 2003 1854 1705 1916 1913 1956 1798 1823 1955 1713 1942 1710 1696 1590 1966 1476 1800 1672 1533 1524 1957 1923 1545 534 1707 1760 1104 1471 1947 1802 1525 1931 1653 1608 1937 1977 1598 1470 1794 1488 1786 1652 1482 1603 1667 1245 1478 667 1948 1885 547 1971 1795 1910 1571 1711 1727 1987 1597 1586 1661 1893 1873 1827 1561 2006 1782 1813 2000 1592 1714 1849 1501 1809 1751 1935 1692 1697 1878 1502 1738 1731 1682 1690 1499 1641 1925 1996 1972 1886 1836 1747 1841 1668 715 1698 1859 1637 1477 1785 1695 1702 1944 1631 1771 1623 1892 1466 1834 1899 201 1801 1978 1830 1591 1673 1949 1846 1677 1657 1576 1817 1851 1894 1754 1604 1568 1730 1985 1614 1980 1554 1997 1960 1983 1848 1883 1968 1729 1716 628 1472 1676 1943 1821 1681 1619 1644 842 1492 1633 1921 775 1861 1584 1974 585 1898 1560 1708 1927 1563 1872 1876 1865 1535 1994 1756 1662 1621 1993 1825 1679 1959 1691 1875])

The naive solution is just grab every combination of n items and test them all until we find one that sums to 2020.

(defn naive-solution
  ([input n]
   (first (for [xs (combinations input n)
                :let [sum (apply + xs)]
                :when (= sum 2020)]
            (apply * xs))))
  ([input]
   (naive-solution input 2)))

The simplest recursive solution short circuits a bit more and so is a little faster with bigger inputs and subsets.

(defn recursive-solution
  ([input n sum product]
   (cond
     (and (zero? n)
          (= sum 2020)) product
     (or (zero? n)
         (> sum 2020)) nil
     :else (some identity
                 (map-indexed
                  (fn [i x]
                    (recursive-solution (concat (take i input)
                                                (drop (inc i) input))
                                        (dec n)
                                        (+ sum x)
                                        (* product x)))
                  input))))
  ([input n]
   (recursive-solution input n 0 1))
  ([input]
   (recursive-solution input 2)))

Testing

Some test cases. It's important that we don't allow edge cases like summing a number with itself.

(deftest solution-tests
  (doseq [solution [naive-solution recursive-solution]]
    (testing (clojure.repl/demunge (str solution))
      (testing "doesn't find the sum if list is too short"
        (is (nil? (solution [1010]))))
      (testing "doesn't allow numbers to sum with themselves"
        (is (nil? (solution [1010 1 2 3]))))
      (testing "returns correct product for valid lists"
        (is (= (* 1010 1010) (solution [1010 1010])))
        (is (= 514579 (solution [1721 979 366 299 675 1456])))
        (is (= 964875 (solution input))))
      (testing "allows combinations of arbitrary size"
        (is (= 241861950 (solution [1721 979 366 299 675 1456] 3)))
        (is (= 158661360 (solution input 3)))))))

Generate a test sequence guaranteed to contain a subset with length n that sums to 2020.

(defn random-input
  [length n]
  (let [[xs rest] (->> (partial rand-int 2100)
                       repeatedly
                       (take (dec length))
                       (split-at (dec n)))
        ;; guarantee at least one hit
        y (apply - 2020 xs)]
    (shuffle (concat [y] xs rest))))

Benchmarks

Comparing the performance of the naive and recursive approaches. Recorded on a Linux VM running on a Chromebook, please don't laugh.

Evaluation count : 6 in 6 samples of 1 calls. Execution time mean : 118.488980 ms Execution time std-deviation : 30.464186 ms Execution time lower quantile : 81.965276 ms ( 2.5%) Execution time upper quantile : 148.631309 ms (97.5%) Overhead used : 31.894745 ns

(comment (quick-bench (recursive-solution (random-input 10000 3) 3)))

Evaluation count : 12 in 6 samples of 2 calls. Execution time mean : 4.233666 sec Execution time std-deviation : 9.750836 sec Execution time lower quantile : 61.125691 ms ( 2.5%) Execution time upper quantile : 21.115343 sec (97.5%) Overhead used : 31.894745 ns

(comment (quick-bench (naive-solution (random-input 100000 3) 3)))
 
(ns advent-of-code-2020.day-2
  (:require [clojure.java.io :as io]
            [clojure.spec.alpha :as s]
            [clojure.string :refer [split-lines]]
            [clojure.test :refer [deftest testing is]]))

Day 2: Password Philosophy

Read lines of password policies and passwords, and check if the password matches the policy. Each line is of the form:

a-b c: password

Where a and b are parameters used to validate the usage of character c in the password.

Fetch the input from a text file.

(defn load-input
  []
  (slurp (io/resource "input/day_2.txt")))

Parsing

We'll use Spec to parse the various parts of each line of input. The rules here are a little loose and wouldn't work if we wanted to gen up random input but we're not interested in that right now.

(s/def ::bound (s/+ (set "0123456789")))
(s/def ::separator (s/+ (set "-: ")))
(s/def ::password (s/+ (set "abcdefghijklmnopqrstuvwxyz")))
(s/def ::password-line
  (s/cat
   :a ::bound
   :sep ::separator
   :b ::bound
   :sep ::separator
   :char char?
   :sep ::separator
   :password ::password))

Coerce a sequence of digit characters in chars into an Integer.

(defn coerce-int
  [chars]
  (Integer/parseInt (apply str chars)))

Parse a single line of input in line into a map holding the :min, :max, :char and :password.

(defn parse-line
  [line]
  (let [{:keys [a b char password]} (s/conform ::password-line (seq line))]
    {:a (coerce-int a)
     :b (coerce-int b)
     :char char
     :password password ;; don't bother coercing to a string
     }))

Check if the password matches the sled rental policy.

(defn sled-rental-policy
  [{:keys [a b char password]}]
  (let [freqs (frequencies password)]
    (<= a (freqs char 0) b)))

Check if the password matches Official Toboggan Corporate policy.

(defn official-toboggan-corporate-policy
  [{:keys [a b char password]}]
  (let [a? (= char (nth password (dec a)))
        b? (= char (nth password (dec b)))]
    (if a? (not b?) b?)))

Does the line contain a valid password for its rule?

(defn valid-line?
  [policy line]
  (policy (parse-line line)))

Counts the number of valid passwords in the input.

(defn count-valid-passwords
  [policy]
  (->> (load-input)
       (split-lines)
       (filter (partial valid-line? policy))
       (count)))
(deftest valid-line-tests
  (testing "sled rental policy"
    (is (valid-line? sled-rental-policy "1-3 a: abcde"))
    (is (not (valid-line? sled-rental-policy "1-3 b: cdefg")))
    (is (valid-line? sled-rental-policy "2-9 c: ccccccccc")))
  (testing "official toboggan corporate policy"
    (is (valid-line? official-toboggan-corporate-policy "1-3 a: abcde"))
    (is (not (valid-line? official-toboggan-corporate-policy "1-3 b: cdefg")))
    (is (not (valid-line? official-toboggan-corporate-policy "2-9 c: ccccccccc")))))
(deftest count-valid-passwords-test
  (is (= 628 (count-valid-passwords sled-rental-policy)))
  (is (= 705 (count-valid-passwords official-toboggan-corporate-policy))))
 
(ns advent-of-code-2020.day-3
  (:require [clojure.java.io :as io]
            [clojure.string :refer [split-lines]]
            [clojure.test :refer [deftest testing is]]))

Day 3: Toboggan Trajectory

Navigation a toboggan from the top left of a world given as input like:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

Where . is open snow and # is a tree.

Fetch the input from a text file.

(defn load-input
  []
  (slurp (io/resource "input/day_3.txt")))

World

The world is given as a multi-line string representing a grid. . represents open snow and # represents a tree. The world holds the current coordinates of the toboggan in its :x and :y keys.

(defn world
  [terrain]
  (let [m (split-lines terrain) 
        width (.length (first m))
        height (count m)]
    {:terrain m
     :width width
     :height height
     :x 0
     :y 0}))

Return the contents of the world at the current toboggan location.

(defn loc
  [{:keys [terrain width x y]}]
  (let [x (mod x width)
        y (+ y (quot x width))]
    (when-let [row (get terrain y nil)]
      (.charAt row x))))

Is there a tree at the current toboggan location?

(defn tree?
  [w]
  (= \# (loc w)))

Move the toboggan in world w by the deltas dx and dy.

(defn move
  [w dx dy]
  (-> w
      (update :x + dx)
      (update :y + dy)))

Is the current toboggan location on the slopes, or has it gone beyond the bottom?

(defn on-piste?
  [w]
  (< (:y w) (:height w)))

Return a lazy sequence of updates to world w as the toboggan follows a slope with deltas dx and dy.

(defn follow-slope
  [w dx dy]
  (->> w
       (iterate #(move % dx dy))
       (take-while on-piste?)))

Count the number of trees passed by the toboggan as it travels world w on the slope with deltas dx and dy.

(defn count-trees
  [w dx dy]
  (->> (follow-slope w dx dy)
       (filter tree?)
       count))

Testing

(def test-terrain
  "..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#")
(deftest slope-test
  (testing "test terrain"
    (let [w (world test-terrain)]
      (is (= 7 (count-trees w 3 1)))
      (is (= 336 (* (count-trees w 1 1)
                    (count-trees w 3 1)
                    (count-trees w 5 1)
                    (count-trees w 7 1)
                    (count-trees w 1 2))))))
  (testing "input"
    (let [w (world (load-input))]
      (is (= 195 (count-trees w 3 1)))
      (is (= 3772314000 (* (count-trees w 1 1)
                           (count-trees w 3 1)
                           (count-trees w 5 1)
                           (count-trees w 7 1)
                           (count-trees w 1 2)))))))
 
(ns advent-of-code-2020.day-4
  (:require [clojure.java.io :as io]
            [clojure.string :refer [split]]
            [instaparse.core :as insta]
            [clojure.spec.alpha :as s]
            [clojure.test :refer [deftest testing is]]))

Day 4: Passport Processing

Validate passports with the following fields:

  • byr (Birth Year)
  • iyr (Issue Year)
  • eyr (Expiration Year)
  • hgt (Height)
  • hcl (Hair Color)
  • ecl (Eye Color)
  • pid (Passport ID)
  • cid (Country ID)

In part one of the puzzle, we write rules to validate the presence of all keys except cid. In part two we more strictly validate the contents of these keys.

Example of scanned passport data. Each passport is a series of key value pairs separated by spaces or newlines. Records are separated by blank lines.

(def example-input
  "ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
byr:1937 iyr:2017 cid:147 hgt:183cm
iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
hcl:#cfa07d byr:1929
hcl:#ae17e1 iyr:2013
eyr:2024
ecl:brn pid:760753108 byr:1931
hgt:179cm
hcl:#cfa07d eyr:2025 pid:166559648
iyr:2011 ecl:brn hgt:59in")
(def invalid-passports
  "eyr:1972 cid:100
hcl:#18171d ecl:amb hgt:170 pid:186cm iyr:2018 byr:1926
iyr:2019
hcl:#602927 eyr:1967 hgt:170cm
ecl:grn pid:012533040 byr:1946
hcl:dab227 iyr:2012
ecl:brn hgt:182cm pid:021572410 eyr:2020 byr:1992 cid:277
hgt:59cm ecl:zzz
eyr:2038 hcl:74454a iyr:2023
pid:3556412378 byr:2007")
(def valid-passports
  "pid:087499704 hgt:74in ecl:grn iyr:2012 eyr:2030 byr:1980
hcl:#623a2f
eyr:2029 ecl:blu cid:129 byr:1989
iyr:2014 pid:896056539 hcl:#a97842 hgt:165cm
hcl:#888785
hgt:164cm byr:2001 iyr:2015 cid:88
pid:545766238 ecl:hzl
eyr:2022
iyr:2010 hgt:158cm hcl:#b6652a ecl:blu byr:1944 eyr:2021 pid:093154719")

Parsing

Time to break out the big guns. We'll define a grammar in Instaparse instead of trying to do it all in spec this time.

Do the lowest common denominator for parsing both parts of the task.

(def parse
  (insta/parser
   "passport = field (<field-separator> field)* <field-separator>?
    <field-separator> = #'\\s'
    <field> = byr | iyr | eyr | hgt | hcl | ecl | pid | cid
    byr = <'byr:'> year
    iyr = <'iyr:'> year
    eyr = <'eyr:'> year
    hgt = <'hgt:'> height
    hcl = <'hcl:'> color
    ecl = <'ecl:'> color
    pid = <'pid:'> string
    cid = <'cid:'> id
    <year> = integer
    height = integer unit?
    <unit> = 'cm' | 'in'
    <color> = hex-color | color-name
    <id> = #'[0-9]+'
    <hex-color> = <'#'>? hexadecimal
    <color-name> = string
    <string> = #'\\S+'
    integer = #'[1-9][0-9]*'
    <hexadecimal> = #'[0-9a-f]+'"
   :partial true))

Do a little cleanup on the parse tree to make it nicer to validate later.

(defn transform
  [parse-tree]
  (insta/transform
   {:integer read-string
    :height vector
    :passport (comp (partial into {}) vector)}
   parse-tree))

Validation

We use two sets of specs, one loose for part on of the task, which just validates the presence of the right keys, another strict for the second part.

(s/def :loose/passport (s/keys :req-un [:loose/byr :loose/iyr :loose/eyr :loose/hgt :loose/hcl :loose/ecl :loose/pid]
                               :opt-un [:loose/cid]))
(s/def :strict/byr (s/int-in 1920 2003))
(s/def :strict/iyr (s/int-in 2010 2021))
(s/def :strict/eyr (s/int-in 2020 2031))
(s/def ::cm (s/int-in 150 194))
(s/def ::in (s/int-in 59 77))
(s/def :strict/hgt (s/or :cm (s/tuple ::cm #{"cm"})
                         :in (s/tuple ::in #{"in"})))
(s/def :strict/pid (fn [s] (re-matches #"[0-9]{9}" s)))
(s/def :strict/hcl (fn [s] (re-matches #"#[0-9a-f]{6}" s)))
(s/def :strict/ecl #{"amb" "blu" "brn" "gry" "grn" "hzl" "oth"})
(s/def :strict/passport (s/keys :req-un [:strict/byr :strict/iyr :strict/eyr :strict/hgt :strict/hcl :strict/ecl :strict/pid]
                                :opt-un [:strict/cid]))

Is the parsed passport valid given the rules defined by spec?

(defn valid-passport?
  [spec passport]
  (s/valid? spec passport))

How many valid passports are there in input as defined by spec?

(defn count-valid-passports
  [spec input]
  (->> (split input #"\n{2,}")
       (map parse)
       (map transform)
       (filter (partial valid-passport? spec))
       count))

Input

Fetch the input from a text file.

(defn load-input
  []
  (slurp (io/resource "input/day_4.txt")))

Testing

(deftest count-valid-passports-test
  (testing "loose parsing"
    (is (= 2 (count-valid-passports :loose/passport example-input)))
    (is (= 219 (count-valid-passports :loose/passport (load-input)))))
  (testing "strict parsing"
    (is (= 0 (count-valid-passports :strict/passport invalid-passports)))
    (is (= 4 (count-valid-passports :strict/passport valid-passports)))
    (is (= 127 (count-valid-passports :strict/passport (load-input))))))
(deftest spec-tests
  (is (s/valid? :strict/byr 2002))
  (is (not (s/valid? :strict/byr 2003)))
  (is (s/valid? :strict/hgt [60 "in"]))
  (is (s/valid? :strict/hgt [190 "cm"]))
  (is (not (s/valid? :strict/hgt [190 "in"])))
  (is (not (s/valid? :strict/hgt [190])))
  (is (s/valid? :strict/hcl "#123abc"))
  (is (not (s/valid? :strict/hcl "#123abz")))
  (is (not (s/valid? :strict/hcl "123abc")))
  (is (s/valid? :strict/ecl "brn"))
  (is (not (s/valid? :strict/ecl "wat")))
  (is (s/valid? :strict/pid "000000001"))
  (is (not (s/valid? :strict/pid "0123456789"))))
 
(ns advent-of-code-2020.day-5
  (:require [clojure.test :refer [deftest testing is]]
            [clojure.java.io :as io]
            [clojure.string :refer [split-lines]]))

Day 5: Binary Boarding

Seats on a plane are identified with a binary partitioning scheme like the following:

FBFBBFFRLR

Where F means the front of the partition, B means back, L means left, R means right, in a plane with 128 rows and 8 columns.

Parsing

Trivially, F and L are zeroes, B and R are ones.

(def bits
  {\F 0
   \L 0
   \B 1
   \R 1})

Seats are just binary numbers, so translate into a long.

(defn parse-seat
  [seat]
  (loop [id 0
         [bit & seat] seat]
    (if-not bit
      id
      (recur (bit-or
              (bit-shift-left id 1)
              (bits bit))
             seat))))

Load and parse all the seats.

(defn seats
  []
  (->> "input/day_5.txt"
       io/resource
       slurp
       split-lines
       (map parse-seat)))

Puzzle

Find the highest seat ID.

(defn highest-seat-id
  [seats]
  (reduce max seats))

Find the missing seat in an otherwise empty plane.

(defn missing-seat
  [seats]
  (reduce (fn [prev seat]
            (let [expected-seat (inc prev)]
              (if (not= seat expected-seat)
                (reduced expected-seat)
                seat)))
          (sort seats)))

Find the missing seat without the initial sort.

(defn missing-seat-linear
  [seats]
  (let [reservations (boolean-array (* 8 128) false)]
    (doseq [seat seats]
      (aset reservations seat true))
    (loop [i 0
           prev false]
      (let [reserved? (aget reservations i)]
        (if (and prev (not reserved?))
          i
          (recur (unchecked-inc-int i) reserved?))))))

Testing

(deftest parse-seat-test
  (is (= 357 (parse-seat "FBFBBFFRLR")))
  (is (= 567 (parse-seat "BFFFBBFRRR")))
  (is (= 119 (parse-seat "FFFBBBFRRR")))
  (is (= 820 (parse-seat "BBFFBBFRLL"))))
(deftest highest-seat-id-test
  (is (= 826 (highest-seat-id (seats)))))
(deftest missing-seat-test
  (is (= 678 (missing-seat (seats))))
  (is (= 678 (missing-seat-linear (seats)))))

Benchmarks

Showing that the linear approach to the missing seat is substantially faster.

(comment
  (let [seats (seats)]
    ;; Evaluation count : 498 in 6 samples of 83 calls.
    ;; Execution time mean : 1.194823 ms
    ;; Execution time std-deviation : 32.001224 µs
    ;; Execution time lower quantile : 1.175012 ms ( 2.5%)
    ;; Execution time upper quantile : 1.250110 ms (97.5%)
    ;; Overhead used : 31.740990 ns

    ;; Found 1 outliers in 6 samples (16.6667 %)
    ;; low-severe	 1 (16.6667 %)
    ;; Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
    (quick-bench (missing-seat seats))

    ;; Evaluation count : 10302 in 6 samples of 1717 calls.
    ;; Execution time mean : 61.160273 µs
    ;; Execution time std-deviation : 3.010229 µs
    ;; Execution time lower quantile : 58.867294 µs ( 2.5%)
    ;; Execution time upper quantile : 66.168131 µs (97.5%)
    ;; Overhead used : 31.740990 ns

    ;; Found 1 outliers in 6 samples (16.6667 %)
    ;; low-severe	 1 (16.6667 %)
    ;; Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
    (quick-bench (missing-seat-linear seats))))
 
(ns advent-of-code-2020.day-6
  (:require [clojure.test :refer [deftest testing is]]
            [clojure.java.io :as io]
            [clojure.string :refer [split split-lines]]
            [clojure.set :refer [union intersection]]))

Day 6: Custom Customs

Fine yes/no answers given by all users in a group, from input like:

abc

a
b
c

ab
ac

a
a
a
a

b

Where each character represents one of 26 questions that were answered yes by a user. Each line is one user, each group is separated by a blank line.

Input

Load today's data.

(defn load-input
  []
  (-> "input/day_6.txt"
      io/resource
      slurp))

Split into groups, and convert each individual response within a group into a set.

(defn responses
  [input]
  (->> (split input #"\n{2,}")
       (map split-lines)
       (map (partial map set))))

Puzzle

Counting all answers to which anybody in a group has answered yes is just the union of their answers.

(def all-yesses
  union)

Sum the totals of each group depending on the provided reducer to combine group answers.

(defn count-answers
  [reducer input]
  (->> input
       responses
       (map (partial reduce reducer))
       (map count)
       (reduce +)))
(def example-group
  "abcx
abcy
abcz")
(def example-groups
  "abc
a
b
c
ab
ac
a
a
a
a
b")
(deftest all-yesses-test
  (is (= 6 (count-answers all-yesses example-group)))
  (is (= 11 (count-answers all-yesses example-groups)))
  (is (= 6778 (count-answers all-yesses (load-input)))))

Part 2

Counting answers to which all members of a group answered yes is just the intersection of their answers.

(def shared-yesses
  intersection)
(def example-aggreements
  "abc
a
b
c
ab
ac
a
a
a
a
b")
(deftest shared-yesses-test
  (is (= 6 (count-answers shared-yesses example-aggreements)))
  (is (= 3406 (count-answers shared-yesses (load-input)))))
 
(ns advent-of-code-2020.day-7
  (:require [clojure.test :refer [deftest testing is]]
            [instaparse.core :as insta]
            [clojure.string :refer [join]]
            [clojure.java.io :as io]
            [clojure.set :refer [union]]))

Day 7: Handy Haversacks

Due to recent aviation regulations, many rules (your puzzle input) are being enforced about bags and their contents; bags must be color-coded and must contain specific quantities of other color-coded bags. Apparently, nobody responsible for these regulations considered how long they would take to enforce!

(def example-rules
  "light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.")

Parsing

Use Instaparse again to make things explicit.

Parse rules into an intermediate format.

(def parse
  (insta/parser
   "rules = bag+
    bag = design <'bags contain'> (contains | empty)+ <'.'>
    design = #'[a-z]+' #'[a-z]+'
    contains = count design <'bag' 's'?>
    empty = <'no other bags'>
    count = #'[0-9]+'"
   :auto-whitespace :comma))

Transform a parse tree into a map of the form:

  :vibrant-plum {:containers #{:shiny-gold}, :contains {:faded-blue 5, :dotted-black 6}}
(defn transform
  [parse-tree]
  (insta/transform
   {:count read-string
    :design (comp keyword (partial join "-") vector)
    :empty (constantly nil)
    :contains vector
    ;; Denormalise rules so we can process them in one sequence.
    :bag (fn [bag & contents] (map (partial cons bag) contents))
    ;; Store each bags `:contains` and `:containers` relationships.
    :rules (fn [& bags]
             (reduce (fn [ret [container count contained]]
                       (if-not contained
                         ret
                         (-> ret
                             (update-in [container :contains] merge {contained count})
                             (update-in [contained :containers] (fnil conj #{}) container))))
                     {}
                     (apply concat bags)))}
   parse-tree))

Load the rules in input.

(defn rules
  [input]
  (-> input parse transform))

Containment

Returns the list of possible containers (both direct and their ancestors) for a certain design of bag under the specified rules.

(defn containers
  [rules design]
  (let [bags (-> rules design :containers)]
    (->> bags
         (map (partial containers rules))
         (reduce union bags))))

Load today's input.

(defn load-input
  []
  (-> "input/day_7.txt"
      io/resource
      slurp))
(deftest containers-tests
  (is (= #{:bright-white
           :muted-yellow
           :dark-orange
           :light-red}
         (containers (rules example-rules) :shiny-gold)))
  (is (= 222 (count (containers (rules (load-input)) :shiny-gold)))))

Contents

Recursively count the bags contained by design given the specified rules, and the bags contained by those bags etc.

(defn count-contents
  [rules design]
  (->> rules
       design
       :contains
       (map (fn [[contents count]] (+ count (* count (count-contents rules contents)))))
       (apply +)))
(deftest contents-test
  (let [rules (rules example-rules)]
    (is (= 0 (count-contents rules :faded-blue)))
    (is (= 0 (count-contents rules :dotted-black)))
    (is (= 11 (count-contents rules :vibrant-plum)))
    (is (= 7 (count-contents rules :dark-olive))))
  (is (= 13264 (count-contents (rules (load-input)) :shiny-gold))))
 
(ns advent-of-code-2020.day-8
  (:refer-clojure :exclude [compile])
  (:require [clojure.test :refer [deftest is]]
            [clojure.java.io :as io]
            [loom.graph :as g]
            [loom.alg :as ga]))

Day 8: Handheld Halting

Implement a simple computer with opcodes with a single argument: nop (no op), acc to add the argument to the accumlator, and jmp which jumps to an offset defined in arg.

We could implement code to interpret the opcodes and update the computer's state at every instructions, but it's actually much simpler just to model the computer's program counter as a traversal through a graph, with the accumulator being the weights on edges originating at acc nodes.

Simple example program with an infinite loop.

(def example-code
  "nop +0
  acc +1
  jmp +4
  acc +3
  jmp -3
  acc -99
  acc +1
  jmp -4
  acc +6")

Parse the code into a format like:

  [[:nop 0]
   [:acc 1]]
(defn instructions
  [code]
  (vec (for [[_ op arg] (re-seq #"(nop|acc|jmp) ([+-]\d+)" code)]
         [(keyword op) (read-string arg)])))

Use this value as an artificially high weight to ensure that only one edge added during debugging is ever followed.

(def debug-weight
  Integer/MAX_VALUE)

Compile the vector of instructions in code into a graph, connecting each line with its logical next line, and adding :acc arguments as edge weights.

(defn compile
  [code & {:keys [debug] :or {debug false}}]
  (apply g/weighted-digraph
         (map-indexed
          (fn [i [op arg]]
            (case op
              ;; When `debug` is `true` we add potential new edges to
              ;; turn `:nop` operators into `:jmp`s and vice-versa.
              :nop (if debug
                     {i (hash-map (+ i arg) debug-weight (inc i) 0 )}
                     [i (inc i) 0])
              :acc [i (inc i) arg]
              :jmp (if debug
                     {i (hash-map (inc i) debug-weight (+ i arg) 0)}
                     [i (+ i arg) 0])))
          (instructions code))))

Run the program and return its accumulator, either after program termination, or after meeting an infinite loop.

(defn run
  [program]
  ;; Enumerate nodes differently depending on whether the program
  ;; is complete or not.
  (->> (if (ga/connected? program)
         (ga/shortest-path program 0 (dec (count (g/nodes program))))
         (ga/bf-traverse program 0))
       (partition 2 1)
       (keep (partial apply g/weight program))
       ;; We want to follow debug edges but not count their weights.
       (remove #{debug-weight})
       (reduce +)))

Load today's data.

(defn load-input
  []
  (-> "input/day_8.txt"
      io/resource
      slurp))
(deftest run-test
  (is (= 5 (-> example-code compile run)))
  (is (= 1930 (-> (load-input) compile run)))
  (is (= 8 (-> example-code (compile :debug true) run)))
  (is (= 1688 (-> (load-input) (compile :debug true) run))))
 
(ns advent-of-code-2020.day-9
  (:require [clojure.test :refer [deftest testing is]]
            [clojure.java.io :as io]
            [clojure.string :refer [split split-lines]]
            [clojure.math.combinatorics :refer [combinations]]))

Day 9: Encoding Error

With a preamble of N numbers, validate that each subsequent number is a sum of two of the previous N numbers.

Get the list of numbers.

(defn load-input
  []
  (->> "input/day_9.txt"
       io/resource
       slurp
       split-lines
       (map read-string)))

Generate some sample data containing the numbers up to preamble-length shuffled, with data appended at the end to validate various scenarios.

(defn example-input
  [preamble-length & data]
  (concat (shuffle (range 1 (inc preamble-length))) data))

Slow implementation to check whether x is the sum of any pair of numbers in preamble.

(defn valid?
  [preamble x]
  (some #{x} (map (partial apply +) (combinations preamble 2))))

Find a number in data that violates the rule that it must be the sum of two previous numbers within a window of preamble-length. Returns nil if data is valid.

(defn check-data
  [preamble-length data]
  (let [[preamble data] (split-at preamble-length data)]
    (loop [preamble preamble
           [x & data] data]
      (when x
        (if-not (valid? preamble x)
          x
          (recur (concat (rest preamble) [x]) data))))))
(def test-input [35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576])
(deftest check-data-tests
  (is (nil? (check-data 25 (example-input 25 26))))
  (is (nil? (check-data 25 (example-input 25 49))))
  (is (= 100 (check-data 25 (example-input 25 100))))
  (is (= 50 (check-data 25 (example-input 25 50))))
  (is (nil? (check-data 25 (example-input 25 45 26))))
  (let [input (concat [20] (range 1 20) (range 21 26) [45])]
    (is (= 65 (check-data 25 (concat input [65]))))
    (is (nil? (check-data 25 (concat input [64]))))
    (is (nil? (check-data 25 (concat input [66])))))
  (is (= 127 (check-data 5 test-input)))
  (is (= 466456641 (check-data 25 (load-input)))))

Find a range of contiguous numbers in input that sum to target, and return the sum of the minimum and maximum in that range.

(defn contiguous-sum
  [target input]
  (first (for [n (range 2 (count input))
               partition (partition n 1 input)
               :when (= target (apply + partition))]
           (+ (apply min partition) (apply max partition)))))
(deftest contiguous-sum-tests
  (is (= 62 (contiguous-sum 127 test-input)))
  (let [input (load-input)]
    (is (= 55732936 (contiguous-sum (check-data 25 input) input)))))