From cfba0cdb161a790cff0e5663ae0a025999ee5bef Mon Sep 17 00:00:00 2001 From: Irene Knapp Date: Wed, 23 Dec 2020 14:48:04 -0800 Subject: 23. wow ... that was a lot. --- 23/src/main.rs | 335 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 335 insertions(+) create mode 100644 23/src/main.rs (limited to '23/src') diff --git a/23/src/main.rs b/23/src/main.rs new file mode 100644 index 0000000..797afa7 --- /dev/null +++ b/23/src/main.rs @@ -0,0 +1,335 @@ +use advent_lib::prelude::*; + +use std::convert::TryFrom; +use std::rc::Rc; +use std::cell::RefCell; + + +mod cup_structure { + use std::rc::Rc; + use std::cell::RefCell; + + pub struct Cup { + label: usize, + numeric_prev: Option>>, + prev: Option>>, + next: Option>>, + } + + impl Cup { + pub fn new(count: usize) -> Vec>> { + let mut all_cups: Vec>> = Vec::new(); + let mut prev: Option>> = None; + + for i in 1 .. count + 1 { + let cup_rc = Rc::new(RefCell::new(Cup { + label: i, + numeric_prev: None, + prev: None, + next: None, + })); + + match prev { + Some(prev_rc) => { + let mut cup = cup_rc.borrow_mut(); + cup.numeric_prev = Some(Rc::clone(&prev_rc)); + cup.prev = Some(Rc::clone(&prev_rc)); + + let mut prev_cup = prev_rc.borrow_mut(); + prev_cup.next = Some(Rc::clone(&cup_rc)); + }, + None => { }, + } + + prev = Some(Rc::clone(&cup_rc)); + all_cups.push(cup_rc); + } + + { + let first_rc = &all_cups[0]; + let last_rc = &all_cups[all_cups.len()-1]; + let mut first_cup = first_rc.borrow_mut(); + let mut last_cup = last_rc.borrow_mut(); + first_cup.numeric_prev = Some(Rc::clone(last_rc)); + first_cup.prev = Some(Rc::clone(last_rc)); + last_cup.next = Some(Rc::clone(first_rc)); + } + + all_cups + } + + #[allow(dead_code)] + pub fn label(&self) -> usize { + self.label + } + + #[allow(dead_code)] + pub fn numeric_prev(&self) -> Rc> { + Rc::clone(self.numeric_prev.as_ref().unwrap()) + } + + #[allow(dead_code)] + pub fn next(&self) -> Rc> { + Rc::clone(self.next.as_ref().unwrap()) + } + + #[allow(dead_code)] + pub fn prev(&self) -> Rc> { + Rc::clone(self.prev.as_ref().unwrap()) + } + + #[allow(dead_code)] + pub fn len(&self) -> usize { + let mut result = 1; + + let mut next_rc = Rc::clone(self.next.as_ref().unwrap()); + loop { + if next_rc.borrow().label == self.label { + break; + } + let next_rc_tmp = Rc::clone(&next_rc.borrow().next.as_ref().unwrap()); + next_rc = next_rc_tmp; + result += 1; + } + + result + } + + pub fn find(&self, to_find: usize) -> Option>> { + let self_rc; + { + let next_cup = self.next.as_ref().unwrap().borrow(); + self_rc = Rc::clone(&next_cup.prev.as_ref().unwrap()); + } + + if self.label == to_find { + Some(self_rc) + } else { + let mut point_rc = Rc::clone(self.next.as_ref().unwrap()); + loop { + let point_label; + { + let point_cup = point_rc.borrow(); + point_label = point_cup.label; + } + if point_label == self.label { + return None; + } + if point_label == to_find { + return Some(point_rc); + } + { + let next_point_rc = Rc::clone(point_rc.borrow().next.as_ref().unwrap()); + point_rc = next_point_rc; + } + } + } + } + + pub fn split_at(self_rc: Rc>, count: usize) + -> (Rc>, Rc>) + { + let mut tail_rc = Rc::clone(self_rc.borrow().next.as_ref().unwrap()); + for _ in 1 .. count { + let new_tail_rc = Rc::clone(tail_rc.borrow().next.as_ref().unwrap()); + tail_rc = new_tail_rc; + } + + let head_last_rc = Rc::clone(tail_rc.borrow().prev.as_ref().unwrap()); + let tail_last_rc = Rc::clone(self_rc.borrow().prev.as_ref().unwrap()); + + if Rc::ptr_eq(&tail_rc, &tail_last_rc) { + let mut tail_cup = tail_rc.borrow_mut(); + tail_cup.prev = Some(Rc::clone(&tail_rc)); + tail_cup.next = Some(Rc::clone(&tail_rc)); + } else { + let mut tail_cup = tail_rc.borrow_mut(); + let mut tail_last_cup = tail_last_rc.borrow_mut(); + tail_cup.prev = Some(Rc::clone(&tail_last_rc)); + tail_last_cup.next = Some(Rc::clone(&tail_rc)); + } + + if Rc::ptr_eq(&self_rc, &head_last_rc) { + let mut self_cup = self_rc.borrow_mut(); + self_cup.next = Some(Rc::clone(&self_rc)); + self_cup.prev = Some(Rc::clone(&head_last_rc)); + } else { + let mut self_cup = self_rc.borrow_mut(); + let mut head_last_cup = head_last_rc.borrow_mut(); + head_last_cup.next = Some(Rc::clone(&self_rc)); + self_cup.prev = Some(Rc::clone(&head_last_rc)); + } + + (Rc::clone(&self_rc), Rc::clone(&tail_rc)) + } + + pub fn splice_after(self_rc: Rc>, + to_insert_rc: Rc>) + { + let mut self_cup = self_rc.borrow_mut(); + + let old_next_rc = Rc::clone(self_cup.next.as_ref().unwrap()); + + let to_insert_last_rc = + Rc::clone(to_insert_rc.borrow().prev.as_ref().unwrap()); + { + let mut to_insert_last_cup = to_insert_last_rc.borrow_mut(); + to_insert_last_cup.next = Some(Rc::clone(&old_next_rc)); + } + + if Rc::ptr_eq(&old_next_rc, &self_rc) { + self_cup.prev = Some(Rc::clone(&to_insert_last_rc)); + } else { + let mut old_next_cup = old_next_rc.borrow_mut(); + old_next_cup.prev = Some(Rc::clone(&to_insert_last_rc)); + } + + let mut to_insert_cup = to_insert_rc.borrow_mut(); + to_insert_cup.prev = Some(Rc::clone(&self_rc)); + self_cup.next = Some(Rc::clone(&to_insert_rc)); + } + + pub fn splice_before(self_rc: Rc>, to_insert_rc: Rc>) { + let prev_cup_rc = Rc::clone(self_rc.borrow().prev.as_ref().unwrap()); + Cup::splice_after(prev_cup_rc, to_insert_rc); + } + } +} // mod cup_structure + +use cup_structure::Cup; + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + + let mut initial_cups: Vec = Vec::new(); + for c in input[0].chars() { + let label = usize::try_from(c.to_digit(10).unwrap()).unwrap(); + initial_cups.push(label); + } + + { + let max_cup = initial_cups.len(); + let cups_by_zero_based_label = Cup::new(max_cup); + + let mut label_iter = initial_cups.iter(); + let first_label: usize = *label_iter.next().unwrap(); + let first_cup_rc = &cups_by_zero_based_label[first_label-1]; + let (mut cups_rc, _) = Cup::split_at(Rc::clone(first_cup_rc), 1); + for label in label_iter { + let next_cup; + { + let next_cup_rc = &cups_by_zero_based_label[*label-1]; + let (next_cup_tmp, _) = Cup::split_at(Rc::clone(next_cup_rc), 1); + next_cup = next_cup_tmp; + } + Cup::splice_before(Rc::clone(&cups_rc), next_cup); + } + + for _ in 0 .. 100 { + cups_rc = iterate_game(Rc::clone(&cups_rc)); + } + + let output1 = game_output1(Rc::clone(&cups_rc)); + println!("{}", output1); + } + + { + let max_cup = 1000000; + let cups_by_zero_based_label = Cup::new(max_cup); + let max_defined_cup = initial_cups.len(); + + let mut label_iter = initial_cups.iter(); + let first_label: usize = *label_iter.next().unwrap(); + let first_cup_rc = &cups_by_zero_based_label[first_label-1]; + let (mut cups_rc, _) = Cup::split_at(Rc::clone(first_cup_rc), 1); + for label in label_iter { + let next_cup_rc = &cups_by_zero_based_label[*label-1]; + let (next_cup, _) = Cup::split_at(Rc::clone(next_cup_rc), 1); + Cup::splice_before(Rc::clone(&cups_rc), next_cup); + } + Cup::splice_before(Rc::clone(&cups_rc), + Rc::clone(&cups_by_zero_based_label[max_defined_cup])); + + for _ in 0 .. 10000000 { + cups_rc = iterate_game(Rc::clone(&cups_rc)); + } + + let output = game_output2(Rc::clone(&cups_rc)); + println!("{}", output); + } + + Ok(()) +} + + +fn game_output1(cups: Rc>) -> String { + let mut output = String::new(); + + let mut cup = cups.borrow().find(1).unwrap(); + { + let next_cup = cup.borrow().next(); + cup = next_cup; + } + loop { + if cup.borrow().label() == 1 { + break; + } + output.push_str(&format!("{}", cup.borrow().label())); + let next_cup = cup.borrow().next(); + cup = next_cup; + } + + output +} + + +fn game_output2(cups: Rc>) -> String { + let mut result = 1; + + let mut cup = cups.borrow().find(1).unwrap(); + { + let next_cup = cup.borrow().next(); + cup = next_cup; + } + result *= cup.borrow().label(); + { + let next_cup = cup.borrow().next(); + cup = next_cup; + } + result *= cup.borrow().label(); + + format!("{}", result) +} + + +fn iterate_game(cups: Rc>) -> Rc> { + let current_cup = Rc::clone(&cups); + let cups = cups.borrow().next(); + + let (transferred_cups, _) = Cup::split_at(cups, 3); + + let mut destination_cup = current_cup.borrow().numeric_prev(); + + loop { + let destination_cup_label = destination_cup.borrow().label(); + if transferred_cups.borrow().find(destination_cup_label).is_none() { + break; + } + let next_destination_cup = + Rc::clone(&destination_cup.borrow().numeric_prev()); + destination_cup = next_destination_cup; + } + + Cup::splice_after(destination_cup, transferred_cups); + + let next_current_cup = current_cup.borrow().next(); + next_current_cup +} -- cgit 1.4.1