Advent of Code 2023 Day 10

Day 10: Pipe Maze

https://adventofcode.com/2023/day/10

You go up to a metal island with a hang glider.

There, you see an animal run into a maze of pipes.

You scan the maze of pipes, that scan is today’s input.

An example input looks like this:

input.txt

..F7.
.FJ|.
SJ.L7
|F--J
LJ...

The pipes are arranged in a two-dimensional grid of tiles:

| is a vertical pipe connecting north and south.
- is a horizontal pipe connecting east and west.
L is a 90-degree bend connecting north and east.
J is a 90-degree bend connecting north and west.
7 is a 90-degree bend connecting south and west.
F is a 90-degree bend connecting south and east.
. is ground; there is no pipe in this tile.
S is the starting position of the animal; there is a pipe on this tile, but your sketch doesn’t show what shape the pipe has.

The pipe the animal ran into is a large, continuous loop.

There are other pipes in your scan that are not connected to the main loop.

Parsing

I decided to represent each type of input as a Tile enum.

enum Tile {
    // | is a vertical pipe connecting north and south.
    NorthSouth,
    // - is a horizontal pipe connecting east and west.
    EastWest,
    // L is a 90-degree bend connecting north and east.
    NorthEast,
    // J is a 90-degree bend connecting north and west.
    NorthWest,
    // 7 is a 90-degree bend connecting south and west.
    SouthWest,
    // F is a 90-degree bend connecting south and east.
    SouthEast,
    // . is ground; there is no pipe in this tile.
    Ground,
    // S is the starting position of the animal; there is a pipe on this tile, but your sketch doesn't show what shape the pipe has.
    Start,
}

A helper to turn characters into variants of that enum:

impl Tile {
    fn from(c: char) -> Self {
        match c {
            '|' => NorthSouth,
            '-' => EastWest,
            'L' => NorthEast,
            'J' => NorthWest,
            '7' => SouthWest,
            'F' => SouthEast,
            '.' => Ground,
            'S' => Start,
            _ => panic!(),
        }
    }
}

I keep track of a coordinate in the 2D grid with Coord:

struct Coord {
    row_idx: usize,
    col_idx: usize,
}

From the input, I parse the coordinate of the start position, and a 2D list of Tiles:

fn parse(input: &str) -> (Vec<Vec<Tile>>, Coord) {
    let mut start = Coord::new(0, 0);
    let map = input
        .lines()
        .enumerate()
        .map(|(row_idx, line)| {
            line.chars()
                .enumerate()
                .map(|(col_idx, c)| {
                    let tile = Tile::from(c);
                    if tile == Start {
                        start = Coord::new(row_idx, col_idx)
                    }
                    tile
                })
                .collect()
        })
        .collect();
    (map, start)
}

Part 1

You want to look at the animal that ran into the pipes. You decide to wait for the animal at the spot that’s the most steps along the loop away from the start, regardless of which direction it took.

The question asks how many steps along the loop it takes to get from the starting position to the point farthest from the starting position?

In other words, you wait at the coordinate that marks the middle of the loop.

Some skeleton/pseudo-code I want to work towards:

let (map, start) = parse(input);
let loop_coords = build_loop(start, &map);
loop_coords.len() / 2

Helpers

The function that turns the map into a set of coordinates that belong to the main loop:

fn build_loop(start: Coord, map: &[Vec<Tile>]) -> HashSet<Coord> {
    let mut loop_coords = HashSet::new();
    loop_coords.insert(start);
    let mut to_visit = start.valid_neighbours(map);

    while let Some(curr_pos) = to_visit.pop() {
        for neighbour in curr_pos.valid_neighbours(map) {
            if !loop_coords.contains(&neighbour) {
                to_visit.push(neighbour);
                loop_coords.insert(neighbour);
            }
        }
    }

    loop_coords
}

That function used a helper that returns the coordinates of the pipes that are directly connected to the current pipe. This is the main logic of this problem, it’s a huge decision-tree.

It figures out which type of Tile I am currently on. Based on that, it figures out which types of Tile are allowed to connect to that. The coordinates a valid connecting tiles are returned by this function.

example: An L pipe (NorthWest in our Tile enum), can only accept a connecting tile in the north, or the west.

It looks in the north location, and if a valid pipe is there, it marks that location as a valid neighbour
It looks in the west location, and if a valid pipe is there, it marks that location as a valid neighbour

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Coord {
    row_idx: usize,
    col_idx: usize,
}

