Implement basic cycling

ankon · ankon · commit 48794fe13977 · 2023-12-19T19:58:56.000+01:00
Note that the east/west tilting is still wrong, but the code structure in general should
now be stable: We cycle until we find that the state is actually stable (by checking a SHA-1
of it), and then return the load.
diff --git a/Cargo.lock b/Cargo.lock
diff --git a/Cargo.toml b/Cargo.toml
@@ -8,6 +8,7 @@ edition = "2021"
 [dependencies]
 muldiv = "1.0.1"
 num = "0.4.1"
+rust-crypto = "0.2.36"
 
 [[bin]]
 name = "adventofcode"
diff --git a/src/day14.rs b/src/day14.rs
@@ -1,4 +1,4 @@
-#[derive(Debug, PartialEq)]
+#[derive(Clone, Copy, Debug, PartialEq)]
 enum Tile {
     Empty = '.' as isize,
     FixedRock = '#' as isize,
@@ -19,17 +19,32 @@ struct Platform {
 
 impl Platform {
     pub fn tilt(&mut self, direction: Direction) {
-        assert_eq!(direction, Direction::North);
-
         let rows = self.tiles.len();
-        for r in 0..rows  {
+        let cols = self.tiles[0].len();
+        match direction {
+            Direction::North => self.tilt_north_south(0..=rows-1, |r| r+1..=rows-1),
+            Direction::West => self.tilt_west_east(0..=cols-1, |c| c+1..=cols-1),
+            Direction::South => self.tilt_north_south(rows-1..=0, |r| r-1..=0),
+            Direction::East => self.tilt_west_east(cols-1..=0, |c| c-1..=0),
+        }
+    }
+
+    pub fn cycle(&mut self) {
+        self.tilt(Direction::North);
+        self.tilt(Direction::West);
+        self.tilt(Direction::South);
+        self.tilt(Direction::East);
+    }
+
+    fn tilt_north_south(&mut self, rows: std::ops::RangeInclusive<usize>, source_rows: impl Fn(usize) -> std::ops::RangeInclusive<usize>) {
+        for r in rows {
             for c in 0..self.tiles[r].len() {
                 if self.tiles[r][c] != Tile::Empty {
                     continue;
                 }
 
                 // Move the closest tile in South direction here.
-                for r2 in r+1..rows {
+                for r2 in source_rows(r) {
                     let other_tile = &mut self.tiles[r2][c];
                     match other_tile {
                         Tile::Empty => {},
@@ -49,6 +64,34 @@ impl Platform {
         }
     }
 
+    fn tilt_west_east(&mut self, cols: std::ops::RangeInclusive<usize>, source_cols: impl Fn(usize) -> std::ops::RangeInclusive<usize>) {
+        for c in cols {
+            for r in 0..self.tiles.len() {
+                if self.tiles[r][c] != Tile::Empty {
+                    continue;
+                }
+
+                // Move the closest tile in South direction here.
+                for c2 in source_cols(c) {
+                    let other_tile = &mut self.tiles[r][c2];
+                    match other_tile {
+                        Tile::Empty => {},
+                        Tile::FixedRock => {
+                            // Abort: This rock won't move, and anything further south will get stuck here.
+                            break;
+                        },
+                        Tile::RoundedRock => {
+                            // This one!
+                            self.tiles[r][c] = Tile::RoundedRock;
+                            self.tiles[r][c2] = Tile::Empty;
+                            break;
+                        },
+                    }
+                }
+            }
+        }
+    }
+
     pub fn total_load(&self, beam: Direction) -> usize {
         assert_eq!(beam, Direction::North);
 
@@ -63,6 +106,16 @@ impl Platform {
         }
         result
     }
+
+    pub fn checksum(&self) -> String {
+        let mut hasher = crypto::sha1::Sha1::new();
+        for row in self.tiles.iter() {
+            for tile in row.iter() {
+                crypto::digest::Digest::input(&mut hasher, &[*tile as u8]);
+            }
+        }
+        crypto::digest::Digest::result_str(&mut hasher)
+    }
 }
 
 impl std::fmt::Display for Platform {
@@ -104,13 +157,36 @@ impl std::str::FromStr for Platform {
 }
 
 pub fn main() {
+    const CYCLES: usize = 1000000000;
     match std::fs::read_to_string("day14.input") {
         Ok(input) => {
             let mut platform: Platform = input.parse().unwrap();
             println!("initial\n{}", platform);
             platform.tilt(Direction::North);
             println!("after tilt\n{}", platform);
             println!("total load = {}", platform.total_load(Direction::North));
+
+            // Complete the first cycle.
+            platform.tilt(Direction::West);
+            platform.tilt(Direction::South);
+            platform.tilt(Direction::East);
+
+            // Complete the remaining cycles
+            let mut previous_checksum = platform.checksum();
+            for cycle in 0..CYCLES-1 {
+                platform.cycle();
+
+                let checksum = platform.checksum();
+                println!("cycle {} checksum = {}", cycle, checksum);
+                if checksum == previous_checksum {
+                    break;
+                }
+                previous_checksum = checksum;
+                if cycle % 1000 == 0 {
+                    println!("complete {}%", cycle/CYCLES*100);
+                }
+            }
+            println!("total load after {} cycles = {}", CYCLES, platform.total_load(Direction::North));
         },
         Err(reason) => println!("error = {}", reason),
     }
@@ -120,6 +196,7 @@ pub fn main() {
 mod test {
     use super::*;
 
+    static CYCLES: usize = 1000000000;
     static DATA: &str = "O....#....
 O.OO#....#
 .....##...
@@ -139,4 +216,24 @@ O.#..O.#.#
         println!("after tilt\n{}", platform);
         assert_eq!(platform.total_load(Direction::North), 136);
     }
+
+    #[test]
+    fn test_part2() {
+        let mut platform: Platform = DATA.parse().unwrap();
+        println!("initial\n{}", platform);
+
+        let mut previous_checksum = platform.checksum();
+        for cycle in 0..CYCLES {
+            platform.cycle();
+
+            let checksum = platform.checksum();
+            println!("cycle {} checksum = {}", cycle, checksum);
+            if checksum == previous_checksum {
+                break;
+            }
+            previous_checksum = checksum;
+        }
+        println!("after tilt\n{}", platform);
+        assert_eq!(platform.total_load(Direction::North), 64);
+    }
 }
