Advent of Code 2024 Day 14

Day 14: Restroom Redoubt

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

You are in the lobby of Easter Bunny HQ. There are a bunch of robots running around.

Today’s input is a list of all robots, it lists:

Their initial position
The change to their position each time they move.

An example input looks like this:

p=0,4 v=3,-3
p=6,3 v=-1,-3
p=10,3 v=-1,2
p=2,0 v=2,-1
p=0,0 v=1,3
p=3,0 v=-2,-2
p=7,6 v=-1,-3
p=3,0 v=-1,-2
p=9,3 v=2,3
p=7,3 v=-1,2
p=2,4 v=2,-3
p=9,5 v=-3,-3

Each line represents 1 robot, the position and velocity are 2 number pairs. A robot only ever moves along a straight line, in other words, each step it takes, add the velocity to its position.

The first number is the column index
The second number is the row index

The area the robots move in is:

101 tiles wide
103 tiles tall

The robots have a special property, they wrap around the area they move in. That means:

if they go off the top, they continue from the bottom
if they go off the bottom, they continue from the top
if they go off the left, they continue from the right
if they go off the right, they continue from the left For an example, the problem description has a good one.

Parsing

If you’ve been following along, you know what I do when I see a puzzle with coordinates by now, Point! And today, I expanded that with a Robot struct. You guessed it, that holds TWO Points.

Data structures

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

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

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Robot {
    pos: Point,
    vel: Point,
}

impl Robot {
    fn new(p_row: i64, p_col: i64, v_row: i64, v_col: i64) -> Self {
        Self {
            pos: Point::new(p_row, p_col),
            vel: Point::new(v_row, v_col),
        }
    }
}

Turning the input into a list of Robots:

fn parse(input: &str) -> Vec<Robot> {
    let mut robots = Vec::new();
    for line in input.lines() {
        let mut nums = Vec::new();
        for num in line
            .split(|c: char| !c.is_ascii_digit() && c != '-')
            .filter(|s| !s.is_empty())
        {
            let num: i64 = num.parse().unwrap();
            nums.push(num);
        }
        // attention! because x is col and y is row this order might not be what you expect!
        let robot = Robot::new(nums[1], nums[0], nums[3], nums[2]);
        robots.push(robot);
    }
    robots
}

Part 1

The question asks for the safety score after 100 steps.

To calculate a safety score for an arrangement of robots, count the amount of bots in each quadrant. Robots that are in the exact middle row or column don’t count towards the safety score.

The safety score is the product of the amount of robots in each quadrant.

Helpers

A function that takes in a list of robots, and calculates the safety score. Paying attention to the global values for the amount of rows and columns in the area.

const ROWS: i64 = 103;
const COLS: i64 = 101;
fn safety(robots: &[Robot]) -> usize {
    let mut sectors = [0; 4];
    let col_mid = COLS / 2;
    let row_mid = ROWS / 2;
    for &Robot { pos, .. } in robots {
        if pos.row == row_mid || pos.col == col_mid {
            continue;
        }
        let top = pos.row < row_mid;
        let left = pos.col < col_mid;
        match (top, left) {
            (true, true) => sectors[0] += 1,
            (true, false) => sectors[1] += 1,
            (false, true) => sectors[2] += 1,
            (false, false) => sectors[3] += 1,
        }
    }
    sectors.iter().product()
}

Code

Move the robots 100 steps and calculate the safety score. Because of a math property, I didn’t loop 100 times and moved each robot once per step. I moved them 100 steps at once.

pub fn part_1(input: &str) -> usize {
    let mut robots = parse(input);
    for Robot { pos, vel } in &mut robots {
        pos.row = (pos.row + vel.row * 100).rem_euclid(ROWS);
        pos.col = (pos.col + vel.col * 100).rem_euclid(COLS);
    }
    safety(&robots)
}

Part 2

The robots have an easter egg, at some point, they form a christms tree.

