23. wow ... that was a lot.

1 files changed, 335 insertions, 0 deletions

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<Rc<RefCell<Cup>>>,
+    prev: Option<Rc<RefCell<Cup>>>,
+    next: Option<Rc<RefCell<Cup>>>,
+  }
+
+  impl Cup {
+    pub fn new(count: usize) -> Vec<Rc<RefCell<Cup>>> {
+      let mut all_cups: Vec<Rc<RefCell<Cup>>> = Vec::new();
+      let mut prev: Option<Rc<RefCell<Cup>>> = 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<RefCell<Cup>> {
+      Rc::clone(self.numeric_prev.as_ref().unwrap())
+    }
+
+    #[allow(dead_code)]
+    pub fn next(&self) -> Rc<RefCell<Cup>> {
+      Rc::clone(self.next.as_ref().unwrap())
+    }
+
+    #[allow(dead_code)]
+    pub fn prev(&self) -> Rc<RefCell<Cup>> {
+      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<Rc<RefCell<Cup>>> {
+      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<RefCell<Cup>>, count: usize)
+      -> (Rc<RefCell<Cup>>, Rc<RefCell<Cup>>)
+    {
+      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<RefCell<Cup>>,
+                        to_insert_rc: Rc<RefCell<Cup>>)
+    {
+      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<RefCell<Cup>>, to_insert_rc: Rc<RefCell<Cup>>) {
+      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<usize> = 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<RefCell<Cup>>) -> 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<RefCell<Cup>>) -> 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<RefCell<Cup>>) -> Rc<RefCell<Cup>> {
+  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
+}