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}
aoc/year2016/day17.rs

aoc/year2016/
day17.rs
