Link to Advent of Code day 18

Today was very fun. I spent a bit of time on part 1 to get a clean solution. It paid off both by making me learn new stuff, and by making part 2 trivial.

Part 1

Rules

Today's exercise consists of digging a lagoon to store lava, and get the volume of lava this lagoon can hold.

The input looks like this:

R 6 (#70c710)
D 5 (#0dc571)
L 2 (#5713f0)
D 2 (#d2c081)
R 2 (#59c680)
D 2 (#411b91)
L 5 (#8ceee2)
U 2 (#caa173)
L 1 (#1b58a2)
U 2 (#caa171)
R 2 (#7807d2)
U 3 (#a77fa3)
L 2 (#015232)
U 2 (#7a21e3)

Each line contains 3 parts:

• the direction of the digger (U R D L can be translated to North/Est/South/West)
• how many meter the digger will dig in this direction
• the color of the trench as RGB Hex color code

So with this input, the trench would looks like this (# are the trenches):

#######
#.....#
###...#
..#...#
..#...#
###.###
#...#..
##..###
.#....#
.######

These trenches can hold 38 cubic meters of lava (38 #). But then, the inside of the lagoon would be digged as well, and it now can hold 62 cubic meters of lava:

#######
#######
#######
..#####
..#####
#######
#####..
#######
.######
.######

For the part one, we have to figure how many cubic meters of lava can the lagoon from the input hold ?

Code

The easiest solution would be to compute each point of the surrounding trenches, use a flood-fill algorithm to add the points in the lagoon, then count the total of points.

But this is both something I have already done, and something not very efficient, so I tried to find a formula for a more elegant solution for this.

I quickly stumbled across the shoelace formula, which I implemented quickly:

# The points are just basic parsing, and are not worth mentioning in the code

def get_lava_cubic_meters(points: list[Point]) -> int:
    arena = 0

    for point_a, point_b in pairwise(points):
        arena += (point_a.x * point_b.y - point_b.x * point_a.y) / 2.0

    return int(arena)

def pairwise(iterable):
    """s -> (s0,s1), (s1,s2), (s2, s3), ...
    From https://docs.python.org/3.9/library/itertools.html#itertools-recipes
    """
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

But with the given example, the result was 42 instead of 62. I struggled a bit, checking if the points were generated correctly and playing with the variables, before looking for clues.

I then saw that Pick's theorem was being mentioned, and it indeed appeared more suitable: it calculates the area of a polygon where all the points are part of a grid, and provides the number of points within the area.

The formula is simple, and requires 2 variables:

1. the area, that we just calculated with the shoelace formula
2. the boundary length, that we can calculate by getting the sum of the distance between each point

The formula is then arena - boundary_len / 2 - 1.

With this formula, I just have to add the boundary length, and it should be good ! While playing a bit with it, I noticed that I had to add 1, instead of subtracting one tho, but I didn't figured why.

The new solution look like this:

def get_lava_cubic_meters(points: list[Point]) -> int:
    boundary_len = 0
    shoelace_area = 0

    for point_a, point_b in pairwise(points):
        shoelace_area += (point_a.x * point_b.y - point_b.x * point_a.y) / 2.0
        boundary_len += manhattan_distance(point_a, point_b)

    pick_area = shoelace_area - boundary_len / 2 + 1
    return int(boundary_len + pick_area)


def manhattan_distance(point_a: Point, point_b: Point):
    return abs(point_a.x - point_b.x) + abs(point_a.y - point_b.y)

And the part 1 is solved !

Part 2

Rules

Didn't we forget something ? The colors !

For the part 2, we discover that the real input was the hex code on the right part of each line:

The first five hexadecimal digits encode the distance in meters as a five-digit hexadecimal number. The last hexadecimal digit encodes the direction to dig: 0 means R, 1 means D, 2 means L, and 3 means U.

Code

So the logic stay the same, but the area is gonna be way larger. If I had opted for the flood-fill logic I would have to re-write everything. But thankfully, the formulas are doing just fine for these numbers.

So the only thing to change was the parsing of the points. It's not super interesting so I won't mention it here, but it's available on the github.

And once this done, the day 18 was solved !

---

All the code is available on github