Advent of Code 2022

Diary of AOC 2022. This is my first time attempting AOC. I ended up with 45 stars. My company had a private leaderboard, and I am competitive enough to take the bait. I chose python to solve the puzzles. I know many people use AOC as an opportunity to learn new languages, but I wanted to go with something familiar. I never used python in a professional setting, but I love using it for scripting and writing scrappy code.

Day 10 check-in -

I am writing this after 10 days of doing AOC. The first few days just needed string manipulations, sets, string slicing, nothing complex. The fifth day’s input was interesting. It required people to parse input of characters that were put inside square brackets. Also, having vertical stacks instead of horizontal ones pissed a few people off.

[D]
[N] [C]
[Z] [M] [P]

I am a big fan of regex. I wrote some very simple regex to transform it into something friendly to parse in python: removed brackets and replaced spaces with hashes.

Day 7 is the day I finally struggled a bit. The problem is about going through a folder structure on a PC and being able to tell each folder’s size. Now the problem itself is a simple tree traversal. I initially decided to write some scrappy code using dictionaries. But it fell apart very quickly. Unlike other tree problems, a folder name isn’t a unique id to represent a node(Folder). Example - A folder, let’s call it A, can have two subfolders, B and C. B can have a subfolder named A.

You can still use this approach by making one simple change - while folder names aren’t unique, the path of a folder always is. The path of a folder can be used as a key. While it’s a bit clunky, it works. But I decided to do this using a class called directory and having pointers to each directory’s parent and children. This makes the code very short. Instead of tracking the connections, I am just letting my computer do it at runtime. I remember thinking; this is it; I should make logic as implicit as possible and only handle things that I need to explicitly (unless you are concerned about performance in some cases). Something I thought of but had not internalized. Day 8 involved traversing a grid that has trees of different heights and finding max length of the substring we have seen in any of the 4 directions on a compass. Nothing too complicated.

Day9 was about a snake of length 1 traversing a grid using a set of rules. We are required to keep track of the tail’s position. It started the same way every other day had, by writing scrappy code. I tried to visualize every possible case and write code for it. Only problem is, ten minutes into it, I wrote code for 16 different conditions, and I wasn’t happy with it.

The input was given as LEFT 6, RIGHT 5, UP 4, DOWN 7, etc.

When I see LEFT 6, I have to move my snake 6 steps to the left, ONE STEP AT A TIME. All I would need to do is write code for the snake’s movement for a step in any direction and I am done. But instead of doing that, I started writing code to infer where the tail would end up after 6 steps and all the positions it would have traced. Debugging was a nightmare, and time was of the essence, so I decided to write code for a single step. Lucky for me, it generalized well to the second part. I am shouting again - “Make the logic implicit dummy. Let the computer do the work”. I think this is the most valuable thing I re-learned while solving AOC. As a programmer especially when you are writing complex software without insane performance requirements, our duty is to define good interfaces that generalize, keep as little state in the code as possible, let the computer handle it. And if possible don’t tell the computer how to solve something. Trust the compiler.

Day 10 was a simple puzzle with a very fun output. The hashes(#s) generated by your program output form English capital letters. It is interesting to think about the question backward. If you were to design the question with unique (and fun) output for every user, how would you go about it? It’s not hard, but I am really glad someone went the distance to do it instead of asking to count number of hashes.

Day 15 check-in -

The difficulty has increased. I felt the heat on some days. It still doesn’t require any complex algorithms to solve the puzzles, but brute force doesn’t cut it anymore either. Let’s dig in.

Day 11 part 2 requires a way to keep big integers small. Surprise, surprise, modulo arithmetic. Multiple clues point towards it. One big clue in the question was a repeating division operation where the divisor is always a prime number. So using the number mod( multiply( list( prime number divisors ))) is the same as using the original number

One thing I like to do to make my “grid” problems if-else free is to pad them with infinities if we are searching for minimas and -infs if we are searching for maximas.

Day13 required you to write a custom parser to read a list of lists. Import json ftw!

I usually simulate the process-specified problem to arrive at the solution. For grid problems, this means creating a huge grid and doing operations on it. Day14 required a more optimal approach. If you want to only know the points that have already been covered, why not just store the coordinates of visited points? In python I used a set to ensure uniqueness, and checking membership in a set is usually O(1). We don’t have to store the “void.”

Can we do better than storing a set of points? Day 15 asked me this question. Each sensor has a rhombus-shaped field around it, and we need to find the field’s intersection with a line parallel to one of its diagonals. Storing every point of the rhombus is impractical in the bounds defined by the question. I realized that we just need to know the circumference to figure out the intersections. The problem is framed for a special case where finding the points of intersection is easy. Once you have the intervals where the line intersects the sensor fields, you just need algorithms for interval merging and searching among intervals to solve the problems.