Module aoc::year2019::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.