As I’ve been solving this year’s Advent of Code puzzles, I’ve been writing some notes in a Markdown file in my solutions repository. I titled this file “DEVLOG.md”, with the intent that it would be a sort of journal spanning the lessons I learned over the course of the month.

I still plan on keeping that DEVLOG - my thoughts on journaling might be worth a post on their own someday - but I wanted to distill some of those lessons in blog posts as well. Since the first handful of puzzles are fairly trivial, this first post covers the entire first week.

I won’t be describing the puzzles or solutions in too much detail, so check the AoC website for the original problem statements and my advent-of-code-2020 repository for my solutions.

Day 1

The first day was really just an appetizer - read in the input, perform some looping operation, modify the loop for part two. The biggest lessons from this day actually came from a coworker. Apparently, the Two-Sum Problem is a classic interview question, and I see why. The brute force solution (nested for loops iterating over all pairs of the input array) is extremely obvious, and has a very obvious run time, O(N^2).

One optimized solution involves sorting the input array first, incurring a time cost of O(nlogn) (assuming one uses merge sort). Then, create two indices; initialize i at the start of the array, and j at the end of the array. Check if array[i] + array[j] == target. If the sum is more than the target, decrement j; if less, increment i.

func twoSum(target int, ints []int) bool {
    sort.Ints(ints)
    i, j := 0, len(ints)-1
    for i < j {
        sum := ints[i] + ints[j]
        if sum == target {
            return true
        } else if sum > target {
            j--
        } else if sum < target {
            i++
        }
    }
    return false
}

Since this walk is considering each element only once, the walk’s time complexity is O(n), meaning the entire optimized solution has a complexity of O(nlogn). The Three-Sum variation of the problem (part two) is essentially the same, but involves “plucking” a value from the list and subtracting it from the target, then using that difference as the target in a call to twoSum(). Here the worst case runs in O(n^2), compared to the triple-nested-for-loop brute force solution that runs in O(n^3).

Day 2

Day 2 involved a bit more complex input parsing, but was otherwise fairly straightforward. One thing I was excited about (and which has featured several times since!) is my countValidPasswords function, which takes in a func(l line) bool as an argument. This means I don’t have to have a second, nearly-identical version of countValidPasswords that only differs by the isValid() function. This is possible thanks to Go’s support for first-class functions.

The other two lessons from this day’s puzzle didn’t come from the puzzle itself, but rather a newday Bash script that I wrote to quickly initialize the essential directory and files for a day’s puzzle. In writing it, I learned about heredocs. Heredocs are string-literals that allow for easy embedding of larger, more complex text strings in a script. I’m using one to store my starter program.

Although I’ve encountered them before, I learned a bit more about the -e and -u Bash flags. There’s a brief writeup about them here, but basically:

• -e sets the errexit flag. If any statement returns a non-zero return code, the script exists.
• -u sets the nounset flag. If an uninitialized variable is encountered, the script exists.

There are many others, but these two are the only ones I needed. Together, they ensure that a) a suffix-less directory is never created, and b) days are never overwritten, since mkdir fails if invoked for a directory that already exists. Basically, they’re protecting me from myself.

Day 3

This day really didn’t feature anything of note, other than a *= operator that I’m not sure I’ve ever used. I will note, however, that grids are very popular concepts in Eric’s puzzles and that we’ll likely see them again. Last year, I built up a small library for Grid and Coordinate types which I may make use of once again if the opportunity presents itself.

Day 4

Ah, day 4. The common complaint I’ve heard about this puzzle was that it was tedious. There really wasn’t a challenge beyond deciding between using regexes or more traditional logical validation. Still, there were a few notable points.

First, since Go doesn’t have sets, I resorted to the idiomatic alternative, map. By using a map[string]bool, an attempt to look up the value for a key that doesn’t exist will return the bool zero value, false. So my eye color lookup was as easy as:

var eyeColors = map[string]bool{
    "brown": true,
    "green": true,
}

func eyeColorIsValid(eyeColor string) bool {
    return eyeColors[eyeColor]
}

