Module day06

Universal Orbit Map

Each object name is 3 characters long, using the characters A to Z and 0 to 9. This is only 36 ^ 3 = 46656 possibilities, so we can use perfect hashing to store contiguous indices for each object, allowing us to lookup a perfect minimal hash for each object.

This is twice as fast as using a FastMap to lookup the indices.

Functions

parse

Convert 3 character object names to contiguous indices for faster lookup.

part1

Recusively follow parent relationships all the way to the root COM object. Cache each object’s depth in order to avoid unecessary work.

part2

Trace Santa’s path all the way to the root COM object keeping track of distance. Then trace our path to the root. As soon as we encounter a non-zero distance then we’ve hit the first common ancestor and can calculate the required transfers.