Advent of Code 2021: Day 1

Advent of Code 2021 - Day 1

This year I decided to join Advent of Code for the first time. I'll be publishing some short posts with my solutions to 2021 AoC puzzles (probably in Python, but I might also throw some Scala in between). You'll find all the code I've written on my AoC github repostiory

Day 1 problem - Sonar Sweep (part 1)

Detailed description of the problem can be found here. But, in short - given a list of inputs like this (these are depth measurements):

199
200
208
210
200
207
240
269
260
263

determine how many times depth had increased:

199 (N/A - no previous measurement)
200 (increased) (1)
208 (increased) (2)
210 (increased) (3)
200 (decreased)
207 (increased) (4)
240 (increased) (5)
269 (increased) (6)
260 (decreased)
263 (increased) (7)

Which is 7 times for above case.

My solution (part 1)

from typing import List


def get_input_data(path: str) -> List[int]:
    with open(path, "rt") as f:
        data = [int(line) for line in f.readlines()]
    return data


def get_increased_count(input_data: List[int]) -> int:
    index_to_value = {}

    comparisons = []
    for i, v in enumerate(input_data):
        index_to_value[i] = v
        if i == 0:
            continue
        comparisons.append(v > index_to_value[i - 1])
    return sum(comparisons)


if __name__ == "__main__":
    input_data = get_input_data("aoc-day-1-input.txt")
    print(get_increased_count(input_data))

get_input_data function takes care of reading and parsing depth measurements data from text file.

The algorithm itself is represented by get_increased_count function which accepts a list of integers.

To solve it in one iteration, I created 2 helper variables:

  • index_to_value dictionary - stores store information about input list element value and index
  • comparisons list - stores booleans that are results of comparisons of adjacent elements . Sum of True values from comparisons list will be a solution for this puzzle.

Algorithm basically looks like this:

  • iterate over input element and keep track of current index (variable i) and value (variable v)
  • store i and v info in index_to_value dictionary
  • on first element of input array, skip to next loop iteration (because first list value has no previous neighbor to whom it could be compared)
  • compare current value with its previous value (retrieved from index_to_value dict) and append comparison result to comparisons list
  • return sum of comparisons variable - comparisons is List[bool]; booleans in Python are subclassing from integers (False - 0, True - 1) so list [True, True, False] is will be treated by sum func as [1, 1, 0] and it will give us the answer to our puzzle

Day 1 problem - Sonar Sweep (part 2)

Again, for more details, please use README from the repo. In short:

Considering every single measurement isn't as useful as you expected: there's just too much noise in the data. Instead, consider sums of a three-measurement sliding window.

Turns out that solution from part 1 is generic enough to help with part 2 - we only need to transform input data so it would be a sums of 3 adjacent elements (3-element sliding window).

So basically input

input_data = [1, 2, 3, 4, 5, 6]

could be split into sliding windows as follows:

input_split_into_windows = [[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6]]

And, since we need to pass sums of windows, our algorithm function from part 1 would need to receive it in below shape:

summed_windows = [sum([1, 2, 3]), sum([2, 3, 4]), sum([3, 4, 5]), sum([4, 5, 6])]

Function get_increased_count_for_sliding_window does the slicing of input list into 3-element windows sums and pass it to generic get_increased_count function to get the answer for puzzle's second part. Whole solution now like this:

from typing import List


def get_input_data(path: str) -> List[int]:
    with open(path, "rt") as f:
        data = [int(line) for line in f.readlines()]
    return data


def get_increased_count(input_data: List[int]) -> int:
    index_to_value = {}

    comparisons = []
    for i, v in enumerate(input_data):
        index_to_value[i] = v
        if i == 0:
            continue
        comparisons.append(v > index_to_value[i - 1])
    return sum(comparisons)


def get_increased_count_for_sliding_window(input_data: List[int]) -> int:
    sums = [sum(input_data[i : i + 3]) for i in range(0, len(input_data) - 2)]
    return get_increased_count(sums)


if __name__ == "__main__":
    input_data = get_input_data("aoc-day-1-input.txt")
    print(get_increased_count(input_data))
    print(get_increased_count_for_sliding_window(input_data))

And that's it for day 1 of Advent of Code 2021 :)!

Take care,
Kuba