Oh boy, more cartesian coordinates.
We're going to read in the pairs of coordinates, we can filter at this point for only horizontal or vertical coordinates and then we're loooking for intersecting lines. There's probably a fancy mathmatical way to do this, but I suspect it's easier to just plot each line on a grid.
## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()
First, lets parse the input into lines
from collections import namedtuple
import re
Coord = namedtuple('Coord', ['x', 'y'])
def line_to_numbers(line):
return [int(x) for x in re.match("(\d+),(\d+) -> (\d+),(\d+)", line).groups()]
assert [1,2,3,4] == line_to_numbers("1,2 -> 3,4")
assert [100,200,300,400] == line_to_numbers("100,200 -> 300,400")
def parse_lines(lines):
coords = []
for line in lines:
a,b,c,d = line_to_numbers(line)
coords.append((Coord(a,b), Coord(c,d)))
return coords
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"""
test_coords = parse_lines(test_lines.split('\n'))
assert 10 == len(test_coords)
assert (Coord(0,9),Coord(5,9)) == test_coords[0]
assert (Coord(8,0),Coord(0,8)) == test_coords[1]
Right, we can turn the numbers into coordinates. We're going to use the filter command, but we need a function that can spot non-horizontal or vertical lines, so let's write that first
def is_vertical_or_horizontal(c):
return c[0].x == c[1].x or c[0].y == c[1].y
assert is_vertical_or_horizontal((Coord(2,2), Coord(2,4)))
assert is_vertical_or_horizontal((Coord(2,2), Coord(4,2)))
assert is_vertical_or_horizontal((Coord(4,2), Coord(2,2)))
assert is_vertical_or_horizontal((Coord(2,4), Coord(2,2)))
assert not is_vertical_or_horizontal((Coord(2,2), Coord(4,4)))
assert not is_vertical_or_horizontal((Coord(2,2), Coord(6,4)))
Now we can filter the list down to just the vertical and horizontal ones
hv_test_coords = list(filter(is_vertical_or_horizontal, test_coords))
assert 6 == len(hv_test_coords)
assert (Coord(0,9),Coord(5,9)) == hv_test_coords[0]
assert (Coord(9,4),Coord(3,4)) == hv_test_coords[1]
assert (Coord(2,2),Coord(2,1)) == hv_test_coords[2]
assert (Coord(7,0),Coord(7,4)) == hv_test_coords[3]
Now we just have to apply those lines to a grid, and then walk the line adding 1 to each number in that coordinate. We're going to need to return a list of coordinates from a start/stop position, and then we're going to want to use some kind of grid object to keep track of the lines.
When we're calculating the lines, we need to remmeber that we wont know whether the start point is left or right of the end point. So we can use min(start.x, stop.x) to find the lowest x, and max(start.x, stop.x) to find the highest x.
def line_from_coords(start, stop):
if start.x == stop.x:
return [Coord(start.x, y) for y in range(min(start.y,stop.y), max(start.y,stop.y)+1)]
else:
return [Coord(x, start.y) for x in range(min(start.x,stop.x), max(start.x,stop.x)+1)]
assert [Coord(2,2), Coord(3,2), Coord(4,2)] == line_from_coords(Coord(2,2), Coord(4,2))
assert [Coord(2,2), Coord(3,2), Coord(4,2)] == line_from_coords(Coord(4,2), Coord(2,2))
assert [Coord(2,2), Coord(2,3), Coord(2,4)] == line_from_coords(Coord(2,2), Coord(2,4))
assert [Coord(2,2), Coord(2,3), Coord(2,4)] == line_from_coords(Coord(2,4), Coord(2,2))
from collections import defaultdict
def apply_lines_to_grid(lines):
grid = defaultdict(int)
for line in lines:
coords = line_from_coords(line[0], line[1])
for coord in coords:
grid[coord] += 1
return grid
assert {Coord(2,2):1, Coord(3,2): 1, Coord(4,2): 2, Coord(4,3):1, Coord(4,4):1} == apply_lines_to_grid([(Coord(2,2),Coord(4,2)), (Coord(4,2),Coord(4,4))])
test_grid = apply_lines_to_grid(hv_test_coords)
assert 5 == len([v for v in test_grid.values() if v > 1])
Ok, that works. We initialise a grid, and then get all the values out, and filter for only the ones greater than 1 and then the length of the list is the number.
Let's try this all on some production data
data = [l.strip() for l in open("day5.txt").readlines()]
coords = list(filter(is_vertical_or_horizontal, parse_lines(data)))
grid = apply_lines_to_grid(coords)
print(len([v for v in grid.values() if v > 1]))
6461
Boom! That works. Now onto
This should be fairly easy, we now need to account for diagonal lines. We're told that we never have to worry about non-45 degree lines, so each line will increase by +/- 1 in each direction.
Luckily this just means redefining the line_from_coords, and not filtering the list.
Our line_from_coords now needs to handle not just determining if it's horizontal or vertical, but also diagonal.
def line_from_coords(start, stop):
if start.x == stop.x:
return [Coord(start.x, y) for y in range(min(start.y,stop.y), max(start.y,stop.y)+1)]
elif start.y == stop.y:
return [Coord(x, start.y) for x in range(min(start.x,stop.x), max(start.x,stop.x)+1)]
else:
# A diagonal line at 45 degrees is always as long as either x or y difference (and both must be the same)
length = max(start.x,stop.x) - min(start.x, stop.x)
dx = 1 if stop.x > start.x else -1
dy = 1 if stop.y > start.y else -1
return [Coord(start.x+i*dx, start.y+i*dy) for i in range(length+1)]
# Horizontal line
assert [Coord(2,2), Coord(3,2), Coord(4,2)] == line_from_coords(Coord(2,2), Coord(4,2))
assert [Coord(2,2), Coord(3,2), Coord(4,2)] == line_from_coords(Coord(4,2), Coord(2,2))
# Vertical line
assert [Coord(2,2), Coord(2,3), Coord(2,4)] == line_from_coords(Coord(2,2), Coord(2,4))
assert [Coord(2,2), Coord(2,3), Coord(2,4)] == line_from_coords(Coord(2,4), Coord(2,2))
# Diagonal line up
assert [Coord(2,2), Coord(3,3), Coord(4,4)] == line_from_coords(Coord(2,2), Coord(4,4))
assert [Coord(4,4), Coord(3,3), Coord(2,2)] == line_from_coords(Coord(4,4), Coord(2,2))
# Diagonal line down
assert [Coord(2,4), Coord(3,3), Coord(4,2)] == line_from_coords(Coord(2,4), Coord(4,2))
assert [Coord(4,2), Coord(3,3), Coord(2,4)] == line_from_coords(Coord(4,2), Coord(2,4))
That algorithm took a lot of tweaking to get right. In this case I had optimised myself into a corner that took a bit of thinking to get out of. Because in the earlier ones, I was using the min(start.x,stop.x) to ensure that the lines always went from left to right or from top to bottom, I had that same thing in here. But doing that made the algorithm far more complex when trying to work out how to calculate the ith item.
I had to stop and rethink from first principles. I remembered the old Bresenham's algorithm for drawing straight lines, which uses basic maths to work out the gradient of a line, the length of a line, and then uses a dx and dy to increment the pixel when needed. (You can find that here: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm)
In this case, we have a guaranteed easier case, we are only dealing with 45 degree lines, and that means that every movement in one axis will be mirrored in a movement in another. That means we can just walk the length of the line in any given direction, and work out all of the parts in another direction. If we were doing that to say 30 degree lines, we'd probably end up with missing bits.
Anyway, now we can generate the lines, we can simply take the prod data, not filter it, and run it through our new function and apply the grid again.
data = [l.strip() for l in open("day5.txt").readlines()]
coords = parse_lines(data)
grid = apply_lines_to_grid(coords)
print(len([v for v in grid.values() if v > 1]))
18065