aoc/year2018/
day13.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
//! # Mine Cart Madness
//!
//! Simulates the mine carts for both parts. When checking the grid we only care about `\`, `/`
//! and `+` characters, all other characters can be ignored. Carts are sorted by `y` and then by
//! `x` before each tick as the movement order is important to resolve collisions or near misses
//! correctly.
use crate::util::grid::*;
use crate::util::point::*;

pub struct Input {
    grid: Grid<u8>,
    carts: Vec<Cart>,
}

#[derive(Clone, Copy)]
pub struct Cart {
    position: Point,
    direction: Point,
    turns: u32,
    active: bool,
}

impl Cart {
    fn new(position: Point, direction: Point) -> Cart {
        Cart { position, direction, turns: 0, active: true }
    }

    fn tick(&mut self, grid: &Grid<u8>) {
        self.position += self.direction;

        match grid[self.position] {
            b'\\' => {
                self.direction = match self.direction {
                    UP => LEFT,
                    DOWN => RIGHT,
                    LEFT => UP,
                    RIGHT => DOWN,
                    _ => unreachable!(),
                }
            }
            b'/' => {
                self.direction = match self.direction {
                    UP => RIGHT,
                    DOWN => LEFT,
                    LEFT => DOWN,
                    RIGHT => UP,
                    _ => unreachable!(),
                }
            }
            b'+' => {
                self.direction = match self.turns {
                    0 => self.direction.counter_clockwise(),
                    1 => self.direction,
                    2 => self.direction.clockwise(),
                    _ => unreachable!(),
                };
                self.turns = (self.turns + 1) % 3;
            }
            _ => (),
        }
    }
}

pub fn parse(input: &str) -> Input {
    let grid = Grid::parse(input);
    let mut carts = Vec::new();

    for (i, b) in grid.bytes.iter().enumerate() {
        let result = match b {
            b'^' => Some(UP),
            b'v' => Some(DOWN),
            b'<' => Some(LEFT),
            b'>' => Some(RIGHT),
            _ => None,
        };

        if let Some(direction) = result {
            let x = i as i32 % grid.width;
            let y = i as i32 / grid.width;
            carts.push(Cart::new(Point::new(x, y), direction));
        }
    }

    Input { grid, carts }
}

pub fn part1(input: &Input) -> String {
    let mut carts = input.carts.clone();
    let mut occupied = input.grid.same_size_with(false);

    loop {
        // Turn order is important.
        carts.sort_unstable_by_key(|c| input.grid.width * c.position.y + c.position.x);

        for cart in &mut carts {
            // Follow tracks to next position.
            occupied[cart.position] = false;
            cart.tick(&input.grid);
            let next = cart.position;

            if occupied[next] {
                return format!("{},{}", next.x, next.y);
            }

            occupied[next] = true;
        }
    }
}

pub fn part2(input: &Input) -> String {
    let mut carts = input.carts.clone();
    let mut occupied = input.grid.same_size_with(false);

    while carts.len() > 1 {
        // Turn order is important.
        carts.sort_unstable_by_key(|c| input.grid.width * c.position.y + c.position.x);

        for i in 0..carts.len() {
            // Crashed carts may not have been removed yet.
            if carts[i].active {
                // Follow tracks to next position.
                occupied[carts[i].position] = false;
                carts[i].tick(&input.grid);
                let next = carts[i].position;

                if occupied[next] {
                    // Mark both carts as crashed.
                    carts.iter_mut().filter(|c| c.position == next).for_each(|c| c.active = false);
                    occupied[next] = false;
                } else {
                    occupied[next] = true;
                }
            }
        }

        // Removed crashed carts to speed up future ticks.
        carts.retain(|c| c.active);
    }

    let last = carts[0].position;
    format!("{},{}", last.x, last.y)
}