This task echoes the one from Day 3 in 2018; this too is a computational geometry problem, and here too we only need to consider overlaps between horizontal and vertical lines. Computational geometry has come up quite often in AoC, in 2018 days 3, 6 and 17 all were geometry challenges in the same vein.
So, we parse the input into lines, then sort by their start coordinates ($x$ first, then $y$), and process the lines in that order. I noticed that some lines have their start and end points 'reversed', with the end coordinates with lower values than their starts, so while parsing I swap those to ensure lines can be kept in sorted order. By sorting, we don't have to know up front how far $x$ and $y$ range and we don't have to concern ourselves with every possible value for $x$ and $y$. This approach is known as the sweep line algorithm.
Instead, we can iterate over the lines in sorted order and keep a heap queue of lines that are still in effect. A line is still in effect if their end point is higher than the stating coordinate of the line being processed (meaning, it is below or to the right of the current line), so the heap is ordered by the end coordinates.
Because we only count overlaps and not the number of lines that overlap on each point, we record the overlapping points as a set. That way we don't accidentally count 3 lines overlapping on the same coordinate as 2 separate overlaps. We also don't need to track all points across all lines, and so don't need to keep counts either. The input puzzle, for example, would require keeping a counter for all 21 points touched, rather than a set for the 5 points with intersections and overlaps.
To calculate the intersections, I adapted the maths for determining the intersection of two line segments from the Wikipedia article on line intersections.
from __future__ import annotations
from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import repeat
from typing import Iterable, NamedTuple
class Point(NamedTuple):
x: int
y: int
def __str__(self) -> str:
return f"{self.x},{self.y}"
@classmethod
def from_str(cls, s: str) -> Point:
return cls(*map(int, s.split(",")))
@dataclass(order=True)
class Line:
start: Point
end: Point
@classmethod
def from_string(cls, line: str) -> Line:
# start should always be to the left / above from end, so all our
# lines run from left to right or top to bottom (not counting diagonal
# slopes going up)
return cls(*sorted(map(Point.from_str, line.split("->"))))
@property
def straight(self) -> bool:
return self.start.x == self.end.x or self.start.y == self.end.y
def __str__(self) -> str:
return f"{self.start} -> {self.end}"
def __mul__(self, p: Point) -> int:
"""Calculate the cross-product of this line and point p"""
dx, dy = self.end.x - self.start.x, self.end.y - self.start.y
return dx * (p.y - self.start.y) - (p.x - self.start.x) * dy
def __and__(self, other: Line) -> Iterable[Point]:
"""Yield all points at which this line intersects with other"""
sstart, send, ostart, oend = self.start, self.end, other.start, other.end
# check for the cross-product of the two lines to check if they intersect
cross_sos, cross_soe = self * ostart, self * oend
cpother = (other * sstart) * (other * send)
if not ((cross_sos * cross_soe <= 0 and cpother <= 0) or not cross_sos):
return
# find if two line segments intersect, and where, adapted from
# https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
sdx, sdy = send.x - sstart.x, send.y - sstart.y
odx, ody = oend.x - ostart.x, oend.y - ostart.y
# With integer coordinates we need to account for diagonal lines
# passing one another and not actually intersecting, which happens
# when they run along 'odd' and 'even' diagonals
if not (self.straight or other.straight):
# intercepts of the diagonals must both be odd or even
sparity = (sstart.y + (sdy // sdx) * sstart.x) % 2
oparity = (ostart.y + (ody // odx) * ostart.x) % 2
if sparity != oparity:
return
denom = sdx * ody - odx * sdy
if denom:
# there is a single intersection point
num = odx * (sstart.y - ostart.y) - ody * (sstart.x - ostart.x)
yield Point(sstart.x + sdx * num // denom, sstart.y + sdy * num // denom)
else:
# lines overlap along a segment
xs = range(ostart.x, min(send.x, oend.x) + 1) if sdx else repeat(ostart.x)
match sdy:
case 0:
ys = repeat(ostart.y)
case _ if sdy < 0:
ys = range(ostart.y, max(send.y, oend.y) - 1, -1)
case _: # > 0
ys = range(ostart.y, min(send.y, oend.y) + 1)
yield from (Point(x, y) for x, y in zip(xs, ys))
@dataclass
class HydrothermalVents:
lines: list[Line]
@classmethod
def from_lines(
cls, lines: list[str], ignore_diagonals: bool = True
) -> HydrothermalVents:
vents = map(Line.from_string, lines)
if ignore_diagonals:
vents = (line for line in vents if line.straight)
return cls(sorted(vents))
def count_most_dangerous(self) -> int:
# heap with (end, line), endpoints per still-active lines
queue: list[tuple[Point, Line]] = []
# all points touched by 2 or more lines.
overlaps: set[Point] = set()
for line in self.lines:
# clear queued lines no longer active (.end to left or above this line)
while queue and queue[0][0] < line.start:
heappop(queue)
overlaps |= {p for _, other in queue for p in other & line}
heappush(queue, (line.end, line))
return len(overlaps)
test_lines = """\
0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2
""".splitlines()
assert HydrothermalVents.from_lines(test_lines).count_most_dangerous() == 5
import aocd
ventlines = aocd.get_data(day=5, year=2021).splitlines()
print("Part 1:", HydrothermalVents.from_lines(ventlines).count_most_dangerous())
Part 1: 7436
Now we need to consider diagonals too. My intersection code already handled most of the work for diagonals; I added a case for $y$ ranging downwards and could load the lines with diagonals included.
Initially, this gave me quite a headache as my numbers kept coming out too high, until I realised that with integer coordinates, two diagonal lines can pass by one another without intersecting, at the point of crossing occupying the 4 cells in a square instead of passing through the same single cell.
assert HydrothermalVents.from_lines(test_lines, False).count_most_dangerous() == 12
print("Part 2:", HydrothermalVents.from_lines(ventlines, False).count_most_dangerous())
Part 2: 21104