this post was submitted on 09 Dec 2024
24 points (96.2% liked)

Advent Of Code

987 readers
14 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
Ategon@programming.dev
Sigmatics@lemmy.ca
CameronDev@programming.dev
24
๐Ÿ’ฟ - 2024 DAY 9 SOLUTIONS -๐Ÿ’ฟ (programming.dev)
submitted 2 weeks ago* (last edited 2 weeks ago) by CameronDev@programming.dev to c/advent_of_code@programming.dev
49 comments fedilink hide all child comments
 

Day 9: Disk Fragmenter

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

you are viewing a single comment's thread
view the rest of the comments
[โ€“] CameronDev@programming.dev 2 points 2 weeks ago* (last edited 2 weeks ago) (1 children)

Rust

Pretty poor performance on part 2, was initially 10s, got down to 2.5s, but still seems pretty poor.

#[cfg(test)]
mod tests {
    fn checksum(p0: &[i64]) -> i64 {
        let mut csum = 0;
        for (i, val) in p0.iter().enumerate() {
            if *val == -1 {
                continue;
            }
            csum += *val * (i as i64);
        }
        csum
    }

    fn defrag(p0: &[i64]) -> Vec<i64> {
        let mut start = 0;
        let mut end = p0.len() - 1;

        let mut defragged = vec![];

        while start != end + 1 {
            if p0[start] != -1 {
                defragged.push(p0[start]);
                start += 1;
                continue;
            }
            if p0[start] == -1 {
                defragged.push(p0[end]);
                start += 1;
                end -= 1;
                while p0[end] == -1 {
                    end -= 1;
                }
            }
        }
        defragged
    }

    fn expand_disk(p0: &str) -> Vec<i64> {
        let mut disk = vec![];
        let mut file_index = 0;
        let mut is_file = true;
        for char in p0.chars() {
            let val = char.to_digit(10).unwrap();
            if is_file {
                for _ in 0..val {
                    disk.push(file_index)
                }
                file_index += 1;
            } else {
                for _ in 0..val {
                    disk.push(-1)
                }
            }
            is_file = !is_file;
        }
        disk
    }
    #[test]
    fn day9_part1_test() {
        let input: String = std::fs::read_to_string("src/input/day_9.txt")
            .unwrap()
            .trim()
            .into();

        let disk: Vec<i64> = expand_disk(&input);

        let defraged = defrag(&disk);

        let checksum = checksum(&defraged);

        println!("{}", checksum);
    }

    fn find_file(p0: &[i64], file: i64) -> (usize, usize) {
        let mut count = 0;
        let mut i = p0.len() - 1;
        while i > 0 && p0[i] != file {
            i -= 1;
        }
        // At end of file
        while i > 0 && p0[i] == file {
            count += 1;
            i -= 1;
        }
        (i + 1, count)
    }

    fn find_slot(p0: &[i64], size: usize, end: usize) -> Option<usize> {
        let mut i = 0;
        while i < end {
            while p0[i] != -1 && i < end {
                i += 1;
            }
            let mut count = 0;
            while p0[i] == -1 && i < end {
                i += 1;
                count += 1;
                if count == size {
                    return Some(i - count);
                }
            }
        }
        None
    }

    fn move_file(p0: &mut [i64], file: i64, size: usize, old_pos: usize, new_pos: usize) {
        for i in 0..size {
            p0[old_pos + i] = -1;
            p0[new_pos + i] = file;
        }
    }

    fn defrag2(p0: &mut [i64]) {
        let mut i = *p0.last().unwrap();
        while i > 0 {
            let (old_pos, size) = find_file(p0, i);
            match find_slot(p0, size, old_pos) {
                None => {}
                Some(new_pos) => {
                    if new_pos < old_pos {
                        move_file(p0, i, size, old_pos, new_pos);
                    }
                }
            }
            i -= 1;
        }
    }

    #[test]
    fn day9_part2_test() {
        let input: String = std::fs::read_to_string("src/input/day_9.txt")
            .unwrap()
            .trim()
            .into();

        let mut disk: Vec<i64> = expand_disk(&input);

        defrag2(&mut disk);

        let checksum = checksum(&disk);

        println!("{}", checksum);
    }
}
[โ€“] CameronDev@programming.dev 2 points 2 weeks ago* (last edited 2 weeks ago) (1 children)

Found a cheaty way to get sub 1s:

    fn defrag2(p0: &mut [i64]) {
        let mut i = *p0.last().unwrap();
        while i > 3000 {  // Stop defragging here, probably cant find free spots after this point
            let (old_pos, size) = find_file(p0, i);
            if let Some(new_pos) = find_slot(p0, size, old_pos) {
                move_file(p0, i, size, old_pos, new_pos);
            }
            i -= 1;
        }
    }

Might be possible to correctly do this in the find_slot code, so that if it fails to find a slot, it never searches for that size again.

edit:

fn defrag2(p0: &mut [i64]) {
        let mut i = *p0.last().unwrap();
        let mut max_size = 10;
        while i > 0 {
            let (old_pos, size) = find_file(p0, i);
            if size <= max_size {
                if let Some(new_pos) = find_slot(p0, size, old_pos) {
                    move_file(p0, i, size, old_pos, new_pos);
                } else {
                    max_size = size - 1;
                }
            }
            if max_size == 0 {
                return;
            }
            i -= 1;
        }
    }

500ms, I can go to sleep now.

[โ€“] CameronDev@programming.dev 2 points 2 weeks ago

haha, kept going at it, got it down to 4ms, by tracking where the searches ended, and starting from there next time.

Definitely done now :D