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

aoc/year2016/
day17.rs
