Day 9: Smoke Basin

my main stumbling block here was self-inflicted. I thought I'd be clever, consider the 4 neighboring squares without regard to overflowing the edges, and use Python's "easier to ask forgiveness than permission" approach and just catch IndexError and ignore it as a way of handling falling off the side of the map.

of course, what I didn't realize at first is that when I'm at x=0 or y=0, the neighbor computation will generate -1 as an index, which is perfectly valid in Python, and means the other edge of the map. so I was inadvertently wrapping around in cases where I shouldn't have been.

and frustratingly, this bug caused no problems at all with the example input, only with my actual input. so I played some printf debugging games of having it print out what it thought were the local minima, and then comparing that by eyeball against the map. once I realized the bug I added the explicit check for if neighbor_x < 0 or neighbor_y < 0 and the rest Just Worked.

def main():
    with open('009.txt') as file:
        lines = file.readlines()

    map = []
    for line in lines:
        row = [int(height) for height in line.strip()]
        map.append(row)

    print(find_local_minima(map))


def find_local_minima(map):
    total = 0
    for x, row in enumerate(map):
        for y, height in enumerate(row):
            neighbors = [
                (x + 1, y),
                (x - 1, y),
                (x, y + 1),
                (x, y - 1),
            ]

            is_local_minimum = True
            for neighbor_x, neighbor_y in neighbors:
                if neighbor_x < 0 or neighbor_y < 0:
                    continue

                try:
                    neighbor_value = map[neighbor_x][neighbor_y]
                    if height >= neighbor_value:
                        is_local_minimum = False
                except IndexError:
                    pass

            if is_local_minimum:
                total += height + 1

    return total

main()

I ended up needing "what are the neighbors of this cell?" in two places, so I split that out into its own function, and this time implemented my own bounds checking for the 4 edges of the map rather than using IndexErrors. this means that callers of get_neighbors can use the return value as-is without needing bounds-checking of their own.

the basin idea made sense to me as a recursive definition - a basin is the low point, plus all the points around it that aren't 9s, plus all the points around them that aren't 9s, and so on.

any recursive algorithm can be implemented in a non-recursive / iterative fashion, and I often find these implementations to be clearer / more understandable. so that's what I did.

my find_basin function keeps a queue of pending points to be considered, starting with the single bottom point. any time I find a neighbor point that belongs to the current basin, I add it to the set of basin points, as well as the queue of pending points whose neighbors should be considered. when I run out of pending points, I know I've explored the entire basin.

def main():
    with open('009.txt') as file:
        lines = file.readlines()

    map = []
    for line in lines:
        row = [int(height) for height in line.strip()]
        map.append(row)

    minima = find_local_minima(map)

    basins = []
    for minimum in minima:
        basin = find_basin(map, minimum)
        basins.append(basin)

    sorted_basins = list(sorted(basins, reverse=True, key=lambda basin: len(basin)))
    print(len(sorted_basins[0]) * len(sorted_basins[1]) * len(sorted_basins[2]))


def find_basin(map, bottom):
    points = set([bottom])
    pending = [bottom]

    while pending:
        current = pending.pop()
        current_x, current_y = current
        current_value = map[current_x][current_y]

        for neighbor in get_neighbors(map, current_x, current_y):
            neighbor_x, neighbor_y = neighbor
            neighbor_value = map[neighbor_x][neighbor_y]
            if neighbor_value != 9 and neighbor_value > current_value:
                if neighbor not in points:
                    points.add(neighbor)
                    pending.append(neighbor)

    return points


def find_local_minima(map):
    minima = []
    for x, row in enumerate(map):
        for y, height in enumerate(row):
            neighbors = get_neighbors(map, x, y)

            is_local_minimum = True
            for neighbor_x, neighbor_y in neighbors:
                neighbor_value = map[neighbor_x][neighbor_y]
                if height >= neighbor_value:
                    is_local_minimum = False

            if is_local_minimum:
                minima.append((x, y))

    return minima


