Day 5: Cafeteria

We break the (fourth?) wall and reach the cafeteria. The Elves just switched their inventory management system and now they have some problems with it. How typical.

But, as always, we can help. They show us their database, which is divided in two paragraphs like this:

(def example "3-5
10-14
16-20
12-18

1
5
8
11
17
32")

The first paragraph are ranges of fresh ingredients, and the second one are ingredients. We need to tell them how many of the ingredients are fresh.

Input parsing

We’ve already dealt with ranges of natural numbers in Day 2, so we’ll once again use the :nats parameter to extract them.
This time in our input we have two paragraphs, separated by a blank line. This kind of input happens frequently so we came prepared for it: the aoc/parse-paragraphs function splits the input into multiple lists, each having lines as a separate elements. The second argument of that function is applied to each line.

(defn parse-data [input]
  (let [[ranges ingredients] (aoc/parse-paragraphs input :nats)]
    [ranges
     (mapv first ingredients)])) ; [1]

Since :nats will extract all integers on a line into a list, for the second paragraph, where there is just one number per line, we immediately extract it with first [1].

(def example-data (parse-data example))

(def data (parse-data (aoc/read-input 5)))

When we parse the example, we get this:

example-data

[[[3 5] [10 14] [16 20] [12 18]] [1 5 8 11 17 32]]

This looks exactly what we need. But beware of the huge numbers in the real input.

Part 1

For each ingredient in the second paragraph, we need to check if it is fresh. In other words, we need to check if it is at least in some of the ranges in the first paragraph:

(defn fresh? [ranges ingredient]
  (some (fn [[lo hi]] (<= lo ingredient hi)) ranges))

The some function does exactly that. We destructure each range into its lo and hi ends, and check if the ingredient is between them.

Now we need to do that for every ingredient and count how many of them are fresh.
We could filter the ingredients to keep only fresh ones, and then count how many fresh are there, but there is a helper function aoc/count-if, which does that in a single step:

(defn part-1 [[ranges ingredients]]
  (aoc/count-if #(fresh? ranges %) ingredients))

(part-1 example-data)

(part-1 data)

Two simple oneliners and Part 1 is done!

Part 2

Here we need to find how many total ingredients are considered fresh, i.e. what is the total size of the ranges. And we must be careful when counting because the ranges overlap.
Remember that we noticed that the real input has huge numbers? A naive solution (e.g. creating a set with all numbers in the ranges) won’t do the trick here. We need to be smarter than that.

The idea is to sort the ranges and then go one by one.
There are two (or three, depending on how you count) situations we can encounter:

L--------------H
   L-------H                    [1]
        L-------------H         [2a]
                  L----------H  [2b]

When we have sorted ranges, we know that each subsequent one will start at least where the previous one started, so no need to check the lower end of the ranges.
If the range we’re looking at has its hi end below the previous one [1], there’s nothing we need to do, all of the points are already included. The other situation is if the hi end is larger than the previous one: there are some new points we need to include. There are two sub-variants of this case: when the lo is below the previously highest point [2a], and when it is larger [2b].

Let’s write some code which deals with this.

(defn part-2 [[ranges _]] ; [1]
  (->> (sort ranges)      ; [2]
       (reduce (fn [[fresh highest :as acc] [lo hi]]  ; [3]
                 (if (<= hi highest)
                   acc                                ; [4]
                   (let [start (max lo (inc highest)) ; [5]
                         size  (- (inc hi) start)]
                     [(+ fresh size) hi])))
               [0 -1])
       first)) ; [6]

For this part we don’t need the list of ingredients (_), just the ranges [1].
Before doing anything else, we sort the ranges (the sort function works out of the box for vector elements, no need to manually specify a comparator).

The accumulator is a vector containing a total amount of fresh ingredients and the highest number seen so far [3].

If the hi of the current range is lower than the highest one so far (the case 1 from the graphical example above), then there’s nothing for us to do, we keep the accumulator as is and move to the next range to check [4].
We can deal with the cases 2a and 2b from the example above in one go: we use max to find the first new ingredient to include [5] and then calculate the size of new fresh ingredients.

The returned accumulator will have two elements, and we’re interested only in the first one [6].

(part-2 example-data)

(part-2 data)

359526404143208

Both parts at once

It turns out that the idea we had for Part 2 can be improved and then used to solve both parts more efficiently.
We can reduce the number of ranges we need to check by merging the ranges that can be merged.

Let’s look again at our example where we have an existing range on the first line and three different situations that can arise with the next range:

L--------------H
   L-------H                    [1]
        L-------------H         [2]
                  L----------H  [3]

In the situation [1], the second range is completely “swallowed” by the existing one, so we don’t have to even consider the second range.
For the situation [2], we can merge those two ranges into one:

L--------------H
        L-------------H
becomes:
L---------------------H

And in the situation [3], as there is no overlap, we keep both ranges as they were.

(defn merge-ranges [ranges]
  (let [[r & rngs] (sort ranges)]
    (reduce (fn [acc [lo hi]]
              (let [[prev-lo prev-hi] (peek acc)]
                (if (<= lo (inc prev-hi))
                  (conj (pop acc) [prev-lo (max prev-hi hi)]) ; [1]
                  (conj acc [lo hi]))))                       ; [2]
            [r]
            rngs)))

If lo of the current range is not higher than prev-hi, it means we should merge those two ranges [1]. Using (max prev-hi hi) allows us to cover both situation 1 and 2 from above: either the current range will be “swallowed” or the existing range will be extended.
If there is no overlap (situation 3), we just add the current range to the list of ranges [2].

For our new Part 1 solution we will also sort the ingredients, and then it is easy to see if an igredient is part of some range. There are three possible scenarios: 1. An ingredient is lower than the current range. Because the ranges are sorted, it means it can’t be part of any subsequent range, and we dismiss it and go to check the next ingredient. 2. If an ingredient is part of the current range, we count it and move to the next ingredient while keeping the current range. 3. If an ingredient is higher than the current range, we need to check that ingredient with the next range.

(defn pt-1 [sorted-ranges sorted-ingredients]
  (loop [[[lo hi] & ranges' :as ranges] sorted-ranges
         [ing & ings' :as ings]         sorted-ingredients
         result                         0]
        (cond
          (or (nil? lo)
              (nil? ing)) result ; [1]
          (< ing lo)      (recur ranges ings' result)
          (<= ing hi)     (recur ranges ings' (inc result))
          :else           (recur ranges' ings result))))

If there are no more ranges or no more ingredients, we came to the end and return the result [1].
Next three conditions follow the scenarios described above.

(defn solve [[ranges ingredients]]
  (let [sorted-ranges (merge-ranges ranges)
        sorted-ingredients (sort ingredients)]
    [(pt-1 sorted-ranges sorted-ingredients)
     (aoc/sum-map (fn [[lo hi]] (inc (- hi lo))) sorted-ranges)])) ; [1]

When we have merged ranges, it is easy to calculate the result for Part 2.

(solve example-data)

[3 14]

(solve data)

[661 359526404143208]

Performance comparison

This looks more efficient than our original solution, but by how much?

(require '[criterium.core :as c])

(c/quick-bench (part-1 data))

Evaluation count : 324 in 6 samples of 54 calls.
             Execution time mean : 1.894434 ms
    Execution time std-deviation : 25.923530 µs
   Execution time lower quantile : 1.873166 ms ( 2.5%)
   Execution time upper quantile : 1.928804 ms (97.5%)
                   Overhead used : 1.831777 ns)

(c/quick-bench (solve data))

Evaluation count : 3006 in 6 samples of 501 calls.
             Execution time mean : 200.332834 µs
    Execution time std-deviation : 1.578994 µs
   Execution time lower quantile : 197.712240 µs ( 2.5%)
   Execution time upper quantile : 201.856749 µs (97.5%)
                   Overhead used : 1.831777 ns)

Almost 10x faster! (And the second one is solving both parts.)

Conclusion

The first task this year where a naive (i.e. brute force) approach won’t work. But it was easy to come up with a sufficiently smart approach which does the trick for Part 2.
The difference between “sufficiently smart” and “smart” solution for Part 1 is about 10x.

And now let’s get ready for the weekend (when, traditionally, the tasks are harder). The only weekend in this year’s AoC. Oh my.

Today’s highlights:

some: is there at least one element of a collection which satisfies a predicate
sort: sort a collection. Shocking, I know.

source: clojure/src/day05.clj