Advent of Code 2023 Day 21

Day 21: Step Counter

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

After fixing the sand supply, you visit the gardener again.

An elf heard of your exploits and wants your help.

Today’s input is a map of the gardens.

An example input looks like this:

input.txt

...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........

# is a rock
. is a garden
S is your starting position

Your starting position is also a garden.

The elf would like to know how many tiles they can reach in a given amount of steps.

Each step the elf can move up/down/left/right given that there is no rock in the way.

Backtracking is allowed, so the elf could go left/right forever if it wants to.

Parsing

I went very imperative today as it was the first thing that came to mind, and it works! I parse the 2D grid of Tile and a starting Coord.

enum Tile {
    Garden,
    Rock,
}

struct Coord {
    col: usize,
    row: usize,
}

fn parse(input: &str) -> (Vec<Vec<Tile>>, Coord) {
    let mut start = Coord { col: 0, row: 0 };
    let mut grid = Vec::new();
    for (y, line) in input.lines().enumerate() {
        let mut row = Vec::new();
        for (x, c) in line.chars().enumerate() {
            let tile = match c {
                '.' => Tile::Garden,
                '#' => Tile::Rock,
                'S' => {
                    start.col = x;
                    start.row = y;
                    Tile::Garden
                }
                _ => panic!(),
            };
            row.push(tile);
        }
        grid.push(row);
    }
    (grid, start)
}

Part 1

The Elf actually needs to get 64 steps today.

Starting from the garden plot marked S on your map, how many garden plots could the Elf reach in exactly 64 steps?

Helpers

A method on a Coord that returns every neighbour in the grid:

impl Coord {
    fn neighbours(&self, rows: usize, cols: usize) -> Vec<Self> {
        let mut res = Vec::new();
        // up
        if self.row > 0 {
            res.push(Coord1 {
                col: self.col,
                row: self.row - 1,
            });
        }
        // down
        if self.row < rows - 1 {
            res.push(Coord1 {
                col: self.col,
                row: self.row + 1,
            });
        }
        // left
        if self.col > 0 {
            res.push(Coord1 {
                col: self.col - 1,
                row: self.row,
            });
        }
        // right
        if self.col < cols - 1 {
            res.push(Coord1 {
                col: self.col + 1,
                row: self.row,
            })
        };

        res
    }
}

I kept track of the locations that could be visited in the same amount of steps in a set.

For each amount of steps, for each position in the set, I inserted every possible neighbour into a new set.

Before moving on to the next step, I update the old set to point to the new set.

Code

day_21.rs

pub fn part_1(input: &str) -> usize {
    let (grid, start) = parse(input);
    let rows = grid.len();
    let cols = grid[0].len();

    let mut set = HashSet::new();
    set.insert(start);

    for _ in 0..64 {
        let mut new_set = HashSet::new();
        for pos in set {
            for n in pos
                .neighbours(rows, cols)
                .into_iter()
                .filter(|pos| grid[pos.row][pos.col] == Tile::Garden)
            {
                new_set.insert(n);
            }
        }
        set = new_set
    }
    set.len()
}

Part 2

Oopsie, turns out the grid is infinitely repeating in every direction. Something, something, magic.

And the number of steps the elf gave you was also wrong, it should have been 26501365.

Helpers

This infinity business means the helpers I wrote are wrong.

A Coord should hold integers that can be negative.

struct Coord {
    col: i64,
    row: i64,
}

And the neighbour logic is no longer limited by puny limits:

impl Coord {
    fn neighbours(&self) -> Vec<Self> {
        let mut res = Vec::new();
        // up
        res.push(Coord {
            col: self.col,
            row: self.row - 1,
        });
        // down
        res.push(Coord {
            col: self.col,
            row: self.row + 1,
        });
        // left
        res.push(Coord {
            col: self.col - 1,
            row: self.row,
        });
        // right
        res.push(Coord {
            col: self.col + 1,
            row: self.row,
        });
        res
    }
}