def get_neighbors(map, x, y):
    neighbors = [
        (x + 1, y),
        (x - 1, y),
        (x, y + 1),
        (x, y - 1),
    ]

    actual_neighbors = []
    for neighbor_x, neighbor_y in neighbors:
        if neighbor_x < 0 or neighbor_y < 0:
            continue

        if neighbor_x >= len(map):
            continue

        if neighbor_y >= len(map[0]):
            continue

        actual_neighbors.append((neighbor_x, neighbor_y))

    return actual_neighbors

main()

m=[[*map(int,l[:-1])]for l in open(0)]
print(sum((1+m[r][c]for r in range(len(m))for c in range(len(m[0]))if all(0>r+i or r+i>=len(m)or 0>c+j or c+j>=len(m[0])or m[r+i][c+j]>m[r][c]for i,j in((0,-1),(0,1),(-1,0),(1,0))))))

import math
m=[[*map(int,l[:-1])]for l in open(0)]
def f(r,c):
 if m[r][c]==9:return 0
 m[r][c]=9;return sum((f(r+i,c+j)for(i,j)in((0,-1),(0,1),(-1,0),(1,0))if 0<=r+i<len(m)and 0<=c+j<len(m[0])))+1
print(math.prod(sorted(f(r,c)for r in range(len(m))for c in range(len(m[0]))if m[r][c]-9)[-3:]))

use std::collections::{HashSet, VecDeque};

use nom::{character::complete::multispace0, IResult};

type Row = Vec<u8>;
type Grid = Vec<Row>;

fn parse_row(input: &str) -> IResult<&str, Row> {
    let (input, _) = multispace0(input)?;
    let (input, row) = nom::character::complete::digit1(input)?;

    let row = row.chars().map(|c| c as u8 - '0' as u8).collect();

    Ok((input, row))
}

fn parse_grid(input: &str) -> IResult<&str, Grid> {
    let (input, grid) = nom::multi::many1(parse_row)(input)?;
    let (input, _) = multispace0(input)?;
    let (input, _) = nom::combinator::eof(input)?;

    Ok((input, grid))
}

// Returns a vector with the coordinates of all low points.
// It finds them in the obvious way: by
// iterating through the grid and checking the neighbors.
fn low_points(grid: &Grid) -> Vec<(usize, usize)> {
    let height = grid.len();
    let width = grid[0].len();
    let mut result = Vec::new();

    for y in 0..height {
        for x in 0..width {
            let val = grid[y][x];

            // North
            if y > 0 && grid[y - 1][x] <= val {
                continue;
            }

            // East
            if x + 1 < width && grid[y][x + 1] <= val {
                continue;
            }

            // South
            if y + 1 < height && grid[y + 1][x] <= val {
                continue;
            }

            // West
            if x > 0 && grid[y][x - 1] <= val {
                continue;
            }

            result.push((x, y));
        }
    }

    result
}

// Starting from a low_point, finds the basin size using a simple floodfill.
fn find_basin_size(grid: &Grid, start: (usize, usize)) -> usize {
    let height = grid.len();
    let width = grid[0].len();

    let mut q = VecDeque::new();
    let mut seen = HashSet::new();
    let mut size = 0;

    q.push_back(start);

    while let Some(coordinate) = q.pop_front() {
        if seen.contains(&coordinate) {
            continue;
        }

        seen.insert(coordinate);

        size += 1;

        let (x, y) = coordinate;
        let val = grid[y][x];

        if y > 0 && grid[y - 1][x] > val && grid[y - 1][x] != 9 {
            q.push_back((x, y - 1));
        }

        if y + 1 < height && grid[y + 1][x] > val && grid[y + 1][x] != 9 {
            q.push_back((x, y + 1));
        }

        if x > 0 && grid[y][x - 1] > val && grid[y][x - 1] != 9 {
            q.push_back((x - 1, y));
        }

        if x + 1 < width && grid[y][x + 1] > val && grid[y][x + 1] != 9 {
            q.push_back((x + 1, y));
        }
    }

    size
}

fn part1(grid: &Grid) -> usize {
    let mut sum = 0;

    for (x, y) in low_points(grid) {
        sum += 1;
        sum += grid[y][x] as usize;
    }

    sum
}

