aoc/year2019/
day06.rs

1//! # Universal Orbit Map
2//!
3//! Each object name is 3 characters long, using the characters `A` to `Z` and `0` to `9`.
4//! This is only 36 ^ 3 = 46656 possibilities, so we can use
5//! [perfect hashing](https://en.wikipedia.org/wiki/Perfect_hash_function) to store contiguous
6//! indices for each object, allowing us to lookup a perfect *minimal* hash for each object.
7//!
8//! This is twice as fast as using a [`FastMap`] to lookup the indices.
9//!
10//! [`FastMap`]: crate::util::hash
11
12/// Convert 3 character object names to contiguous indices for faster lookup.
13pub fn parse(input: &str) -> Vec<usize> {
14    // Convert 'A'.."Z" and '0'..'9' to a number between 0 and 36.
15    let digit = |b: u8| {
16        if b.is_ascii_digit() { (b - b'0') as usize } else { (10 + b - b'A') as usize }
17    };
18
19    // Hash each 3 character object name.
20    let perfect_hash = |object: &str| -> usize {
21        let bytes = object.as_bytes();
22        digit(bytes[0]) + 36 * digit(bytes[1]) + 1296 * digit(bytes[2])
23    };
24
25    // Pre-seed known indices for objects that we need to specifically lookup later.
26    let mut indices = [0_u16; 36 * 36 * 36];
27    indices[perfect_hash("COM")] = 1;
28    indices[perfect_hash("SAN")] = 2;
29    indices[perfect_hash("YOU")] = 3;
30    let mut current = 4;
31
32    // Assign sequential indices to each object the first time that we encounter it.
33    // 0 is used as a special "empty" value.
34    let mut lookup = |s: &str| {
35        let hash = perfect_hash(s);
36        if indices[hash] == 0 {
37            let previous = current;
38            indices[hash] = current;
39            current += 1;
40            previous as usize
41        } else {
42            indices[hash] as usize
43        }
44    };
45
46    // Build parent-child relationships for each object. Add one extra for the unused 0 special
47    // value and another as there is always one more object than input lines.
48    let lines: Vec<_> = input.lines().collect();
49    let mut parent = vec![0; lines.len() + 2];
50
51    for line in lines {
52        let left = lookup(&line[..3]);
53        let right = lookup(&line[4..]);
54        parent[right] = left;
55    }
56
57    parent
58}
59
60/// Recusively follow parent relationships all the way to the root COM object. Cache each object's
61/// depth in order to avoid unecessary work.
62pub fn part1(input: &[usize]) -> usize {
63    fn orbits(parent: &[usize], cache: &mut [Option<usize>], index: usize) -> usize {
64        if let Some(result) = cache[index] {
65            result
66        } else {
67            let result = 1 + orbits(parent, cache, parent[index]);
68            cache[index] = Some(result);
69            result
70        }
71    }
72
73    let cache = &mut vec![None; input.len()];
74    cache[0] = Some(0);
75    cache[1] = Some(0);
76    (0..input.len()).map(|index| orbits(input, cache, index)).sum()
77}
78
79/// Trace Santa's path all the way to the root COM object keeping track of distance. Then
80/// trace our path to the root. As soon as we encounter a non-zero distance then we've hit
81/// the first common ancestor and can calculate the required transfers.
82pub fn part2(input: &[usize]) -> u16 {
83    let mut distance = vec![0_u16; input.len()];
84    let mut index = 2; // SAN
85    let mut count = 0;
86
87    // COM = 1
88    while index != 1 {
89        distance[index] = count;
90        index = input[index];
91        count += 1;
92    }
93
94    index = 3; // YOU
95    count = 0;
96
97    while distance[index] == 0 {
98        index = input[index];
99        count += 1;
100    }
101
102    distance[index] + count - 2
103}
aoc/year2019/day06.rs

aoc/year2019/
day06.rs
