Advent of Code 2024 Day 18

Day 18: RAM Run

https://adventofcode.com/2024/day/18

Another day, another familiar sensation. This time, you’re inside a computer again.

Some algorithm is corrupting bytes in the memory where you are, one byte at a time. That’s today’s input, an ordered list of byte locations the algorithm is going to corrupt. When a position becomes corrupt, you can no longer be at that location.

An example input looks like this:

5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0

Each line is a location, in a col_idx,row_idx form.

Wait a minute, this is another 2D-grid problem!

Parsing

Alright, you might already know the drill, time for a Point. Then turn the input into a list of them.

#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
struct Point {
    row: i32,
    col: i32,
}

impl Point {
    fn new(row: i32, col: i32) -> Self {
        Self { row, col }
    }
}

fn parse(input: &str) -> Vec<Point> {
    input
        .lines()
        .map(|line| {
            let (col, row) = line.split_once(',').unwrap();
            Point::new(row.parse().unwrap(), col.parse().unwrap())
        })
        .collect()
}

Part 1

You need to get out of this place while you still can.

The grid you are in is 71 by 71 in size (the problem mentions 70, but those are 0-indexed numbers!).
You start at row: 0, col: 0
The goal is at row: 70, col: 70

The question asks what the minimum amount of steps is to reach the goal after 1024 positions have become corrupted.

Each step you can move in the 4 directions if that location isn’t corrupted. This is a breadth-first-search again, so I used some of the helpers from previous days.

Helpers

impl Point {
    fn new(row: i32, col: i32) -> Self {
        Self { row, col }
    }

    fn add(&self, other: &Self) -> Self {
        Self::new(self.row + other.row, self.col + other.col)
    }

    fn dirs() -> [Point; 4] {
        [
            // up
            Self::new(-1, 0),
            // right
            Self::new(0, 1),
            // down
            Self::new(1, 0),
            // left
            Self::new(0, -1),
        ]
    }

    fn is_in_bounds(&self, rows: i32, cols: i32) -> bool {
        (self.row >= 0 && self.row < rows) && (self.col >= 0 && self.col < cols)
    }

    fn neighbours(&self, rows: i32, cols: i32) -> Vec<Self> {
        let mut neighbours = Vec::new();
        for dir in Self::dirs() {
            let next = self.add(&dir);
            if next.is_in_bounds(rows, cols) {
                neighbours.push(next);
            }
        }
        neighbours
    }
}

Code

Breadth-first-search, where each item in the queue is a (point, score) pair, and the score increases by 1 each step. Point neighbours are only considered if they are not corrupted.

Before starting the search, I create a set of the first 1024 points in the input that become corrupted.

const ROWS: i32 = 71;
const COLS: i32 = 71;
const SIZE: usize = 1024;

fn part_1(input: &str) -> u32 {
    let falling = parse(input);
    let corrupted: HashSet<&Point> = falling.iter().take(SIZE).collect();

    let start = Point::new(0, 0);
    let end = Point::new(ROWS - 1, COLS - 1);

    let mut q = VecDeque::new();
    let mut seen = HashSet::new();
    q.push_back((start, 0));
    seen.insert(start);

    while let Some((pos, cost)) = q.pop_front() {
        if pos == end {
            return cost;
        }
        for neighbour in pos.neighbours(ROWS, COLS) {
            if corrupted.contains(&neighbour) {
                continue;
            }
            if seen.insert(neighbour) {
                q.push_back((neighbour, cost + 1));
            }
        }
    }

    panic!("at the disco");
}

Part 2

The historians want to know how slow they can go before a byte is corrupted that makes it impossible to reach the end from the start. I refactored my code from part1 a bit so the search logic is its own function that either returns a cost, or nothing. If it returns nothing, there is no possible path from start to finish.

The helper takes in a set of locations that are corrupted.

I then used that helper and performed a binary search on the list of input positions. At some position, crossing from start to end becomes impossible.

Everything before that point: a path exists
Everything after that point: no path exists

Helpers

fn search(
    corrupted: &HashSet<&Point>,
    start: Point,
    end: Point,
    rows: i32,
    cols: i32,
) -> Option<u32> {
    let mut q = VecDeque::new();
    let mut seen = HashSet::new();
    q.push_back((start, 0));
    seen.insert(start);

    while let Some((pos, cost)) = q.pop_front() {
        if pos == end {
            return Some(cost);
        }
        for neighbour in pos.neighbours(rows, cols) {
            if corrupted.contains(&neighbour) {
                continue;
            }
            if seen.insert(neighbour) {
                q.push_back((neighbour, cost + 1));
            }
        }
    }

    None
}

