From 4b2d3167ee366054880407f23533cfe7983ab80d Mon Sep 17 00:00:00 2001 From: Curtis McEnroe Date: Sat, 9 Dec 2017 02:28:21 -0500 Subject: Day 7, part 2 I don't even know what this is. Don't look at it. --- 2017/src/bin/day07.rs | 69 ++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 65 insertions(+), 4 deletions(-) diff --git a/2017/src/bin/day07.rs b/2017/src/bin/day07.rs index 9d2d75a..f579cbc 100644 --- a/2017/src/bin/day07.rs +++ b/2017/src/bin/day07.rs @@ -9,7 +9,42 @@ struct Program { disc: Vec>>, } -fn solve1(input: &str) -> String { +impl Program { + fn total_weight(&self) -> u32 { + self.weight + self.disc.iter().map(|p| p.borrow().total_weight()).sum::() + } + + fn balance(&self) -> Option { + for child in &self.disc { + match child.borrow().balance() { + Some(x) => return Some(x), + None => (), + } + } + if self.disc.is_empty() { + return None; + } + + let mut disc = self.disc.clone(); + disc.sort_by_key(|p| p.borrow().total_weight()); + let max = disc.iter().map(|p| p.borrow().total_weight()).max().unwrap(); + let min = disc.iter().map(|p| p.borrow().total_weight()).min().unwrap(); + let avg = disc.iter().map(|p| p.borrow().total_weight()).sum::() / disc.len() as u32; + if min == max { + return None; + } else if avg - min < max - avg { + let child = disc.last().unwrap().borrow(); + let diff = child.total_weight() - min; + return Some(child.weight - diff); + } else { + let child = disc.first().unwrap().borrow(); + let diff = max - child.total_weight(); + return Some(child.weight + diff); + } + } +} + +fn solve1(input: &str) -> (String, Rc>) { let mut programs: HashMap>> = HashMap::new(); for line in input.lines() { let mut words = line.split_whitespace(); @@ -43,18 +78,23 @@ fn solve1(input: &str) -> String { program.weight = weight; program.disc = disc; } - programs.into_iter() .find(|&(_, ref p)| Rc::strong_count(p) == 1) .unwrap() - .0 +} + +fn solve2(input: &str) -> u32 { + let root = solve1(input).1; + let balance = root.borrow().balance().unwrap(); + balance } fn main() { let mut input = String::new(); io::stdin().read_to_string(&mut input).unwrap(); - println!("Part 1: {}", solve1(&input)); + println!("Part 1: {}", solve1(&input).0); + println!("Part 2: {}", solve2(&input)); } #[test] @@ -74,6 +114,27 @@ jptl (61) ugml (68) -> gyxo, ebii, jptl gyxo (61) cntj (57) +" + ).0); +} + +#[test] +fn part2() { + assert_eq!(60, solve2( +"\ +pbga (66) +xhth (57) +ebii (61) +havc (66) +ktlj (57) +fwft (72) -> ktlj, cntj, xhth +qoyq (66) +padx (45) -> pbga, havc, qoyq +tknk (41) -> ugml, padx, fwft +jptl (61) +ugml (68) -> gyxo, ebii, jptl +gyxo (61) +cntj (57) " )); } -- cgit 1.4.1