This also means the parsing logic is slightly different, the part where I set the starting coordinate should now set signed integers instead of unsigned ones.

I read someone’s solution, translated it to Rust, and tried to understand it as best I could.

This part requires some investigation of the input again. It uses some properties of the input that are NOT ALL PRESENT in the example input.

The input is a square with an odd numbered size
The starting location is in the perfect middle of the square
All tiles on the starting row are gardens
All tiles on the starting column are gardens

This means that the quickest way to reach any edge is half of (the size of the square - 1).

It turns out that all the properties combined let you represent the amount of positions reachable in a certain amount of steps with a function. A quadratic function.

Let be the number of spaces you can reach after an amount of steps.
Let be the length of the input grid.
Let be the amount of steps needed to reach the edge of that grid

, , , … are all quadratic functions.

You can find that function by finding 3 values and then calculating which quadratic function satisfies all 3.

In our code we keep track of the first 3 values: the results to those 3 functions I wrote above.

What the question is looking for is .

And

Only is unknown here, plugging in the known numbers:

With all those numbers known calculating becomes, as my high-school math teacher would say, trivial.

Ugh, I just felt a pang of anger even typing those words.
Nearly every time that word is said, it’s a lie.
It was then, and it certainly is now.

And to repeat, I most certainly didn’t do this myself.

Code

day_21.rs

pub fn part_2(input: &str) -> usize {
    let goal = 26_501_365;
    let (grid, start) = parse(input);
    let size = grid.len();
    // the amount of steps it takes to reach an edge of the map (all tiles in the same row and column as start are gardens)
    let to_edge = size / 2;
    let mut fn_results = Vec::new();
    let mut set = HashSet::new();
    set.insert(start);

    for count in 1.. {
        let mut new_set = HashSet::new();

        for pos in set {
            for n in pos.infinite_neighbours().into_iter().filter(|pos| {
                let y = pos.row.rem_euclid(size as i64) as usize;
                let x = pos.col.rem_euclid(size as i64) as usize;
                grid[y][x] == Tile::Garden
            }) {
                new_set.insert(n);
            }
        }
        set = new_set;

        if count == to_edge + size * fn_results.len() {
            fn_results.push(set.len());

            if fn_results.len() == 3 {
                // EITHER
                // let delta0 = fn_results[0];
                // let delta1 = fn_results[1] - fn_results[0];
                // let delta2 = fn_results[2] - 2 * fn_results[1] + fn_results[0];

                // return delta0
                //     + delta1 * (goal / size)
                //     + delta2 * ((goal / size) * ((goal / size) - 1) / 2);

                // OR, written differently:
                let n = goal / size;

                let a0 = fn_results[0];
                let a1 = fn_results[1];
                let a2 = fn_results[2];

                let b0 = a0;
                let b1 = a1 - a0;
                let b2 = a2 - a1;
                return b0 + b1 * n + (n * (n - 1) / 2) * (b2 - b1);
            }
        }
    }

    panic!()
}

Final code

day_21.rs

