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: u32,
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'\\' => {
33                self.direction = match self.direction {
34                    UP => LEFT,
35                    DOWN => RIGHT,
36                    LEFT => UP,
37                    RIGHT => DOWN,
38                    _ => unreachable!(),
39                }
40            }
41            b'/' => {
42                self.direction = match self.direction {
43                    UP => RIGHT,
44                    DOWN => LEFT,
45                    LEFT => DOWN,
46                    RIGHT => UP,
47                    _ => unreachable!(),
48                }
49            }
50            b'+' => {
51                self.direction = match self.turns {
52                    0 => self.direction.counter_clockwise(),
53                    1 => self.direction,
54                    2 => self.direction.clockwise(),
55                    _ => unreachable!(),
56                };
57                self.turns = (self.turns + 1) % 3;
58            }
59            _ => (),
60        }
61    }
62}
63
64pub fn parse(input: &str) -> Input {
65    let grid = Grid::parse(input);
66    let mut carts = Vec::new();
67
68    for (i, b) in grid.bytes.iter().enumerate() {
69        let result = match b {
70            b'^' => Some(UP),
71            b'v' => Some(DOWN),
72            b'<' => Some(LEFT),
73            b'>' => Some(RIGHT),
74            _ => None,
75        };
76
77        if let Some(direction) = result {
78            let x = i as i32 % grid.width;
79            let y = i as i32 / grid.width;
80            carts.push(Cart::new(Point::new(x, y), direction));
81        }
82    }
83
84    Input { grid, carts }
85}
86
87pub fn part1(input: &Input) -> String {
88    let mut carts = input.carts.clone();
89    let mut occupied = input.grid.same_size_with(false);
90
91    loop {
92        // Turn order is important.
93        carts.sort_unstable_by_key(|c| input.grid.width * c.position.y + c.position.x);
94
95        for cart in &mut carts {
96            // Follow tracks to next position.
97            occupied[cart.position] = false;
98            cart.tick(&input.grid);
99            let next = cart.position;
100
101            if occupied[next] {
102                return format!("{},{}", next.x, next.y);
103            }
104
105            occupied[next] = true;
106        }
107    }
108}
109
110pub fn part2(input: &Input) -> String {
111    let mut carts = input.carts.clone();
112    let mut occupied = input.grid.same_size_with(false);
113
114    while carts.len() > 1 {
115        // Turn order is important.
116        carts.sort_unstable_by_key(|c| input.grid.width * c.position.y + c.position.x);
117
118        for i in 0..carts.len() {
119            // Crashed carts may not have been removed yet.
120            if carts[i].active {
121                // Follow tracks to next position.
122                occupied[carts[i].position] = false;
123                carts[i].tick(&input.grid);
124                let next = carts[i].position;
125
126                if occupied[next] {
127                    // Mark both carts as crashed.
128                    carts.iter_mut().filter(|c| c.position == next).for_each(|c| c.active = false);
129                    occupied[next] = false;
130                } else {
131                    occupied[next] = true;
132                }
133            }
134        }
135
136        // Removed crashed carts to speed up future ticks.
137        carts.retain(|c| c.active);
138    }
139
140    let last = carts[0].position;
141    format!("{},{}", last.x, last.y)
142}
aoc/year2018/day13.rs

aoc/year2018/
day13.rs
