Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

deep

Advent of Code 2021 - Day 1

Day 1: Sonar Sweep

Useful Links

Concepts and Packages Demonstrated

LoggingNumPy

Reading filesmaptimerrangedeque

Problem Intro

As is typical for AoC, Day 1 is a trivial challenge.

We’re told we’re performing a sonar sweep of the ocean floor, to map the depth. We need to figure out how quickly the depth increases.

I wrote two different solutions to this problem.

Solution #1

Part 1

The goal for part 1 is to parse a list of depth figures, and count how many times the depth increases.

Basic Setup

The code expects the input file to be stored in a file called input.txt, and for this file to be in a folder called input, which lives in the same place as the script.

folder

I can alternative between sample input and the real input by commenting out the appropriate SCRIPT_DIR. We then use the with open context manager to open the file, read its entire contents, split the file into separate lines, and store these lines in a list called depths. Note that each item in depths is a string.

Also of note: I’m using the Python logging module, rather than simply print() statements. The advantage of the logging module is that we explicitly specify the “level” for any given logging statement. Any logging statements below the specified threshold will not be suppressed. Here’s a demo of how to use the logging module:

# initialise the Root logger
# It will print the time (including milliseconds), the logging level, and the logger name
logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", datefmt='%H:%M:%S')
# now get a named instance of the logger for our application
logger = logging.getLogger(__name__) 

# Set the logging threshold of our logging instance to DEBUG
logger.setLevel(logging.DEBUG) 

# print some stuff
logger.debug("We'll see this.")
logger.info("And this.")

# now set threshold to INFO; everything below INFO is now suppressed
logger.setLevel(logging.INFO) 

# print some more stuff
logger.debug("We will NOT see this.")
logger.info("But we will see this.")

The output from the above looks like this:

09:08:46.929:DEBUG:__main__:    We'll see this.
09:08:46.929:INFO:__main__:     And this
09:08:46.929:INFO:__main__:     But we will see this.

The next thing to note is that I’m using the time module, in order to time the overall execution of the program. I capture the time t1, then run the main() function (which runs everything), then capture time t2. Finally, subtract the time t2 from t1, and report the difference. The output looks like this:

2022-01-05 20:25:01.365:INFO:__main__:  There are 2000 measurements
2022-01-05 20:25:01.365:INFO:__main__:  Depth increases 1451 times
2022-01-05 20:25:01.365:INFO:__main__:  Execution time: 0.0025 seconds

Solving the Problem

The input data looks something like this:

199
200
208
210
200

This is a simple problem. We want to look at each number, and see if it’s bigger than the previous number.

I want to be able to work with a list of numbers, not a list of strings. So I convert the list of str to a list of int using the map() function. This function takes two parameters: first, a function we want to apply, and secondly, a collection we want to apply the funtion to. So in this case, we’re applying the int() function against every member of depths. The result is a new list, which is now made up of int values.

Now we iterate through each depth in the list, starting at 1, and compare each depth (i) to the previous depth (i-1). Everytime depth[i] is greater than depth[i-1], we increment our counter.

Trivial!

Part 2

Now the challenge is a tiny bit harder. Rather than comparing each number to the last, we now need to compare a sliding window of 3 numbers to the previous 3 numbers.

    # Part 2
    measurements_window_sz = 3
    three_measurements = deque(depths[0:measurements_window_sz], maxlen=measurements_window_sz)
    last_three_sum = sum(three_measurements)
    
    increase_counter = 0
    for i in range(measurements_window_sz, len(depths)):
        three_measurements.append(depths[i])
        current_three_sum = sum(three_measurements)
        if current_three_sum > last_three_sum:
            increase_counter += 1
            
        last_three_sum = current_three_sum
    
    logger.info("Depth increases %d times", increase_counter)

For this part, I’m using a deque (pronounced “deck”); it’s short for “double-ended queue”. A cool thing about the deque is that we can tell it to only keep the last n items that were added to it. We do this with maxlen. So here I create a deque using the first three values from depths, and tell the deque to only ever keep 3 values.

We use sum() to add up all the numbers in the deque.

Now we iterate through depths, starting at the 4th item. With each iteration, we add the new number to the deque. The deque automatically bins the oldest number, so it only ever retains the last three numbers. We sum() the deque again, and compare to the previous sum. Each time the sum is greater than the previous, we increase the counter.

The output for both parts looks like this:

2022-01-06 23:16:51.650:INFO:__main__:  There are 2000 measurements
2022-01-06 23:16:51.650:INFO:__main__:  Depth increases 1451 times
2022-01-06 23:16:51.650:INFO:__main__:  Depth increases 1395 times
2022-01-06 23:16:51.650:INFO:__main__:  Execution time: 0.0450 seconds

Solution #2

Here I’m using Numpy, a data science package that is awesome for manipulating arrays of data. It makes for much shorter code in a problem like this.

Setup

If you don’t have Numpy installed, the easiest way to install it is with pip:

py -m pip install numpy

The rest of the setup is the same as before.

Solving the Problem

import logging
import os
import time
import numpy as np

SCRIPT_DIR = os.path.dirname(__file__) 
INPUT_FILE = "input/input.txt"
# INPUT_FILE = "input/sample_input.txt"

logging.basicConfig(format="%(asctime)s.%(msecs)03d:%(levelname)s:%(name)s:\t%(message)s", 
                    datefmt='%Y-%m-%d %H:%M:%S')
logger = logging.getLogger(__name__)
logger.setLevel(logging.INFO)

def main():
    input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
    depths = np.loadtxt(input_file)
    
    # Part 1
    # sum count of where depth n is greater than depth n-1, where n starts at 1, to the last.
    increase_count = (depths[1:] > depths[:-1]).sum()
    logger.info("Part 1: Depth increases %d times", increase_count)
    
    # Part 2
    window_sz = 3
    # sum count of where n > n-3, where n starts at 3, to the last.
    increase_count = (depths[window_sz:] > depths[:-window_sz]).sum()
    logger.info("Part 2:Depth increases %d times", increase_count)

Rather than reading the file and splitting it, we load the input file directly into a numpy array. And now we can apply our comparison for every member of the array in a single line! The line below means: compare every item in the array, starting at n, with every item starting at n-1 (and ending one before the end), and count how many times the first is greater than the second.

    increase_count = (depths[1:] > depths[:-1]).sum()

So that’s it for Part 1!

For Part 2, we can basically use the same solution, once we realise that:

    x[n+3] + x[n+2] + x[n+1] > x[n+2] + x[n+1] + x[n]
  = x[n+3]                   >                   x[n]

(This is simply cancelling redundant terms on both sides.)

So now we can use the same Numpy solution, but comparing n+3 to n each time, rather than n+1 to n.

And that’s it!