this post was submitted on 05 Dec 2023
34 points (100.0% liked)

Advent Of Code

768 readers
1 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 2023

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
 

Day 5: If You Give a Seed a Fertilizer


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)
  • Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ


πŸ”’This post will be unlocked when there is a decent amount of submissions on the leaderboard to avoid cheating for top spots

πŸ”“ Unlocked after 27 mins (current record for time, hard one today)

you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 3 points 11 months ago* (last edited 11 months ago) (1 children)

Like many others, I really didn't enjoy this one. I particularly struggled with part 02, which ended up with me just brute forcing it and checking each seed. On my system it took over 15 minutes to run, which is truly awful. I'm open to pointers on how I could better have solved part two.

Solution in Rust πŸ¦€

Formatted Solution on GitLab

Code

use std::{
    env, fs,
    io::{self, BufReader, Read},
};

fn main() -> io::Result<()> {
    let args: Vec = env::args().collect();
    let filename = &args[1];
    let file1 = fs::File::open(filename)?;
    let file2 = fs::File::open(filename)?;
    let mut reader1 = BufReader::new(file1);
    let mut reader2 = BufReader::new(file2);

    println!("Part one: {}", process_part_one(&mut reader1));
    println!("Part two: {}", process_part_two(&mut reader2));
    Ok(())
}

#[derive(Debug)]
struct Map {
    lines: Vec,
}

impl Map {
    fn map_to_lines(&self, key: u32) -> u32 {
        for line in &self.lines {
            if line.in_range(key) {
                return line.map(key);
            }
        }
        key
    }
}

#[derive(Debug)]
struct MapLine {
    dest_range: u32,
    source_range: u32,
    range_length: u32,
}

impl MapLine {
    fn map(&self, key: u32) -> u32 {
        let diff = key - self.source_range;
        if self.dest_range as i64 + diff as i64 > 0 {
            return (self.dest_range as i64 + diff as i64) as u32;
        }
        key
    }

    fn in_range(&self, key: u32) -> bool {
        self.source_range <= key
            && (key as i64) < self.source_range as i64 + self.range_length as i64
    }
}

fn parse_input(reader: &amp;mut BufReader) -> (Vec, Vec<map>) {
    let mut almanac = String::new();
    reader
        .read_to_string(&amp;mut almanac)
        .expect("read successful");
    let parts: Vec&lt;&amp;str> = almanac.split("\n\n").collect();
    let (seeds, others) = parts.split_first().expect("at least one part");
    let seeds: Vec&lt;_> = seeds
        .split(": ")
        .last()
        .expect("at least one")
        .split_whitespace()
        .map(|s| s.to_string())
        .collect();
    let maps: Vec&lt;_> = others
        .iter()
        .map(|item| {
            let lines_iter = item
                .split(':')
                .last()
                .expect("exists")
                .trim()
                .split('\n')
                .map(|nums| {
                    let nums_split = nums.split_whitespace().collect::>();
                    MapLine {
                        dest_range: nums_split[0].parse().expect("is digit"),
                        source_range: nums_split[1].parse().expect("is digit"),
                        range_length: nums_split[2].parse().expect("is digit"),
                    }
                });
            Map {
                lines: lines_iter.collect(),
            }
        })
        .collect();
    (seeds, maps)
}

fn process_part_one(reader: &amp;mut BufReader) -> u32 {
    let (seeds, maps) = parse_input(reader);
    let mut res = u32::MAX;
    for seed in &amp;seeds {
        let mut val = seed.parse::().expect("is digits");
        for map in &amp;maps {
            val = map.map_to_lines(val);
        }
        res = u32::min(res, val);
    }
    res
}

fn process_part_two(reader: &amp;mut BufReader) -> u32 {
    let (seeds, maps) = parse_input(reader);
    let seed_chunks: Vec&lt;_> = seeds.chunks(2).collect();
    let mut res = u32::MAX;
    for chunk in seed_chunks {
        let range_start: u32 = chunk[0].parse().expect("is digits");
        let range_length: u32 = chunk[1].parse().expect("is digits");
        let range_end: u32 = range_start + range_length;
        for seed in range_start..range_end {
            let mut val = seed;
            for map in &amp;maps {
                val = map.map_to_lines(val);
            }
            res = u32::min(res, val);
        }
    }
    res
}

#[cfg(test)]
mod tests {
    use super::*;

    const INPUT: &amp;str = "seeds: 79 14 55 13

seed-to-soil map:
50 98 2
52 50 48

soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15

fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4

water-to-light map:
88 18 7
18 25 70

light-to-temperature map:
45 77 23
81 45 19
68 64 13

temperature-to-humidity map:
0 69 1
1 0 69

humidity-to-location map:
60 56 37
56 93 4";

    #[test]
    fn test_process_part_one() {
        let input_bytes = INPUT.as_bytes();
        assert_eq!(35, process_part_one(&amp;mut BufReader::new(input_bytes)));
    }

    #[test]
    fn test_process_part_two() {
        let input_bytes = INPUT.as_bytes();
        assert_eq!(46, process_part_two(&amp;mut BufReader::new(input_bytes)));
    }
}

[–] [email protected] 5 points 11 months ago (1 children)

I got far enough to realize that you probably needed to work backwards and given a location, determine the accompanying seed, and then check if that seed is one of the ones listed in the range. Still though, starting at 0 for location and working up was taking forever to find the first valid seed

Someone in this thread pointed out that if you picked the first value of each range in the map, working backwards from those points will get you a short list of seeds which map to low values. You then check if those seeds are valid, and also check the location of the first seeds in the range (the rest of the seeds in the range don't matter because those are covered by the first check). This ends up with about 200 locations which you can sort, to get the lowest value.

[–] [email protected] 3 points 11 months ago

I tried brute forcing it but couldn't get the process to finish. Iterating through hundreds of millions of seeds is no bueno.

After reading your comment though I got the idea to map whole seed ranges instead of individual seeds. That finished in no time of course.