SHARE
TWEET

Untitled

a guest Dec 6th, 2019 206 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. pub mod day06 {
  2.     use lazy_static::lazy_static;
  3.     use std::collections::HashMap;
  4.     use std::fmt::Write;
  5.     use indextree::Arena;
  6.     use itertools::Itertools;
  7.  
  8.     fn count_orbits(arena: &Arena<&str>, node: indextree::NodeId, depth: i32) -> i32 {
  9.         depth + node.children(&arena).map(|child| count_orbits(arena, child, depth + 1)).sum::<i32>()
  10.     }
  11.  
  12.     pub fn run(file_string: String) {
  13.         // Parse input into tuple pairs (not totally necessary)
  14.         let pairs : Vec<(&str, &str)> = file_string.lines()
  15.             .map(|line| line.split(")").next_tuple().unwrap())
  16.             .collect();
  17.  
  18.         // Build graph
  19.         let mut arena = &mut Arena::new();
  20.         let mut id_map : HashMap<&str, indextree::NodeId> = HashMap::new();
  21.  
  22.         for (center, orbit) in &pairs {
  23.             let center_id = *id_map.entry(center).or_insert_with(|| arena.new_node(*center));
  24.             let orbit_id = *id_map.entry(orbit).or_insert_with(|| arena.new_node(*orbit));
  25.             center_id.append(orbit_id, &mut arena);
  26.         }
  27.  
  28.         // Part 1 - Compute total orbits from graph
  29.         let total_orbits = count_orbits(arena, *id_map.get("COM").unwrap(), 0);
  30.         writeln!(&mut result, "Day 6, Problem 1 - [{}]", total_orbits).unwrap(); // 270768
  31.  
  32.         // Part 2 - Find path between two arbitrary nodes
  33.         let you_to_com : Vec<indextree::NodeId> = id_map.get("YOU").unwrap().ancestors(&arena).collect();
  34.         let santa_to_com : Vec<indextree::NodeId> = id_map.get("SAN").unwrap().ancestors(&arena).collect();
  35.        
  36.         // Index of last shared object
  37.         let transfer_point = you_to_com.iter().rev()
  38.             .zip(santa_to_com.iter().rev())
  39.             .take_while(|pair| pair.0 == pair.1)
  40.             .count() - 1;
  41.  
  42.  
  43.         // Compute transfers
  44.         let transfers = (you_to_com.len() - transfer_point - 2) + (santa_to_com.len() - transfer_point - 2);
  45.         writeln!(&mut result, "Day 6, Problem 2 - [{}]", transfers).unwrap(); // 451
  46.     }
  47. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top