🎄🧑‍💻 Day 2: Dive!

Thu, 2 Dec 2021

Go here to read Day 2's puzzle text in full.

Part 1

The puzzle input was a list of instructions. Each of them includes a direction keyword between forward, down, or up, and a positive integer indicating how many steps we are making in the given direction. For example:

forward 5  
down 5  
forward 8  
up 3  
down 8  
forward 2

The only note: up means that we should subtract the corresponding value from the total depth; down increments the depth, instead. The problem was asking to compute the product between the final horizontal position and depth.

Similar to what we did in Day 1, with Python we can obtain the solution with a simple loop over the list of lines returned by our friend fileinput.input():

import fileinput

h_pos = 0
depth = 0

for line in fileinput.input():
	x = int(line.split()[-1])
	if line.startswith('forward'):
		h_pos += x
	elif line.startswith('down'):
		depth += x
	elif line.startswith('up'):
		depth -= x 

The answer is then h_pos * depth. Nothing particularly difficult, even slightly boring (I’ll be punished for having said that 😁).

Part 2

The second half of the problem introduces the third quantity to track (the aim) that makes things a bit more interesting. Depth is not the running sum between up and down instructions, each taken with the correct sign; up/down will change the value of the aim, and the depth is updated only after a forward instruction: depth = depth + aim * x, where x is the numeric argument to forward.

The simplest way requires to add two lines to our previous code and change the variable we are incrementing/decrementing when encountering up or down:

h_pos = 0
depth = 0
aim = 0

for line in fileinput.input():
	x = int(line.split()[-1])
	if line.startswith('forward'):
		h_pos += x
		depth += aim * x
	elif line.startswith('down'):
		aim += x
	elif line.startswith('up'):
		aim -= x 

Once again, the answer to this part is h_pos * depth.

Another way to look at the problem

We can read the puzzle input in a different way which opens up a second (among many) ways of obtaining the solution. We could consider the three instruction types arrays, or vectors, and the entire input as a matrix. Like this (I’m using the first letter of each instruction):

First, note that we also have to add zeroes as these vectors must be of the same length: it’s a sparse matrix¹ as we have only 6 non-zero values. We can now add the aim (a) and depth (D) columns:

The answer, if our input were the example above, would be (2+8+5) x 60 = 900, that is, the sum of the f column times the last value of the D columns. Step by step:

1. Calculate the a column, which is the list of successive accumulated totals of d - u.
2. Multiply columns f and a element-wise
3. Calculate again the accumulated totals for the list obtained in step 2 and take the last element.
4. Calculate the sum of f and multiply it by the value obtained in step 3.

First, we must read the instructions and create the initial vectors (forward, up, and down), adding a zero each time that instruction type is not updated. For the example above, we end up with three lists, fList, uList, and dList:

{fList, uList, dList} = {
	{5, 0, 8, 0, 0, 2},
	{0, 0, 0, 3, 0, 0},
	{0, 5, 0, 0, 8, 0}
}

Now, translating into code the steps above:

1. aimList = Accumulate[dList - uList]
2. fList * aimList is automatically an element-wise multiplication in the Wolfram Language
3. depthList = Accumulate[fList * aimList] is the second array resulting from a running sum
4. result = Total@fList * Last@depthList

I admit that, after having written about it, this second way of interpreting the problem is overly complicated and it doesn't bring that many insights (and it's probably not faster). I was motivated to find a different approach and write it in a different language than Python.

Once again, if you're interested, you can find the full code of both approaches in my GitHub repo.

#advent of code #programming #python #wolfram