year2018/
day13.rs

1use utils::geometry::{Direction, Turn};
2use utils::grid;
3use utils::prelude::*;
4
5/// Simulating mine carts on intersecting tracks.
6#[derive(Clone, Debug)]
7pub struct Day13 {
8    grid: Vec<u8>,
9    carts: Vec<Cart>,
10    cols: usize,
11    offsets: [isize; 4],
12}
13
14#[derive(Clone, Debug, PartialEq, Eq, Hash)]
15struct Cart {
16    location: usize,
17    direction: Direction,
18    next_turn: Turn,
19    crashed: bool,
20}
21
22impl Day13 {
23    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
24        let mut carts = Vec::new();
25
26        let (_, cols, grid) = grid::parse(
27            input,
28            1,
29            0,
30            |b| b,
31            |b| matches!(b, b'|' | b'-' | b'/' | b'\\' | b'+' | b' '),
32            |location, b| {
33                let (track, direction) = match b {
34                    b'^' => (b'|', Direction::Up),
35                    b'v' => (b'|', Direction::Down),
36                    b'<' => (b'-', Direction::Left),
37                    b'>' => (b'-', Direction::Right),
38                    _ => {
39                        return Err(
40                            "expected track ('|', '-', '/', '\\', '+'), cart ('^', 'v', '<', '>') or ' '",
41                        );
42                    }
43                };
44                carts.push(Cart {
45                    location,
46                    direction,
47                    next_turn: Turn::Left,
48                    crashed: false,
49                });
50                Ok(track)
51            },
52        )?;
53
54        Ok(Self {
55            grid,
56            carts,
57            cols,
58            offsets: [-(cols as isize), 1, cols as isize, -1],
59        })
60    }
61
62    #[must_use]
63    pub fn part1(&self) -> String {
64        let mut carts = self.carts.clone();
65
66        let mut bitset = vec![0u64; self.grid.len().div_ceil(64)];
67        for cart in &carts {
68            bitset[cart.location / 64] |= 1 << (cart.location % 64);
69        }
70
71        loop {
72            carts.sort_unstable_by_key(|cart| cart.location);
73
74            for cart in &mut carts {
75                bitset[cart.location / 64] &= !(1 << (cart.location % 64));
76
77                self.move_cart(cart);
78
79                if bitset[cart.location / 64] & (1 << (cart.location % 64)) != 0 {
80                    return self.coordinates_str(cart.location);
81                }
82
83                bitset[cart.location / 64] |= 1 << (cart.location % 64);
84            }
85        }
86    }
87
88    #[must_use]
89    pub fn part2(&self) -> String {
90        assert!(
91            !self.carts.len().is_multiple_of(2),
92            "no solution found: part 2 requires an odd number of carts"
93        );
94
95        let mut carts = self.carts.clone();
96
97        let mut bitset = vec![0u64; self.grid.len().div_ceil(64)];
98        for cart in &carts {
99            bitset[cart.location / 64] |= 1 << (cart.location % 64);
100        }
101
102        while carts.len() > 1 {
103            carts.sort_unstable_by_key(|cart| cart.location);
104
105            for i in 0..carts.len() {
106                if carts[i].crashed {
107                    continue;
108                }
109
110                let old_loc = carts[i].location;
111                bitset[old_loc / 64] &= !(1 << (old_loc % 64));
112
113                self.move_cart(&mut carts[i]);
114                let new_loc = carts[i].location;
115
116                if bitset[new_loc / 64] & (1 << (new_loc % 64)) != 0 {
117                    for cart in carts.iter_mut() {
118                        cart.crashed |= cart.location == new_loc;
119                    }
120
121                    bitset[new_loc / 64] &= !(1 << (new_loc % 64));
122                } else {
123                    bitset[new_loc / 64] |= 1 << (new_loc % 64);
124                }
125            }
126
127            carts.retain(|cart| !cart.crashed);
128        }
129        self.coordinates_str(carts[0].location)
130    }
131
132    #[inline]
133    fn move_cart(&self, cart: &mut Cart) {
134        cart.location = cart
135            .location
136            .wrapping_add_signed(self.offsets[cart.direction as usize]);
137
138        let track = self.grid[cart.location];
139        match track {
140            b'/' => {
141                cart.direction = match cart.direction {
142                    Direction::Up => Direction::Right,
143                    Direction::Right => Direction::Up,
144                    Direction::Down => Direction::Left,
145                    Direction::Left => Direction::Down,
146                };
147            }
148            b'\\' => {
149                cart.direction = match cart.direction {
150                    Direction::Up => Direction::Left,
151                    Direction::Left => Direction::Up,
152                    Direction::Right => Direction::Down,
153                    Direction::Down => Direction::Right,
154                };
155            }
156            b'+' => {
157                cart.direction = cart.direction.turn(cart.next_turn);
158
159                cart.next_turn = match cart.next_turn {
160                    Turn::Left => Turn::None,
161                    Turn::None => Turn::Right,
162                    Turn::Right => Turn::Left,
163                };
164            }
165            b'|' | b'-' => {}
166            b' ' | 0 => panic!("no solution found: a cart left the track"),
167            _ => unreachable!(),
168        }
169    }
170
171    fn coordinates_str(&self, location: usize) -> String {
172        format!(
173            "{},{}",
174            (location % self.cols) - 1,
175            (location / self.cols) - 1
176        )
177    }
178}
179
180examples!(Day13 -> (&'static str, &'static str) [
181    {
182        input: "/->-\\        \n|   |  /----\\\n| /-+--+-\\  |\n| | |  | v  |\n\\-+-/  \\-+--/\n  \\------/   ",
183        part1: "7,3",
184    },
185    {
186        input: "/>-<\\  \n|   |  \n| /<+-\\\n| | | v\n\\>+</ |\n  |   ^\n  \\<->/",
187        part2: "6,4",
188    },
189]);
year2018/day13.rs

year2018/
day13.rs
