day09

1 files changed, 172 insertions, 0 deletions

diff --git a/2024/day09.rs b/2024/day09.rs
new file mode 100644
index 0000000..986bf74
--- /dev/null
+++ b/2024/day09.rs
@@ -0,0 +1,172 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+#![allow(unused_mut)]
+use std::env;
+use std::fs::File;
+use std::io::Read;
+
+#[derive(Debug, PartialEq, Clone)]
+struct Block {
+    isfile: bool,
+    id: u64,
+}
+
+fn print_fs(fs: &Vec<Block>) {
+    for b in fs {
+        if b.isfile {
+            print!("{}", b.id);
+        } else {
+            print!(".");
+        }
+    }
+    println!();
+}
+
+fn compact(mut fs: Vec<Block>) -> Vec<Block> {
+    for i in (0..fs.len()).rev() {
+        if !fs[i].isfile {
+            continue;
+        }
+        for j in 0..fs.len() {
+            if i < j {
+                break;
+            }
+            if !fs[j].isfile {
+                fs.swap(i, j);
+                break;
+            }
+        }
+    }
+    fs
+}
+
+fn same(index: usize, fs: &Vec<Block>) -> (usize, usize) {
+    let mut start: usize = 0;
+    let mut end: usize = 0;
+    let b = &fs[index];
+
+    for e in index..fs.len() {
+        if fs[e].isfile == b.isfile && (!fs[e].isfile || fs[e].id == b.id) {
+            end = e;
+        } else {
+            break;
+        }
+    }
+
+    for s in (0..=index).rev() {
+        if fs[s].isfile == b.isfile && (!fs[s].isfile || fs[s].id == b.id) {
+            start = s;
+        } else {
+            break;
+        }
+    }
+
+    return (start, end - start + 1);
+}
+
+fn compact2(mut fs: Vec<Block>) -> Vec<Block> {
+    let mut i = fs.len() - 1;
+    loop {
+        let mut il;
+        (i, il) = same(i, &fs);
+
+        if !fs[i].isfile {
+            if i == 0 {
+                break;
+            }
+            i -= 1;
+            continue;
+        }
+
+        let mut j = 0;
+        let mut jl;
+        loop {
+            (j, jl) = same(j, &fs);
+            if j > i {
+                break;
+            }
+            if fs[j].isfile || il > jl {
+                if j + jl >= fs.len() {
+                    break;
+                }
+                j = j + jl;
+                continue;
+            }
+
+            for r in 0..il {
+                fs.swap(i + r, j + r);
+            }
+
+            if j + jl >= fs.len() {
+                break;
+            }
+            j = j + jl;
+        }
+
+        if i == 0 {
+            break;
+        }
+        i -= 1;
+    }
+
+    fs
+}
+
+fn checksum(fs: &Vec<Block>) -> u64 {
+    let mut sum = 0;
+    for i in (0..fs.len()).rev() {
+        if fs[i].isfile {
+            sum += (i as u64) * fs[i].id;
+        }
+    }
+    return sum;
+}
+
+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 mut lines = content.trim_end().split("\n");
+
+    let line = lines.next().unwrap();
+
+    let mut fs: Vec<Block> = Vec::new();
+    let mut isfile = true;
+    let mut id = 0;
+    for (i, c) in line.chars().enumerate() {
+        let n = c.to_digit(10).unwrap() as usize;
+
+        for j in 0..n {
+            let b = Block {
+                isfile: isfile,
+                id: id,
+            };
+            fs.push(b);
+        }
+        if isfile {
+            id += 1;
+        }
+        isfile ^= true;
+    }
+
+    //print_fs(&fs);
+    let fs1 = compact(fs.clone());
+    //print_fs(&fs1);
+    let res1 = checksum(&fs1);
+
+    //print_fs(&fs);
+    let fs2 = compact2(fs.clone());
+    //print_fs(&fs2);
+    let res2 = checksum(&fs2);
+
+    println!("res1: {}", res1);
+    println!("res2: {}", res2);
+    assert_eq!(res1, 6370402949053);
+    assert_eq!(res2, 6398096697992);
+}