Day three and we compare a bunch of letters.
What is Advent of Code?
In this little series, I want to write about the thought processes I have behind solving the puzzles presented in Advent of Code.
During the Advent of Code small coding puzzles are presented with varying levels of difficulty. They're always Christmas-themed text puzzles where you help elves out of some mess to save the holidays. The puzzles are deliberately ambiguous to not bias puzzlers into a certain solution, they always have an example input in the text to explain some details and an input file for each day that comes in the form of a text file you can download. The solution is a simple number or a string you enter, which is checked by the website automatically. After you finish part 1, part 2 unlocks, which is a variation on part 2. This can be a little twist on part 1 or a large twist that changes the problem formulation into a problem that would take brute force solutions to compute longer than the heat death of the universe would take.
Find my solutions here: github.com/JesperDramsch/advent-of-code
These descriptions won't be a perfect narrative, but rather how I think about these problems and where I see different solutions. I apologise for the possibility of rambling!
The example input
I looked at this input and thought we were cracking codes on day 3. That would be something wouldn't it?!
vJrwpWtwJgWrhcsFMMfFFhFp jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL PmmdzqPrVvPwwTWBwg wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn ttgJtRGJQctTZtZT CrZsJsPPZsGzwwsLwLmpwMDw
I was completely wrong. We simply compare the first part to the second part. Let's code!
On this one the parsing gets interesting.
I figured I could use a
set() to compare the compartments, but I didn't want to implement this in the parsing right away, since I figured part 2 would throw us for a loop.
Instead I would implement a simple comparison with a set intersection in a function:
def match_compartments(comp1, comp2): return set(comp1) & set(comp2)
Sets are very easy and fast to compare, so they're usually my first choice here. Even if the items aren't numbers, we quickly get all the items each set, or in this case apartment have in common.
The problem with sets and the reason I didn't use it for parsing right away is that each item can only be once in the rucksack.
Then there was a chance we'd have double items and this wouldn't work out. But for this one, I was lucky.
Prioritizing the items was fairly straight-forward. I just used a trick that each letter has a corresponding number, we can get with
ord(), the only problem is that they're not the right numbers. However, I despise writing out a list of
abcde... bad enough to figure out the offsets by hand.
def prioritize(item): offset = 96 if item == item.lower() else 38 return ord(item) - offset
I assumed part 2 would be different from what it was.
Turns out it was easiest to parse the data differently altogether, because we didn't need the split of each rucksack into compartments.
I used the same ugly trick from day 1 to group the items in the loop, but it works… so far…
We needed the intersection of three sets this time, but Python also does this with
set.intersection(*rucksacks), which is pretty great!
These errors are written from memory, because I only remembered after day 3 that I wanted to write this log. They will be more detailed tomorrow:
- Can't index into a set.
sum(map(...) for ...)caused mixed
mapto not be summed. Sum the integers in the map first to ensure equal type.
- Encoding error loading the readme in
conftest.pyon windows. Always load text files with
encoding="utf8"or there will be errors.
- Used the set union, when I should have used the intersection in part 2.
- Badges were added at the beginning of the loop, so the last badges of the group weren't added to the list, which caused a low result. There are probably clean fixes, but I just added an empty item to the data, to add an extra final loop to not repeat the code unnecessarily.