fn part2(grid: &Grid) -> usize {
    let mut basin_sizes: Vec<usize> = low_points(grid)
        .iter()
        .map(|&s| find_basin_size(grid, s))
        .collect();

    basin_sizes.sort_unstable();
    basin_sizes.iter().rev().take(3).product()
}

fn main() {
    let input = include_str!("../../input-09.txt");
    let grid = parse_grid(input).expect("Failed to parse puzzle").1;

    println!("Part I:  {}", part1(&grid));
    println!("Part II: {}", part2(&grid));
}

def compute_p1(input)
  sum = 0
  grid = Grid.new(input)
  grid.each_index do |x,y|
    value = grid.get(x,y).to_i
    neighbors = grid.neighbors(x,y).reject {_1.nil?}.map(&:to_i)
    sum += (1+value) if neighbors.all? { _1 > value }
  end
  return sum
end

class Grid
  attr_accessor :grid
  attr_reader :width
  attr_reader :height
  attr_reader :default

  def initialize(input, default: nil)
    @grid = input.lines
              .map(&:strip)
              .map(&:chars)
    @width = @grid[0].size
    @height = @grid.size
    @default = default
  end

  def get(x,y)
    if x < 0 || x >= @width || y < 0 || y >= @height
      @default
    else
      @grid[y][x]
    end
  end

  def set(x,y,val)
    if x < 0 || x >= @width || y < 0 || y >= @height
      raise "Tried to write out of bounds"
    else
      @grid[y][x] = val
    end
  end

  def each_index
    height.times do |y|
      width.times do |x|
        yield(x,y)
      end
    end
  end

  def ==(other)
    return false if other.class != Grid
    return other.grid == @grid
  end

  def neighbors(x,y)
    [
      [-1, -1], [0, -1], [+1, -1],
      [-1,  0],          [+1, 0],
      [-1, +1], [0, +1], [+1, +1]
    ].map { |dx, dy| get(x+dx, y+dy) }
  end

  def to_s
    s = ""
    height.times do |y|
      width.times do |x|
        s << get(x,y) || default.to_s
      end
      s << "\n"
    end
    return s
  end

  def count(value)
    @grid.flatten.count(value)
  end
end

def compute_p2(input)
  grid = Grid.new(input)

  low_points = []
  grid.each_index do |x,y|
    value = grid.get(x,y).to_i
    neighbors = grid.neighbors(x,y).reject {_1.nil?}.map(&:to_i)
    low_points.push([x,y]) if neighbors.all? { _1 > value }
  end

  basin_sizes = Hash.new(0)

  low_points.each do |point|
    visited = []
    open_set = [point]

    until open_set.empty?
      cur_x, cur_y = open_set.shift
      visited.push([cur_x, cur_y])

      [
                 [0, -1],
        [-1,  0],        [+1, 0],
                 [0, +1]
      ].each do |dx, dy|
        nx, ny = cur_x + dx, cur_y + dy
        next if visited.include?([nx, ny]) || open_set.include?([nx,ny])

        cell = grid.get(nx, ny)
        next if cell.nil? || cell == '9'

        open_set.push([nx, ny])
      end
    end

    basin_sizes[point] += visited.uniq.size
  end

  basin_sizes.values.sort[-3..].inject(:*)
end

I ran into a minor hitch in that I initially wanted to use an actual Set object for the visited/open sets, but the default implementation in the stdlib doesn't really support easily removing an arbitrary value the way I can with Array#shift/Array#pop (since a set is unordered by definition, and shift/pop rely on the collection having an order). Arrays work fine, but I have to go a bit out of the way to make sure I don't end up with duplicate entries.

Part A wasn't too bad, just built a grid with defaultdicts and searched it to find the low points. Mostly just keeping track of the boundaries and what-not. At some point I managed to swap my x and y axes, but I just ran with it.

Interestingly, using the default dict grid instead of my normal stacked lists meant that going out of bounds would automatically generate a new entry into the dictionary and then crash because the dictionary size changed mid-loop, instead of just crashing due to an array out of bounds exception

from collections import defaultdict

#data = test_data
data = real_data
data = data.split('\n')

grid = defaultdict(lambda: defaultdict(int))

