🎄🧑‍💻 Day 1: Sonar sweep

Wed, 1 Dec 2021

Go here to read Day 1 puzzle text in full.

Part 1

The first half of the problem is rather straightforward: we have to read a list of integers and count how many times the number in the i-th row is greater than the one in the i-1 row. This is equivalent to saying that we want to operate on a fixed-size window of data in our input. As the problem's text suggests, we may call our input depths as it represents the readings of a sonar which measures… well, depth.

In Python, it's immediate to loop over N lists (or iterables in general) while considering, at each step, a tuple of N elements: we can use the zip library function.

When the input is a list, I like using the fileinput module that “iterates over the lines of all files listed in sys.argv[1:], defaulting to sys.stdin if the list is empty”. Quick and useful.

import fileinput

depths = [int(line.strip()) for line in fileinput.input()]

Standard Python stuff here: a list comprehension that performs two operations on each line of input: trims any whitespace character and converts a string into an integer.

To calculate the number of times the depth measurement increased, we need a simple for loop:

increased = 0

for i, j in zip(depths[:-1], depth[1:]):
	if j > i:
		increased += 1

The zip function allows iterating over the input list twice, shifting the second “copy” by one element. In this way, zip returns a list of tuples of the form (depths[i], depths[i+1]), and we can subtract these two elements to determine if the depth has increased or not. The value of increased is the solution to the first part.

It's day one, and this problem is indeed very easy. But that doesn't mean that we can try to find a different solution. As I said in the brief intro, I want to compare at least two implementations of my solution, changing it in a way that suits the strengths of the programming language used.

How would I write the solution above with the Wolfram Language? One well-known advantage of that language is its enormous built-in library of functions — that’s why it is powerful and versatile for a wide range of fields. In the Wolfram Language, there's no need to invent a way to shift an array and apply a function to a tuple of elements whose length is the size of the shift (in our case, 2 elements): this function is built-in and is called MovingMap.

countPositiveIncrements[list_List] :=
		Count[MovingMap[Apply[Subtract], list, 1], _?Negative]

And the solution to Part 1 is as simple as calling countPositiveIncrements on our input. Although it’s a simple line, the above definition contains a few core features of the language that it might be interesting to look at in detail. Starting from the innermost part.

Apply[Subtract] handles the fact that Subtract expects two “positional” arguments, to use a term more appropriate to Python, and not a list of two elements. This is the purpose of Apply which behaves very much like the unpacking operator * of Python. Its syntax is Apply[func, expr], and in Python would translate roughly into def func(*expr): .... Here Apply is written in its operator form, that is, a generic form that can be applied to an arbitrary expression.

One level up, there’s MovingMap[f, data, N]: it applies f to a tuple of N elements in the specified data. The result with f = Apply[Subtract] is a list of M - N elements, if M is the size of data, where each element is data[[i]] - data[[i+1]]¹.

The outermost part simply counts how many negative elements there are in the resulting list, which corresponds to the times a depth measurement increased.

The last question is: how can we define our own MovingMap in Python? We have only to figure out how to reshape our data so that we can apply a function on tuples with size + 1 elements. We can work it out with pen and paper for two easy cases, with size equal to 2 and 3. The general expression is:

new_data = [data[i:i - size] for i in range(size)] + [data[size:]]

M must be positive and less than the length of data to make sense. Lastly, we have to apply our function to each element (a tuple) of new_data. Python provides the map method that does that. Here’s our final moving map function in Python:

def moving_map(func, data, size=1):
    """Applies `func` over a window of size `size` in the specified `data`"""
    assert size > 0 and size < len(data), "Invalid window size"
    M = len(data) - size - 1
    new_data = [data[i:i - M] for i in range(M)] + [data[M:]]
    return list(map(func, new_data))

This function returns the same list we would obtain with Apply in the Wolfram Language.

To obtain the answer to Part 1 with our moving_map function, we can use a simple lambda to filter how many elements are positive:

positive_increments = filter(lambda x: x > 0, moving_map(lambda x: x[-1] - x[0], depths, 1))

# Answer to Part 1
part_1 = len(list(positive_increments))

Part 2

The second part increases slightly the difficulty of the problem, but not much if we have the built-in MovingMap (or our moving_map) function. There’s one additional step: first, we have to consider “sums of a three-measurement sliding window”. Easy enough:

sums_three_sized = moving_map(sum, depths, size=2)

Then, we have to count again how many times these sums of three depth measurements increase, as done in Part 1. Writing a generic moving_map function paid off.

Final words

I hope my explanation was clear and not too long (probably it was). I’m still judging how much in detail I want to go in these posts. Forgive me if I take a while to find the optimal length. And I would love to read a comment if you found it interesting!

Ah, you can find the full code here, for all the days I’m able to find and write a solution.

#advent of code #programming #python #wolfram