codetrotter_aoc_2019_solutions 0.9.0

/*
 * Copyright (c) 2020 Erik Nordstrøm <erik@nordstroem.no>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

use std::collections::HashMap;

solution_printer!(6, print_solution, input_generator, INPUT, solve_part_1, solve_part_2);

pub const INPUT: &str = include_str!("../input/2019/day6.txt");

/// ### Day 6: Universal Orbit Map
///
/// [https://adventofcode.com/2019/day/6](https://adventofcode.com/2019/day/6)
///
/// You've landed at the Universal Orbit Map facility on Mercury.  Because
/// navigation in space often involves transferring between orbits, the orbit
/// maps here are useful for finding efficient routes between, for example, you
/// and Santa. You download a map of the local orbits (your puzzle input).
///
/// Except for the universal Center of Mass (`COM`), every object in space is in
/// orbit around exactly one other object.  An [orbit](https://en.wikipedia.org/wiki/Orbit) looks roughly like this:
///
/// ```text
///                   \
///                    \
///                     |
///                     |
/// AAA--> o            o <--BBB
///                     |
///                     |
///                    /
///                   /
/// ```
///
/// In this diagram, the object `BBB` is in orbit around `AAA`. The path that `BBB`
/// takes around `AAA` (drawn with lines) is only partly shown. In the map data,
/// this orbital relationship is written `AAA)BBB`, which means "`BBB` is in orbit
/// around `AAA`".
///
/// Before you use your map data to plot a course, you need to make sure it
/// wasn't corrupted during the download.  To verify maps, the Universal Orbit
/// Map facility uses *orbit count checksums* - the total number of *direct orbits*
/// (like the one shown above) and *indirect orbits*.
///
/// Whenever `A` orbits `B` and `B` orbits `C`, then `A` *indirectly orbits* `C`.  This chain
/// can be any number of objects long: if `A` orbits `B`, `B` orbits `C`, and `C` orbits
/// `D`, then `A` indirectly orbits `D`.
///
/// For example, suppose you have the following map:
///
/// ```text
/// COM)B
/// B)C
/// C)D
/// D)E
/// E)F
/// B)G
/// G)H
/// D)I
/// E)J
/// J)K
/// K)L
/// ```
///
/// Visually, the above map of orbits looks like this:
///
/// ```text
///         G - H       J - K - L
///        /           /
/// COM - B - C - D - E - F
///                \
///                 I
/// ```
///
/// In this visual representation, when two objects are connected by a line,
/// the one on the right directly orbits the one on the left.
///
/// Here, we can count the total number of orbits as follows:
///
///   - `D` directly orbits `C` and indirectly orbits `B` and `COM`, a total of `3`
///     orbits.
///   - `L` directly orbits `K` and indirectly orbits `J`, `E`, `D`, `C`, `B`, and `COM`, a
///     total of `7` orbits.
///   - `COM` orbits nothing.
///
/// The total number of direct and indirect orbits in this example is `42`.
///
/// *What is the total number of direct and indirect orbits* in your map data?
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_06::{input_generator, solve_part_1};
///
/// const EXINPUT: &str =
///   "COM)B\n\
///    B)C\n\
///    C)D\n\
///    D)E\n\
///    E)F\n\
///    B)G\n\
///    G)H\n\
///    D)I\n\
///    E)J\n\
///    J)K\n\
///    K)L";
///
/// assert_eq!(solve_part_1(&mut input_generator(EXINPUT)), 42);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_06::{INPUT, input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&mut input_generator(INPUT)), 333679);
/// ```
pub fn solve_part_1<'a, T> (input_orbit_pairs: &mut T) -> u32
  where T: Iterator<Item = OrbitPair<'a>>
{
  let orbits = orbits_from_orbit_pairs(input_orbit_pairs);
  get_total_number_of_orbits_direct_and_indirect(&orbits, "COM", 0)
}

fn get_total_number_of_orbits_direct_and_indirect (orbits: &Orbits, body: &str, num_others_orbited_by_body: u32) -> u32
{
  match orbits.get(body)
  {
    None => num_others_orbited_by_body,
    Some(orbiters) =>
    {
      num_others_orbited_by_body + orbiters.iter().map(|&orbiter|
        get_total_number_of_orbits_direct_and_indirect(orbits, orbiter, num_others_orbited_by_body + 1)).sum::<u32>()
    },
  }
}

pub type OrbitPair<'a> = (&'a str, &'a str);
pub type Orbits<'a> = HashMap<&'a str, Vec<&'a str>>;
pub type Orbiting<'a> = HashMap<&'a str, &'a str>;

pub fn orbits_from_orbit_pairs<'a, T> (orbit_pairs: &mut T) -> Orbits<'a>
  where T: Iterator<Item = OrbitPair<'a>>
{
  let mut orbits = Orbits::new();
  for (orbited, orbiter) in orbit_pairs
  {
    let orbiters = orbits.entry(orbited).or_insert(Default::default());
    orbiters.push(orbiter);
  }
  orbits
}

pub fn input_generator (input: &'static str) -> impl Iterator<Item = OrbitPair>
{
  input.lines().map(|orbit_pair_str|
  {
    let (orbited, remain) = orbit_pair_str.split_at(orbit_pair_str.find(")").unwrap());
    let orbiter = &remain[1..];
    (orbited, orbiter)
  })
}

/// ### Day 6, Part Two
///
/// [https://adventofcode.com/2019/day/6#part2](https://adventofcode.com/2019/day/6#part2)
///
/// Now, you just need to figure out how many *orbital transfers* you (`YOU`) need
/// to take to get to Santa (`SAN`).
///
/// You start at the object `YOU` are orbiting; your destination is the object
/// `SAN` is orbiting. An orbital transfer lets you move from any object to an
/// object orbiting or orbited by that object.
///
/// For example, suppose you have the following map:
///
/// ```text
/// COM)B
/// B)C
/// C)D
/// D)E
/// E)F
/// B)G
/// G)H
/// D)I
/// E)J
/// J)K
/// K)L
/// K)YOU
/// I)SAN
/// ```
///
/// Visually, the above map of orbits looks like this:
///
/// ```text
///                           YOU
///                          /
///         G - H       J - K - L
///        /           /
/// COM - B - C - D - E - F
///                \
///                 I - SAN
/// ```
///
/// In this example, `YOU` are in orbit around `K`, and `SAN` is in orbit around `I`.
/// To move from `K` to `I`, a minimum of `4` orbital transfers are required:
///
///   - `K` to `J`
///   - `J` to `E`
///   - `E` to `D`
///   - `D` to `I`
///
/// Afterward, the map of orbits looks like this:
///
/// ```text
///         G - H       J - K - L
///        /           /
/// COM - B - C - D - E - F
///                \
///                 I - SAN
///                  \
///                   YOU
/// ```
///
/// *What is the minimum number of orbital transfers required* to move from the
/// object `YOU` are orbiting to the object `SAN` is orbiting? (Between the objects
/// they are orbiting - *not* between `YOU` and `SAN`.)
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_06::{input_generator, solve_part_2};
///
/// const EXINPUT: &str =
///   "COM)B\n\
///    B)C\n\
///    C)D\n\
///    D)E\n\
///    E)F\n\
///    B)G\n\
///    G)H\n\
///    D)I\n\
///    E)J\n\
///    J)K\n\
///    K)L\n\
///    K)YOU\n\
///    I)SAN";
///
/// assert_eq!(solve_part_2(&mut input_generator(EXINPUT)), 4);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_06::{INPUT, input_generator, solve_part_2};
/// assert_eq!(solve_part_2(&mut input_generator(INPUT)), 370);
/// ```
pub fn solve_part_2<'a, T> (input_orbit_pairs: &mut T) -> usize
  where T: Iterator<Item = OrbitPair<'a>>
{
  let orbiting = orbiting_from_orbit_pairs(input_orbit_pairs);

  let mut you_orbit = *orbiting.get("YOU").unwrap();
  let mut santa_orbits = *orbiting.get("SAN").unwrap();

  let mut you_orbits_from_com = vec![];
  while you_orbit != "COM"
  {
    you_orbits_from_com.push(you_orbit);
    you_orbit = *orbiting.get(you_orbit).unwrap();
  }
  drop(you_orbit);

  let mut santa_orbits_from_com = vec![];
  while santa_orbits != "COM"
  {
    santa_orbits_from_com.push(santa_orbits);
    santa_orbits = *orbiting.get(santa_orbits).unwrap();
  }
  drop(santa_orbits);

  let mut distance_between_you_and_santa = 0;

  let mut you_orbits_from_com: &[&str] = &*you_orbits_from_com;
  if you_orbits_from_com.len() > santa_orbits_from_com.len()
  {
    let num_orbits_from_com_diff = you_orbits_from_com.len() - santa_orbits_from_com.len();
    you_orbits_from_com = &you_orbits_from_com[num_orbits_from_com_diff..];
    distance_between_you_and_santa += num_orbits_from_com_diff;
  }

  let mut santa_orbits_from_com: &[&str] = &*santa_orbits_from_com;
  if santa_orbits_from_com.len() > santa_orbits_from_com.len()
  {
    let num_orbits_from_com_diff = santa_orbits_from_com.len() - you_orbits_from_com.len();
    santa_orbits_from_com = &santa_orbits_from_com[num_orbits_from_com_diff..];
    distance_between_you_and_santa += num_orbits_from_com_diff;
  }

  if you_orbits_from_com.len() > 0
  {
    while you_orbits_from_com[0] != santa_orbits_from_com[0]
    {
      you_orbits_from_com = &you_orbits_from_com[1..];
      santa_orbits_from_com = &santa_orbits_from_com[1..];
      distance_between_you_and_santa += 2;
    }
  }

  distance_between_you_and_santa
}

pub fn orbiting_from_orbit_pairs<'a, T> (orbit_pairs: &mut T) -> Orbiting<'a>
  where T: Iterator<Item = OrbitPair<'a>>
{
  orbit_pairs.map(|(orbited, orbiter)| (orbiter, orbited)).collect()
}