Code

fn part_2(input: &str) -> String {
    let falling = parse(input);

    let start = Point::new(0, 0);
    let end = Point::new(ROWS - 1, COLS - 1);

    let mut low = 0;
    let mut high = falling.len() - 1;

    while low < high {
        let mid = (low + high) / 2;
        let corrupted: HashSet<&Point> = falling.iter().take(mid + 1).collect();
        if search(&corrupted, start, end, ROWS, COLS).is_some() {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    let last = falling[low];
    format!("{},{}", last.col, last.row)
}

Final code

1
use std::collections::{HashSet, VecDeque};
2

3
const ROWS: i32 = 71;
4
const COLS: i32 = 71;
5
const SIZE: usize = 1024;
6

7
#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
8
struct Point {
9
    row: i32,
10
    col: i32,
11
}
12

13
impl Point {
14
    fn new(row: i32, col: i32) -> Self {
15
        Self { row, col }
16
    }
17

18
    fn add(&self, other: &Self) -> Self {
19
        Self::new(self.row + other.row, self.col + other.col)
20
    }
21

22
    fn dirs() -> [Point; 4] {
23
        [
24
            // up
25
            Self::new(-1, 0),
26
            // right
27
            Self::new(0, 1),
28
            // down
29
            Self::new(1, 0),
30
            // left
31
            Self::new(0, -1),
32
        ]
33
    }
34

35
    fn is_in_bounds(&self, rows: i32, cols: i32) -> bool {
36
        (self.row >= 0 && self.row < rows) && (self.col >= 0 && self.col < cols)
37
    }
38

39
    fn neighbours(&self, rows: i32, cols: i32) -> Vec<Self> {
40
        let mut neighbours = Vec::new();
41
        for dir in Self::dirs() {
42
            let next = self.add(&dir);
43
            if next.is_in_bounds(rows, cols) {
44
                neighbours.push(next);
45
            }
46
        }
47
        neighbours
48
    }
49
}
50

51
fn parse(input: &str) -> Vec<Point> {
52
    input
53
        .lines()
54
        .map(|line| {
55
            let (col, row) = line.split_once(',').unwrap();
56
            Point::new(row.parse().unwrap(), col.parse().unwrap())
57
        })
58
        .collect()
59
}
60

61
fn part_1(input: &str) -> u32 {
62
    let falling = parse(input);
63
    let corrupted: HashSet<&Point> = falling.iter().take(SIZE).collect();
64

65
    let start = Point::new(0, 0);
66
    let end = Point::new(ROWS - 1, COLS - 1);
67

68
    search(&corrupted, start, end, ROWS, COLS).unwrap()
69
}
70

71
fn search(
72
    corrupted: &HashSet<&Point>,
73
    start: Point,
74
    end: Point,
75
    rows: i32,
76
    cols: i32,
77
) -> Option<u32> {
78
    let mut q = VecDeque::new();
79
    let mut seen = HashSet::new();
80
    q.push_back((start, 0));
81
    seen.insert(start);
82

83
    while let Some((pos, cost)) = q.pop_front() {
84
        if pos == end {
85
            return Some(cost);
86
        }
87
        for neighbour in pos.neighbours(rows, cols) {
88
            if corrupted.contains(&neighbour) {
89
                continue;
90
            }
91
            if seen.insert(neighbour) {
92
                q.push_back((neighbour, cost + 1));
93
            }
94
        }
95
    }
96

97
    None
98
}
99

100
fn part_2(input: &str) -> String {
101
    let falling = parse(input);
102

103
    let start = Point::new(0, 0);
104
    let end = Point::new(ROWS - 1, COLS - 1);
105

106
    let mut low = 0;
107
    let mut high = falling.len() - 1;
108

109
    while low < high {
110
        let mid = (low + high) / 2;
111
        let corrupted: HashSet<&Point> = falling.iter().take(mid + 1).collect();
112
        if search(&corrupted, start, end, ROWS, COLS).is_some() {
113
            low = mid + 1;
114
        } else {
115
            high = mid;
116
        }
117
    }
118

119
    let last = falling[low];
120
    format!("{},{}", last.col, last.row)
121
}

Date

Tagged

Part of series

Older post

Newer post

Advent of Code 2024 Day 18

Day 18: RAM Run

Parsing

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code