Advent of Code 2023 Day 14

Day 14: Parabolic Reflector Dish

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

Turns out the mirrors from yesterday are used to power a concentrated solar mirror thingamajig. The mirrors are not calibrated correctly, that must be why the lava isn’t being made.

It being an advent of code elven mirror, it’s calibrated in the most convoluted way possible.

It uses a bunch of rocks to put pressure on the mirrors.

Today’s input is the arrangement of the calibration device (so, plane with a bunch of rocks on it).

An example input looks like this:

input.txt

O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....

O is a round rock
# is a square rock
. is empty space

You can tilt the calibration device.

The round rocks roll, the square rocks stay put.

Parsing

An enum to keep track of what a tile holds:

enum Tile {
    Round,
    Square,
    Empty,
}

A function to parse the input into a 2D list of Tile:

fn parse(input: &str) -> Vec<Vec<Tile>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| match c {
                    '.' => Tile::Empty,
                    '#' => Tile::Square,
                    'O' => Tile::Round,
                    _ => panic!("at the disco"),
                })
                .collect()
        })
        .collect()
}

Part 1

The question asks how much total load would be on the north support beams after sliding the rocks north.

The load is determined by the location of the rounded rocks.

Each rounded rock contributes a load equal to the number of rows from the rock to the south edge of the platform, including the row the rock is on.

Helpers

A function that slides all round rocks to the north:

fn slide_north(grid: &mut Vec<Vec<Tile>>) {
    for col in 0..grid[0].len() {
        let mut empty_or_round_row = 0;
        for row in 0..grid.len() {
            let curr = grid[row][col];
            match curr {
                Tile::Square => empty_or_round_row = row + 1,
                Tile::Round => {
                    // swap the current tile with the empty_or_round one
                    let replace_with = std::mem::replace(&mut grid[empty_or_round_row][col], curr);
                    let _ = std::mem::replace(&mut grid[row][col], replace_with);
                    empty_or_round_row += 1;
                }
                Tile::Empty => (),
            }
        }
    }
}

A function that calculated the total weight of a grid:

fn weight(grid: &Vec<Vec<Tile>>) -> usize {
    grid.iter()
        .rev()
        .enumerate()
        .map(|(i, row)| {
            let round_rocks = row.iter().filter(|tile| **tile == Tile::Round).count();
            round_rocks * (i + 1)
        })
        .sum()
}

Combining these helpers makes the final code for part1 very short.

Code

day_14.rs

pub fn part_1(input: &str) -> usize {
    let mut grid = parse(input);
    slide_north(&mut grid);
    weight(&grid)
}

Part 2

The platform has a “spin cycle” button.

It slides the rocks: north, the west, then south, then east.

If you do that enough times, the mirrors will surely be calibrated.

The question asks what the total load is after 1000000000 cycles.

So, Advent of Code, huge number of cycles, that must mean a cycle detection problem.

First, I’ll code enough to try this problem brute-force, but I’m not getting my hopes up.

Helpers

First, a function that applies a full cycle to a grid (tilting north, west, south, east).

Tilting north, west, south, east means tilting in a counterclockwise pattern.

That’s the same as:

Tilt north
Turn grid clockwise
Tilt north
Turn grid clockwise
Tilt north
Turn grid clockwise
Tilt north
Turn grid clockwise

fn cycle(mut grid: Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    for _ in 0..4 {
        slide_north(&mut grid);
        let rotated = clockwise(&grid);
        grid = rotated;
    }
    grid
}

So the next helper is the one that turns a grid clockwise. To do that, change every (x, y) coordinate to an (y, -x) coordinate.

// rotate 90 degrees clockwise: (x, y) -> (y, -x)
fn clockwise(grid: &Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
    let size = grid.len();
    let mut rotated = vec![vec![Tile::Empty; size]; size];
    for row in 0..size {
        for col in 0..size {
            rotated[col][size - 1 - row] = grid[row][col];
        }
    }
    rotated
}

As I suspected, brute-forcing is a no-go. Time to put on the cycle-detecting hat! (It’s a regular hat, my ears are cold.)