Second, I learned about strconv.ParseInt(), which made converting from a hex-string (e.g. 12af3c) to an integer (e.g. 1224508) easy. The function apparently allows for the conversion of any arbitrary base between 2 and 36, as well as 0 (in which case the base is determined by the input string’s prefix). I don’t plan on encountering a base-27 number anytime soon, but it’s nice to know that it won’t impede me!

Day 5

After the slog that was day 4, day 5 was easy! I immediately recognized that the puzzle description was describing a kind of binary search, though we were given the “steps” rather than a way of determining them for ourselves. Go’s built in sort.Search() might be applicable here, if one could somehow use a given boarding pass sequence in a search function.

Of note is one solution I saw on Twitter which recognized that one can simply replace the charcters in a boarding pass with ones and zeroes to get the binary representation of the seat ID. In fact, that’s all the seat ID formula (row * 8 + col) is doing by effectively shifting the row digits left three. That’s a very elegant way to do it.

One recurring lesson that these problems teach is the decomposition of a large problem into smaller, easier problems. Today’s is a great example of that. For part one, I have to find the largest seat ID, so I made a calcMaxSeatID() function. How do I get the max seat ID? I need to calculate all of the individual seat IDs and find the max. How do I calculate an individual seat ID? Easy, row * 8 + col. How do I find row and col? Functions for calcRow() and calcCol(). Here we finally get to the meat of the puzzle - given a string, how do I binary search through a slice of integers? That’s the real challenge, and everything before that is just getting there.

Day 6

On day 6, my answer for part two was delayed by not fully considering my algorithm before writing it. The idea that I would have to reuse my part one solution, but with a count, was fairly immediate. Subsequently using that count wasn’t entirely clear, so my first attempt at part two involved something like if len(rs) == len(g). Completely off the mark, but I was in guess-and-check mode. If I would have taken the time to think it through, I might have finished a minute before I did…

Day 7

And finally, we get to the end of the first week of Advent of Code 2020! Day 7 was notably harder than the previous six days. For one, the input was quite complex. I approached it by splitting the first part (the bag to which this rule pertains) from the second part (the contents of that bag). Then I used a regex to extract the individual sub-bags from the second part.

func main() {
    // bags have a color string and a map[color]int of contents
    bs := bags{}
	scanner := bufio.NewScanner(os.Stdin)

	for scanner.Scan() {
		b := bag{color(""), contents{}}
		l := strings.Split(scanner.Text(), " bags contain ")
        b.color = color(l[0])
        // defined elsewhere, contentsMatch = regexp.MustCompile(`(?U:(\d+) (.+) bag[s]?)`)
		for _, c := range contentsMatch.FindAllStringSubmatch(l[1], -1) {
			count, _ := strconv.Atoi(c[1])
			b.contents[color(c[2])] = count
		}
		bs[b.color] = b
    }
}

I wasted about a half hour debugging the result of that FindAllStringSubmatch() call before realizing that I was accessing elements 0 and 1 instead of elements 1 and 2. That leads me to an important note to myself: the first element is the full match. I made this same mistake earlier in the week when helping a friend debug their own regex, so it’s worth repeating a few times. The first element is the full match. The first element is the full match. The first element is the full match.

That should do it.

Anyway, the actual tree traversal was simple - recursively traverse the tree for each color in a bag. I didn’t run into more difficulty until I had to modify my traversal algorithm to remember not only the list of colors it encountered, but also the accumulated counts. Rather than try to modify the existing traversal function to work with both parts, I originally created a copy of it specifically for part two. Then, once I got the second star, I went back and refactored my solution to eliminated the duplicate flow.

In the future (read: tonight), I’ll change two things:

1. Make more use of custom return types. If I would have started with a custom type declaration (e.g. type contents map[color]int) I would have been able to modify my implementation without lots of copy-and-pasting.
2. Make more use of methods, instead of only using functions. It’s strange, because historically I’ve written way more methods (functions with a struct receiver) than plain functions. But the solutions thus far have benefitted from using plain functions. Methods would help me keep things more organized and clearer, especially when performing operations that are specific to a certain data type.

Conclusion

All told, this first week was a solid opening to yet another Advent of Code. The puzzles were admittedly easier than previous years’ first week, but Day 7 has me convinced that we’re in for 18 more challenges.

Until next time,
- Mario