# Lavaduct Lagoon

`2023-12-25`

Original Prompt ## Part 1

This smells an awful lot like Day 10, which introduced us to:

- Pick’s Theorem, for finding the number of points in a shape given its area and border points
- the Shoelace formula, for finding the area of a shape given its border points

I could reuse all the math code from that day:

```
from itertools import pairwise
GridPoint = tuple[int, int]
def num_points(outline: list[GridPoint]) -> int: """ the number of the points inside an outline plus the number of points in the outline """ # shoelace - find the float area in a shape area = ( sum( row1 * col2 - row2 * col1 for (row1, col1), (row2, col2) in pairwise(outline) ) / 2 ) # pick's theorem - find the number of points in a shape given its area return int(abs(area) - 0.5 * len(outline) + 1) + len(outline)
```

The only changes are:

- I put my math into a single function
- I renamed some variables
- I switched
`zip(l, l[1:])`

to`itertools.pairwise`

, which does the same thing (TIL!)

With that, we can do part 1 literally:

```
...
OFFSETS: dict[str, GridPoint] = { "R": (0, 1), "D": (1, 0), "L": (0, -1), "U": (-1, 0),}
class Solution(StrSplitSolution): def part_1(self) -> int: points: list[GridPoint] = [(0, 0)]
for line in self.input: direction, distance_str, _ = line.split()
for _ in range(int(distance_str)): points.append(add_points(OFFSETS[direction], points[-1]))
return num_points(points)
```

again, using

`add_points`

from my graph utils

Not bad at all! Not sure what those colors are for though…

## Part 2

Ah, not colors, just huge numbers. Let’s start by doing it literally again and see where that gets us. Our code adapts well, with just minor changes needed:

```
...
OFFSETS = { "R": (0, 1), "D": (1, 0), "L": (0, -1), "U": (-1, 0),}OFFSET_INDEXES = list(OFFSETS.values())
class Solution(StrSplitSolution): ...
def part_1(self) -> int: def part_2(self) -> int: points: list[GridPoint] = [(0, 0)]
for line in self.input: direction, distance_str, _ = line.split() _, _, hex_str = line.split() distance = int(hex_str[2:-2], 16) offset = OFFSET_INDEXES[int(hex_str[-2])]
for _ in range(distance): points.append(add_points(offset, points[-1]))
return num_points(points)
```

Python keeping dict insertion order means careful ordering on our `OFFSETS`

allows for index-based access. Then, targeting string indexing and `int('...', 16)`

to convert from a hex gets us our big numbers. The big problem now is that it’s slow.

Out of curiosity, I let it run for a full minute (using `timeout -v 60s ./advent`

) and… it *did* work! It just took 48 seconds of computing a *very* long list of points (the example alone has `6405263`

points in the outline). Let’s speed that up.

At first I was going to try and pre-compute large number of shoelace ranges (the part that actually has to iterate over an entire range of points). Then it hit me: we’re always moving in a straight line; let’s only worry about the start and end of each segment. This turns `[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]`

into `[(0, 0), (0, 4)]`

. Spread that over segments that are hundreds of thousands of meters long and we’ve got some pretty significant speedups!

We’ll be able to draw the same paths effectively, but we’ll have to track the length of our border separately (since we can’t rely on the length of the outline) anymore; we’ll start there.

`def num_points(outline: list[GridPoint], border_length: int) -> int: # shoelace - find the float area in a shape area = ( sum( row1 * col2 - row2 * col1 for (row1, col1), (row2, col2) in pairwise(outline) ) / 2 ) # pick's theorem - find the number of points in a shape given its area return int(abs(area) - 0.5 * `~~len(outline)~~ + 1) + ~~len(outline)~~ return int(abs(area) - 0.5 * border_length + 1) + border_length

Next we adapt our part 2 code to scale its offsets:

```
...
class Solution(StrSplitSolution): ...
def part_2(self) -> int: outline: list[GridPoint] = [(0, 0)] border_length = 0
for line in self.input: _, _, hex_str = line.split()
distance = int(hex_str[2:-2], 16)
offset = OFFSET_INDEXES[int(hex_str[-2])] scaled_offset = (offset[0] * distance, offset[1] * distance)
outline.append(add_points(scaled_offset, outline[-1])) border_length += distance
return num_points(outline, border_length)
```

Now our answer is instant! There are only `15`

points in the example’s `outline`

list (down from `6,405,263`

), hence the speed up.

## Extra Credit

The last order of business is combining our part 1 and part 2 code into a single implementation. We could use the part 2 approach for part one (overkill though it may be); the only difference between the parts is the way they pull an `offset`

and a `distance`

out of the input. So if we make that configurable, we can do it all in a single function:

```
from typing import Callable...
class Solution(StrSplitSolution): def part_2(self) -> int: def _solve(self, get_heading: Callable[[str], tuple[GridPoint, int]]): outline: list[GridPoint] = [(0, 0)] border_length = 0
for line in self.input: _, _, hex_str = line.split() offset = OFFSET_INDEXES[int(hex_str[-2])] distance = int(hex_str[2:-2], 16) offset, distance = get_heading(line)
scaled_offset = (offset[0] * distance, offset[1] * distance) outline.append(add_points(scaled_offset, outline[-1])) border_length += distance
return num_points(outline, border_length)
```

Lastly, each part defines how to extract data from input:

```
...
class Solution(StrSplitSolution): ...
def part_1(self) -> int: def parse_line(line: str): direction, distance_str, _ = line.split() return OFFSETS[direction], int(distance_str)
return self._solve(parse_line)
def part_2(self) -> int: def parse_line(line: str): _, _, hex_str = line.split() offset = OFFSET_INDEXES[int(hex_str[-2])] distance = int(hex_str[2:-2], 16) return offset, distance
return self._solve(parse_line)
```

Our `_solve`

function could now work with basically any input format (as long as it could produce a basic offset and direction). Now that’s what I call maintainable!