aoc/year2016/day17.rs
1//! # Two Steps Forward
2//!
3//! Brute force search over every possible path. Work is parallelized over multiple threads.
4//! Keeping each thread busy and spreading the work as evenly as possible is quite tricky. Some
5//! paths can dead-end quickly while others can take the majority of exploration time.
6//!
7//! To solve this we implement a very simple version of work sharing. Threads process paths locally
8//! stopping every now and then to return paths to a global queue. This allows other threads that
9//! have run out of work to pickup new paths to process.
10//!
11//! The approach from "Waiting: Parking and Condition Variables" in the excellent book
12//! [Rust Atomics and Locks](https://marabos.nl/atomics/) prevent idle threads from busy
13//! looping on the mutex.
14use crate::util::md5::*;
15use crate::util::thread::*;
16use std::sync::{Condvar, Mutex};
17
18type Input = (Vec<u8>, usize);
19type Item = (u8, u8, usize, Vec<u8>);
20
21struct State {
22 todo: Vec<Item>,
23 min: Vec<u8>,
24 max: usize,
25 inflight: usize,
26}
27
28struct Shared {
29 prefix: usize,
30 mutex: Mutex<State>,
31 not_empty: Condvar,
32}
33
34pub fn parse(input: &str) -> Input {
35 // Initial starting position is the top left corner.
36 let input = input.trim().as_bytes();
37 let prefix = input.len();
38 let start = (0, 0, prefix, extend(input, prefix, 0));
39
40 // State shared between threads.
41 let state = State { todo: vec![start], min: vec![], max: 0, inflight: threads() };
42 let shared = Shared { prefix, mutex: Mutex::new(state), not_empty: Condvar::new() };
43
44 // Search paths in parallel.
45 spawn(|| worker(&shared));
46
47 let state = shared.mutex.into_inner().unwrap();
48 (state.min, state.max)
49}
50
51pub fn part1(input: &Input) -> &str {
52 str::from_utf8(&input.0).unwrap()
53}
54
55pub fn part2(input: &Input) -> usize {
56 input.1
57}
58
59/// Process local work items, stopping every now and then to redistribute items back to global pool.
60/// This prevents threads idling or hotspotting.
61fn worker(shared: &Shared) {
62 let mut local = State { todo: vec![], min: vec![], max: 0, inflight: 0 };
63
64 loop {
65 // Process local work items.
66 explore(shared, &mut local);
67
68 // Acquire mutex.
69 let mut state = shared.mutex.lock().unwrap();
70
71 // Update min and max paths.
72 if state.min.is_empty() || local.min.len() < state.min.len() {
73 state.min.clone_from(&local.min);
74 }
75 state.max = state.max.max(local.max);
76
77 if local.todo.is_empty() {
78 // Mark ourselves as idle then notify all other threads in case we're done.
79 state.inflight -= 1;
80 shared.not_empty.notify_all();
81
82 loop {
83 // Pickup available work.
84 if let Some(item) = state.todo.pop() {
85 state.inflight += 1;
86 local.todo.push(item);
87 break;
88 }
89 // If no work available and no other thread is doing anything, then we're done.
90 if state.inflight == 0 {
91 return;
92 }
93 // Put thread to sleep until another thread notifies us that work is available.
94 // This avoids busy looping on the mutex.
95 state = shared.not_empty.wait(state).unwrap();
96 }
97 } else {
98 // Redistribute excess local work items back to the global queue then notify all other
99 // threads that there is new work available.
100 state.todo.extend(local.todo.drain(1..));
101 shared.not_empty.notify_all();
102 }
103 }
104}
105
106/// Explore at most 100 paths, stopping sooner if we run out.
107/// 100 is chosen empirically as the amount that results in the least total time taken.
108///
109/// Too low and threads waste time locking the mutex, reading and writing global state.
110/// Too high and some threads are starved with no paths, while other threads do all the work.
111fn explore(shared: &Shared, local: &mut State) {
112 for _ in 0..100 {
113 let Some((x, y, size, mut path)) = local.todo.pop() else { break };
114
115 if x == 3 && y == 3 {
116 // Stop if we've reached the bottom right room.
117 let adjusted = size - shared.prefix;
118 if local.min.is_empty() || adjusted < local.min.len() {
119 // Remove salt and padding.
120 local.min = path[shared.prefix..size].to_vec();
121 }
122 local.max = local.max.max(adjusted);
123 } else {
124 // Explore other paths.
125 let [result, ..] = hash(&mut path, size);
126
127 if y > 0 && is_open(result, 28) {
128 local.todo.push((x, y - 1, size + 1, extend(&path, size, b'U')));
129 }
130 if y < 3 && is_open(result, 24) {
131 local.todo.push((x, y + 1, size + 1, extend(&path, size, b'D')));
132 }
133 if x > 0 && is_open(result, 20) {
134 local.todo.push((x - 1, y, size + 1, extend(&path, size, b'L')));
135 }
136 if x < 3 && is_open(result, 16) {
137 local.todo.push((x + 1, y, size + 1, extend(&path, size, b'R')));
138 }
139 }
140 }
141}
142
143/// Check if a door is open based on MD5 hex digit (b-f means open).
144#[inline]
145fn is_open(hash: u32, shift: u32) -> bool {
146 ((hash >> shift) & 0xf) > 0xa
147}
148
149/// Convenience function to generate new path.
150fn extend(src: &[u8], size: usize, b: u8) -> Vec<u8> {
151 // Leave room for MD5 padding.
152 let mut next = vec![0; buffer_size(size + 1)];
153 // Copy existing path and next step.
154 next[..size].copy_from_slice(&src[..size]);
155 next[size] = b;
156 next
157}