for index, row in enumerate(data):
    for index2, val in enumerate(list(row)):
        grid[index2][index] = int(val)

bounds_y = len(grid.keys())
bounds_x = len(grid[0].keys())

directions = [(1,0),(-1,0),(0,1),(0,-1)]

threat = 0

for y_pos in grid.keys():
    row = ""
    for x_pos in grid[y_pos].keys():
        lower_found = False
        for direction in directions:
            nearby_x = x_pos + direction[0]
            nearby_y = y_pos + direction[1]
            if nearby_x >= 0 and nearby_x < bounds_x and nearby_y >= 0 and nearby_y < bounds_y:
                if grid[nearby_y][nearby_x] <= grid[y_pos][x_pos]: #Assumes there are no ties
                    lower_found = True
        if not lower_found:
            row = row + "X"
            #print(grid[y_pos][x_pos] + 1)
            threat = threat + grid[y_pos][x_pos] + 1
        else:
            row = row + str(grid[y_pos][x_pos])
    #print(row)
print(threat)

This was a bit more difficult. I used the low points I generated in part A to build a list of starting points. Then I recursively searched outward from those points, adding any nearby locations that weren't already part of the basin. When there was nothing left to find I just took the size of the basin and shoved it into a list.

from collections import defaultdict

#data = test_data
data = real_data
data = data.split('\n')

grid = defaultdict(lambda: defaultdict(int))

for index, row in enumerate(data):
    for index2, val in enumerate(list(row)):
        grid[index2][index] = int(val)

bounds_y = len(grid.keys())
bounds_x = len(grid[0].keys())

directions = [(1,0),(-1,0),(0,1),(0,-1)]

low_point_list = []
for y_pos in grid.keys():
    row = ""
    for x_pos in grid[y_pos].keys():
        lower_found = False
        for direction in directions:
            nearby_x = x_pos + direction[0]
            nearby_y = y_pos + direction[1]
            if nearby_x >= 0 and nearby_x < bounds_x and nearby_y >= 0 and nearby_y < bounds_y:
                if grid[nearby_y][nearby_x] <= grid[y_pos][x_pos]: #Assumes there are no ties
                    lower_found = True
        if not lower_found:
            row = row + "X"
            #print(grid[y_pos][x_pos] + 1)
            low_point_list.append((y_pos, x_pos))
            threat = threat + grid[y_pos][x_pos] + 1
        else:
            row = row + str(grid[y_pos][x_pos])
    #print(row)
def search_nearby(location, basin):
    x_pos = location[1]
    y_pos = location[0]
    for direction in directions:
        nearby_x = x_pos + direction[0]
        nearby_y = y_pos + direction[1]
        if (nearby_y, nearby_x)  not in basin:
            if nearby_x >= 0 and nearby_x < bounds_x and nearby_y >= 0 and nearby_y < bounds_y:
                if grid[nearby_y][nearby_x] < 9:
                    basin.append((nearby_y, nearby_x))
                    search_nearby((nearby_y, nearby_x), basin)

basin_sizes = []                    
for low_point in low_point_list:
    basin = [low_point]
    search_nearby(low_point, basin)
    basin_sizes.append(len(basin))
basin_sizes.sort()
print(basin_sizes)
print(basin_sizes[-3] * basin_sizes[-2] * basin_sizes[-1])

• Make sure to try to keep X and Y straight. It's alright if you flip them from what the input is, but you need to be consistent about how YOU use them

• There are only 4 directions neighboring each point, but sometimes those checks will send you out of bounds of your grid. Think about how to stop your program from crashing or giving strange results when that happens

• If you're not careful about how you search for the basins, you might end up in an infinite loop of checking for locations that are already stored in your basin

Split the input with

"=ARRAYFORMULA(
  IF(ISBLANK(A2:A),,
   SPLIT(
    REGEXREPLACE(A2:A,""(.)"",""$1|""),
    ""|"")))"

then pop this in and drag it around for the 100x100

"=IF(
  AND(
   F2<IF(ISBLANK(F1),9,F1),
   F2<IF(ISBLANK(G2),9,G2),
   F2<IF(ISBLANK(F3),9,F3),
   F2<IF(ISBLANK(E2),9,E2)),
  F2+1,)"

