1use crate::util::grid::*;
18use crate::util::hash::*;
19use crate::util::point::*;
20use crate::util::thread::*;
21
22pub fn parse(input: &str) -> Grid<u8> {
23 Grid::parse(input)
24}
25
26pub fn part1(grid: &Grid<u8>) -> usize {
28 let mut grid = grid.clone();
29 let mut position = grid.find(b'^').unwrap();
30 let mut direction = UP;
31 let mut result = 1;
32
33 while grid.contains(position + direction) {
34 if grid[position + direction] == b'#' {
35 direction = direction.clockwise();
36 continue;
37 }
38
39 let next = position + direction;
40
41 if grid[next] == b'.' {
43 result += 1;
44 grid[next] = b'^';
45 }
46
47 position = next;
48 }
49
50 result
51}
52
53pub fn part2(grid: &Grid<u8>) -> usize {
55 let mut grid = grid.clone();
56 let mut position = grid.find(b'^').unwrap();
57 let mut direction = UP;
58 let mut path = Vec::with_capacity(5_000);
59
60 while grid.contains(position + direction) {
61 if grid[position + direction] == b'#' {
62 direction = direction.clockwise();
63 }
64
65 let next = position + direction;
66
67 if grid[next] == b'.' {
69 path.push((position, direction));
70 grid[next] = b'^';
71 }
72
73 position = next;
74 }
75
76 let shortcut = Shortcut::from(&grid);
78 let result = spawn_parallel_iterator(&path, |iter| worker(&shortcut, iter));
79 result.into_iter().sum()
80}
81
82fn worker(shortcut: &Shortcut, iter: ParIter<'_, (Point, Point)>) -> usize {
83 let mut seen = FastSet::new();
84 iter.filter(|&&(position, direction)| {
85 seen.clear();
86 is_cycle(shortcut, &mut seen, position, direction)
87 })
88 .count()
89}
90
91fn is_cycle(
92 shortcut: &Shortcut,
93 seen: &mut FastSet<(Point, Point)>,
94 mut position: Point,
95 mut direction: Point,
96) -> bool {
97 let obstacle = position + direction;
98
99 while shortcut.up.contains(position) {
100 if !seen.insert((position, direction)) {
102 return true;
103 }
104
105 position = match direction {
107 UP => {
108 let next = shortcut.up[position];
109 if position.x == obstacle.x && position.y > obstacle.y && obstacle.y >= next.y {
110 obstacle - UP
111 } else {
112 next
113 }
114 }
115 DOWN => {
116 let next = shortcut.down[position];
117 if position.x == obstacle.x && position.y < obstacle.y && obstacle.y <= next.y {
118 obstacle - DOWN
119 } else {
120 next
121 }
122 }
123 LEFT => {
124 let next = shortcut.left[position];
125 if position.y == obstacle.y && position.x > obstacle.x && obstacle.x >= next.x {
126 obstacle - LEFT
127 } else {
128 next
129 }
130 }
131 RIGHT => {
132 let next = shortcut.right[position];
133 if position.y == obstacle.y && position.x < obstacle.x && obstacle.x <= next.x {
134 obstacle - RIGHT
135 } else {
136 next
137 }
138 }
139 _ => unreachable!(),
140 };
141
142 direction = direction.clockwise();
143 }
144
145 false
146}
147
148struct Shortcut {
149 up: Grid<Point>,
150 down: Grid<Point>,
151 left: Grid<Point>,
152 right: Grid<Point>,
153}
154
155impl Shortcut {
156 fn from(grid: &Grid<u8>) -> Self {
157 let mut up = grid.same_size_with(ORIGIN);
158 let mut down = grid.same_size_with(ORIGIN);
159 let mut left = grid.same_size_with(ORIGIN);
160 let mut right = grid.same_size_with(ORIGIN);
161
162 for x in 0..grid.width {
163 let mut last = Point::new(x, -1);
164
165 for y in 0..grid.height {
166 let point = Point::new(x, y);
167 if grid[point] == b'#' {
168 last = Point::new(x, y + 1);
169 }
170 up[point] = last;
171 }
172 }
173
174 for x in 0..grid.width {
175 let mut last = Point::new(x, grid.height);
176
177 for y in (0..grid.height).rev() {
178 let point = Point::new(x, y);
179 if grid[point] == b'#' {
180 last = Point::new(x, y - 1);
181 }
182 down[point] = last;
183 }
184 }
185
186 for y in 0..grid.height {
187 let mut last = Point::new(-1, y);
188
189 for x in 0..grid.width {
190 let point = Point::new(x, y);
191 if grid[point] == b'#' {
192 last = Point::new(x + 1, y);
193 }
194 left[point] = last;
195 }
196 }
197
198 for y in 0..grid.height {
199 let mut last = Point::new(grid.width, y);
200
201 for x in (0..grid.width).rev() {
202 let point = Point::new(x, y);
203 if grid[point] == b'#' {
204 last = Point::new(x - 1, y);
205 }
206 right[point] = last;
207 }
208 }
209
210 Shortcut { up, down, left, right }
211 }
212}