From 9e486d06af28a2b4ff5987257174c4213ff8c5f6 Mon Sep 17 00:00:00 2001
From: alex <>
Date: Mon, 9 Dec 2024 10:32:42 +0100
Subject: [PATCH] Day09 - part 1

---
 src/day09.rs | 136 +++++++++++++++++++++++++++++++++++++++++++++++++++
 src/main.rs  |   2 +
 2 files changed, 138 insertions(+)
 create mode 100644 src/day09.rs

diff --git a/src/day09.rs b/src/day09.rs
new file mode 100644
index 0000000..42a1409
--- /dev/null
+++ b/src/day09.rs
@@ -0,0 +1,136 @@
+use std::error::Error;
+use std::path::Path;
+
+struct Puzzle {
+    // a block is represented as a tuple composed of (start, length, value)
+    blocks: Vec<(u64, u64, u64)>,
+    // a free block is represented as a tuple composed of (start, length)
+    free: Vec<(u64, u64)>,
+}
+
+impl Puzzle {
+    pub fn new(input: &str) -> Self {
+        let mut blocks = Vec::new();
+        let mut free = Vec::new();
+        let mut start: u64 = 0;
+        input.chars().filter(|c| *c != '\n').collect::<Vec<char>>()
+            .chunks(2).enumerate()
+            .for_each(|(i, b)| {
+                let l = (b[0].to_string()).parse::<u64>().unwrap();
+                blocks.push((start, l, i as u64));
+                start += l;
+                if b.len() > 1 {
+                    let l = (b[1].to_string()).parse::<u64>().unwrap();
+                    free.push((start, l));
+                    start += l;
+                }
+            });
+
+        Self { blocks, free }
+    }
+
+    fn fill_free(self: &mut Self, free_idx: usize, last_block: usize) -> usize {
+        let (free_start, free_length) = self.free[free_idx];
+        if free_length == 0 {
+            return last_block;
+        }
+        let block_idx = last_block + 1;
+        let (block_start, block_length, block_value) = self.blocks.pop().unwrap();
+        if block_length <= free_length {
+            self.blocks.insert(block_idx, (free_start, block_length, block_value));
+            self.free[free_idx].0 += block_length;
+            self.free[free_idx].1 = free_length - block_length;
+        }
+        else {
+            self.blocks.insert(block_idx, (free_start, free_length, block_value));
+            self.blocks.push((block_start, block_length - free_length, block_value));
+            self.free[free_idx].1 = 0;
+        }
+        block_idx
+    }
+
+    fn first_free_idx(self: &Self) -> Option<usize> {
+        self.free.iter().enumerate()
+            .filter(|(_, (_, length))| *length > 0)
+            .map(|(i, _)| i)
+            .nth(0)
+    }
+
+    fn can_compact(self: &Self) -> bool {
+        let last_block = self.blocks.last().unwrap();
+        let last_block_end = last_block.0 + last_block.1 - 1;
+        self.free.iter()
+            .filter(|(_, length)| *length > 0)
+            .any(|(start, _)| *start < last_block_end)
+    }
+
+    fn compact(self: &mut Self) {
+        let mut block_idx = 0;
+        while self.can_compact() {
+            let first_free = self.first_free_idx();
+            if first_free.is_some() {
+                let free_idx = first_free.unwrap();
+                block_idx = self.fill_free(free_idx, block_idx);
+            }
+            else {
+                break;
+            }
+        }
+    }
+}
+
+fn run_part1(input: &str) -> Result<u64, Box<dyn Error>> {
+    println!("Running {} - part 1", get_day());
+
+    let mut puzzle = Puzzle::new(input);
+    puzzle.compact();
+    let res = puzzle.blocks.into_iter()
+        .map(|(start, length, value)| {
+            (start..(start+length)).map(|i| i*value).sum::<u64>()
+        })
+        .sum();
+
+    Ok(res)
+}
+
+fn run_part2(input: &str) -> Result<u64, Box<dyn Error>> {
+    println!("Running {} - part 2", get_day());
+
+    Ok(0)
+}
+
+pub fn run(input: &str) -> Result<(), Box<dyn Error>> {
+    let res = run_part1(&input)?;
+    println!("{res}");
+
+    let res = run_part2(&input)?;
+    println!("{res}");
+
+    Ok(())
+}
+
+fn get_day() -> String {
+    let filename = file!();
+    Path::new(filename).file_stem().unwrap().to_str().unwrap().to_string()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static TEXT_INPUT_0: &str = "\
+12345";
+    static TEXT_INPUT: &str = "\
+2333133121414131402";
+
+    #[test]
+    fn test_part1() {
+        assert_eq!(60, run_part1(TEXT_INPUT_0).unwrap());
+        assert_eq!(1928, run_part1(TEXT_INPUT).unwrap());
+    }
+
+    #[test]
+    fn test_part2() {
+        assert_eq!(0, run_part2(TEXT_INPUT).unwrap());
+    }
+}
diff --git a/src/main.rs b/src/main.rs
index d3f9981..a66cb4d 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -12,6 +12,7 @@ pub mod day05;
 pub mod day06;
 pub mod day07;
 pub mod day08;
+pub mod day09;
 
 fn main() {
     let args: Vec<String> = env::args().collect();
@@ -42,6 +43,7 @@ fn run(day: &str, input_file: &str) -> Result<(), Box<dyn Error>> {
         "day06" => day06::run(&input)?,
         "day07" => day07::run(&input)?,
         "day08" => day08::run(&input)?,
+        "day09" => day09::run(&input)?,
         _ => return Err(format!("unknown or unimplemented day \"{day}\"").into()),
     }
     Ok(())
-- 
2.39.5