I hate formulas like this

This was pretty straightforward. The only trick I used was to pad the heatmap to avoid bounds checking.

const MAX = 9;
const DIRECTIONS = [
    [ 0, -1], // Left
    [ 0,  1], // Right
    [-1,  0], // Up
    [ 1,  0]  // Down
];

function padmap(map) {
    let padrow = new Array(map[0].length + 2).fill(MAX);
    return [padrow, ...map.map(row => [MAX, ...row, MAX]), padrow];
}

function find_low_points(heatmap) {
    let low_points = [];

    for (let row = 1; row < heatmap.length - 1; row++) {
        for (let col = 1; col < heatmap[0].length - 1; col++) {
            let is_lower = DIRECTIONS.filter(([dr, dc]) =>
                heatmap[row][col] < heatmap[row + dr][col + dc]
            );
            if (is_lower.length == DIRECTIONS.length) {
                low_points.push([heatmap[row][col], row, col]);
            }
        }
    }

    return low_points;
}

let heatmap    = padmap(IO.readlines(line => line.split('').map(n => parseInt(n, 10))));
let low_points = find_low_points(heatmap);
let part_a     = low_points.reduce((t, p) => t + p[0] + 1, 0);
IO.print(`Part A: ${part_a}`);

For this part, once you have the low points, all you need to do is perform a walk or traversal from each low point until you run out of locations (ie. no more 9s). For this, I used a traditional iterative frontier based approach.

In terms of JavaScript there were still a few gotchas that I am still learning. For instance, adding an Array to a Set works, but it compares the reference/pointer instead of the contents, so you can never find the Array again. To work around this, I gave each location or node an integer identifier based on its row and column.

function find_basins(heatmap, low_points) {
    return low_points.map(([_, row, col]) => walk_heatmap(heatmap, [row, col]));
}

function walk_heatmap(heatmap, start) {
    let frontier = [start];
    let visited  = new Set();

    while (frontier.length) {
        let [row, col] = frontier.shift();
        let node_id    = row*heatmap[0].length + col;

        if (visited.has(node_id)) {
            continue;
        }

        visited.add(node_id);

        DIRECTIONS.forEach(([dr, dc]) => {
            if (heatmap[row + dr][col + dc] < MAX) {
                frontier.push([row + dr, col + dc]);
            }
        });
    }

    return visited.size;
}

let basins     = find_basins(heatmap, low_points);
let part_b     = basins.sort((a, b) => b - a).slice(0, 3).reduce((s, n) => s * n, 1);
IO.print(`Part B: ${part_b}`);

#!/usr/bin/awk -f
BEGIN { FS = "" }

{
	for (x = 1; x <= NF; ++x)
		grid[x, NR] = $x
}

END {
	for (i in grid) {
		split(i, xy, SUBSEP)
		x = xy[1]
		y = xy[2]

		flag = 1

		for (ox = -1; ox <= 1; ox += 2) {
			adj = grid[x + ox, y]
			if (grid[x, y] >= adj && adj != "")
				flag = 0

			adj = grid[x, y + ox]
			if (grid[x, y] >= adj && adj != "")
				flag = 0
		}

		if (flag)
			total += grid[x, y] + 1
	}

	print total
}

#!/usr/bin/awk -f
function flood(x, y, z) {
	if (grid[x, y] >= z && grid[x, y] != 9 && grid[x, y] != "") {
		size += 1
		z = grid[x, y]
		grid[x, y] = 9

		flood(x - 1, y, z)
		flood(x + 1, y, z)
		flood(x, y - 1, z)
		flood(x, y + 1, z)
	}
}

BEGIN { FS = "" }

{
	for (x = 1; x <= NF; ++x)
		grid[x, NR] = $x
}

