NickyMeulemanNime

• ### By

• Nicky Meuleman

• ### Older post

Advent of Code 2023 Day 20

Advent of Code 2023 Day 22

1. Day 21: Step Counter
2. Parsing
3. Part 1
4. Part 2
5. Helpers
1. Code
6. Final code

# Advent of Code 2023 Day 21

## Day 21: Step Counter

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

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,}.css-13aqjzy{display:inline-block;}
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:

So

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
.css-1mjim83{display:inline-block;width:2ch;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;opacity:0.3;margin-right:0.5rem;}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        // up13        if self.row > 0 {14            res.push(Coord {15                col: self.col,16                row: self.row - 1,17            });18        }19        // down20        if self.row < rows - 1 {21            res.push(Coord {22                col: self.col,23                row: self.row + 1,24            });25        }26        // left27        if self.col > 0 {28            res.push(Coord {29                col: self.col - 1,30                row: self.row,31            });32        }33        // right34        if self.col < cols - 1 {35            res.push(Coord {36                col: self.col + 1,37                row: self.row,38            })39        };40
41        res42    }43
44    fn infinite_neighbours(&self) -> Vec<Self> {45        let mut res = Vec::new();46        // up47        res.push(Coord {48            col: self.col,49            row: self.row - 1,50        });51        // down52        res.push(Coord {53            col: self.col,54            row: self.row + 1,55        });56        // left57        res.push(Coord {58            col: self.col - 1,59            row: self.row,60        });61        // right62        res.push(Coord {63            col: self.col + 1,64            row: self.row,65        });66        res67    }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::Garden89                }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 pos111                .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_set119    }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 quadratic124// 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::Garden143            }) {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                // EITHER154                // 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 delta0159                //     + 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}