Advent of Code: Day 14 - Extended Polymerization

Unfortunately, I wasn’t able to solve today’s puzzle myself, so I’ve asked my friend for help. The task was again about exponential growth, very similar to the day 6 puzzle. However, I wasn’t able to grasp how to keep things from growing this time.

As you may remember, in the lanternfish puzzle, I’ve figured out, that if we use frequencies on current fish, we obtain their counters, and counts of fish with those counters respectively. It was only a matter of time to notice the pattern with which lanternfish counters change.

Today’s task was very similar, but the puzzle itself lead me in the wrong direction. To explain what’ve happened let’s parse the input, as I initially did:

day13> (ns day14 (:require [clojure.string :as str]))
nil
day14> (def example-input "NNCB

CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C")
#'day14/example-input
day14> (defn read-input []
         (let [lines (->> example-input
                          str/split-lines)
               polymer (first lines)
               recipes (drop 2 lines)]
           {:polymer (seq polymer)
            :recipes (reduce #(let [[pattern replacement] (str/split %2 #"\s+->\s+")]
                                (conj %1 [(seq pattern) (seq (str (first pattern) replacement))]))
                             {} recipes)}))
#'day14/read-input
day14> (read-input)
{:polymer (\N \N \C \B),
 :recipes
 {(\C \H) (\C \B),
  (\N \N) (\N \C),
  (\H \C) (\H \B),
  (\N \C) (\N \B),
  (\N \H) (\N \C),
  (\C \N) (\C \C),
  (\N \B) (\N \B),
  (\B \C) (\B \B),
  (\B \B) (\B \N),
  (\B \H) (\B \H),
  (\C \C) (\C \N),
  (\H \N) (\H \C),
  (\C \B) (\C \H),
  (\H \B) (\H \C),
  (\B \N) (\B \B),
  (\H \H) (\H \N)}}

As you can see, I’ve pre-computed the replacements. I did it because the task said, that the patterns overlap, and “the second element of one pair is the first element of the next pair”. So I’ve realized, that we can ditch the third letter completely, and we’ll be “fine”. You can see that this assumption is correct:

day14> (def recipes (:recipes (read-input)))
#'day14/recipes
day14> (str/join (mapcat #(recipes % %) (partition-all 2 1 (:polymer (read-input)))))
"NCNBCHB"
day14> (str/join (mapcat #(recipes % %) (partition-all 2 1 *1)))
"NBCCNBBBCBHCB"
day14> (str/join (mapcat #(recipes % %) (partition-all 2 1 *1)))
"NBBBCNCCNBBNBNBBCHBHHBCHB"
day14> (str/join (mapcat #(recipes % %) (partition-all 2 1 *1)))
"NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB"

However, it is also growing exponentially.

Now, in order to fix this, we need to look at this polymer string as a set of pairs. We’re already working with it as a set of pairs here, since we’re using partitioning, but these pairs grow with the string, and as you may remember from the lanterfish task, we were able to solve it with frequencies function:

day14> (frequencies (partition 2 1 "NNCB"))
{(\N \N) 1, (\N \C) 1, (\C \B) 1}
day14> (frequencies (partition 2 1 "NCNBCHB"))
{(\N \C) 1, (\C \N) 1, (\N \B) 1, (\B \C) 1, (\C \H) 1, (\H \B) 1}
day14> (frequencies (partition 2 1 "NBBBCNCCNBBNBNBBCHBHHBCHB"))
{(\C \H) 2, (\N \C) 1, (\C \N) 2, (\N \B) 4, (\B \C) 3, (\B \B) 4,
 (\B \H) 1, (\C \C) 1, (\H \B) 3, (\B \N) 2, (\H \H) 1}
day14> (frequencies (partition 2 1 "NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB"))
{(\H \C) 3, (\N \C) 1, (\N \H) 1, (\C \N) 3, (\N \B) 9, (\B \C) 4, (\B \B) 9,
 (\B \H) 3, (\C \C) 2, (\H \N) 1, (\C \B) 5, (\B \N) 6, (\H \H) 1}
day14> (frequencies (partition 2 1 "NBBNBBNBBBNBBNBBCNCCNBBBCCNBCNCCNBBNBBNBBNBBNBBNBNBBNBBNBBNBBNBBCHBHHBCHBHHNHCNCHBCHBNBBCHBHHBCHB"))
{(\C \H) 6, (\H \C) 1, (\N \C) 3, (\N \H) 1, (\C \N) 6, (\N \B) 19, (\B \C) 8,
 (\B \B) 19, (\B \H) 3, (\C \C) 3, (\H \N) 1, (\H \B) 8, (\B \N) 15, (\H \H) 3}
day14> (frequencies (partition 2 1 "NBBNBBNBBNBBNBBNBNBBNBBNBBNBBNBBCCNBCNCCNBBNBNBBCNCCNBBBCCNBCNCCNBBNBBNBBNBBNBBNBBNBBNBBNBBNBBNBBBNBBNBBNBBNBBNBBNBBNBBNBBNBBNBBCBHCBHHNHCBBCBHCBHHNHCNCHBCCNBCBHCBBCBHCBBNBBNBBCBHCBHHNHCBBCBHCB"))
{(\C \H) 1, (\H \C) 9, (\N \C) 4, (\N \H) 3, (\C \N) 10, (\N \B) 41, (\B \C) 12, (\B \B) 42,
 (\B \H) 9, (\C \C) 6, (\H \N) 3, (\C \B) 14, (\H \B) 1, (\B \N) 34, (\H \H) 3}

As can be seen, even though the polymer string grows exponentially, the result of partitioning and counting all of them grows much slower in size. This was the first thing I’ve thought about when I saw the growth rate, and remembered day 6. And even though such a brute-force approach worked on the input, it was a wrong approach, as part two asked to compute 40 iterations. So I’ve kinda knew how to fix it, I mean, we just need to find a way to maintain such kind of table by hand, and we’ll be done in no time. But my earlier mistake prevented me from doing it. And that mistake was in the algorithm I’ve written for parsing the input.

Part two (struggle)

As you can see, I’ve precomputed all input and output patterns, but the task specifically mentioned that the letters are inserted in between, and I totally forgot that. Let’s look into the pairs again:

day14> (partition 2 1 "NNCB")
((\N \N) (\N \C) (\C \B))

Now, if we replace these patterns, with our old method, we’ll get these patterns:

day14> (partition 2 1 "NCNBCHB")
((\N \C) (\C \N) (\N \B) (\B \C) (\C \H) (\H \B))

Now, let’s replace original patterns, as suggested by the task:

day14> (->> "NNCB"
            (partition 2 1)
            (mapcat '{(\N \N) (\N \C \N)
                      (\N \C) (\N \B \C)
                      (\C \B) (\C \H \B)})
            (partition 2 1))
((\N \C) (\C \N) (\N \N) (\N \B) (\B \C) (\C \C) (\C \H) (\H \B))

By doing it this way we get extra pairs that should not be there. These pairs are (N N) and (C C), as these are the points of overlapping, which can be illustrated like this:

NCN
||NBC
||||CHB
|||||||
vvvvvvv
NCNBCHB

If we remove overlapping pairs we’ll get the correct result:

((\N \C) (\C \N) (\N \B) (\B \C) (\C \H) (\H \B))

What we need to notice here, is that this method above can be used to generate all possible pairs without overlapping. To do so we need to translate a pair into two pairs. For example, the (N C) pair is transformed into two pairs (N B) and (B C) as this is just the same as (N [B) C]. Doing it this way, we get the correct amount of pairs from the get-go:

day14> (->> "NNCB"
            (partition 2 1)
            (map '{(\N \N) [(\N \C) (\C \N)]
                   (\N \C) [(\N \B) (\B \C)]
                   (\C \B) [(\C \H) (\H \B)]})
            flatten
            (partition 2))
((\N \C) (\C \N) (\N \B) (\B \C) (\C \H) (\H \B))

That’s the bit of information that I couldn’t figure out myself. To be completely honest, even while writing it, I’m not sure if I understood the task correctly in the first place. The overlapping point suggests that I’m correct. On the other hand the same result can be constructed like this:

N N C B
 ^ ^ ^
 | | |
 C B H

We’re literally inserting new letters between existing letters, which is a totally different approach but it also works.

So in order to solve this task, we need to take a list of pairs, and transform each into two more pairs, as shown above. But instead of storing these pairs in a list, we can use a hashmap, that stores their counts. Additionally to that, we need a separate hashmap for counting inserted letters. On each step, we see how many instances of the given pair were there, and insert that many letters into the hash table. We convert a pair to two more pairs and insert as many of each into another hash table. This repeats until needed amount of iterations have passed:

day14> (defn solve [n {:keys [polymer recipes]}]
         (loop [n n
                letters (frequencies polymer)
                pairs (frequencies (partition 2 1 polymer))]
           (if (> n 0)
             (let [[letters pairs]
                   (reduce (fn [[letters pairs]
                                [[a b :as pair] n]]
                             (let [letter (recipes pair)
                                   add (fnil (partial + n) 0)]
                               [(update letters letter add)
                                (-> pairs
                                    (update [a letter] add)
                                    (update [letter b] add))]))
                           [letters {}]
                           pairs)]
               (recur (dec n) letters pairs))
             [letters pairs])))
#'day14/solve
day14> (solve 1 {:polymer (seq "NNCB")
                 :recipes '{(\N \N) \C
                            (\N \C) \B
                            (\C \B) \H}})
[{\N 2, \C 2, \B 2, \H 1},
 {[\N \C] 1, [\C \N] 1, [\N \B] 1, [\B \C] 1, [\C \H] 1, [\H \B] 1}]

Day 14 thoughts

I was a bit frustrated by this task, but it’s OK. I know that such tasks are my weakness, and it’s good that I’ve managed to finish them, even with a bit of help. A small ambiguity of the task was a bit problematic, but I’ve also failed to see the correct transformation.

Hopefully, tomorrow’s task will be in another category!