This time, I am using Rust.
Parsing
Our input is a grid of characters that represent a map with different regions. I parse this into a hashmap with row, col coordinates as the key and the character as the value.
fn parse_input(input: String) -> HashMap<Point, char> {
input
.trim()
.lines()
.enumerate()
.flat_map(|(row, line)| {
line.chars()
.enumerate()
.map(move |(col, ch)| ((Point::new(row as i32, col as i32)), ch))
})
.collect()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Point {
row: i32,
col: i32,
}
impl Point {
fn new(row: i32, col: i32) -> Self {
Point { row: row, col: col }
}
}Part One
We need to divide our input into regions based on its type. What makes this annoying and complicated is that there can be multiple regions that have the same type so we cannot simply group the points based on their type and need to look at the boundaries between regions.
My method to divide the input up into regions is vaguely similar to breadth-first search.
In its general form, we start by assuming that we have a list of incomplete regions. Then, for each region, we iterate over its points and then iterate over each point’s neighbors. For each such neighbor, there are two options based on the type of the neighbor: if it is the same type, then that region is extended, otherwise we create a new region consisting of only that neighbor.
We now have a new list of incomplete regions. We repeat this process on this new list and continue repeating this process until there are no unvisited neighbors in each region, that is, we have visited every point on the grid. We keep track of the part of the grid already visited to prevent visiting the same points multiple times in an infinite loop.
It is possible (and actually quite frequent) that when we create new single-point regions, we have created multiple regions whose points are neighbors with each other, making them actually part of the same region. To deal with this, we merge intersecting regions in our new list of regions as the last step before continuing on to the next iteration of the loop. In the next iteration of the main loop, each single-point region expands to cover its neighbors, making the adjacent regions intersecting which causes them to be merged together into a single region. This also covers cases where regions of the same type that earlier appeared disjoint are actually connected to to each other.
To start this algorithm, my initial regions are simply a single region with a single point at (0, 0). This then expands to eventually cover the entire input grid.
impl Point {
fn neighbors(self) -> impl Iterator<Item = Self> {
let neighbors = vec![
Point::new(1, 0),
Point::new(0, 1),
Point::new(-1, 0),
Point::new(0, -1),
];
neighbors.into_iter().map(move |diff| self + diff)
}
}
impl Add for Point {
type Output = Self;
fn add(self, other: Point) -> Point {
Point {
row: self.row + other.row,
col: self.col + other.col,
}
}
}
impl Sub for Point {
type Output = Self;
fn sub(self, other: Point) -> Point {
Point {
row: self.row - other.row,
col: self.col - other.col,
}
}
}
fn create_regions(input: &HashMap<Point, char>) -> Vec<HashSet<Point>> {
let mut visited_regions_points = HashSet::new();
let mut regions = Vec::new();
regions.push({
let mut first_region = HashSet::new();
first_region.insert(Point::new(0, 0));
first_region
});
loop {
let mut next_regions = Vec::new();
let mut updated = false;
for region in ®ions {
let region_type = input[region.iter().next().unwrap()];
let mut next_region = region.clone();
for &point in region {
visited_regions_points.insert(point);
for neighbor in point.neighbors() {
if !visited_regions_points.contains(&neighbor) {
match input.get(&neighbor) {
Some(&x) if x == region_type => {
next_region.insert(neighbor);
updated = true;
}
Some(_) => {
next_regions.push({
let mut new_region = HashSet::new();
new_region.insert(neighbor);
new_region
});
updated = true;
}
None => {}
}
}
}
}
next_regions.push(next_region);
}
if !updated {
break;
}
regions = merge_regions(next_regions, input);
}
regions
}To merge regions, we first group regions of the same type together via a sort. Then, for each chunk of regions of the same type, we check each combination of two regions to see if they intersect. If the regions intersect, both the regions are replaced by their union.
fn merge_regions(
mut regions: Vec<HashSet<Point>>,
grid: &HashMap<Point, char>,
) -> Vec<HashSet<Point>> {
regions.sort_unstable_by_key(|region| grid[region.iter().next().unwrap()]);
let mut merged_regions = Vec::new();
let mut i = 0;
while i < regions.len() {
let current_region_type = grid[regions[i].iter().next().unwrap()];
let chunk_len = regions[i..]
.iter()
.take_while(|x| grid[x.iter().next().unwrap()] == current_region_type)
.count();
let mut combined_regions = regions[i..][..chunk_len].to_vec();
for k in 0..chunk_len {
for l in (k + 1)..chunk_len {
let intersection = combined_regions[k]
.intersection(&combined_regions[l])
.copied()
.collect::<HashSet<_>>();
if !intersection.is_empty() {
let union_ = combined_regions[k]
.union(&combined_regions[l])
.copied()
.collect::<HashSet<_>>();
combined_regions[k] = union_;
combined_regions[l] = HashSet::new();
}
}
}
merged_regions.extend(combined_regions.into_iter().filter(|x| !x.is_empty()));
i += chunk_len;
}
merged_regions
}Our answer is found by summing up the price for fencing each region. The price of a region is the product of its area and its perimeter.
fn part1(input: &HashMap<Point, char>) -> usize {
let regions = create_regions(input);
regions
.iter()
.map(|region| region.len() * region_perimeter(region, input))
.sum()
}To find the perimeter of a region, we sum up the number of different-type (or nonexistent) neighbors that each point has.
fn region_perimeter(region: &HashSet<Point>, grid: &HashMap<Point, char>) -> usize {
let region_type = grid[region.iter().next().unwrap()];
region
.iter()
.copied()
.map(|point| {
point
.neighbors()
.filter(|neighbor| grid.get(&neighbor) != Some(®ion_type))
.count()
})
.sum()
}Part Two
Due to a bulk discount, the price of a region is now the product of the area and the number of sides of a region. We now calculate the total price using this new formula.
fn part2(input: &HashMap<Point, char>) -> usize {
let regions = create_regions(input);
regions
.iter()
.map(|region| region.len() * region_num_sides(region, input))
.sum()
}To calculate the number of sides per region, we first get the points having a neighbor in that direction that is not in the region, for each one of the 4 neighbor directions. This list of points is collected into a hashmap with the direction as the key and a list of the points having non-region neighbors in that direction as the value.
Now, all the horizontal sides will have the same row with consecutive columns and all the vertical sides will have the same column with consecutive rows. For the vertical directions, we sort the points on their rows, then sort again on their columns. Since the sorts are stable, this ends up grouping points with equal columns together and within the points with same column, the points are sorted by their row. We then count the number of groups per direction that have the same column and consecutive rows. This gives us the number of vertical sides. For the horizontal sides, we do the same thing but with rows and columns switched.
A more elegant and readable solution would have been to create an enum of the four neighbor directions and use them for grouping instead of relying on the neighbors being outputted in a specific order.
fn region_num_sides(region: &HashSet<Point>, grid: &HashMap<Point, char>) -> usize {
let region_type = grid[region.iter().next().unwrap()];
let fence_points = region.iter().copied().flat_map(|point| {
point
.neighbors()
.enumerate()
.filter(|&(_i, neighbor)| grid.get(&neighbor) != Some(®ion_type))
.map(move |(i, _neighbor)| (i, point))
});
let mut fence = HashMap::new();
for (direction, point) in fence_points {
fence.entry(direction).or_insert(Vec::new()).push(point);
}
let mut num_sides = 0;
for direction in [1, 3] {
// each side will have col same, row consecutive
fence
.get_mut(&direction)
.unwrap()
.sort_by_key(|point| point.row);
fence
.get_mut(&direction)
.unwrap()
.sort_by_key(|point| point.col);
let mut i = 0;
while i < fence[&direction].len() {
let chunk_len = fence[&direction][i..]
.windows(2)
.take_while(|points| {
points[0].col == points[1].col && points[1].row - points[0].row == 1
})
.count()
+ 1;
num_sides += 1;
i += chunk_len;
}
}
for direction in [0, 2] {
// each side will have row same, col consecutive
fence
.get_mut(&direction)
.unwrap()
.sort_by_key(|point| point.col);
fence
.get_mut(&direction)
.unwrap()
.sort_by_key(|point| point.row);
let mut i = 0;
while i < fence[&direction].len() {
let chunk_len = fence[&direction][i..]
.windows(2)
.take_while(|points| {
points[0].row == points[1].row && points[1].col - points[0].col == 1
})
.count()
+ 1;
num_sides += 1;
i += chunk_len;
}
}
num_sides
}