day18

1 files changed, 151 insertions, 0 deletions

diff --git a/2024/day18.rs b/2024/day18.rs
new file mode 100644
index 0000000..52f8ff1
--- /dev/null
+++ b/2024/day18.rs
@@ -0,0 +1,151 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+#![allow(unused_mut)]
+use std::cmp::min;
+use std::collections::HashMap;
+use std::collections::HashSet;
+use std::env;
+use std::fs::File;
+use std::io::Read;
+
+fn dfs(
+    depth: i64,
+    sx: i64,
+    sy: i64,
+    size: i64,
+    m: &Vec<Vec<bool>>,
+    lut: &mut HashMap<(i64, i64), i64>,
+) -> i64 {
+    if sx == size - 1 && sy == size - 1 {
+        return depth;
+    }
+
+    if let Some(val) = lut.get(&(sx, sy)) {
+        if *val < depth {
+            return 99999999999;
+        }
+    }
+    lut.insert((sx, sy), depth);
+
+    let mut s = 99999999999;
+
+    for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
+        let mut x = sx + dx;
+        let mut y = sy + dy;
+        if 0 <= x && x < size && 0 <= y && y < size {
+            if m[y as usize][x as usize] {
+                let a = dfs(depth + 1, x, y, size, &m, lut);
+                s = min(s, a);
+            }
+        }
+    }
+
+    return s;
+}
+
+fn bfs(size: i64, m: &Vec<Vec<bool>>) -> i64 {
+    let mut new_pos: HashSet<(i64, i64)> = HashSet::new();
+    let mut all_pos: HashSet<(i64, i64)> = HashSet::new();
+    let mut cur_pos: HashSet<(i64, i64)>;
+
+    new_pos.insert((0, 0));
+
+    all_pos = &all_pos | &new_pos;
+    cur_pos = new_pos.clone();
+    new_pos.clear();
+
+    for depth in 0.. {
+        for (sx, sy) in cur_pos.clone() {
+            for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
+                let mut x = sx + dx;
+                let mut y = sy + dy;
+                if sx == size - 1 && sy == size - 1 {
+                    return depth;
+                }
+                if 0 <= x && x < size && 0 <= y && y < size {
+                    if m[y as usize][x as usize] {
+                        if !all_pos.contains(&(x, y)) {
+                            new_pos.insert((x, y));
+                        }
+                    }
+                }
+            }
+        }
+        if new_pos.len() == 0 {
+            return 0;
+        }
+        all_pos = &all_pos | &new_pos;
+        cur_pos = new_pos.clone();
+        new_pos.clear();
+    }
+
+    return 0;
+}
+
+fn print_m(m: &Vec<Vec<bool>>) {
+    for l in m {
+        for c in l {
+            if *c == true {
+                print!(".");
+            } else {
+                print!("#");
+            }
+        }
+        println!();
+    }
+}
+
+fn main() {
+    let args: Vec<String> = env::args().collect();
+    let filename = if args.len() == 1 {
+        "in/".to_owned() + args[0].split('/').last().unwrap() + ".pzl"
+    } else {
+        args[1].clone()
+    };
+    let mut f = File::open(filename).expect("cannot open file");
+    let mut content = String::new();
+    f.read_to_string(&mut content).expect("cannot read file");
+    let lines = content.trim_end().split("\n");
+
+    let mut bytes: Vec<(i64, i64)> = Vec::new();
+    for line in lines {
+        let (a, b) = line.split_once(',').unwrap();
+        bytes.push((a.parse().unwrap(), b.parse().unwrap()));
+    }
+    //println!("{:?}", bytes);
+
+    //let size = 6 + 1;
+    //let mut fall = 12;
+    let size = 70 + 1;
+    let mut fall = 1024;
+
+    let mut m: Vec<Vec<bool>> = vec![vec![true; size]; size];
+    for i in 0..fall {
+        let x = bytes[i].0 as usize;
+        let y = bytes[i].1 as usize;
+        m[y][x] = false;
+    }
+    //print_m(&m);
+
+    let mut lut: HashMap<(i64, i64), i64> = HashMap::new();
+    //let res1 = dfs(0, 0, 0, size as i64, &m, &mut lut);
+    let res1 = bfs(size as i64, &m);
+
+    let mut res2;
+    loop {
+        let x = bytes[fall].0 as usize;
+        let y = bytes[fall].1 as usize;
+        m[y][x] = false;
+        fall += 1;
+        let res = bfs(size as i64, &m);
+        if res == 0 {
+            res2 = format!("{},{}", x, y);
+            break;
+        }
+    }
+
+    println!("res1: {}", res1);
+    println!("res2: {}", res2);
+    assert_eq!(res1, 324);
+    assert_eq!(res2, "46,23");
+}