Advent of Code 2018  Day 3
Christopher Kruse Dec 3 '18 Originally published at ballpointcarrot.net on Dec 03, 2018 γ»7 min read
Solving these problems has been more difficult than I originally imagined  these aren't your FizzBuzzlevel problems; they're asking for a little bit more (especially the second halves). I got a little bit of a head start on day three, as I'm three hours behind the release of the problems, and that means I get to have some time before bed to think about them. This proved bad, as I was laying in bed thinking about solving things (which makes sleeping nigh impossible :D).
On this particular night/day, I had some issues with work (and I was oncall for my team at the time), so I got a second chance to look at them early in the morning (3amish local time). But, once I was up, I was up, so once the work problem subsided, I took a crack at getting the rest of the problem solved.
This is my first of these writeups to take place afterthefact, so let me know if there's any issues with how it was covered here vs. the previous days.
Day 3, Part 1
After we saved the cloth from the previous problem, it's now up to the Elves to figure out how to cut it optimally. The problem statement makes the first assertion that the fabric is a square of 1000x1000 square inches. This proved useful to my method of solving the problem, as you'll see below.
Each elf makes a claim on the fabric to designate a rectangle they want to cut. The claims have the following format:
#12 @ 3,4: 5x6
Which is to be interpreted as "Claim number 12
, with the top corner location of (x,y) = (3,4)
, has a width of 5
and a height of 6
."
To make sense of this, I used a regular expression to isolate the various numerical terms (while regex is a superpower, it is also a bit of a rabbithole, and I won't cover its general concepts here). Unfortunately, while Java 7+ has support for a regex feature called named capture groups, Clojure does not have that support out of the box. However, the regex with the named groups still functions, but I can only get positional arguments. I built out a function that took an input claim, and built out a rather interesting set of responses:
(defrecord Claim [claimnumber squares])
(defn converttogrid
"Converts a claim into a sequence of 'taken' squares."
[claim gridwidth]
;; Named groups would be great here, but Clojure doesn't support this natively.
(let [matcher #"#(?<claim>\d+)\s@\s(?<x>\d+),(?<y>\d+):\s(?<width>\d+)x(?<height>\d+)$"
matches (refind matcher claim)
[_ claim horiz vert width height] matches
x (Integer. horiz)
y (Integer. vert)
w (Integer. width)
h (Integer. height)
rows (take h (iterate inc y))]
(>> (map #(range (+ x (* gridwidth %)) (+ (+ x w) (* gridwidth %))) rows)
(flatten)
(set)
(Claim. (Integer. claim) ))))
Let's walk through this example a little.
The first thing we see is the definition of a clojure record (similar to a struct). Because Clojure lives on the JVM, this builds out effectively a Java class and allows you to instantiate objects of that type. The problem above could have been solved with a simple map, but I wanted to give readers of the codebase an easier way to have a mental model of the transformed claim. Additionally, this helps us keep track of the claim number, which is not important in Part 1, but makes a reappearance in Part 2.
Because we know the width of the field we'll be working with in units, I made a choice to build out the "rectangle" that a claim represented by identifying the cells that the rectangle makes up. For example, in a 5x5 grid, with a claim of #1 @ 2,0: 3x3
:
This leaves us with a set of squares: #{2 3 4 7 8 9 12 13 14}
. The practical upshot here is now we can use set logic (difference, intersection, union) to manipulate the rectangles and calculate our details for overlaps. And that's just what I did:
(defn getoverlap
"returns the amount of overlap based on calculated inputs.
Answer provided in square units matching the units entered
(for the case of the problem, square inches)."
[claims]
;; Perform intersection to find any matches, then union to combine; repeat through the list.
(loop [mappedarea (map #(converttogrid % 1000) claims)
sharedfabric #{}
intersections #{}]
(if (empty? mappedarea)
intersections
(let [intersect (set/intersection sharedfabric (:squares (first mappedarea)))
union (set/union sharedfabric (:squares (first mappedarea)))]
(recur (rest mappedarea) union (set/union intersections intersect))))))
Again we see our friends loop
and recur
from Day 2. This section highlights one of my favorite things about Clojure  maniuplating data in bulk. We pass into this a vector of claim strings, that are parsed in the function above it. In just one map
call, however, we were able to convert each of those strings into a grid area 1000x1000 wide. Once we have objects we can compute easily against, we go about calculating. :)
The set/intersection
notation is new to these examples, because clojure.set
is outside of Clojure's "Core" namespace  up until now we've been using functions packaged in clojure.core
, which is loaded by default for a Clojure runtime. Since clojure.set
isn't, we have to import it into the namespace (and in our case, provide it a nice short name to use when calling):
(ns aoc.aoc3
(:require [clojure.set :as set]))
This allows us to call functions in clojure.set
by using set/fnname
. For each iteration of the loop, we do three things:
 We check against the "shared fabric". This is done by doing a set intersection between the current rectangle (defined by
(first mappedarea)
) and all of the rectangles that came before it.  We define the "shared fabric" by adding the current rectangle to the rectangles that have already been added by a set union.
 When we cut back into the next iteration, we take the union of all found intersections in previous iterations, and the intersections we've found in this run. This piece is what gives us our total overlap at the end, as we're constantly accumulating more overlap; because it's a set, however, we're not recounting the same values, we're just including them as "overlapped" already.
Once this was done, I was able to solve Part 1 quickly.
Day 3, Part 2 (Sports Team: 0)
Now that we've found the overlapping area, our challenge is to find the rectangle which does not have any overlapping area within the list of claims. This is where keeping that claim number comes in handy.
I wanted to come up with a clever way of using the set notation used above to make a lightningquick function for processing the list of rectangles to find one with no overlap, but nothing came to mind. (If anyone finds one, let me know and I'll owe you a coffee.) Instead, I used a little more of a brute force method: compare each grid to the list of grids, and cut out when you find no set intersections. This was a little more computationally intensive (O(n^2)
), but given the count limit in the sample input, it wasn't too bad to sit for a few seconds while the laptop pounded it out.
I had one hiccup as I was putting this together  how do I managed the list of claims so that I don't run an intersection with myself? That would cause even the "no overlap" rectangle to match (as it's matching itself). What I ended up doing was breaking out the function that handled the overlapping calculation to have a check at the top that said "if you're the same rectangle by claim number, then return nil
"  this allows you to pass the full list and not worry about matching yourself.
(defn overlappingclaim [c1 c2]
(cond
(= (:claimnumber c1) (:claimnumber c2)) nil
(notempty (set/intersection (:squares c1) (:squares c2))) c2))
(defn findnooverlap
"given a set of input claims, find the claim that has no overlap
with any other claims."
[claims]
(let [gridclaims (map #(converttogrid % 1000) claims)]
(loop [idx 0 ignores #{}]
(ifnot (contains? (:claimid (nth gridclaims idx)) ignores)
(iflet [overlap (some #(overlappingclaim (nth gridclaims idx) %) gridclaims)]
(recur (inc idx) (conj ignores (:claimnumber overlap)))
(:claimnumber (nth gridclaims idx)))
(recur (inc idx) ignores)))))
Cool Clojurey things to point out here:

cond
. Think ofcond
as a bit of aif/else
on steroids. It allows you to pass a pair of items: test expression, and success expression. If the test expression passes (ie, returnstrue
), then the success expression is evaluated and returned (immediately  it does not fall through to other condition pairs). This means I don't have to nestif
calls, which makes it easier to read (IMO). 
iflet
. This is basically a conditional binding (think variable) assignment: if the binding value is notnil
, then assign the value that binding for the scope of theiflet
. It saves you from the alltoocommon pattern of:
# ruby
my_var = doThingPossibly()
if my_var
# do other things
end
or
# python
if doExpensiveThing():
repeatItForVariable = doExpensiveThing()
# do other things
And again, my code is available in a Github Gist. Until tomorrow!