Advent Of Code - 2023 - Day 5 - Optimized Solution in Rust

main.rs

use std::fs;
use std::collections::HashMap;
use std::time::Instant;
use itertools::Itertools;

fn apply_mapping(current: u32, map: &Mapping) -> u32 {
    let mut value: u32 = current;

    for entity in &map.mappings {
        if value >= entity.src && value < entity.src + entity.range {
            value = entity.dest + (value - entity.src);
            break;
        }
    }
    return value;
}

fn apply_range_mappings(ranges: &mut Vec<(u32, u32)>, maps: &HashMap<String, Mapping>)  -> Vec<(u32, u32)> {
    let mut ranges_clone = ranges.clone();

    for map_name in ["soil", "fertilizer", "water", "light", "temperature", "humidity", "location"] {
        let mapping = maps.get(map_name).unwrap();
        ranges_clone = apply_range_mapping(&mut ranges_clone, mapping);
    }
    ranges_clone
}

fn apply_range_mapping(ranges: &mut Vec<(u32, u32)>, map: &Mapping) -> Vec<(u32,u32)> {
    let mut new_ranges = vec![];
    let mut i = 0;

    while i < ranges.len() {
        let mut matched = false;
        for entity in &map.mappings {
            let entity_range = (entity.src, entity.src+entity.range);
            let os = ranges[i].0.max(entity_range.0);
            let oe = ranges[i].1.min(entity_range.1);
            if os < oe {
                new_ranges.push((os - entity.src+entity.dest, oe-entity.src+entity.dest));
                matched = true;
                // Check these again for other matches
                if os > ranges[i].0 { ranges.push((ranges[i].0, os)); }
                if ranges[i].1 > oe { ranges.push((oe, ranges[i].1)); }
                // If a match found we can break
                break;
            }
        }
        if !matched { new_ranges.push((ranges[i].0, ranges[i].1)); }
        i+=1;
    }
    new_ranges
}

fn read_file(file: &str) -> Vec<String> {
    fs::read_to_string(file)
        .expect("Unable to open file")
        .split("\n\n")
        .filter(|s| !s.is_empty())
        .map(|s| s.to_string())
        .collect::<Vec<String>>()
}

fn parse_seeds(seeds: String) -> Vec<u32> {
    seeds
        .split_once(": ")
        .unwrap()
        .1
        .split_whitespace()
        .map(|num| num.parse::<u32>().unwrap())
        .collect()
}

fn parse_maps(mut groups: Vec<String>) -> HashMap<String, Mapping> {
    let mut maps:HashMap<String, Mapping> = HashMap::new();

    while let Some(item) = groups.pop() {
        let mut contents = item.split('\n').filter(|str| !str.is_empty()).map(|str| str.to_string()).collect::<Vec<String>>();

        let map_row = contents.remove(0);
        let (_, _, to) = map_row.split_once(' ').unwrap().0.split('-').collect_tuple().unwrap();

        let mappings : Vec<MapRange> = contents
            .iter()
            .map(|line| {
                MapRange::from(line)
            })
            .collect::<Vec<MapRange>>();

        maps.insert(to.to_string(), Mapping { mappings });
    }
    maps
}

#[derive(Debug)]
struct Mapping {
    mappings: Vec<MapRange>
}

#[derive(Debug)]
struct MapRange {
    src: u32,
    dest: u32,
    range: u32
}
impl From<(u32,u32,u32)> for MapRange {
    fn from(value: (u32, u32, u32)) -> Self {
        MapRange {
            src: value.1,
            dest: value.0,
            range: value.2
        }
    }
}
impl From<&String> for MapRange {
    fn from(value: &String) -> Self {
        MapRange::from(
            value
                .split(' ')
                .map(|num| num.parse::<u32>().unwrap())
                .collect_tuple::<(u32,u32,u32)>()
                .unwrap()
        )
    }
}

fn part1(seeds: &Vec<u32>, maps: &HashMap<String, Mapping>) -> u32 {
    let mut part1 = u32::MAX;

    for seed in seeds {
        let mut current = *seed;
        for map_name in ["soil", "fertilizer", "water", "light", "temperature", "humidity", "location"] {
            let mapping = maps.get(map_name).unwrap();
            current = apply_mapping(current, mapping);
        }
        part1 = part1.min(current);
    }

    part1
}

fn part2(seeds: &Vec<u32>, maps: &HashMap<String, Mapping>) -> u32 {
    let mut ranges: Vec<(u32, u32)> = vec![];
    for seed_pair in seeds.chunks(2) {
        ranges.push((seed_pair[0], seed_pair[0] + seed_pair[1] - 1));
    }

    ranges = apply_range_mappings(&mut ranges, maps);
    ranges.sort();

    ranges[0].0
}

fn main() {
    let start = Instant::now();

    let mut groups = read_file("d5");
    let seeds = parse_seeds(groups.remove(0));
    let maps = parse_maps(groups);

    let parse_duration = start.elapsed();

    let part1 = part1(&seeds, &maps);
    let part_1_duration = start.elapsed();

    let part2 = part2(&seeds, &maps);
    let part_2_duration = start.elapsed();

    println!("Parse:");
    println!("Time elapsed: {:?}", parse_duration);
    println!("Part 1: {}", part1);
    println!("Time elapsed: {:?}", part_1_duration);
    println!("Part 2: {:?}", part2);
    println!("Time elapsed: {:?}", part_2_duration);
}