Advent of Code 2018 - Day 3

Solving these problems has been more difficult than I originally imagined - these aren't your FizzBuzz-level 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 on-call for my team at the time), so I got a second chance to look at them early in the morning (3am-ish 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 after-the-fact, 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 rabbit-hole, 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 [claim-number squares])

(defn convert-to-grid
  "Converts a claim into a sequence of 'taken' squares."
  [claim grid-width]
  ;; 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 (re-find 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 (* grid-width %)) (+ (+ x w) (* grid-width %))) 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 re-appearance 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:

5x5-grid

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 get-overlap
  "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 [mapped-area (map #(convert-to-grid % 1000) claims)
         shared-fabric #{}
         intersections #{}]
    (if (empty? mapped-area)
      intersections
      (let [intersect (set/intersection shared-fabric (:squares (first mapped-area)))
            union (set/union shared-fabric (:squares (first mapped-area)))]
        (recur (rest mapped-area) 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/fn-name. For each iteration of the loop, we do three things:

  1. We check against the "shared fabric". This is done by doing a set intersection between the current rectangle (defined by (first mapped-area)) and all of the rectangles that came before it.
  2. We define the "shared fabric" by adding the current rectangle to the rectangles that have already been added by a set union.
  3. 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 lightning-quick 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 overlapping-claim [c1 c2]
  (cond
    (= (:claim-number c1) (:claim-number c2)) nil
    (not-empty (set/intersection (:squares c1) (:squares c2))) c2))

(defn find-no-overlap
  "given a set of input claims, find the claim that has no overlap
  with any other claims."
  [claims]
  (let [grid-claims (map #(convert-to-grid % 1000) claims)]
    (loop [idx 0 ignores #{}]
      (if-not (contains? (:claim-id (nth grid-claims idx)) ignores)
        (if-let [overlap (some #(overlapping-claim (nth grid-claims idx) %) grid-claims)]
          (recur (inc idx) (conj ignores (:claim-number overlap)))
          (:claim-number (nth grid-claims idx)))
        (recur (inc idx) ignores)))))

Cool Clojure-y things to point out here:

  1. cond. Think of cond as a bit of a if/else on steroids. It allows you to pass a pair of items: test expression, and success expression. If the test expression passes (ie, returns true), 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 nest if calls, which makes it easier to read (IMO).
  2. if-let. This is basically a conditional binding (think variable) assignment: if the binding value is not nil, then assign the value that binding for the scope of the if-let. It saves you from the all-too-common pattern of:
my_var = doThingPossibly()
if my_var
  # do other things
end

or

if (doExpensiveThing()):
    repeatItForVariable = doExpensiveThing()
    # do other things

And again, my code is available in a Github Gist. Until tomorrow!

/Programming/ /AoC2018/ /advent-of-code/