<jupyter_start><jupyter_text>Day 9 - Smoke Basinhttps://adventofcode.com/2021/day/9 Part 1<jupyter_code>from pathlib import Path

INPUTS = Path('input.txt').read_text().strip().split('\n')

def is_low_point(x: int, y: int) -> bool:
    point = int(INPUTS[x][y])
    adjacent = []
    if x > 0:
        adjacent.append(int(INPUTS[x-1][y]))
    if x < len(INPUTS) - 1:
        adjacent.append(int(INPUTS[x+1][y]))
    if y > 0:
        adjacent.append(int(INPUTS[x][y-1]))
    if y < len(INPUTS[x]) - 1:
        adjacent.append(int(INPUTS[x][y+1]))
    return point < min(adjacent)

risk = 0
for x, row in enumerate(INPUTS):
    for y, val in enumerate(row):
        if is_low_point(x, y):
            risk += 1 + int(val)

print(f"Risk level: {risk}")<jupyter_output>Risk level: 458<jupyter_text>Part 2Because each low point is unique in that no other points near it are lower, and because each low point belongs to a single basin, we can start from those low points and expand outwards to locate all points that exist within the basin. `9`s are boundaries and act as our stopping points (if we don't hit the edges of the map).For those step I decided to build up a more robust `Point` object that could handle certain details, like pulling a value from the set of inputs or checking if its coordinates were in-bounds.I went with referring to the global `INPUTS` list initially, but in trying to test things found I needed to use local variables. So, an `inputs` argument can be used to supplement test inputs, using `INPUTS` as a default value.<jupyter_code>from dataclasses import dataclass


@dataclass
class Point:
    x: int
    y: int

    def value(
        self,
        inputs: list[str] = INPUTS,
    ) -> int:
        return int(inputs[self.x][self.y])

    def exists(
        self,
        inputs: list[str] = INPUTS,
    ) -> bool:
        """Whether the given (x,y) coordinate exists in the INPUTS.

        Useful as a shorthand for checking for out-of-bounds indices.
        """
        return (0 <= self.x < len(inputs)) and (0 <= self.y < len(inputs[0]))

    def __hash__(self) -> int:
        """Defining this magic method allows us to use Points within a `set()`.
        That allows us to more quickly determine unique points.
        """
        # Just comes down to a tuple of the X and Y values
        return hash((self.x, self.y))<jupyter_output><empty_output><jupyter_text>Now the method for finding basin points. Brute forcing with simple loops is impossible given the freeform nature of the basins (they may form extra pathways that bend around boundaries, for instance). So, this called for a recursive search.I spent several days waffling on this solution (while also dealing with home life!) before finally realizing I could send the intermediary set of points in the basin along with the recursive calls, thereby allowing it to test if any given point had already been tested. This helps avoid circular logic in which an area is tested more than once from different approaches, which would lead to infinite recursion.So, the initial call starts with an empty cloud, and initializes one as a `set()`. The starting point checks to see if it's already present in the cloud, or if that point is a boundary wall (value `9`); in which case the unchanged cloud is returned up the stack. Otherwise, the starting point is added to the cloud, and the search pattern kicks off, attempting to recurse in the 4 cardinal directions (up, down, left, right). The method then returns a new point cloud each time it successfully runs back to the outer call, which replaces the old one. Finally, the whole cloud is returned back to the original call.<jupyter_code>def basin_points(
    start: Point,
    cloud: set[Point] = None,
    inputs: list[str] = INPUTS,
) -> set[Point]:
    """Recursively searches for all points belonging to a basin.

    Each basin only contains 1 low point, defined as a point that is lower
    than any other adjacent point. Because only 1 of these points exists per basin,
    logically all other points are adjacent to some higher-value point(s).

    Therefore, search all 4 directions radiating from the given point,
    returning a cloud of points. If an adjacent node is >= in value to the current,
    excluding a 9, continue the search.
    """
    if cloud is None:
        # Don't use set() as the default argument, as that's a mutable object.
        # Multiple runs of the same function will return clouds that are all
        # duplicates of each other, connected to the exact same set() object!
        # Instead, create a new set at call time like so:
        cloud = set()
    if start in cloud or start.value(inputs=inputs) == 9:
        # Hit a point that was already checked or a boundary wall of height 9
        return cloud
    cloud.add(start)
    # Search along all adjacent routes
    adjacent = [
        Point(x=start.x - 1, y=start.y),  # up
        Point(x=start.x + 1, y=start.y),  # down
        Point(x=start.x, y=start.y - 1),  # left
        Point(x=start.x, y=start.y + 1),  # right
    ]
    for point in adjacent:
        if point.exists(inputs=inputs):
            # Send the current cloud down the recursive stack,
            # allowing each call to check if the calling point was already searched.
            # This avoids circular paths being tested, which might be difficult to
            # account for otherwise.
            # The completed recursive call returns a new cloud to use in subsequent calls.
            cloud = basin_points(start=point, cloud=cloud, inputs=inputs)
    # After going in all 4 directions from the starting point and all points connected,
    # the final returned cloud in the outermost call contains the entire point cloud
    # for this basin.
    return cloud<jupyter_output><empty_output><jupyter_text>After some initial insanity, I had to go with *some* testing to make sure I was getting the kinds of point clouds I expected.<jupyter_code>def test_basin_points():
    """Test the basin points method using sample data from the AoC site."""
    inputs = [
        "2199943210",
        "3987894921",
        "9856789892",
        "8767896789",
        "9899965678",
    ]
    start = Point(0, 0)
    points = basin_points(start=start, inputs=inputs)
    assert points == {Point(x=1, y=0), Point(x=0, y=1), Point(x=0, y=0)}


test_basin_points()<jupyter_output><empty_output><jupyter_text>With the above method ready to go, we go through the inputs again, looking for low points. This time, we have the program return the point clouds for the basins those low points reside in.<jupyter_code>basins = []
for x, row in enumerate(INPUTS):
    for y, val in enumerate(row):
        if is_low_point(x, y):
            low_point = Point(x, y)
            basins.append(basin_points(start=low_point))<jupyter_output><empty_output><jupyter_text>With that list of point clouds in hand, solving the problem is simple:<jupyter_code># Obtain the length of each basin (each being a set() object)
basin_sizes = [len(x) for x in basins]

# Sort those lengths in reverse, so they're descending in order.
# Then, slice the first 3 using [:3], and use expansion to throw those
# into their own variables
largest, second, third = sorted(basin_sizes, reverse=True)[:3]
print(f"{largest=}, {second=}, {third=}")

# Finally, the solution, being the product of those 3 numbers
product = largest * second * third
print(f"Product of three largest: {product}")<jupyter_output>largest=114, second=111, third=110
Product of three largest: 1391940
{'fraction_non_alphanumeric': 0.08473677231136455, 'fraction_numerical': 0.015382575255271183, 'mean_word_length': 3.331993107409535, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 31, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '364889', 'license': 'MIT', 'n_tokens_mistral': 2238, 'n_tokens_neox': 2118, 'n_words': 976, 'path': '2021/day09/main.ipynb', 'repo_name': 'GriceTurrble/advent-of-code-2020-answers', 'size': '7541'}