Advent of Code 2016 - Day 3

Useful Links

Concepts and Packages Demonstrated

Problem Intro

This puzzle is about triangles. We’re given a list of numbers, three per line, like this:

10  25
 8  12
4  15

Each set of three numbers represents the lengths of the sides of a potential triangle.

Part 1

In your puzzle input, how many of the listed triangles are possible?

A triangle is valid if the sum of any two sides is greater than the third side. A simpler way to check this is to find the longest side and check if it’s shorter than the sum of the other two.

My approach is to:

Read each line of the input.
Convert the three numbers on each line into a list of integers.
Pass this list to a function is_valid_triangle that checks for validity.
Use filter() to keep only the valid triangles.

Here’s the is_valid_triangle function:

def is_valid_triangle(triangle: list) -> bool:
    """ Valid triangles have one length greater than the sum of the two shorter lengths.

    Args:
        triangle (list): side lengths of this triangle

    Returns:
        [bool]: Whether valid, according to the rules
    """
    triangle = sorted(triangle)
    return triangle[0] + triangle[1] > triangle[2]

This function first sorts the side lengths in ascending order. Then, it checks if the sum of the two shortest sides (triangle[0] and triangle[1]) is greater than the longest side (triangle[2]). If this condition holds, the triangle is valid.

And here’s how I process the input for Part 1:

    triangles = []
    for line in data:
        lengths = [int(x) for x in line.split()]
        triangles.append(lengths)

Here, I’m using a list comprehension to process each line. Let’s break down [int(x) for x in line.split()]:

line.split(): This splits the line of text into a list of strings. For example, " 5 10 25" becomes ['5', '10', '25'].
for x in ...: This iterates through each string x in the list created by line.split().
int(x): This converts each string x into an integer.
[...]: The square brackets collect the results of int(x) for each x into a new list.

So, for each line of input, this list comprehension creates a list of three integer side lengths.

Finally, I use filter() to create a new list containing only the valid triangles:

    valid_triangles = list(filter(is_valid_triangle, triangles))

Part 2

In your puzzle input, instead of reading by rows, if you read by columns, how many of the listed triangles are possible?

Instead of each row representing a triangle, the numbers are read down the columns. So, the first three numbers in the first column form a triangle, the next three in the first column form another, and so on.

The challenge here is to transform the data. I need to read the numbers in column-major order. My solution uses a combination of zip and itertools.chain.

First, I create a list of lists, where each inner list contains the three numbers from a row.
Then, I use zip(*all_numbers) to transpose the rows and columns. This gives me three lists, where each list contains all the numbers from a column.
Finally, I use itertools.chain(*transposed_nums) to flatten these three lists into a single list of numbers.

Here’s the code for that transformation:

    all_numbers = []
    for line in data:
        nums = [int(x) for x in line.split()]
        all_numbers.append(nums)
    
    transposed_nums = list(zip(*all_numbers))

For example, if all_numbers was [[1, 2, 3], [4, 5, 6], [7, 8, 9]], transposed_nums would become [(1, 4, 7), (2, 5, 8), (3, 6, 9)].

Then, itertools.chain(*transposed_nums) is used to flatten this list of tuples into a single list of numbers. This effectively concatenates all the tuples from transposed_nums into one long sequence.

    all_numbers = list(chain(*transposed_nums))

Once I have this flattened list, I can iterate through it three numbers at a time to form the triangles and check their validity, similar to Part 1.

    triangles = []
    for i, _ in enumerate(all_numbers):
        if i % 3 == 0:
            triangles.append([all_numbers[i], all_numbers[i+1], all_numbers[i+2]])

    valid_triangles = list(filter(is_valid_triangle, triangles))

This approach is efficient because it avoids complex indexing and manual iteration over the columns. zip and itertools.chain are powerful tools for this kind of data manipulation.

A Note on `filter()`

In both parts of this solution, I use the built-in filter() function to select the valid triangles. The filter() function is a concise and readable way to filter elements from an iterable (like a list) based on a function that returns True or False.

The syntax is filter(function, iterable). In my code, filter(is_valid_triangle, triangles) applies the is_valid_triangle function to each triangle in the triangles list. The filter() function then returns a filter object, which is an iterator that yields only the items for which is_valid_triangle returned True.

To get a list of these valid triangles, I wrap the filter object in list():

valid_triangles = list(filter(is_valid_triangle, triangles))

This is a common and Pythonic way to filter data. It’s often more memory-efficient than a list comprehension for large datasets because it doesn’t create the new list in memory all at once. You can read more about filter() here.

‹›