website/content/wiki/aoc/2021/05.md

title	date	day	stars
AoC 2021 - Day 5	2021-12-05T13:51:01+01:00	5	2

Today's challenge is here. Here we get a punch of lines in the form of two points and we have to find number of points where they cross. For parsing the data I used a regular expression (\d+),(\d+) -> (\d+),(\d+).

Loading data from the input file:

pattern = re.compile(r'(\d+),(\d+) -> (\d+),(\d+)')


def loader() -> list[Tuple[Tuple[int, int], Tuple[int, int]]]:
    with open('../.input/day05', 'r') as f:
        return [
            ((int(x1), int(y1)), (int(x2), int(y2)))
            for x1, y1, x2, y2
            in pattern.findall(f.read())
        ]

Task 1

In this task we have to find number of points where lines cross, but we have to skip the diagonal lines. When I was solving this task I did a mistake and I included the logic for counting the diagonal lines as well.

Here is the function for generating the list of points for any line. I used generators pretty liberally as well as the itertools.repeat function, which is used to generate infinite sequences of a single value. I had to use that for cases where the line is vertical or horizontal, because otherwise the zip function would stop at the first iteration.

def find_points_in_line(x1, y1, x2, y2, skip_diagonal: bool = False) -> Iterable[Tuple[int, int]]:
    if skip_diagonal and x1 != x2 and y1 != y2:
        return []
    if x2 < x1 and y2 < y1:
        return find_points_in_line(x2, y2, x1, y1)
    if x2 < x1:
        y = (y for y in range(y1, y2 + 1)) if y1 != y2 else repeat(y1)
        return zip(range(x1, x2 - 1, -1), y)
    if y2 < y1:
        x = (x for x in range(x1, x2 + 1)) if x1 != x2 else repeat(x1)
        return zip(x, range(y1, y2 - 1, -1))
    if x1 == x2:
        return zip(repeat(x1), range(min(y1, y2), max(y1, y2) + 1))
    if y1 == y2:
        return zip(range(min(x1, x2), max(x1, x2) + 1), repeat(y1))
    return zip(range(x1, x2 + 1), range(y1, y2 + 1))

Here we use two sets to store the visited points as well as the points where lines cross. We can do this because we don't need to know how many lines cross at any given point, just the number of crossing points in general. A set is a perfect choice for this, it saves us memory and time.

def solve1(skip_diagonal=True) -> int:
    visited_pts = set()
    crossed_pts = set()
    for (start, end) in loader():
        for x, y in find_points_in_line(*start, *end, skip_diagonal):
            if (x, y) in visited_pts:
                crossed_pts.add((x, y))
            else:
                visited_pts.add((x, y))
    return len(crossed_pts)

Task 2

Do I need to say anything here? 😄

def solve2() -> int:
    return solve1(skip_diagonal=False)