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

aoc/year2019/
day06.rs
