year2016/
day17.rs

1use utils::md5;
2use utils::prelude::*;
3
4/// Finding the shortest and longest path in a MD5 maze.
5#[derive(Clone, Debug)]
6pub struct Day17 {
7    part1: String,
8    part2: u32,
9}
10
11impl Day17 {
12    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
13        let mut path = input.as_bytes().to_vec();
14        let mut shortest = Vec::new();
15        let mut longest = 0;
16        Self::find_paths(0, 0, &mut path, input.len(), &mut shortest, &mut longest);
17
18        Ok(Self {
19            part1: String::from_utf8(shortest).unwrap(),
20            part2: longest,
21        })
22    }
23
24    fn find_paths(
25        x: u32,
26        y: u32,
27        path: &mut Vec<u8>,
28        prefix_len: usize,
29        shortest_path: &mut Vec<u8>,
30        longest_path: &mut u32,
31    ) {
32        if x == 3 && y == 3 {
33            let path_len = path.len() - prefix_len;
34            if shortest_path.is_empty() || path_len < shortest_path.len() {
35                shortest_path.clear();
36                shortest_path.extend_from_slice(&path[prefix_len..]);
37            }
38            if path_len as u32 > *longest_path {
39                *longest_path = path_len as u32;
40            }
41            return;
42        }
43
44        let [first_u32, ..] = md5::hash(path);
45        if y > 0 && (first_u32 >> 28) & 0xF > 0xA {
46            path.push(b'U');
47            Self::find_paths(x, y - 1, path, prefix_len, shortest_path, longest_path);
48            path.pop();
49        }
50        if y < 3 && (first_u32 >> 24) & 0xF > 0xA {
51            path.push(b'D');
52            Self::find_paths(x, y + 1, path, prefix_len, shortest_path, longest_path);
53            path.pop();
54        }
55        if x > 0 && (first_u32 >> 20) & 0xF > 0xA {
56            path.push(b'L');
57            Self::find_paths(x - 1, y, path, prefix_len, shortest_path, longest_path);
58            path.pop();
59        }
60        if x < 3 && (first_u32 >> 16) & 0xF > 0xA {
61            path.push(b'R');
62            Self::find_paths(x + 1, y, path, prefix_len, shortest_path, longest_path);
63            path.pop();
64        }
65    }
66
67    #[must_use]
68    pub fn part1(&self) -> &str {
69        &self.part1
70    }
71
72    #[must_use]
73    pub fn part2(&self) -> u32 {
74        self.part2
75    }
76}
77
78examples!(Day17 -> (&'static str, u32) [
79    {
80        input: "ihgpwlah",
81        part1: "DDRRRD",
82        part2: 370,
83    },
84    {
85        input: "kglvqrro",
86        part1: "DDUDRLRRUDRD",
87        part2: 492,
88    },
89    {
90        input: "ulqzkmiv",
91        part1: "DRURDRUDDLLDLUURRDULRLDUUDDDRR",
92        part2: 830,
93    },
94]);
year2016/day17.rs

year2016/
day17.rs
