aoc/year2018/
day13.rs

1//! # Mine Cart Madness
2//!
3//! Simulates the mine carts for both parts. When checking the grid we only care about `\`, `/`
4//! and `+` characters, all other characters can be ignored. Carts are sorted by `y` and then by
5//! `x` before each tick as the movement order is important to resolve collisions or near misses
6//! correctly.
7use crate::util::grid::*;
8use crate::util::point::*;
9
10pub struct Input {
11    grid: Grid<u8>,
12    carts: Vec<Cart>,
13}
14
15#[derive(Clone, Copy)]
16pub struct Cart {
17    position: Point,
18    direction: Point,
19    turns: u8,
20    active: bool,
21}
22
23impl Cart {
24    fn new(position: Point, direction: Point) -> Cart {
25        Cart { position, direction, turns: 0, active: true }
26    }
27
28    fn tick(&mut self, grid: &Grid<u8>) {
29        self.position += self.direction;
30
31        match grid[self.position] {
32            b'\\' => self.direction = Point::new(self.direction.y, self.direction.x),
33            b'/' => self.direction = Point::new(-self.direction.y, -self.direction.x),
34            b'+' => {
35                self.direction = match self.turns {
36                    0 => self.direction.counter_clockwise(),
37                    1 => self.direction,
38                    _ => self.direction.clockwise(), // 2 turns
39                };
40                self.turns = (self.turns + 1) % 3;
41            }
42            _ => (),
43        }
44    }
45}
46
47pub fn parse(input: &str) -> Input {
48    let grid = Grid::parse(input);
49    let mut carts = Vec::new();
50
51    for (i, b) in grid.bytes.iter().enumerate() {
52        let direction = match b {
53            b'^' => UP,
54            b'v' => DOWN,
55            b'<' => LEFT,
56            b'>' => RIGHT,
57            _ => continue,
58        };
59
60        let x = i as i32 % grid.width;
61        let y = i as i32 / grid.width;
62        carts.push(Cart::new(Point::new(x, y), direction));
63    }
64
65    Input { grid, carts }
66}
67
68pub fn part1(input: &Input) -> String {
69    let mut carts = input.carts.clone();
70    let mut occupied = input.grid.same_size_with(false);
71
72    loop {
73        // Turn order is important.
74        carts.sort_unstable_by_key(|c| input.grid.width * c.position.y + c.position.x);
75
76        for cart in &mut carts {
77            // Follow tracks to next position.
78            occupied[cart.position] = false;
79            cart.tick(&input.grid);
80            let next = cart.position;
81
82            if occupied[next] {
83                return format!("{},{}", next.x, next.y);
84            }
85
86            occupied[next] = true;
87        }
88    }
89}
90
91pub fn part2(input: &Input) -> String {
92    let mut carts = input.carts.clone();
93    let mut occupied = input.grid.same_size_with(false);
94
95    while carts.len() > 1 {
96        // Turn order is important.
97        carts.sort_unstable_by_key(|c| input.grid.width * c.position.y + c.position.x);
98
99        for i in 0..carts.len() {
100            // Crashed carts may not have been removed yet.
101            if carts[i].active {
102                // Follow tracks to next position.
103                occupied[carts[i].position] = false;
104                carts[i].tick(&input.grid);
105                let next = carts[i].position;
106
107                if occupied[next] {
108                    // Mark both carts as crashed.
109                    carts.iter_mut().filter(|c| c.position == next).for_each(|c| c.active = false);
110                    occupied[next] = false;
111                } else {
112                    occupied[next] = true;
113                }
114            }
115        }
116
117        // Removed crashed carts to speed up future ticks.
118        carts.retain(|c| c.active);
119    }
120
121    let last = carts[0].position;
122    format!("{},{}", last.x, last.y)
123}
aoc/year2018/day13.rs

aoc/year2018/
day13.rs
