From 88f90cb6fc1e5b37f14bc096d85ee6c1d4e2ab72 Mon Sep 17 00:00:00 2001 From: alex Date: Thu, 14 Dec 2023 17:50:36 +0100 Subject: [PATCH] Day14 - part 2 --- src/day14.rs | 190 ++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 187 insertions(+), 3 deletions(-) diff --git a/src/day14.rs b/src/day14.rs index 2e7441c..9430896 100644 --- a/src/day14.rs +++ b/src/day14.rs @@ -2,6 +2,8 @@ use std::io::Read; use std::error::Error; use std::fs::File; +use std::collections::VecDeque; + pub fn run(input_file: &str) -> Result<(), Box> { let mut f = File::open(input_file)?; let mut input = String::new(); @@ -47,7 +49,9 @@ impl Puzzle { } pub fn print(&self) { - self.rows.iter().for_each(|r| { println!("{:?}", r); }); + self.rows.iter().for_each(|r| { + println!("{:?}", r.iter().collect::()); + }); } pub fn roll_north(&mut self) { @@ -79,6 +83,65 @@ impl Puzzle { } } + pub fn roll_south(&mut self) { + self.rows.reverse(); + self.roll_north(); + self.rows.reverse(); + } + + // fonctionne par ligne + pub fn roll_west(&mut self) { + for j in 0..self.height { + let mut i = 0; + while i < self.width { + while i < self.width && self.rows[j][i] != 'O' { + i += 1; + } + if i >= self.width { + continue; + } + if self.rows[j][i] == 'O' { + if i == 0 { + i += 1; + continue; + } + let mut k = i; + while k > 0 && self.rows[j][k - 1] == '.' { + k -= 1; + } + self.rows[j][i] = '.'; + self.rows[j][k] = 'O'; + //println!("{:2} swap: {} -> {}", j, i, k); + //self.print(); + } + i += 1; + } + } + } + + pub fn roll_east(&mut self) { + self.reverse_columns(); + self.roll_west(); + self.reverse_columns(); + } + + pub fn reverse_columns(&mut self) { + for j in 0..self.height { + for i in 0..(self.width / 2) { + let tmp = self.rows[j][i]; + self.rows[j][i] = self.rows[j][self.width - 1 - i]; + self.rows[j][self.width - 1 - i] = tmp; + } + } + } + + pub fn cycle(&mut self) { + self.roll_north(); + self.roll_west(); + self.roll_south(); + self.roll_east(); + } + pub fn total_load_north(&self) -> u64 { self.rows.iter().enumerate() .map(|(i, r)| { @@ -94,6 +157,12 @@ impl Puzzle { }) .sum() } + + pub fn to_string(&self) -> String { + self.rows.iter() + .map(|r| format!("{}\n", r.iter().collect::())) + .collect::() + } } fn run_part1(input: &str) -> Result> { @@ -107,7 +176,55 @@ fn run_part1(input: &str) -> Result> { fn run_part2(input: &str) -> Result> { println!("Running day14 - part 2"); - let res = 0; + let mut puzzle = Puzzle::new(input); + + // on suppose que la succession de cycle converge vers une boucle de cycles + // trouver la boucle + // + // un état A donnera toujours l'état B + // + // si on stocke les états à chaque tour, et qu'on le retrouve alors + // on a la boucle + // + // i - loop_start + // <--------------------------> + // 1 2 3 4 5 6 7 8 9 10 11 12 13 + // a - b - c - d - e - f - g - h - i - h - j - i - f - g ... + // \ | + // +----<--------<---------<-+ + // + + let n_cycle = 1000000000; + let mut seen: VecDeque<(String, u64)> = VecDeque::new(); + let mut loop_start = 1; // 1-based + let mut loop_len = 0; + for i in 1..=n_cycle { + puzzle.cycle(); + let v = (puzzle.to_string(), puzzle.total_load_north()); + //println!("puzzle string: {:?}", v.0); + //println!("cycle {} - {:3}", i, v.1); + if seen.contains(&v) { + // pop_front() retire le premier item de la boucle + // il y aura un item en moins à retirer lorsqu'on récupère le résultat + while seen.pop_front() != Some(v.clone()) { + loop_start += 1; + } + loop_len = (i - 1) - loop_start + 1; + break; + } + seen.push_back(v); + } + //dbg!(&seen); + + // nombre de cycle à partir du début + let idx = (n_cycle - loop_start) % loop_len; + + // on avance jusqu'à l'item idx (sachant que certains items ont déjà été retirés) + for i in 1..idx { + seen.pop_front(); + } + + let res = seen.pop_front().unwrap().1; Ok(res) } @@ -133,9 +250,76 @@ O.#..O.#.# assert_eq!(136, res.unwrap()); } + #[test] + fn day14_part2_cycle1() { + let mut puzzle = Puzzle::new(TEXT_INPUT); + puzzle.cycle(); + //println!("puzzle string: {:?}", puzzle.to_string()); + let expected = vec![ ".....#....", + "....#...O#", + "...OO##...", + ".OO#......", + ".....OOO#.", + ".O#...O#.#", + "....O#....", + "......OOOO", + "#...O###..", + "#..OO#....", + ]; + puzzle.rows.iter().zip(expected) + .for_each(|(res, exp)| { + assert_eq!(res.iter().collect::(), exp); + }); + } + + #[test] + fn day14_part2_cycle2() { + let mut puzzle = Puzzle::new(TEXT_INPUT); + puzzle.cycle(); + puzzle.cycle(); + let expected = vec![ ".....#....", + "....#...O#", + ".....##...", + "..O#......", + ".....OOO#.", + ".O#...O#.#", + "....O#...O", + ".......OOO", + "#..OO###..", + "#.OOO#...O", + ]; + puzzle.rows.iter().zip(expected) + .for_each(|(res, exp)| { + assert_eq!(res.iter().collect::(), exp); + }); + } + + #[test] + fn day14_part2_cycle3() { + let mut puzzle = Puzzle::new(TEXT_INPUT); + puzzle.cycle(); + puzzle.cycle(); + puzzle.cycle(); + let expected = vec![ ".....#....", + "....#...O#", + ".....##...", + "..O#......", + ".....OOO#.", + ".O#...O#.#", + "....O#...O", + ".......OOO", + "#...O###.O", + "#.OOO#...O", + ]; + puzzle.rows.iter().zip(expected) + .for_each(|(res, exp)| { + assert_eq!(res.iter().collect::(), exp); + }); + } + #[test] fn day14_part2() { let res = run_part2(TEXT_INPUT); - assert_eq!(0, res.unwrap()); + assert_eq!(64, res.unwrap()); } } -- 2.39.5