END {
	for (i in grid) {
		split(i, xy, SUBSEP)
		x = xy[1]
		y = xy[2]

		flag = 1

		for (ox = -1; ox <= 1; ox += 2) {
			adj = grid[x + ox, y]
			if (grid[x, y] >= adj && adj != "")
				flag = 0

			adj = grid[x, y + ox]
			if (grid[x, y] >= adj && adj != "")
				flag = 0
		}

		if (flag)
			pt[x, y] = grid[x, y]
	}

	for (i in pt) {
		split(i, xy, SUBSEP)
		size = 0

		flood(xy[1], xy[2], pt[i])
		sizes[size] += 1

		if (size > max || max == "")
			max = size
	}

	k = 3

	for (i = max; i >= 0 && k > 0; --i) {
		for (j = sizes[i]; j > 0 && k > 0; --j) {
			k -= 1

			if (total == "")
				total = i
			else
				total *= i
		}
	}

	print total
}

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::{HashMap,HashSet};

use point2d::point2d::Point2D;

fn neighbor_addresses(pt: &Point2D) -> Vec<Point2D> {
    vec![Point2D{ x: pt.x  , y: pt.y-1 },  // up
         Point2D{ x: pt.x+1, y: pt.y   },  // right
         Point2D{ x: pt.x  , y: pt.y+1 },  // down
         Point2D{ x: pt.x-1, y: pt.y   }]  // left
}

fn neighbor_values(pt: &Point2D, map: &HashMap<Point2D,i64>) -> Vec<i64> {
    let neighbors = neighbor_addresses(&pt);
    let mut values: Vec<i64> = Vec::new();
    for neighbor in neighbors {
        match map.get(&neighbor) {
            Some(value) => values.push(*value),
            None => {},
        }
    }
    values
}

fn is_low(pt: Point2D, map: &HashMap<Point2D,i64>) -> bool {
    let neighbor_values = neighbor_values(&pt, &map);
    map.get(&pt).unwrap() < neighbor_values.iter().min().unwrap()
}

fn uphill_neighbors(pt: Point2D, map: &HashMap<Point2D,i64>) -> Vec<Point2D> {
    let this_value = map.get(&pt).unwrap();
    let neighbors = neighbor_addresses(&pt);
    let mut uphill: Vec<Point2D> = Vec::new();
    for neighbor in neighbors {
        match map.get(&neighbor) {
            Some(value) => {
                if value > this_value && value < &9 {
                    uphill.push(neighbor);
                    for n in uphill_neighbors(neighbor,&map) { uphill.push(n); }
                }
            },
            None => {},
        }
    }
    uphill
}

fn risk_level(pt: Point2D, map: &HashMap<Point2D,i64>) -> i64 {
    map.get(&pt).unwrap() + 1
}