1use std::collections::HashSet;
2
3#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
4struct Coord {
5    col: i64,
6    row: i64,
7}
8
9impl Coord {
10    fn neighbours(&self, rows: i64, cols: i64) -> Vec<Self> {
11        let mut res = Vec::new();
12        // up
13        if self.row > 0 {
14            res.push(Coord {
15                col: self.col,
16                row: self.row - 1,
17            });
18        }
19        // down
20        if self.row < rows - 1 {
21            res.push(Coord {
22                col: self.col,
23                row: self.row + 1,
24            });
25        }
26        // left
27        if self.col > 0 {
28            res.push(Coord {
29                col: self.col - 1,
30                row: self.row,
31            });
32        }
33        // right
34        if self.col < cols - 1 {
35            res.push(Coord {
36                col: self.col + 1,
37                row: self.row,
38            })
39        };
40
41        res
42    }
43
44    fn infinite_neighbours(&self) -> Vec<Self> {
45        let mut res = Vec::new();
46        // up
47        res.push(Coord {
48            col: self.col,
49            row: self.row - 1,
50        });
51        // down
52        res.push(Coord {
53            col: self.col,
54            row: self.row + 1,
55        });
56        // left
57        res.push(Coord {
58            col: self.col - 1,
59            row: self.row,
60        });
61        // right
62        res.push(Coord {
63            col: self.col + 1,
64            row: self.row,
65        });
66        res
67    }
68}
69
70#[derive(Debug, PartialEq)]
71enum Tile {
72    Garden,
73    Rock,
74}
75
76fn parse(input: &str) -> (Vec<Vec<Tile>>, Coord) {
77    let mut start = Coord { col: 0, row: 0 };
78    let mut grid = Vec::new();
79    for (y, line) in input.lines().enumerate() {
80        let mut row = Vec::new();
81        for (x, c) in line.chars().enumerate() {
82            let tile = match c {
83                '.' => Tile::Garden,
84                '#' => Tile::Rock,
85                'S' => {
86                    start.col = x as i64;
87                    start.row = y as i64;
88                    Tile::Garden
89                }
90                _ => panic!(),
91            };
92            row.push(tile);
93        }
94        grid.push(row);
95    }
96    (grid, start)
97}
98
99pub fn part_1(input: &str) -> usize {
100    let (grid, start) = parse(input);
101    let rows = grid.len();
102    let cols = grid[0].len();
103
104    let mut set = HashSet::new();
105    set.insert(start);
106
107    for _ in 0..64 {
108        let mut new_set = HashSet::new();
109        for pos in set {
110            for n in pos
111                .neighbours(rows as i64, cols as i64)
112                .into_iter()
113                .filter(|pos| grid[pos.row as usize][pos.col as usize] == Tile::Garden)
114            {
115                new_set.insert(n);
116            }
117        }
118        set = new_set
119    }
120    set.len()
121}
122
123// Let f(n) be the number of spaces you can reach after n steps. Let X be the length of your input grid. f(n), f(n+X), f(n+2X), ...., is a quadratic
124// You can find it by finding the first 3 values, then use that to interpolate the final answer.
125pub fn part_2(input: &str) -> usize {
126    let goal = 26_501_365;
127    let (grid, start) = parse(input);
128    let size = grid.len();
129    // the amount of steps it takes to reach an edge of the map (all tiles in the same row and column as start are gardens)
130    let to_edge = size / 2;
131    let mut fn_results = Vec::new();
132    let mut set = HashSet::new();
133    set.insert(start);
134
135    for count in 1.. {
136        let mut new_set = HashSet::new();
137
138        for pos in set {
139            for n in pos.infinite_neighbours().into_iter().filter(|pos| {
140                let y = pos.row.rem_euclid(size as i64) as usize;
141                let x = pos.col.rem_euclid(size as i64) as usize;
142                grid[y][x] == Tile::Garden
143            }) {
144                new_set.insert(n);
145            }
146        }
147        set = new_set;
148
149        if count == to_edge + size * fn_results.len() {
150            fn_results.push(set.len());
151
152            if fn_results.len() == 3 {
153                // EITHER
154                // let delta0 = fn_results[0];
155                // let delta1 = fn_results[1] - fn_results[0];
156                // let delta2 = fn_results[2] - 2 * fn_results[1] + fn_results[0];
157
158                // return delta0
159                //     + delta1 * (goal / size)
160                //     + delta2 * ((goal / size) * ((goal / size) - 1) / 2);
161
162                // OR, written differently:
163                let n = goal / size;
164
165                let a0 = fn_results[0];
166                let a1 = fn_results[1];
167                let a2 = fn_results[2];
168
169                let b0 = a0;
170                let b1 = a1 - a0;
171                let b2 = a2 - a1;
172                return b0 + b1 * n + (n * (n - 1) / 2) * (b2 - b1);
173            }
174        }
175    }
176
177    panic!()
178}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 21

Day 21: Step Counter

Parsing

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code