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³ = 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            indices[hash] = current;
38            current += 1;
39        }
40        indices[hash] as usize
41    };
42
43    // Build parent-child relationships for each object. Add one extra for the unused 0 special
44    // value and another as there is always one more object than input lines.
45    let lines: Vec<_> = input.lines().collect();
46    let mut parent = vec![0; lines.len() + 2];
47
48    for line in lines {
49        let left = lookup(&line[0..3]);
50        let right = lookup(&line[4..7]);
51        parent[right] = left;
52    }
53
54    parent
55}
56
57/// Recursively follow parent relationships all the way to the root COM object. Cache each object's
58/// depth in order to avoid unnecessary work.
59pub fn part1(input: &[usize]) -> usize {
60    fn orbits(parent: &[usize], cache: &mut [Option<usize>], index: usize) -> usize {
61        if let Some(result) = cache[index] {
62            result
63        } else {
64            let result = 1 + orbits(parent, cache, parent[index]);
65            cache[index] = Some(result);
66            result
67        }
68    }
69
70    let cache = &mut vec![None; input.len()];
71    cache[0] = Some(0); // Special empty value
72    cache[1] = Some(0); // COM
73    (0..input.len()).map(|index| orbits(input, cache, index)).sum()
74}
75
76/// Trace Santa's path all the way to the root COM object keeping track of distance. Then
77/// trace our path to the root. As soon as we encounter a non-zero distance then we've hit
78/// the first common ancestor and can calculate the required transfers.
79pub fn part2(input: &[usize]) -> u16 {
80    let mut distance = vec![0_u16; input.len()];
81    let mut index = 2; // SAN
82    let mut count = 0;
83
84    // COM = 1
85    while index != 1 {
86        distance[index] = count;
87        index = input[index];
88        count += 1;
89    }
90
91    index = 3; // YOU
92    count = 0;
93
94    while distance[index] == 0 {
95        index = input[index];
96        count += 1;
97    }
98
99    distance[index] + count - 2
100}
aoc/year2019/day06.rs

aoc/year2019/
day06.rs
