diff options
| -rw-r--r-- | 23/Cargo.toml | 11 | ||||
| -rw-r--r-- | 23/input | 1 | ||||
| -rw-r--r-- | 23/input.small | 1 | ||||
| -rw-r--r-- | 23/src/main.rs | 335 | ||||
| -rw-r--r-- | 23/tests/main.rs | 14 | ||||
| -rw-r--r-- | Cargo.lock | 8 | ||||
| -rw-r--r-- | Cargo.nix | 35 | ||||
| -rw-r--r-- | Cargo.toml | 1 |
8 files changed, 406 insertions, 0 deletions
diff --git a/23/Cargo.toml b/23/Cargo.toml new file mode 100644 index 0000000..28383e3 --- /dev/null +++ b/23/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "advent_23" +version = "0.1.0" +authors = ["Irene Knapp <ireneista@gmail.com>"] +edition = "2018" + +[dependencies] +advent_lib = { path = "../lib" } + +[dev-dependencies] +assert_cmd = "0.10" diff --git a/23/input b/23/input new file mode 100644 index 0000000..c13a556 --- /dev/null +++ b/23/input @@ -0,0 +1 @@ +362981754 diff --git a/23/input.small b/23/input.small new file mode 100644 index 0000000..ab40847 --- /dev/null +++ b/23/input.small @@ -0,0 +1 @@ +389125467 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 +} diff --git a/23/tests/main.rs b/23/tests/main.rs new file mode 100644 index 0000000..4b8bde1 --- /dev/null +++ b/23/tests/main.rs @@ -0,0 +1,14 @@ +use assert_cmd::prelude::*; +use std::process::Command; + + +#[test] +fn personal_input() -> Result<(), Box<dyn std::error::Error>> { + let mut command = Command::cargo_bin("advent_23")?; + + command.arg("input"); + command.assert().success().stdout("24798635\n12757828710\n"); + + Ok(()) +} + diff --git a/Cargo.lock b/Cargo.lock index fccfa2c..d2334f1 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -181,6 +181,14 @@ dependencies = [ ] [[package]] +name = "advent_23" +version = "0.1.0" +dependencies = [ + "advent_lib", + "assert_cmd", +] + +[[package]] name = "advent_lib" version = "0.1.0" dependencies = [ diff --git a/Cargo.nix b/Cargo.nix index c5446f4..c95516a 100644 --- a/Cargo.nix +++ b/Cargo.nix @@ -248,6 +248,16 @@ rec { # File a bug if you depend on any for non-debug work! debug = internal.debugCrate { inherit packageId; }; }; + "advent_23" = rec { + packageId = "advent_23"; + build = internal.buildRustCrateWithFeatures { + packageId = "advent_23"; + }; + + # Debug support which might change between releases. + # File a bug if you depend on any for non-debug work! + debug = internal.debugCrate { inherit packageId; }; + }; "advent_lib" = rec { packageId = "advent_lib"; build = internal.buildRustCrateWithFeatures { @@ -854,6 +864,31 @@ rec { ]; }; + "advent_23" = rec { + crateName = "advent_23"; + version = "0.1.0"; + edition = "2018"; + crateBin = [ + { name = "advent_23"; path = "src/main.rs"; } + ]; + src = (builtins.filterSource sourceFilter ./23); + authors = [ + "Irene Knapp <ireneista@gmail.com>" + ]; + dependencies = [ + { + name = "advent_lib"; + packageId = "advent_lib"; + } + ]; + devDependencies = [ + { + name = "assert_cmd"; + packageId = "assert_cmd"; + } + ]; + + }; "advent_lib" = rec { crateName = "advent_lib"; version = "0.1.0"; diff --git a/Cargo.toml b/Cargo.toml index 8ee9c55..34c5520 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -23,4 +23,5 @@ members = [ "20", "21", "22", + "23", ] |