Advent of Code: Day 7

Remembering last year’s AoC, I can tell that solving one puzzle per day is much more pleasant than solving a bunch of puzzles in a single day. Last year I felt the burden of unsolved days, and an eternal race with the clock to keep up with others. Thankfully, this year is different!

The Treachery of Whales

Today a giant whale wants to eat us, but a swarm of crabs in tiny submarines wants to help us escape. In order to do that, we need to help crabs to align in a straight line with the least amount of fuel. The example input resembles a horizontal position of each crab, and goes as follows: 16,1,2,0,4,2,7,1,2,14.

When crab moves from position 0 to position 1 its submarine looses 1 unit of fuel. So to move from position 16 to 5, the crab needs to spend 11 units of fuel. We need to find such a position that total fuel unit loss is as small as possible. Let’s start with the example input:

day6> (ns day7)
nil
day7> (require '[aoc-commons :refer [parse-long]]
               '[clojure.string :as str])
nil
day7> (def example-input [16,1,2,0,4,2,7,1,2,14])
#'day7/example-input

Now we just need to compute fuel consumption for a given position:

day7> (defn fuel-consumption [input pos]
        (->> input
             (map #(Math/abs (- % pos)))
             (reduce +)))
#'day7/fuel-consumption
day7> (fuel-consumption example-input 2)
37

As can be seen, computing fuel consumption for position 2 yields a correct result. Now we only need to check what position is the most optimal one, meaning that it uses the least amount of fuel:

day7> (defn solve [input]
        (let [min (apply min input)
              max (apply max input)]
          (->> (range min (inc max))
               (map (partial fuel-consumption input))
               sort
               first)))
#'day7/solve
day7> (solve example-input)
37

We only care for the positions in range of our numbers. So if the minimum position is 10 and the maximum is 15 there’s no point going below 10 or above 15. Since the range yields a non-inclusive range, we need to inc the upper bound.

This again yields 37, as it is the least amount of fuel we can use to align everyone. It also works for the real input, but it is quite slow:

day7> (time (solve (read-input)))
"Elapsed time: 6545.965142 msecs"
343468

While slowness may be an issue in the second part, as the previous day clearly illustrated, let’s hope it will not cause too much trouble.

Part two

OK, we’ve got it slightly wrong, and crab submarines use a lot more fuel to move. So to move from position 1 to 5, the submarine uses 1+2+3+4+5 amount of fuel. This is called a triangular number, and is computed with the following formula: n(n+1)/2:

day7> (defn triangle-number [n]
        (/ (* n (inc n)) 2))
#'day7/triangle-number
day7> (triangle-number 5)
15

Now, all we need to do is to plug this function into our solution. Instead of duplicating the code, let’s rewrite our two functions to support an additional modifier argument:

day7> (defn fuel-consumption [input modifier pos]
        (->> input
             (map #(modifier (Math/abs (- % pos))))
             (reduce +)))
#'day7/fuel-consumption
day7> (defn solve
        ([input] (solve input identity))
        ([input modifier]
         (let [min (apply min input)
               max (apply max input)]
           (->> (range min max)
                (map (partial fuel-consumption input modifier))
                sort
                first))))
#'day7/solve

The solve function now optionally accepts a second argument. When only one argument is given, the arity dispatcher goes to the first body ([input] (solve input identity)), which calls the same function but with two arguments. The default value for modifier is identity, which is a function that returns the argument it was given as is. Now we can use our triangle-number as a modifier to compute the result:

day7> (solve example-input)
37
day7> (solve example-input triangle-number)
168

This works for real input data as well:

day7> (time (solve (read-input) triangle-number))
"Elapsed time: 6256.100167 msecs"
96086265

The required time hasn’t changed much, as we just added one small formula to an already working solution. I’m fine with the current results.

Day 7 thoughts

Today’s task was quite simple. Perhaps there’s a more optimal solution to it, but I can’t think of one to be honest. Luckily, today the speed was not a blocker, just a minor inconvenience.

See you tomorrow!