fn map_extents(map: &HashMap<Point2D,i64>) -> (i64,i64,i64,i64) {
    let xmin = &map.keys().map(|&pt| pt.x).min().unwrap();
    let ymin = &map.keys().map(|&pt| pt.y).min().unwrap();
    let xmax = &map.keys().map(|&pt| pt.x).max().unwrap();
    let ymax = &map.keys().map(|&pt| pt.y).max().unwrap();
    (*xmin,*ymin,*xmax,*ymax)
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Build smoke map
    let mut smoke_map: HashMap<Point2D,i64> = HashMap::new();
    for (y,line) in input.iter().enumerate() {
        for (x,ch) in line.chars().enumerate() {
            let (x,y,v) = (x as i64, y as i64, ch.to_digit(10).unwrap());
            smoke_map.insert(Point2D{x,y},v.into());
        }
    }

    // Part 1
    let mut part1: i64 = 0;
    let mut basins: Vec<Point2D> = Vec::new();
    let (xmin,ymin,xmax,ymax) = map_extents(&smoke_map);
    for y in ymin..=ymax {
        for x in xmin..=xmax {
            let pt = Point2D { x: x, y: y };
            if is_low(pt,&smoke_map) {
                basins.push(pt);
                part1 += risk_level(pt,&smoke_map);
            }
        }
    }
    println!("Part 1: {}", part1); // 575

    // Part 2
    let mut basin_sizes: Vec<usize> = Vec::new();
    for basin in basins {
        let basin = uphill_neighbors(basin,&smoke_map);
        let this_basin: HashSet<Point2D> = HashSet::from_iter(basin);
        let basin_size = this_basin.len() + 1;
        basin_sizes.push(basin_size);
    }
    basin_sizes.sort_by(|a,b| b.cmp(a)); // descending sort
    let part2 = basin_sizes[0] * basin_sizes[1] * basin_sizes[2];
    println!("Part 2: {}", part2); // 1019700

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

pub mod point2d {
    use std::ops::{Add,AddAssign};
    use std::iter::Sum;
    extern crate num_complex;
    use num_complex::Complex;

    #[derive(Debug, Copy, Clone, Hash)]
    pub struct Point2D {
        pub x: i64,
        pub y: i64,
    }

    impl Point2D {
        pub fn new(x: i64, y: i64) -> Self {
            Self {
                x: x, y: y,
            }
        }
        pub fn zeros() -> Self {
            Self {
                x: 0, y: 0,
            }
        }
        pub fn from_complex(cmplx: Complex<i64>) -> Self {
            Self {
                x: cmplx.re, y: cmplx.im,
            }
        }
        pub fn as_complex(self) -> Complex<i64> {
            Complex::new(self.x, self.y)
        }
        pub fn as_tuple(self) -> (i64,i64) {
            (self.x, self.y)
        }
    }
    impl Add for Point2D {
        type Output = Self;
        fn add(self, other: Self) -> Self {
            Self {
                x: self.x + other.x,
                y: self.y + other.y,
            }
        }
    }
    impl AddAssign for Point2D {
        fn add_assign(&mut self, other: Self) {
            *self = Self {
                x: self.x + other.x,
                y: self.y + other.y,
            };
        }
    }
    impl PartialEq for Point2D {
        fn eq(&self, other: &Self) -> bool {
            self.x == other.x && self.y == other.y
        }
    }
    impl Eq for Point2D {}

    impl Sum for Point2D {
        fn sum<I>(iter: I) -> Self
        where
            I: Iterator<Item = Self>,
        {
            iter.fold(Self { x: 0, y: 0 }, |a, b| Self {
                x: a.x + b.x,
                y: a.y + b.y,
            })
        }
    }
}

I probably could've used structs but I think my code is pretty readable and reasonably concise as it is :)

use crate::lib::aoc;
use std::collections::BinaryHeap;
use std::collections::HashSet;
use std::collections::VecDeque;

// Assumes that (row, col) are valid coordinates
fn get_neighbor_coords(
    heightmap: &[Vec<u32>],
    (row, col): (usize, usize),
) -> HashSet<(usize, usize)> {
    if row == 0 && col == 0 {
        // Top-left corner
        HashSet::from([(row + 1, col), (row, col + 1)])
    } else if row == heightmap.len() - 1 && col == 0 {
        // Bottom-left corner
        HashSet::from([(row - 1, col), (row, col + 1)])
    } else if row == 0 && col == heightmap[row].len() - 1 {
        // Top-right corner
        HashSet::from([(row + 1, col), (row, col - 1)])
    } else if row == heightmap.len() - 1 && col == heightmap[row].len() - 1 {
        // Bottom-right corner
        HashSet::from([(row - 1, col), (row, col - 1)])
    } else if row == 0 {
        // Top-row, not a corner
        HashSet::from([(row + 1, col), (row, col + 1), (row, col - 1)])
    } else if row == heightmap.len() - 1 {
        // Bottom-row, not a corner
        HashSet::from([(row - 1, col), (row, col + 1), (row, col - 1)])
    } else if col == 0 {
        // Left-column, not a corner
        HashSet::from([(row + 1, col), (row - 1, col), (row, col + 1)])
    } else if col == heightmap[row].len() - 1 {
        // Right-column, not a corner
        HashSet::from([(row + 1, col), (row - 1, col), (row, col - 1)])
    } else {
        // Not on any edge
        HashSet::from([
            (row + 1, col),
            (row - 1, col),
            (row, col + 1),
            (row, col - 1),
        ])
    }
}

fn get_basin_size(heightmap: &[Vec<u32>], (row, col): (usize, usize)) -> u32 {
    // Use a bfs???
    let mut queue: VecDeque<(usize, usize)> = VecDeque::from([(row, col)]);
    let mut have_been_explored: HashSet<(usize, usize)> = HashSet::from([(row, col)]);
    while !queue.is_empty() {
        let (row, col) = queue.pop_front().unwrap();
        // 9s are crests, i.e. they aren't in the basin
        if heightmap[row][col] == 9 {
            continue;
        }
        // Now check all edges
        for coord in get_neighbor_coords(heightmap, (row, col)) {
            if heightmap[coord.0][coord.1] != 9 && !have_been_explored.contains(&coord) {
                have_been_explored.insert(coord);
                queue.push_back(coord);
            }
        }
    }

    have_been_explored.len() as u32
}

pub fn run() {
    let heightmap: Vec<Vec<u32>> = aoc::get_lines("./inputs/day9.in")
        .iter()
        .map(|line| {
            line.chars().fold(Vec::new(), |mut accum, cur| {
                accum.push(cur.to_digit(10).expect("Failed to convert a char to u32!"));
                accum
            })
        })
        .collect();

    let mut low_points: HashSet<(usize, usize)> = HashSet::new();
    for row in 0..heightmap.len() {
        for col in 0..heightmap[row].len() {
            let neighbor_coords = get_neighbor_coords(&heightmap, (row, col));
            let is_low_point =
                neighbor_coords
                    .iter()
                    .fold(true, |is_low_point, (neighbor_row, neighbor_col)| {
                        is_low_point
                            && heightmap[row][col] < heightmap[*neighbor_row][*neighbor_col]
                    });
            if is_low_point {
                low_points.insert((row, col));
            }
        }
    }

    let low_point_risk_values: Vec<u32> = low_points
        .iter()
        .map(|(row, col)| heightmap[*row][*col] + 1)
        .collect();

    let low_point_risk_values_sum = low_point_risk_values.iter().sum();

    let mut basin_sizes: BinaryHeap<u32> = BinaryHeap::new();
    for low_point in low_points {
        basin_sizes.push(get_basin_size(&heightmap, low_point));
    }

    let multiplicand_largest_3_basins =
        basin_sizes.pop().unwrap() * basin_sizes.pop().unwrap() * basin_sizes.pop().unwrap();

    aoc::output(
        9,
        "sum",
        low_point_risk_values_sum,
        multiplicand_largest_3_basins,
    );
}

Today is the 2^nd day I've had prior engagements which mean I was very late starting. I'm never going to compete for the top 100 but I'm not going to do well on any of the private leaderboards I joined now. Oh well.

I converting every digit of my input into a number and made a hash table to map point -> height. It's actually not a graph.

(define input (graph (map-input digits)))

(define (digits l)
  (map string->number (regexp-match* #rx"[0-9]" l)))

(define (graph input)
  (for*/hash ([(row r) (in-indexed input)]
              [(height c) (in-indexed row)])
    (values (list r c) height)))

The strategy is to find points lower than all their neighbours. Don't be stupid like me and think there must be 4 regions in your input because the example had 4.
I didn't bother with bounds checking generating neighbours because height is 9 or less, so I used a default height of 10 for missing neighbours.

(define (part-01 input)
  (for*/sum ([(point height) (in-hash input)]
             #:when (lowest? input point height))
    (add1 height)))

(define (lowest? G p h)
  (for/and ([n (neighbours G p)])
    (< h (hash-ref G n 10))))

(define (neighbours G p)
  (match-define (list x y) p)
  (list (list (add1 x) y)
        (list (sub1 x) y)
        (list x (add1 y))
        (list x (sub1 y))))

I generated a list of all basin sizes starting from each of the lowest points. Basin size is the number of visited points using a basic DFS. I ignored any points over 8 (which excludes the default of 10 for missing points again.)

(define (part-02 input)
  (define basins
    (for*/list ([(point height) (in-hash input)]
                #:when (lowest? input point height))
      (basin-size input point)))
  (match-define (list* 1st 2nd 3rd _) (sort basins >))
  (* 1st 2nd 3rd))

(define (basin-size G p)
  (define (expand p visited)
    (for/fold ([visited visited])
              ([n (neighbours G p)]
               #:unless (set-member? visited n)
               #:unless (> (hash-ref G n 10) 8))
      (set-union (expand n (set-add visited n)))))
  (set-count (expand p (set p))))