There are many ways to verify this, the most straightforward, and the one I initially did, is to print out the arrangement of robots repeatedly.

With the help of others, it turn out that the first time all robots occupy a unique position is the iteration the christmas tree is shown.

So I looped infinitely and broke the loop the first time no 2 robots occupy the same location.

use itertools::Itertools;

fn part_2(input: &str) -> usize {
    let mut robots = parse(input);
    for i in 0.. {
        for Robot { pos, vel } in &mut robots {
            pos.row = (pos.row + vel.row).rem_euclid(ROWS);
            pos.col = (pos.col + vel.col).rem_euclid(COLS);
        }
        if robots.iter().map(|robot| robot.pos).all_unique() {
            return i + 1;
        }
    }
    panic!("No tree");
}

Final code

1
use itertools::Itertools;
2

3
#[derive(PartialEq, Eq, Hash, Clone, Copy)]
4
struct Point {
5
    row: i64,
6
    col: i64,
7
}
8

9
impl Point {
10
    fn new(row: i64, col: i64) -> Self {
11
        Self { row, col }
12
    }
13
}
14

15
#[derive(PartialEq, Eq, Hash, Clone, Copy)]
16
struct Robot {
17
    pos: Point,
18
    vel: Point,
19
}
20

21
impl Robot {
22
    fn new(p_row: i64, p_col: i64, v_row: i64, v_col: i64) -> Self {
23
        Self {
24
            pos: Point::new(p_row, p_col),
25
            vel: Point::new(v_row, v_col),
26
        }
27
    }
28
}
29

30
const ROWS: i64 = 103;
31
const COLS: i64 = 101;
32
fn parse(input: &str) -> Vec<Robot> {
33
    let mut robots = Vec::new();
34
    for line in input.lines() {
35
        let mut nums = Vec::new();
36
        for num in line
37
            .split(|c: char| !c.is_ascii_digit() && c != '-')
38
            .filter(|s| !s.is_empty())
39
        {
40
            let num: i64 = num.parse().unwrap();
41
            nums.push(num);
42
        }
43
        // attention! because x is col and y is row this order might not be what you expect!
44
        let robot = Robot::new(nums[1], nums[0], nums[3], nums[2]);
45
        robots.push(robot);
46
    }
47
    robots
48
}
49

50
fn safety(robots: &[Robot]) -> usize {
51
    let mut sectors = [0; 4];
52
    let col_mid = COLS / 2;
53
    let row_mid = ROWS / 2;
54
    for &Robot { pos, .. } in robots {
55
        if pos.row == row_mid || pos.col == col_mid {
56
            continue;
57
        }
58
        let top = pos.row < row_mid;
59
        let left = pos.col < col_mid;
60
        match (top, left) {
61
            (true, true) => sectors[0] += 1,
62
            (true, false) => sectors[1] += 1,
63
            (false, true) => sectors[2] += 1,
64
            (false, false) => sectors[3] += 1,
65
        }
66
    }
67
    sectors.iter().product()
68
}
69

70
pub fn part_1(input: &str) -> usize {
71
    let mut robots = parse(input);
72
    for Robot { pos, vel } in &mut robots {
73
        pos.row = (pos.row + vel.row * 100).rem_euclid(ROWS);
74
        pos.col = (pos.col + vel.col * 100).rem_euclid(COLS);
75
    }
76
    safety(&robots)
77
}
78

79
pub fn part_2(input: &str) -> usize {
80
    let mut robots = parse(input);
81
    for i in 0.. {
82
        for Robot { pos, vel } in &mut robots {
83
            pos.row = (pos.row + vel.row).rem_euclid(ROWS);
84
            pos.col = (pos.col + vel.col).rem_euclid(COLS);
85
        }
86
        if robots.iter().map(|robot| robot.pos).all_unique() {
87
            return i + 1;
88
        }
89
    }
90
    panic!("No tree");
91
}

Date

Tagged

Part of series

Older post

Newer post