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)

  • bugsmith@programming.dev
    3·
    1 year ago

    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)));
    }
}

    :::</map>

    • bamboo@lemmy.blahaj.zoneEnglish
      5·
      1 year ago

      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.

      • walter_wiggles@lemmy.nz
        3·
        1 year 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.