impl Coord {
    fn new(row_idx: usize, col_idx: usize) -> Self {
        Self { row_idx, col_idx }
    }

    fn valid_neighbours(&self, map: &[Vec<Tile>]) -> Vec<Coord> {
        let mut neighbours = vec![];
        let max_height = map.len() - 1;
        let max_width = map[0].len() - 1;

        match map[self.row_idx][self.col_idx] {
            Ground => (),
            Start => {
                // north
                if self.row_idx > 0 {
                    let tile = map[self.row_idx - 1][self.col_idx];
                    if matches!(tile, NorthSouth | SouthWest | SouthEast) {
                        neighbours.push(Coord::new(self.row_idx - 1, self.col_idx));
                    }
                }
                // south
                if self.row_idx < max_height {
                    let tile = map[self.row_idx + 1][self.col_idx];
                    if matches!(tile, NorthSouth | NorthWest | NorthEast) {
                        neighbours.push(Coord::new(self.row_idx + 1, self.col_idx))
                    }
                }
                // west
                if self.col_idx > 0 {
                    let tile = map[self.row_idx][self.col_idx - 1];
                    if matches!(tile, EastWest | SouthEast | NorthEast) {
                        neighbours.push(Coord::new(self.row_idx, self.col_idx - 1))
                    }
                }
                // east
                if self.col_idx < max_width {
                    let tile = map[self.row_idx][self.col_idx + 1];
                    if matches!(tile, EastWest | NorthWest | SouthWest) {
                        neighbours.push(Coord::new(self.row_idx, self.col_idx + 1))
                    }
                }
            }
            NorthSouth => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // south
                if self.row_idx < max_height && map[self.row_idx + 1][self.col_idx] != Ground {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
            }
            EastWest => {
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
            NorthEast => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
            NorthWest => {
                // north
                if self.row_idx > 0 {
                    match map[self.row_idx - 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
                        _ => (),
                    }
                }
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
            }
            SouthWest => {
                // south
                if self.row_idx < max_height {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
                // west
                if self.col_idx > 0 {
                    match map[self.row_idx][self.col_idx - 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
                        _ => (),
                    }
                }
            }
            SouthEast => {
                // south
                if self.row_idx < max_height {
                    match map[self.row_idx + 1][self.col_idx] {
                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
                        _ => (),
                    }
                }
                // east
                if self.col_idx < max_width {
                    match map[self.row_idx][self.col_idx + 1] {
                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
                        _ => (),
                    }
                }
            }
        }

        neighbours
    }
}

Code

The reused code is not listed here, because otherwise this post would become huge.

day_10.rs

pub fn part_1(input: &str) -> usize {
    let (map, start) = parse(input);
    let loop_coords = build_loop(start, &map);
    loop_coords.len() / 2
}

Part 2

The animal did not emerge. Its nest is probably within an area that’s enclosed by the loop.

This is an example loop with only pipes that are part of the main loop.

...........
.S-------7.
.|F-----7|.
.||.....||.
.||.....||.
.|L-7.F-J|.
.|..|.|..|.
.L--J.L--J.
...........

There are 4 tiles that are completely inside the loop, marked as I below. The tiles marked as O are not inside.

...........
.S-------7.
.|F-----7|.
.||OOOOO||.
.||OOOOO||.
.|L-7OF-J|.
.|II|O|II|.
.L--JOL--J.
.....O.....

The animal is small, and can squeeze between 2 pipes, even if there isn’t a . tile in between!

Here O tiles are still not inside the loop, and I tiles are:

..........
.S------7.
.|F----7|.
.||OOOO||.
.||OOOO||.
.|L-7F-J|.
.|II||II|.
.L--JL--J.
..........

The question asks how many tiles are enclosed by the loop.

Option 1: flood fill

Because of that rule where the animal can fit between 2 pipes, a regular floodfill approach will not work. You would end up also counting tiles that are still accessible from the outside.

However, if you expend every tile into a 3x3 grid of tiles, there are guaranteed to be gaps between tiles, where floodfill can pass.

In ASCII: | turns into:

.#.
.#.
.#.

- turns into:

...
###
...

J turns into:

..#
..#
###

and so forth…

Start the floodfill at an empty tile. The tiles that are still empty at the end are inside the loop. Remember to account for the fact that 1 empty tile turned into a 3x3 grid of empty tiles when you first expanded the grid.

Option 2: even-odd rule

This is the solution I ended up coding.

Get the coordinates of the loop
Clean the map:
1. Replace that starting coordinate with a segment of pipe
2. Only keep segments of pipe that are part of the main loop
Apply the even-odd rule to the clean map

in pseudo-code:

let (map, start) = parse(input);
let loop_coords = build_loop(start, &map);
let clean_map = clean_map(start, &loop_coords, map);
let count = count_enclosed_tiles(clean_map);
count

Helpers

The helpers that takes the initial map, and returns a cleaned up map:

It only hold pieces of pipe that are part of the main loop, all other coordinates are ground tiles.
It replaces that start position with a valid piece of pipe

/// replace start with a valid pipe segment, and only keep pipe segments that are part of the loop
fn clean_map(start: Coord, loop_coords: &HashSet<Coord>, map: Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    let start_pipe = get_start_pipe(&map, start);

    map.into_iter()
        .enumerate()
        .map(|(row_idx, line)| {
            line.into_iter()
                .enumerate()
                .map(|(col_idx, tile)| match tile {
                    Start => start_pipe,
                    pipe if loop_coords.contains(&Coord::new(row_idx, col_idx)) => pipe,
                    _ => Ground,
                })
                .collect()
        })
        .collect()
}

That function used another helper to figure out which piece of pipe is located at the start coordinates:

fn get_start_pipe(map: &Vec<Vec<Tile>>, start: Coord) -> Tile {
    let neighbours = start.valid_neighbours(map);
    let north = neighbours
        .iter()
        .find(|coord| coord.row_idx < start.row_idx)
        .is_some();
    let south = neighbours
        .iter()
        .find(|coord| coord.row_idx > start.row_idx)
        .is_some();
    let west = neighbours
        .iter()
        .find(|coord| coord.col_idx < start.col_idx)
        .is_some();
    let east = neighbours
        .iter()
        .find(|coord| coord.col_idx > start.col_idx)
        .is_some();

    match (north, west, south, east) {
        (true, true, _, _) => NorthWest,
        (true, _, true, _) => NorthSouth,
        (true, _, _, true) => NorthEast,
        (_, true, true, _) => SouthWest,
        (_, _, true, true) => SouthEast,
        (_, true, _, true) => EastWest,
        _ => panic!("No valid tile to replace Start with was found"),
    }
}

With a clean map, I used the even-odd rule to count the amount of tiles that are enclosed by that loop.

Basically if it’s an S shaped joint (FJ, L7) it’s a cross over into the other side, while if it’s a U shaped joint (F7, LJ) you end up on the same side
Chris Biscardi

Code

The reused code is not listed here, because otherwise this post would become huge.

day_10.rs

pub fn part_2(input: &str) -> usize {
    let (map, start) = parse(input);
    let loop_coords = build_loop(start, &map);
    let map = clean_map(start, &loop_coords, map);
    // scan from top to bottom and left to right, counting how many tiles are inside the loop.
    // keep track of a boolean that tells me if I'm inside the loop
    // every time I cross a vertical pipe that does not horizontally block the top (the place where I am in the loop), flip that state
    let mut inside = false;
    map.into_iter()
        .flatten()
        .filter(|tile| match tile {
            Ground => inside,
            NorthSouth | NorthWest | NorthEast => {
                inside = !inside;
                false
            }
            _ => false,
        })
        .count()
}

Final code

day_10.rs

1use std::collections::HashSet;
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq)]
4enum Tile {
5    // | is a vertical pipe connecting north and south.
6    NorthSouth,
7    // - is a horizontal pipe connecting east and west.
8    EastWest,
9    // L is a 90-degree bend connecting north and east.
10    NorthEast,
11    // J is a 90-degree bend connecting north and west.
12    NorthWest,
13    // 7 is a 90-degree bend connecting south and west.
14    SouthWest,
15    // F is a 90-degree bend connecting south and east.
16    SouthEast,
17    // . is ground; there is no pipe in this tile.
18    Ground,
19    // S is the starting position of the animal; there is a pipe on this tile, but your sketch doesn't show what shape the pipe has.
20    Start,
21}
22use Tile::*;
23impl Tile {
24    fn from(c: char) -> Self {
25        match c {
26            '|' => NorthSouth,
27            '-' => EastWest,
28            'L' => NorthEast,
29            'J' => NorthWest,
30            '7' => SouthWest,
31            'F' => SouthEast,
32            '.' => Ground,
33            'S' => Start,
34            _ => panic!(),
35        }
36    }
37}
38
39#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
40struct Coord {
41    row_idx: usize,
42    col_idx: usize,
43}
44
45impl Coord {
46    fn new(row_idx: usize, col_idx: usize) -> Self {
47        Self { row_idx, col_idx }
48    }
49
50    fn valid_neighbours(&self, map: &[Vec<Tile>]) -> Vec<Coord> {
51        let mut neighbours = vec![];
52        let max_height = map.len() - 1;
53        let max_width = map[0].len() - 1;
54
55        match map[self.row_idx][self.col_idx] {
56            Ground => (),
57            Start => {
58                // north
59                if self.row_idx > 0 {
60                    let tile = map[self.row_idx - 1][self.col_idx];
61                    if matches!(tile, NorthSouth | SouthWest | SouthEast) {
62                        neighbours.push(Coord::new(self.row_idx - 1, self.col_idx));
63                    }
64                }
65                // south
66                if self.row_idx < max_height {
67                    let tile = map[self.row_idx + 1][self.col_idx];
68                    if matches!(tile, NorthSouth | NorthWest | NorthEast) {
69                        neighbours.push(Coord::new(self.row_idx + 1, self.col_idx))
70                    }
71                }
72                // west
73                if self.col_idx > 0 {
74                    let tile = map[self.row_idx][self.col_idx - 1];
75                    if matches!(tile, EastWest | SouthEast | NorthEast) {
76                        neighbours.push(Coord::new(self.row_idx, self.col_idx - 1))
77                    }
78                }
79                // east
80                if self.col_idx < max_width {
81                    let tile = map[self.row_idx][self.col_idx + 1];
82                    if matches!(tile, EastWest | NorthWest | SouthWest) {
83                        neighbours.push(Coord::new(self.row_idx, self.col_idx + 1))
84                    }
85                }
86            }
87            NorthSouth => {
88                // north
89                if self.row_idx > 0 {
90                    match map[self.row_idx - 1][self.col_idx] {
91                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
92                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
93                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
94                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
95                        _ => (),
96                    }
97                }
98                // south
99                if self.row_idx < max_height && map[self.row_idx + 1][self.col_idx] != Ground {
100                    match map[self.row_idx + 1][self.col_idx] {
101                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
102                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
103                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
104                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
105                        _ => (),
106                    }
107                }
108            }
109            EastWest => {
110                // west
111                if self.col_idx > 0 {
112                    match map[self.row_idx][self.col_idx - 1] {
113                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
114                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
115                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
116                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
117                        _ => (),
118                    }
119                }
120                // east
121                if self.col_idx < max_width {
122                    match map[self.row_idx][self.col_idx + 1] {
123                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
124                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
125                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
126                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
127                        _ => (),
128                    }
129                }
130            }
131            NorthEast => {
132                // north
133                if self.row_idx > 0 {
134                    match map[self.row_idx - 1][self.col_idx] {
135                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
136                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
137                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
138                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
139                        _ => (),
140                    }
141                }
142                // east
143                if self.col_idx < max_width {
144                    match map[self.row_idx][self.col_idx + 1] {
145                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
146                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
147                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
148                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
149                        _ => (),
150                    }
151                }
152            }
153            NorthWest => {
154                // north
155                if self.row_idx > 0 {
156                    match map[self.row_idx - 1][self.col_idx] {
157                        NorthSouth => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
158                        SouthWest => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
159                        SouthEast => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
160                        Start => neighbours.push(Coord::new(self.row_idx - 1, self.col_idx)),
161                        _ => (),
162                    }
163                }
164                // west
165                if self.col_idx > 0 {
166                    match map[self.row_idx][self.col_idx - 1] {
167                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
168                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
169                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
170                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
171                        _ => (),
172                    }
173                }
174            }
175            SouthWest => {
176                // south
177                if self.row_idx < max_height {
178                    match map[self.row_idx + 1][self.col_idx] {
179                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
180                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
181                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
182                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
183                        _ => (),
184                    }
185                }
186                // west
187                if self.col_idx > 0 {
188                    match map[self.row_idx][self.col_idx - 1] {
189                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
190                        SouthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
191                        NorthEast => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
192                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx - 1)),
193                        _ => (),
194                    }
195                }
196            }
197            SouthEast => {
198                // south
199                if self.row_idx < max_height {
200                    match map[self.row_idx + 1][self.col_idx] {
201                        NorthSouth => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
202                        NorthWest => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
203                        NorthEast => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
204                        Start => neighbours.push(Coord::new(self.row_idx + 1, self.col_idx)),
205                        _ => (),
206                    }
207                }
208                // east
209                if self.col_idx < max_width {
210                    match map[self.row_idx][self.col_idx + 1] {
211                        EastWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
212                        NorthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
213                        SouthWest => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
214                        Start => neighbours.push(Coord::new(self.row_idx, self.col_idx + 1)),
215                        _ => (),
216                    }
217                }
218            }
219        }
220
221        neighbours
222    }
223}
224
225fn parse(input: &str) -> (Vec<Vec<Tile>>, Coord) {
226    let mut start = Coord::new(0, 0);
227    let map = input
228        .lines()
229        .enumerate()
230        .map(|(row_idx, line)| {
231            line.chars()
232                .enumerate()
233                .map(|(col_idx, c)| {
234                    let tile = Tile::from(c);
235                    if tile == Start {
236                        start = Coord::new(row_idx, col_idx)
237                    }
238                    tile
239                })
240                .collect()
241        })
242        .collect();
243    (map, start)
244}
245
246fn build_loop(start: Coord, map: &[Vec<Tile>]) -> HashSet<Coord> {
247    let mut loop_coords = HashSet::new();
248    loop_coords.insert(start);
249    let mut to_visit = start.valid_neighbours(map);
250
251    while let Some(curr_pos) = to_visit.pop() {
252        for neighbour in curr_pos.valid_neighbours(map) {
253            if !loop_coords.contains(&neighbour) {
254                to_visit.push(neighbour);
255                loop_coords.insert(neighbour);
256            }
257        }
258    }
259
260    loop_coords
261}
262
263pub fn part_1(input: &str) -> usize {
264    let (map, start) = parse(input);
265    let loop_coords = build_loop(start, &map);
266    loop_coords.len() / 2
267}
268
269fn get_start_pipe(map: &Vec<Vec<Tile>>, start: Coord) -> Tile {
270    let neighbours = start.valid_neighbours(map);
271    let north = neighbours
272        .iter()
273        .find(|coord| coord.row_idx < start.row_idx)
274        .is_some();
275    let south = neighbours
276        .iter()
277        .find(|coord| coord.row_idx > start.row_idx)
278        .is_some();
279    let west = neighbours
280        .iter()
281        .find(|coord| coord.col_idx < start.col_idx)
282        .is_some();
283    let east = neighbours
284        .iter()
285        .find(|coord| coord.col_idx > start.col_idx)
286        .is_some();
287
288    match (north, west, south, east) {
289        (true, true, _, _) => NorthWest,
290        (true, _, true, _) => NorthSouth,
291        (true, _, _, true) => NorthEast,
292        (_, true, true, _) => SouthWest,
293        (_, _, true, true) => SouthEast,
294        (_, true, _, true) => EastWest,
295        _ => panic!("No valid tile to replace Start with was found"),
296    }
297}
298
299/// replace start with a valid pipe segment, and only keep pipe segments that are part of the loop
300fn clean_map(start: Coord, loop_coords: &HashSet<Coord>, map: Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
301    let start_pipe = get_start_pipe(&map, start);
302
303    map.into_iter()
304        .enumerate()
305        .map(|(row_idx, line)| {
306            line.into_iter()
307                .enumerate()
308                .map(|(col_idx, tile)| match tile {
309                    Start => start_pipe,
310                    pipe if loop_coords.contains(&Coord::new(row_idx, col_idx)) => pipe,
311                    _ => Ground,
312                })
313                .collect()
314        })
315        .collect()
316}
317
318pub fn part_2(input: &str) -> usize {
319    let (map, start) = parse(input);
320    let loop_coords = build_loop(start, &map);
321    let map = clean_map(start, &loop_coords, map);
322    // scan from top to bottom and left to right, counting how many tiles are inside the loop.
323    // keep track of a boolean that tells me if I'm inside the loop
324    // every time I cross a vertical pipe that does not horizontally block the top (the place where I am in the loop), flip that state
325    let mut inside = false;
326    map.into_iter()
327        .flatten()
328        .filter(|tile| match tile {
329            Ground => inside,
330            NorthSouth | NorthWest | NorthEast => {
331                inside = !inside;
332                false
333            }
334            _ => false,
335        })
336        .count()
337}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 10

Day 10: Pipe Maze

Parsing

Part 1

Helpers

Code

Part 2

Option 1: flood fill

Option 2: even-odd rule

Helpers

Code

Final code