Advent of Code 2016 - Day 3

Useful Links

Concepts and Packages Demonstrated

filter itertools zip chain Comprehensions Logging os Timing and Progress

Problem Intro

This puzzle challenges us to identify valid triangles from a given list of side lengths. We’re provided with a list of numbers, and our task is to determine how many of these sets of three numbers can form a valid triangle.

The rule for a valid triangle is that the sum of any two sides must be greater than the remaining side. For example, a triangle with sides 5, 10, and 25 is invalid because 5 + 10 is not greater than 25.

The input data looks like this, with each line representing three potential side lengths:

10  25
20 30
13 14

Part 1

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

For Part 1, we process the input data line by line. Each line contains three space-separated numbers, which represent the side lengths of a potential triangle. We need to count how many of these satisfy the triangle inequality theorem.

The core logic is encapsulated in 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.

In the main function, we read the input file, parse each line into a list of integers, and then use the filter function with is_valid_triangle to count the valid triangles:

    triangles = []
    for line in data:
        lengths = [int(x) for x in line.split()]
        triangles.append(lengths)
    
    valid_triangles = list(filter(is_valid_triangle, triangles))
    
    logging.info("Part 1")
    logging.info(f"We have a total of {len(triangles)} triangles, of which {len(valid_triangles)} are valid.")

Part 2

Now that you’ve helpfully marked up some of the impossible triangles, you notice that the Elves are actually reading this list in a different way. Instead of reading each line as a single triangle, they’re reading three numbers from a column at a time. That is, the first number of the first three lines together form the first triangle, the second number of the first three lines form the second triangle, and the third number of the first three lines form the third triangle. Then, the next three lines are read the same way, and so on.

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

Part 2 introduces a twist: instead of reading triangle side lengths horizontally (row by row), we now read them vertically (column by column). This means we need to group the first numbers of three consecutive lines, then the second numbers of those same three lines, and finally the third numbers. This process repeats for every block of three lines.

The key challenge here is to “transpose” the data. The solution uses zip and itertools.chain to achieve this efficiently.

First, we parse all numbers from the input into a list of lists, where each inner list represents a row:

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

Next, we use zip(*all_numbers) to transpose the data. zip with the * operator unpacks the all_numbers list, effectively treating each inner list as a separate argument to zip. This results in tuples where the first elements of all inner lists are grouped, then the second elements, and so on.

    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))

Now, all_numbers contains all the side lengths in the correct order for column-wise triangle formation. We then iterate through this flattened list, taking three numbers at a time to form new triangles:

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

Finally, we apply the is_valid_triangle function again to this new set of triangles to count the valid ones, just like in Part 1.

    valid_triangles = list(filter(is_valid_triangle, triangles))
    logging.info("Part 2")
    logging.info(f"We have a total of {len(triangles)} triangles, of which {len(valid_triangles)} are valid.")

‹›