Intro⌗

So far the Advent of Code has been going well but it is still early days! Lets jump right into day three and hope that things keep going well!

The Puzzle⌗

Today’s puzzle involves elves having mis-packed their backpacks! Each backpack has two compartments and each compartment is supposed to filled of mutually exclusive sets of items. Unfortunately, exactly one item in each backpack is present in each compartment! Disaster!

I need to find out which item has been put into both backpack compartments for each backpack, the item can be different between backpacks.

Finally I need to score the priority of those items as the puzzle answer.

Input⌗

The elves’ backpacks are represented as lines in a text file. Each line contains exclusively alphabetic characters [a-z][A-Z] and each character represents a type of item.

BzRmmzZHzVBzgVQmZLPtqqffPqWqJmPLlL
hpvvTDcrCjhpcrvcGGhfLHMlLtMCqflNlWPJlJ
hGjhncHhGnhbTHczBBZVVSbRwgSgRV
rWVQjPQQjGRWNSrWrPjcptwBpqqJBtJBBcZgMdtq
... many lines of input!

Each backpack has two compartments. Those are represented by the first and second half of each line respectfully.

I’m going to use the slurp function again! I’m going to read the input and use clojure.string/split-lines to get a list of strings representing each backpack. That’ll be a good starting point to start building the actual solution.

(ns day3.core
  (:require [clojure.string :as str]))

(def input (str/split-lines (slurp "./advent-of-code/day3/input.txt")))

(take 4 input)

("BzRmmzZHzVBzgVQmZLPtqqffPqWqJmPLlL" "hpvvTDcrCjhpcrvcGGhfLHMlLtMCqflNlWPJlJ" "hGjhncHhGnhbTHczBBZVVSbRwgSgRV" "rWVQjPQQjGRWNSrWrPjcptwBpqqJBtJBBcZgMdtq")

Part 1⌗

First things first. I want to be able to take a line of text from the input and split it in two. Thankfully Clojure has a function for splitting a list at an index! That function would be split-at which takes an index and the collection.

(split-at 4 "0123456789")

[(\0 \1 \2 \3) (\4 \5 \6 \7 \8 \9)]

I can use that with the count of the line to give me both backpack compartments. :-)

Now to find out which ‘item’ / char is duplicated between each half. I’m just going to use a nested map which. That will be O(n^2) but the input isn’t too large and hopefully because map is lazy it won’t always be the worst case!

(mapcat #(map (fn [y] (when (= y %) %)) compartment-1) compartment-2)

Okay, I’ve used mapcat to flatten the nested list of lists I’d get back otherwise. When the item is the same in both compartments I’m returning the item otherwise I’m returning nil. Then I just need to remove all the nil values and return the first value!

I can pull all of that into a function:

(defn find-miss-packed-item [backpack]
  (let [[compartment-1 compartment-2]
      (split-at (/ (count backpack) 2) backpack)]
    (->> compartment-2
       (mapcat #(map (fn [y] (when (= y %) %)) compartment-1))
       (remove nil?)
       first)))

Now I just need to work on scoring the priority of an item. A lowercase a is worth 1, b is 2 and so on until z = 26 before the uppercase chars A = 27 B = 28 and so on.

Now… I could write a map of all the chars and their corresponding score but I’m a bit lazy… Chars are basically numbers anyway right? I can cast the letter into an int and then just subtract isn’t ASCII value with an offset to find the correct priority. The only issue with this plan is that the ASCII values for the upper and lowercase letters are non sequential and the uppercase letter have lower values than the lowercase ones. I need to check the casing and then use a different offset.

(defn item-priority [item]
  (if (Character/isLowerCase item)
    (- (int item) 96)
    (- (int item) 38)))

(map item-priority "abxyzABXZ")

(1 2 24 25 26 27 28 50 52)

That’s looking pretty good! Now I just need to glue it all together and sum the priorities!

(defn part-1 [backpacks]
  (->> backpacks
       (map find-miss-packed-item)
       (map item-priority)
       (reduce +)))

(part-1 input)

7824

And boom! I’m done with part one! :-)

Part 2⌗

Time for the second half. This time the issue is that the elves travel in groups of three but have their badges in the backpacks still! The badge for each group of three is the only common item that each elf has in its backpack.

The backpacks are already ordered by group so I just need to find the common item and sum the priorities again.

Right first thing to do is to split the input into the groups of three lines. Clojure has a partition function which is perfect for this!

(partition 3 [1 2 3 4 5 6 7 8 9])

((1 2 3) (4 5 6) (7 8 9))

Now just to find the common item in each group. Again I’m just going to use nested map calls. That looks kinda funky but yeah it’ll work and again it is lazy so Clojure should only run enough iterations until it finds the common item. Worst case is O(n^3) though. :/

(defn find-common-item [backpacks]
  (let [[a b c] backpacks]
    (->>
     (mapcat
      (fn [x]
      (mapcat
       (fn [y]
	 (map
	  (fn [z] (when (= x y z) z))
	  c))
       b))
      a)
     (remove nil?)
     (first))))

(find-common-item ["abc" "bcd" "cde"])

\c

Nice! Once again I just need to glue that together and I should be done!

(defn part-2 [backpacks]
  (->> backpacks
       (partition 3)
       (map find-common-item)
       (map item-priority)
       (reduce +)))

(part-2 input)

2798

Lets put that in to the answer on Aoc and…

Your puzzle answer was 2798.

Both parts of this puzzle are complete!

Great! Day 3 done! Not too bad but slightly trickier than yesterday.

If you’re interested, I’ve put the code for this and the other AoC challenges I’ve done on github.

Thanks for reading!