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

aoc/year2016/
day17.rs