I keep track of every grid pattern I saw so far. Each time I cycle the grid, I check if the new pattern exists in that list.

If the pattern appeared before, I hit the start of a new cycle. The length of a cycle is the total length of the list - the index where the repeat happened.

Using that length, figure out the index of the pattern the entire loop will end on.

Code

day_14.rs

pub fn part_2(input: &str) -> usize {
    let mut grid = parse(input);
    let mut seen = vec![grid.clone()];

    loop {
        grid = cycle(grid);
        // check if the cycled map has already been seen
        if let Some(idx) = seen.iter().position(|x| x == &grid) {
            // figure out length of cycle (watch out: a cycle might only start after a number of steps)
            let cycle_len = seen.len() - idx;
            // use cycle length to figure out the index of the final step in the seen list
            let final_idx = idx + (1_000_000_000 - idx) % cycle_len;
            return weight(&seen[final_idx]);
        }
        seen.push(grid.clone());
    }
}

Final code

day_14.rs

1#[derive(Debug, Clone, Copy, PartialEq)]
2enum Tile {
3    Round,
4    Square,
5    Empty,
6}
7
8fn parse(input: &str) -> Vec<Vec<Tile>> {
9    input
10        .lines()
11        .map(|line| {
12            line.chars()
13                .map(|c| match c {
14                    '.' => Tile::Empty,
15                    '#' => Tile::Square,
16                    'O' => Tile::Round,
17                    _ => panic!("at the disco"),
18                })
19                .collect()
20        })
21        .collect()
22}
23
24fn slide_north(grid: &mut Vec<Vec<Tile>>) {
25    for col in 0..grid[0].len() {
26        let mut empty_or_round_row = 0;
27        for row in 0..grid.len() {
28            let curr = grid[row][col];
29            match curr {
30                Tile::Square => empty_or_round_row = row + 1,
31                Tile::Round => {
32                    // swap the current tile with the empty_or_round one
33                    let replace_with = std::mem::replace(&mut grid[empty_or_round_row][col], curr);
34                    let _ = std::mem::replace(&mut grid[row][col], replace_with);
35                    empty_or_round_row += 1;
36                }
37                Tile::Empty => (),
38            }
39        }
40    }
41}
42
43fn weight(grid: &Vec<Vec<Tile>>) -> usize {
44    grid.iter()
45        .rev()
46        .enumerate()
47        .map(|(i, row)| {
48            let round_rocks = row.iter().filter(|tile| **tile == Tile::Round).count();
49            round_rocks * (i + 1)
50        })
51        .sum()
52}
53
54// rotate 90 degrees clockwise: (x, y) -> (y, -x)
55fn clockwise(grid: &Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
56    let size = grid.len();
57    let mut rotated = vec![vec![Tile::Empty; size]; size];
58    for row in 0..size {
59        for col in 0..size {
60            rotated[col][size - 1 - row] = grid[row][col];
61        }
62    }
63    rotated
64}
65
66fn cycle(mut grid: Vec<Vec<Tile>>) -> Vec<Vec<Tile>> {
67    for _ in 0..4 {
68        slide_north(&mut grid);
69        let rotated = clockwise(&grid);
70        grid = rotated;
71    }
72    grid
73}
74
75pub fn part_1(input: &str) -> usize {
76    let mut grid = parse(input);
77    slide_north(&mut grid);
78    weight(&grid)
79}
80
81pub fn part_2(input: &str) -> usize {
82    let mut grid = parse(input);
83    let mut seen = vec![grid.clone()];
84
85    loop {
86        grid = cycle(grid);
87        // check if the cycled map has already been seen
88        if let Some(idx) = seen.iter().position(|x| x == &grid) {
89            // figure out length of cycle (watch out: a cycle might only start after a number of steps)
90            let cycle_len = seen.len() - idx;
91            // use cycle length to figure out the index of the final step in the seen list
92            let final_idx = idx + (1_000_000_000 - idx) % cycle_len;
93            return weight(&seen[final_idx]);
94        }
95        seen.push(grid.clone());
96    }
97}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 14

Day 14: Parabolic Reflector Dish

Parsing

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code