Advent of Code: Day 5, 2023 (Rust)

Link to the GitHub

Link to Advent of Code

Link to Day 4

Story

We made it past the betting-addicted Elf and now we are onto greener pastures… literally. Now we are speaking with the gardener elf who is running an efficient and impressive farming operation. And we also located the source of the water blockage! The farm ran out of filter sand and so they could supply clean snow-making water.

Darn! A text, email, or even a letter weeks ago could have let us save the trouble of these elf escapades.

So now we must wait for a ferry onto another strange place to find sand since no one can be bothered to do their jobs!

In the meantime, we help the farmer with next year’s farming operation. Where to plant seeds based on the type of the seed and its optimal soil, moisture, etc (The puzzle input)

Why should we care or learn from these puzzles?

This is a great question. Not only are you learning to code with Rust or whatever coding language you prefer, but you also are running into common challenges. These include:

1. parsing strings into a structured format
2. Setting up a data-cleaning pipeline
3. Dealing with potentially large and exponentially growing data (Part 2)
4. ETL pipelines

This almanac story problem is neat because it's about taking a piece of data, walking through different transformations, and getting something at the end. This ETL (extract, transform, and load) pipeline is used all the time in companies and real-world data.

Part 1

The first small challenge as always is to parse the puzzle input.

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

We can just iterate over every line and parse the information into two helpful structs:

#[derive(Debug, PartialEq)]
pub struct ConversionChart {
    pub name: String,
    pub conversions: Vec<Conversion>,
}

#[derive(Debug, PartialEq)]
pub struct Conversion {
    pub source: u32,
    pub destination: u32,
    pub range_len: u32,
}

These structures will prove handy because they now encapsulate the data and the meaning behind it.

As for parsing the information, we just need to iterate through the lines, and check if the line is:

1. Empty
2. Contains the word map
3. contains the word seeds
4. Or does it have just three numbers on it

With that logic in mind, we write a simple parsing function.

pub fn read_input(input: &str) -> (Vec<u32>, Vec<ConversionChart>) {
    let mut seeds: Vec<u32> = Vec::new();
    let mut charts: Vec<ConversionChart> = Vec::new();
    // a regex to match the conversion lines, which look like "50 98 2. Three numbers separated by spaces."
    let re = Regex::new(r"(\d+) (\d+) (\d+)").unwrap();
    // a regex to match blank lines with optional newline characters
    let blank_re = Regex::new(r"^\s*\n?$").unwrap();

    // iterate over lines.

    for line in input.lines() {
        // seeds line
        if line.contains("seeds") {
            line.split(":")
                .nth(1)
                .unwrap()
                .split(" ")
                .filter(|s| !s.is_empty())
                .for_each(|s| seeds.push(s.parse::<u32>().unwrap()));
        } else if line.contains("map") {
            // start of a new chart
            let stripped = line.trim().split(" ").nth(0).unwrap();
            charts.push(ConversionChart {
                name: stripped.to_string(),
                conversions: Vec::new(),
            });
        } else if re.is_match(line) {
            // conversion line contains numbers
            let caps = re.captures(line).unwrap();
            let source = caps.get(2).unwrap().as_str().parse::<u32>().unwrap();
            let destination = caps.get(1).unwrap().as_str().parse::<u32>().unwrap();
            let range_len = caps.get(3).unwrap().as_str().parse::<u32>().unwrap();
            let chart = charts.last_mut().unwrap();
            chart.conversions.push(Conversion {
                source,
                destination,
                range_len,
            });
        } else if blank_re.is_match(line) {
            // blank line, do nothing
        } else {
            panic!("Unrecognized line: {}", line);
        }
    }

    (seeds, charts)
}

After writing some unit tests, we can confirm that the parsing is working as expected.

Now onto the actual problem.

We need to take each seed and pass it through the various maps to find its location . Each Seed will have a possible location. We just have to walk each seed through these transformations.

So we are going to make a impl block on the ConversionChart and Conversion :

impl ConversionChart {
    pub fn map_number_to_number(&self, source: &u64) -> u64 {
        let destination: u64 = *source;
        for conversion in &self.conversions {
            let possible = conversion.map_number_to_number(destination);
            // if there is a possible conversion, use it if lower than the current destination
            // TODO can there be multiple mappings for a single seed?
            if let Some(new_destination) = possible {
                return new_destination;
            }
        }
        destination
    }
}

impl Conversion {
    pub fn map_number_to_number(&self, source: u64) -> Option<u64> {
        if source >= self.source && source < self.source + self.range_len {
            Some(source - self.source + self.destination)
        } else {
            None
        }
    }
}

This will cover the cases where there is no matching conversion and so the seed’s conversion value is its current value. One thing I’m not sure of is if there can be a range that matches more than one seed. I didn’t handle that case but it seems to have worked out okay.

So now with these helper functions, writing the solve() isn’t too hard:

pub fn solve(input: &str) {
    let (seeds, charts) = input::read_input(input);

    let answer = seeds
        .iter()
        .map(|seed| map_seed_to_location(seed, &charts))
        .min()
        .unwrap();

    println!("Lowest location is: {}", answer);
}

pub fn map_seed_to_location(seed: &u64, charts: &Vec<input::ConversionChart>) -> u64 {
    let mut location = *seed;
    for chart in charts {
        location = chart.map_number_to_number(&location);
    }
    location
}

Now after running cargo run 5 1 I get an answer of around 993 million! That is the right answer! Woohoo!

Part 2

So at first glance, part two seems not too hard, just a few changes, but I have a bad feeling about it.

