Advent of Code, 2018, Day 3 is all about plotting overlapping rectangles on a grid.
Part 1
How many positions on the grid are covered by multiple claims?
Parsing a claim is just a matter of parsing all the integers in the string.
(defn parse-claim [raw]
; Sample Claim: "#266 @ 105,418: 27x14"
(let [matches (re-seq #"\d+" raw)
[id x1 y1 w h] (map #(Integer/parseInt %) matches)]
{:id id :x x1 :y y1 :w w :h h}))
From there we can derive the positions covered by a particular claim:
(defn explode-cells [{:keys [x y w h]}]
(for [y (range y (+ y h))
x (range x (+ x w))] [x y]))
...which allows us to count how many times each position is covered by a claim:
(defn overlay-claims [claims]
(frequencies (mapcat explode-cells claims)))
After removing cells only covered by one claim we know how many cells were covered by multiple claims:
(defn part1 [lines]
(->> (map parse-claim lines)
overlay-claims
(remove #(= 1 (second %)))
count))
That's part 1 all done.
Part 2
What is the ID of the only claim not overlapped by any others?
Part 2 Implemented with Brute Force
At first I thought that it would be easier to write the brute-force version of this algorithm. Something like comparing each claim against every other claim to find which one doesn't overlap with any others. You can probably envision the doubly-nested loop this would require in most procedural languages. In Clojure the outer loop is implemented with loop/recur and the inner loop is a map call (map check...).
(defn overlapping? [claim1 claim2]
(->> [claim1 claim2] overlapping empty? not))
(defn part2 [lines]
(let [length (dec (count lines))
claims (cycle (map parse-claim lines))]
(loop [current (first claims)
remaining (rest claims)]
(let [check (partial overlapping? current)
overlaps (remove false? (map check (take length remaining)))]
(if (empty? overlaps)
(:id current)
(recur (first remaining)
(rest remaining)))))))
In "Big O" notation this strategy can be described as O(n2), or 'quadratic'. The implications of this are that as the number of claims grows linearly, the number of computations grows by an exponential power (2 in this case). With 1300+ items in my input file there are almost 1.7 million claim comparisons to make and so this solution took over a minute to run to completion. While I'm proud of my usage of cycle, this solution is too slow for satisfaction.
Part 2 Implemented with Indexing
Given that we have an index of how many claims are on each cell we can do better. This solution seemed a bit harder to envision at first, but it turns out to be less code, and has 'Linear' Big O behavior which is so much more tennable than exponential growth.
Once we have the index of claimed cells we can iterate over each claim, looking up its cells in the index. If each cell is only ever claimed once, then that is the claim we seek and so, return its ID.
(defn part2 [lines]
(let [claims (map parse-claim lines)
counts (overlay-claims claims)]
(first
(for [claim claims
:let [cells (explode-cells claim)
counted (for [cell cells] (counts cell))
ones (filter #(= 1 %) counted)]
:when (= (count cells) (count ones))]
(:id claim)))))
For comparison, this solution runs in about half a second for the same number of items (1300+). Once again, Clojure's powerful list comprehension form is very helpful with it's :let and :when clauses. There does appear to be a doubly nested for 'loop' here, but it's not nearly as expensive since the innermost loop is simply doing fast lookups into the hashmap index.
This solution was inspired by an incredibly concise (and functionally-designed) Python solution by reddit user u794575248.