December 8, 2019

Advent of Code 2019 - Week 1

Since we're on day 8 of AoC, I can now post my solutions for the first week of problems. I'm going to walk through each of my solutions in this post, so if you just want to see the code you can find that here.

I used Lumo for everything, and here's how I read the input for each problem.

(defn get-input []
  (-> *command-line-args*
      (first)
      (fs/readFileSync #js {:encoding "UTF-8"})))

Day 1

Day 1 starts off easy – map the fuel formula across the input then sum it all up.

(defn calculate-fuel [mass]
  (- (js/Math.floor (/ mass 3)) 2))

(defn part-one []
  (->> (clojure.string/split (get-input) #"\n")
       (map (comp calculate-fuel js/parseInt))
       (apply +)
       println))

Part 2

Part two of this problem is a really good fit for lazy sequences. I can calculate the amount of fuel required per module, then generate a lazy sequence by continuing to call my calculate-fuel function on the result using iterate.

(defn calculate-fuel-fuel [mass]
   (take-while pos? (iterate calculate-fuel mass)))

(defn part-two []
  (->> (clojure.string/split (get-input) #"\n")
       (mapcat (comp calculate-fuel-fuel calculate-fuel js/parseInt))
       (apply +)
       println))

Day 2

The input for Day 2's problem is a list of integers that's going to be both the "program" and the "memory" for our intcode computer. Since we'll have to do in-place updates on this list, one option is to use recursion.

(def op-lookup
  {1 +
   2 *})

(defn run-program [ip program]
  (let [[op i1 i2 o] (subvec program ip (+ ip 4))]
    (if (= 99 op)
      program
      (let [result ((get op-lookup op) (get program i1) (get program i2))]
        (recur (+ ip 4) (assoc program o result))))))

Each set of opcodes and params is exactly 4 "words" so we just need to keep moving the instruction pointer forward 4 positions every time we process and recurse.

To restore the gravity on the ship we need to set position 1 in our program to 12 and position 2 to 2 then run the program.

(def program
  (mapv js/parseInt (clojure.string/split (get-input) #",")))

(defn part-one []
  (->> (assoc program 1 12 2 2)
       (run-program 0)
       first
       println))

Part 2

To find the noun and verb for part 2, I generated all the possible combinations of n and v with 0 <= n,v <= 100, then ran the program with each set of inputs and filtered for the target value. Generating the inputs this way isn't necessarily the best option because your stack could be exhausted before you find the target but hey, it worked here.

(defn part-two []
  (let [target   19690720
        attempts (for [n (range 100)
                       v (range 100)] [n v])]
    (->> attempts
         (map (fn [[n v]]
                [(->> (assoc program 1 n 2 v)
                      (run-program 0)
                      (first))
                 [n v]]))
         (some (fn [[total [n v]]]
                 (if (= target total) (+ v (* 100 n)))))
         println)))

Day 3

My first thought after reading the program was "okay, if I'm going to find the intersections of two wires then I'm going to have to know all of the points that each wire crosses", so let's start with that.

(defn generate-wire-segment [[x-start y-start] [direction units]]
  (case direction
    "U" (for [y (range (inc y-start) (+ (inc y-start) units))] [x-start y])
    "D" (for [y (range (dec y-start) (- (dec y-start) units) -1)] [x-start y])
    "R" (for [x (range (inc x-start) (+ (inc x-start) units))] [x y-start])
    "L" (for [x (range (dec x-start) (- (dec x-start) units) -1)] [x y-start])))

(defn generate-wire [wire directions]
  (if (empty? directions)
    wire
    (let [next-line (generate-wire-segment (or (last wire) [0 0]) (first directions))]
      (recur (into wire next-line) (rest directions)))))

(generate-wire [] [["R" 3] ["U" 2] ["R" 1] ["D" 6]])
=> [[1 0] [2 0] [3 0] [3 1] [3 2] [4 2] [4 1] [4 0] [4 -1] [4 -2] [4 -3] [4 -4]]

So far so good. Now we'll generate the points for both wires and find the intersections:

(defn parse-directions [dir-string]
  (map (fn [dir]
         [(first dir) (js/parseInt (apply str (rest dir)))])
       (clojure.string/split dir-string #",")))

(defn generate-wires []
  (->> (clojure.string/split (get-input) #"\n")
       (mapv parse-directions)
       (mapv (partial generate-wire []))))

(defn get-intersections [wires]
  (->> wires
       (map set)
       (apply set/intersection)))

Finally, we calculate the manhattan distance for each intersection and take the minimum:

(defn part-one []
  (let [wires (generate-wires)]
    (->> wires
         (get-intersections)
         (map (fn [[x y]] (+ (js/Math.abs x) (js/Math.abs y))))
         (apply min)
         println)))

Part 2

With the way we generated the wire coordinates, finding the steps to each intersection for part two is actually really easy:

(defn get-steps-to-intersection [wire intersection]
  (inc (count (take-while #(not= intersection %) wire))))

(defn part-two []
  (let [wires (generate-wires)]
    (->> (get-intersections wires)
         (map (fn [intersection]
                [(get-steps-to-intersection (first wires) intersection)
                 (get-steps-to-intersection (second wires) intersection)]))
         (map (partial apply +))
         (apply min)
         println)))

Day 4

This is where I started thinking "this would be so gross in another language"... But let's not dwell on that thought 😅; how do we approach this?

  1. Generate our range of numbers
  2. Filter for 6-digit nums – my range already consists of 6-digit numbers so I can skip this check
  3. Filter out numbers that don't have non-decreasing digits – this is easy to do if we just break the number up into its digits and apply <=.
  4. Filter out numbers that don't have two identical, adjacent digits

Now here I stopped for a moment and almost considered using a regex. Instead, I used partition to group the digits into adjacent pairs and filtered out the numbers that did not have a pair containing identical elements.

(defn part-one []
  (->> (range 152085 670283)
       (filter #(->> (str %)
                     (map js/parseInt)
                     (apply <=)))
       (filter #(some (fn [[a b]] (= a b))
                      (partition 2 1 (str %))))
       count
       println))

Part 2

To handle the new criteria in part 2 (the two adjacent matching digits are not part of a larger group of matching digits), I tried to do more partition magic but it just wasn't working out – so I turned back to regex.

Using re-find we can get the first match in a string:

(re-find #"\d" "111233")
=> "1"

And from clojuredocs.org,

When there are parenthesized groups in the pattern and re-find finds a match, it returns a vector. The first item is the part of the string that matches the entire pattern, and each successive item are the parts of the string that matched the 1st, 2nd, etc. parenthesized groups.

(re-find #"(\d)" "111233")
=> ["1" "1"]

re-seq on the other hand will return a lazy seq of successive matches. Both re-seq and re-find use java.util.regex.Matcher.find() so we'll get similar results with parenthesized groups. Now let's update our regex to find sequences of adjacent numbers.

(re-seq #"(\d)\1+" "111233")
=> (["111" "1"] ["33" "3"])

Going back to the AoC problem now, we can filter our numbers like so:

(defn part-two []
  (->> (range 152085 670283)
       (filter #(->> (str %)
                     (map js/parseInt)
                     (apply <=)))
       (filter #(some (fn [x] (= 2 (count x)))
                      (map first (re-seq #"(\d)\1+" (str %)))))
       count
       println))

Day 5

It's the return of the intcode computer! We need to add more instructions and support for parameter modes so I'm going to change up my approach. First, some helpers:

(def acs-program
  (mapv js/parseInt (clojure.string/split (get-input) #",")))

(def op-lookup
  {1 +
   2 *})

(defn ->computer [input]
  {:ip    0
   :mem   acs-program
   :input input})

(defn read-word [computer address]
  (get-in computer [:mem address]))

(defn read-offset-word [computer offset]
  (get-in computer [:mem (+ offset (:ip computer))]))

(defn write-word [computer address value]
  (assoc-in computer [:mem address] value))

(defn parse-opcode [computer]
  (let [opcode (gstring/format "%05d" (read-offset-word computer 0))
        op     (->> (subvec (into [] opcode) 3)
                    (apply str)
                    (js/parseInt))
        modes  (->> (subvec (into [] opcode) 0 3)
                    (reverse)
                    (mapv js/parseInt))]
    {:op    op
     :modes modes}))

(defn normalize-param [computer modes offset]
  (if (zero? (modes (dec offset))) ;; dec because no mode for instruction
    (read-word computer (read-offset-word computer offset))
    (read-offset-word computer offset)))

(defn move-ip [computer offset]
  (update computer :ip + offset))

Then we'll update our handlers for each instruction:

(defn binary-op [computer {:keys [op modes]}]
  (let [f           (op-lookup op)
        p1          (normalize-param computer modes 1)
        p2          (normalize-param computer modes 2)
        out-address (read-offset-word computer 3)]
    (-> computer
        (write-word out-address (f p1 p2))
        (move-ip 4))))

(defn input-op [computer]
  (-> computer
      (write-word (read-offset-word computer 1) (first (:input computer)))
      (update :input rest)
      (move-ip 2)))

(defn output-op [computer {:keys [modes]}]
  (println (normalize-param computer modes 1))
  (-> computer
      (move-ip 2)))

And finally our run-program gets extended for our new instructions

(defn run-program [computer]
  (let [opcode (parse-opcode computer)]
    (case (:op opcode)
      99 computer
      (1 2) (recur (binary-op computer opcode))
      3 (recur (input-op computer))
      4 (recur (output-op computer opcode)))))

(defn part-one []
  (run-program (->computer [1])))

(part-one)

Part 2

Updating the code to handle part 2 is straightforward:

(def op-lookup
  {1 +
   2 *
   7 (comp #(if (true? %) 1 0) <)
   8 (comp #(if (true? %) 1 0) =)})

(defn jump-op [computer {:keys [op modes]}]
  (let [pred   (if (= 5 op) (comp not zero?) zero?)
        param  (normalize-param computer modes 1)
        target (normalize-param computer modes 2)]
    (if (pred param)
      (assoc computer :ip target)
      (move-ip computer 3))))

(defn run-program [computer]
  (let [opcode (parse-opcode computer)]
    (case (:op opcode)
      99 computer
      (1 2 7 8) (recur (binary-op computer opcode))
      3 (recur (input-op computer))
      4 (recur (output-op computer opcode))
      (5 6) (recur (jump-op computer opcode)))))

Day 6

Ah, graph problems! I had fun with this one because it forced me to revist some stuff that I learned in my data structures and algorithms classes.

We're given our input as pairs of [orbitee orbiter] so let's start by putting that into a hashmap:

(defn ->orbiter-map [orbits]
  (reduce (fn [res orbit]
            (let [[orbitee orbiter] (clojure.string/split orbit #"\)")]
              (update res orbitee (fnil conj #{}) orbiter)))
          {}
          orbits))

Let's see what this looks like when we feed it the sample data

(-> (get-input)
    (clojure.string/split #"\n")
    (->orbiter-map))
=> {"COM" #{"B"}
    "B"   #{"C" "G"}
    "C"   #{"D"}
    "D"   #{"E" "I"}
    "E"   #{"F" "J"}
    "G"   #{"H"}
    "J"   #{"K"}
    "K"   #{"L"}}

Now let's see what the graph actually looks like:

(defn ->deep-orbiter-map [root orbiter-map]
  (if-let [orbiters (get orbiter-map root)]
    {root (apply merge (map #(->deep-orbiter-map % orbiter-map) orbiters))}
    {root nil}))

(->> (clojure.string/split (get-input) #"\n")
     (->orbiter-map)
     (->deep-orbiter-map "COM"))
=> {"COM" {"B" {"C" {"D" {"E" {"F" nil
                               "J" {"K" {"L" nil}}}
                          "I" nil}}
                "G" {"H" nil}}}}

Yup, looks like the example.

        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I

Now we need to generate paths from COM to every node (not just the leaves!) I'm going to do this using tree-seq. Let's remind ourselves of how it works.

Returns a lazy sequence of the nodes in a tree, via a depth-first walk. branch? must be a fn of one arg that returns true if passed a node that can have children (but may not). children must be a fn of one arg that returns a sequence of the children. Will only be called on nodes for which branch? returns true. Root is the root node of the tree.

And here's my function to generate the paths

(defn get-all-orbit-paths [deep-orbiter-map]
  (let [children (fn [path]
                   (if-let [v (get-in deep-orbiter-map path)]
                     (map (fn [x] (conj path x)) (keys v))
                       []))
        branch? (fn [node] (-> (children node) seq boolean))]
    (->> (keys deep-orbiter-map)
         (map vector)
         (mapcat #(tree-seq branch? children %)))))

The children function gets the value from the orbit graph at the path we are currently exploring, and if it's not nil (ie. our path has orbiters) then we return a sequence of paths from COM to each of those orbiters.

The branch? function simple calls the children function and checks that it's not empty.

(->> (clojure.string/split (get-input) #"\n")
     (->orbiter-map)
     (->deep-orbiter-map "COM")
     (#(get % "COM"))
     get-all-orbit-paths)
=> (["B"]
    ["B" "C"]
    ["B" "C" "D"]
    ["B" "C" "D" "E"]
    ["B" "C" "D" "E" "F"]
    ["B" "C" "D" "E" "J"]
    ["B" "C" "D" "E" "J" "K"]
    ["B" "C" "D" "E" "J" "K" "L"]
    ["B" "C" "D" "I"]
    ["B" "G"]
    ["B" "G" "H"])

Looking good! Note that we leave off COM because we don't want to include it in the counts. Now we just have to add up all the orbits.

(defn part-one []
  (->> (clojure.string/split (get-input) #"\n")
       (->orbiter-map)
       (->deep-orbiter-map "COM")
       (#(get % "COM"))
       get-all-orbit-paths
       (map count)
       (apply +)
       println))

Part 2

I have to admit part two stumped me at first. How can I find the shortest path from YOU to SAN without computing all of the shortest paths? I stared at the graph generated by the sample data for a little bit and noted the following properties:

  1. Edges are directed (from orbitee to orbiter)
  2. There are no cycles
  3. Each object can orbit at most one other object

So not only do we have a DAG, but we have a tree. This is probably obvious if you look at the sample graph but I really did have to think about this for a second. This means we simply need to find the paths YOU->COM and SAN->COM then take the non-overlapping segments to get the YOU->SAN path.

To do this, let's first generate a map of orbiter->orbitee (the opposite of what we started with):

(defn ->orbitee-map [orbits]
  (reduce (fn [res orbit]
            (let [[orbitee orbiter] (clojure.string/split orbit #"\)")]
              (assoc res orbiter orbitee)))
          {}
          orbits))

(->orbitee-map (clojure.string/split (get-input) #"\n"))
=> {"K" "J"
    "L" "K"
    "G" "B"
    "J" "E"
    "H" "G"
    "E" "D"
    "C" "B"
    "F" "E"
    "B" "COM"
    "I" "D"
    "D" "C"}

To get the path to COM:

(defn path-to-COM [root orbitee-map]
  (if-let [orbitee (get orbitee-map root)]
    (cons root (path-to-COM orbitee orbitee-map))
    [root]))

And putting it all together:

(defn part-two []
  (let [orbitee-map (-> (get-input)
                        (clojure.string/split #"\n")
                        (->orbitee-map))
        SAN-path    (path-to-COM "SAN" orbitee-map)
        YOU-path    (path-to-COM "YOU" orbitee-map)
        common      (set/intersection (set SAN-path) (set YOU-path))]
    (-> (set/union
         (set/difference (set SAN-path) common)
         (set/difference (set YOU-path) common))
        (set/difference #{"SAN" "YOU"}) ;; we want the orbit jumps, not the whole path
        count
        println)))

Day 7

It's back to the intcode computer, but this time we need to pipe 5 of them together. We'll start with the code from Day 5's solution and add on to that.

First we're going to add a new key, :output, to our computer. We're going to need this to pipe the data between computers.

(defn ->computer [input]
  {:ip     0
   :mem    acs-program
   :input  input
   :output []})

And instead of printing then recursing when we see instruction 4, we're going to store the output and halt execution.

(defn output-op [computer {:keys [modes]}]
  (-> computer
      (update :output conj (normalize-param computer modes 1))
      (move-ip 2)))

(defn run-program [computer]
  (let [opcode (parse-opcode computer)]
    (case (:op opcode)
      99 computer
      (1 2 7 8) (recur (binary-op computer opcode))
      3 (recur (input-op computer))
      4 (output-op computer opcode)
      (5 6) (recur (jump-op computer opcode)))))

Now let's chain our computers together:

(defn run-amplifiers [computers]
  (let [computer (run-program (first computers))
        result   (last (:output computer))]
    (if (empty? (rest computers))
        result
        (recur (update-in (vec (rest computers)) [0 :input] conj result)))))

Each time we run the program on a computer, we take its output and add it onto the inputs for the next computer. Each computer accepts a phase setting as its first input so let's initialize our computers with those:

(defn create-computers [phase-settings]
  (mapv #(->computer [%]) phase-settings))

Then we generate all the phase configurations we're going to test and off we go!

(defn permutations [coll]
  (->> coll
       (clj->js)
       (.permutation combinatorics) ;; "js-combinatorics" from npm
       (.toArray)
       (js->clj)))

(defn part-one []
  (->>  (permutations (range 5))
        (map #(-> (create-computers %)
                  (update-in [0 :input] conj 0) ;; pass 0 as the second input to computer 1
                  (run-amplifiers)))
        (apply max)
        println))

Part 2

I had a really hard time understanding what was being asked here. Thankfully Reddit figured it out.

We need to know when each computer has halted (ie. read instruction 99) so let's keep track of that:

(defn ->computer [input]
  {:ip     0
   :mem    acs-program
   :input  input
   :output []
   :halted false})

And we should update this flag when the program halts:

(defn run-program [computer]
  (let [opcode (parse-opcode computer)]
    (case (:op opcode)
      99 (assoc computer :halted true)
      (1 2 7 8) (recur (binary-op computer opcode))
      3 (recur (input-op computer))
      4 (output-op computer opcode)
      (5 6) (recur (jump-op computer opcode)))))

Finally, we need to update run-amplifiers so it keeps looping until all of the computers have halted. Remember, the state of each computer should not be reset in between the feedback loops!

(defn next-computer-idx [computers idx]
  (mod (inc idx) (count computers)))

(defn run-amplifiers [computers]
  (loop [idx       0
         computers computers]
    (let [computer      (run-program (computers idx))
          result        (last (:output computer))
          next-idx      (next-computer-idx computers idx)
          next-computer (update (computers next-idx) :input conj result)]
      (if (every? :halted computers)
        (-> computers last :output last) ;; get the last output from computer E
        (recur next-idx (assoc computers idx computer next-idx next-computer))))))

Now just test with a different permutation of phase settings

(defn part-two []
  (->>  (permutations (range 5 10))
        (map #(-> (create-computers %)
                  (update-in [0 :input] conj 0) ;; pass 0 as the second input to computer 1
                  (run-amplifiers)))
        (apply max)
        println))


That's all for week 1! I hope you learned something from reading my solutions. 😄 If I continue to post my solutions I'll probably split them up... This post ended up being very long!

Tags: clojure aoc