Now instead of taking the 20 seeds we have, we have to generate massive ranges of seeds. Just eyeballing the input, we have to generate around 1.8 billion numbers! 1.8 B * 64-bit unsigned integers ( 8 bytes) = 115 B bits (14.4 B bytes) or about 14.4 GB.

Sheesh that is going to blow up my memory!

To confirm our theory, here is my v1 function:

fn convert_seeds_to_ranges(seeds: Vec<u64>) -> HashSet<u64> {
    // chunks(2) will split the vector into pairs
    assert_eq!(seeds.len() % 2, 0);
    seeds
        .chunks(2)
        .map(|pair| {
            let start = pair[0];
            let len = pair[1];
            (start, len)
        })
        .flat_map(|(start, len)| (start..start + len).collect::<Vec<u64>>())
        .collect::<HashSet<u64>>()
}

I run this and get a lovely KILLED message after 25 GB of memory is consumed.

We can’t store 1.8 B items, but we can do 1.8 B operations. We have to calculate, keep the min, the move on. No collecting to a vec .

But wait, we cannot reasonably check all 1.8 B without special computing power (like GPUs or massive parallelization). Some quick benchmark testing shows that every seed takes about 0.00016 s or 160 μs. Checking 1.8 B seeds would still take 80 hours.

Instead, we have to approach this differently. We can think in terms of data flowing through all the conversions. The picture below shows the flow of data as it passes through the conversions. We can see that at each conversion, a range can continue or be broken into sub-ranges. We need to treat this data with ranges and sub-ranges, not with individual data-points (seeds)

https://www.reddit.com/r/adventofcode/comments/18bn2oz/2023_day_5c_first_time_using_paths_in_wpf/

We can walk through each conversion and see if our input range is fully covered, needs to split between multiple conversions, or has to fall back onto the default 1 to 1 conversion.

We have three scenarios:

1. Where a single conversion covers the entire range of the input
2. Where a single conversion covers one end of the input
3. Where a single conversion covers a middle section of the input

Scenario 1

Scenario 2

Scenario 3

Let's code this into the impl blocks

First, each Conversion needs to take in a Range and return RangeMapping

#[derive(PartialEq, Debug)]
struct RangeMapping {
    converted_range: Option<Range<u64>>,
    unconverted_ranges: Vec<Range<u64>>,
}

This allows the return type to be one of the three scenarios described above.

impl Conversion {

    fn map_range_to_ranges(&self, range: Range<u64>) -> RangeMapping {
        // scenario 4: range is entirely outside the source range
        if (range.end < self.source) || (range.start > self.source + self.range_len) {
            return RangeMapping {
                converted_range: None,
                unconverted_ranges: vec![range],
            };
        } else if (range.start >= self.source) && (range.end <= self.source + self.range_len) {
            // scenario 1: range is entirely within the source range
            let converted_range = range.start - self.source + self.destination
                ..range.end - self.source + self.destination;
            RangeMapping {
                converted_range: Some(converted_range),
                unconverted_ranges: Vec::new(),
            }
        } else if range.start < self.source {
            if range.end <= self.source + self.range_len {
                // scenario 2.1: range starts before the source range, but ends within it
                let converted_range = self.destination..range.end - self.source + self.destination;
                let unconverted_range = range.start..self.source;
                RangeMapping {
                    converted_range: Some(converted_range),
                    unconverted_ranges: vec![unconverted_range],
                }
            } else {
                // scenario 3: range starts before the source range, and ends after source + len
                let converted_range = self.destination
                    ..self.destination + self.range_len;
                let left_unconverted_range = range.start..self.source;
                let right_unconverted_range = self.source + self.range_len..range.end;
                RangeMapping {
                    converted_range: Some(converted_range),
                    unconverted_ranges: vec![left_unconverted_range, right_unconverted_range],
                }
            }
        } else {
            // scenario 2.2: range starts after the source range, and ends after it
            let converted_range =
                self.destination..self.destination + (self.range_len - (range.start - self.source));
            let unconverted_range = self.source + self.range_len..range.end;
            RangeMapping {
                converted_range: Some(converted_range),
                unconverted_ranges: vec![unconverted_range],
            }
        }
    }
}

With that bit of code out of the way, now we can have our conversion chart keep track of taking a Range and passing it through all the levels of conversion.

impl ConversionChart {
    
    pub fn map_range_to_ranges(&self, range: Range<u64>) -> Vec<Range<u64>> {
        // go through each conversion and try to map the range to it
        // if there is a match, return the converted range + recurse on the unconverted ranges
        for conversion in &self.conversions {
            let mapping = conversion.map_range_to_ranges(range.clone());
            if let Some(converted_range) = mapping.converted_range
            {
                // Recursively process unconverted ranges
                let mut result_ranges = vec![converted_range];
                let recursive_results: Vec<Range<_>> = mapping
                    .unconverted_ranges
                    .iter()
                    .flat_map(|r| self.map_range_to_ranges(r.clone()))
                    .collect();
                result_ranges.extend(recursive_results);
                return result_ranges;
            }
        }

        // If no conversion matches, return the original range
        vec![range]
    }
    
}

Finally, we just iterate through each range through each layer of conversion, then sort the ranges, and get the start of the lowest range.

All done!

Review

• That was a tough one!
• Working with ranges is much easier than working with individual data points. This is also true when working with log data and other time series data that doesn’t change much over a point in time
• It is incredible how these problems go from easy to insanely hard and you have to reengineer the whole approach.

Rustaceans 🚀

Thank you for being a part of the Rustaceans community! Before you go:

• Show your appreciation with a clap and follow the publication
• Discover how you can contribute your own insights to Rustaceans.
• Connect with us: X | Weekly Rust Newsletter