day15 part2

1 files changed, 130 insertions, 6 deletions

diff --git a/2024/day15.rs b/2024/day15.rs
index f3c499e..67fcb2d 100644
--- a/2024/day15.rs
+++ b/2024/day15.rs
@@ -1,6 +1,7 @@
 #![allow(dead_code)]
 #![allow(unused_variables)]
 #![allow(unused_mut)]
+use std::collections::HashSet;
 use std::env;
 use std::fs::File;
 use std::io::Read;
@@ -40,6 +41,94 @@ fn sim(rx: i64, ry: i64, dx: i64, dy: i64, mut m: &mut Vec<Vec<Field>>) -> (i64,
     }
 }
 
+fn sim2(rx: i64, ry: i64, dx: i64, dy: i64, mut m: &mut Vec<Vec<char>>) -> (i64, i64) {
+    let mx = rx + dx;
+    let my = ry + dy;
+
+    let mut boxes: Vec<(i64, i64)> = Vec::new();
+    let mut new_boxes: HashSet<(i64, i64)> = HashSet::new();
+    let mut all_boxes: HashSet<(i64, i64)> = HashSet::new();
+    let mut cur_boxes: HashSet<(i64, i64)>;
+
+    let f = m[my as usize][mx as usize];
+    match f {
+        '#' => return (rx, ry),
+        '.' => return (mx, my),
+        '[' => {
+            new_boxes.insert((mx, my));
+            boxes.push((mx, my));
+            new_boxes.insert((mx + 1, my));
+            boxes.push((mx + 1, my));
+        }
+        ']' => {
+            new_boxes.insert((mx, my));
+            boxes.push((mx, my));
+            new_boxes.insert((mx - 1, my));
+            boxes.push((mx - 1, my));
+        }
+        _ => panic!(),
+    }
+
+    all_boxes = &all_boxes | &new_boxes;
+    cur_boxes = new_boxes.clone();
+    new_boxes.clear();
+
+    loop {
+        for (x, y) in cur_boxes.clone() {
+            let nx = x + dx;
+            let ny = y + dy;
+            let f = m[ny as usize][nx as usize];
+            match f {
+                '#' => return (rx, ry),
+                '.' => (),
+                '[' => {
+                    if !all_boxes.contains(&(nx, ny)) {
+                        new_boxes.insert((nx, ny));
+                        if !boxes.contains(&(nx, ny)) {
+                            boxes.push((nx, ny));
+                        }
+                    }
+                    if !all_boxes.contains(&(nx + 1, ny)) {
+                        new_boxes.insert((nx + 1, ny));
+                        if !boxes.contains(&(nx + 1, ny)) {
+                            boxes.push((nx + 1, ny));
+                        }
+                    }
+                }
+                ']' => {
+                    if !all_boxes.contains(&(nx, ny)) {
+                        new_boxes.insert((nx, ny));
+                        if !boxes.contains(&(nx, ny)) {
+                            boxes.push((nx, ny));
+                        }
+                    }
+                    if !all_boxes.contains(&(nx - 1, ny)) {
+                        new_boxes.insert((nx - 1, ny));
+                        if !boxes.contains(&(nx - 1, ny)) {
+                            boxes.push((nx - 1, ny));
+                        }
+                    }
+                }
+                _ => panic!(),
+            }
+        }
+        if new_boxes.len() == 0 {
+            break;
+        }
+        all_boxes = &all_boxes | &new_boxes;
+        cur_boxes = new_boxes.clone();
+        new_boxes.clear();
+    }
+
+    for (x, y) in boxes.into_iter().rev() {
+        let tmp = m[y as usize][x as usize];
+        m[y as usize][x as usize] = m[(y + dy) as usize][(x + dx) as usize];
+        m[(y + dy) as usize][(x + dx) as usize] = tmp;
+    }
+
+    return (mx, my);
+}
+
 fn gps(m: &Vec<Vec<Field>>) -> i64 {
     let mut ret = 0;
     for y in 0..m.len() {
@@ -52,6 +141,18 @@ fn gps(m: &Vec<Vec<Field>>) -> i64 {
     return ret as i64;
 }
 
+fn gps2(m: &Vec<Vec<char>>) -> i64 {
+    let mut ret = 0;
+    for y in 0..m.len() {
+        for x in 0..m[0].len() {
+            if m[y][x] == '[' {
+                ret += 100 * y + x;
+            }
+        }
+    }
+    return ret as i64;
+}
+
 fn print_m(m: &Vec<Vec<Field>>) {
     for l in m {
         for f in l {
@@ -65,6 +166,19 @@ fn print_m(m: &Vec<Vec<Field>>) {
     }
 }
 
+fn print_m2(rx: i64, ry: i64, m: &Vec<Vec<char>>) {
+    for (y, l) in m.iter().enumerate() {
+        for (x, c) in l.iter().enumerate() {
+            if x as i64 == rx && y as i64 == ry {
+                print!("@");
+            } else {
+                print!("{}", c);
+            }
+        }
+        println!();
+    }
+}
+
 fn main() {
     let args: Vec<String> = env::args().collect();
     let filename = if args.len() == 1 {
@@ -80,8 +194,10 @@ fn main() {
     let mut rx = 0;
     let mut ry = 0;
     let mut m: Vec<Vec<Field>> = Vec::new();
+    let mut m2: Vec<Vec<char>> = Vec::new();
     for (y, line) in para1.split("\n").enumerate() {
         let mut l: Vec<Field> = Vec::new();
+        let mut l2: Vec<char> = Vec::new();
         for (x, c) in line.chars().enumerate() {
             let x = x as i64;
             let y = y as i64;
@@ -89,17 +205,25 @@ fn main() {
                 rx = x;
                 ry = y;
             }
-
             if c == 'O' {
                 l.push(Field::Box);
+                l2.push('[');
+                l2.push(']');
             } else if c == '#' {
                 l.push(Field::Wall);
+                l2.push('#');
+                l2.push('#');
             } else {
                 l.push(Field::Empty);
+                l2.push('.');
+                l2.push('.');
             }
         }
         m.push(l);
+        m2.push(l2);
     }
+    let mut rx2 = 2 * rx;
+    let mut ry2 = ry;
 
     let mut dirs: Vec<(i64, i64)> = Vec::new();
     for line in para2.split("\n") {
@@ -114,19 +238,19 @@ fn main() {
             dirs.push(d);
         }
     }
-    //println!("{:?}", dirs);
 
     for dir in dirs {
         (rx, ry) = sim(rx, ry, dir.0, dir.1, &mut m);
+        (rx2, ry2) = sim2(rx2, ry2, dir.0, dir.1, &mut m2);
         //print_m(&m);
+        //print_m2(rx2, ry2, &m2);
     }
-
     let res1 = gps(&m);
 
-    let mut res2 = 0;
+    let res2 = gps2(&m2);
 
     println!("res1: {}", res1);
     println!("res2: {}", res2);
-    //assert_eq!(res1, 1414416);
-    //assert_eq!(res2, );
+    assert_eq!(res1, 1414416);
+    assert_eq!(res2, 1386070);
 }