advent_of_code_2023_05_rust

lib.rs

pub mod parser;
pub mod ranges;

use parser::{Input, RemapRule};

use crate::ranges::apply_ruleset_remaps;

impl RemapRule {
    pub fn remap(&self, num: u64) -> u64 {
        let src_range = self.source_range();

        if src_range.contains(&num) {
            let offset = num - src_range.start;
            let res = self.destination_range().start + offset;
            return res;
        }
        return num;
    }
}

pub fn part1(input: &str) -> u64 {
    let inp = Input::new(input);
    let remap_rules = inp.get_sorted_remaps();

    // For every seed, apply every matching rule, getting us to location nums
    let location_nums_it = inp.get_seeds().into_iter().map(|&seed_id| {
        remap_rules.iter().fold(seed_id, |seed_id, rules| {
            let rule = rules
                .iter()
                .find(|rule| rule.source_range().contains(&seed_id));
            rule.map_or(seed_id, |rule| rule.remap(seed_id))
        })
    });

    let locations = location_nums_it.clone().collect::<Vec<_>>();
    dbg!(locations);

    // Get the smallest location number.
    location_nums_it.min().unwrap()
}
pub fn part2(input: &str) -> u64 {
    let inp = Input::new(input);
    let remap_rule_sets: Vec<&Vec<RemapRule>> = inp.get_sorted_remaps();
    let remap_rule_sets: Vec<Vec<RemapRule>> =
        remap_rule_sets.iter().map(|&v| v.to_owned()).collect();

    let location_ranges_it = inp
        .get_seed_ranges()
        .into_iter()
        .map(|seed_range| {
            let x = apply_ruleset_remaps(seed_range.clone(), &remap_rule_sets);
            println!("Remapped seed range {seed_range:?} -> {x:?}");
            x.into_iter()
        })
        .flatten();

    let location_ranges = location_ranges_it.collect::<Vec<_>>();
    dbg!(&location_ranges);

    let smallest_location = location_ranges
        .into_iter()
        .fold(u64::MAX, |cur_min, range| cur_min.min(range.start));

    smallest_location
}

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

    static TEST_INPUT: &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_part1() {
        assert_eq!(part1(TEST_INPUT), 35);
    }

    #[test]
    fn test_part2() {
        assert_eq!(part2(TEST_INPUT), 46);
    }
}

main.rs

use std::{fs::File, io::Read};

use aoc::{part1, part2};

fn main() {
    let mut file = File::open("input.txt").unwrap();
    let mut contents = String::new();
    file.read_to_string(&mut contents).unwrap();

    let ans1 = part1(&contents);
    println!("Part 1 ans: {}", ans1);

    let ans2 = part2(&contents);
    println!("Part 2 ans: {}", ans2);
}

parser.rs

use std::{collections::HashMap, ops::Range};

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct RemapRule {
    source_range_start: u64,
    destination_range_start: u64,
    range_length: u64,
}

impl RemapRule {
    pub fn new(source_range_start: u64, destination_range_start: u64, range_length: u64) -> Self {
        return Self {
            source_range_start,
            destination_range_start,
            range_length,
        };
    }

    pub fn destination_range(&self) -> Range<u64> {
        self.destination_range_start..(self.destination_range_start + self.range_length)
    }

    pub fn source_range(&self) -> Range<u64> {
        self.source_range_start..(self.source_range_start + self.range_length)
    }
}

#[derive(Debug)]
pub struct Input {
    seeds: Vec<u64>,
    category_remaps: HashMap<String, Vec<RemapRule>>,
}

impl Input {
    pub fn new(input: &str) -> Self {
        let mut lines_it = input.lines();

        let seeds: Vec<u64> = lines_it
            .next()
            .unwrap()
            .split(" ")
            .skip(1)
            .map(|x| x.parse::<u64>().unwrap())
            .collect();

        let mut category_maps: HashMap<String, Vec<RemapRule>> = HashMap::new();
        let mut last_cat = "";
        for line in lines_it {
            if line.ends_with(":") {
                last_cat = line.strip_suffix(" map:").unwrap();
                category_maps.insert(last_cat.to_owned(), vec![]);

                continue;
            }
            if line.is_empty() {
                continue;
            }

            let nums_vec: Vec<u64> = line
                .split(" ")
                .skip_while(|x| *x == " ")
                .map(|x| x.parse::<u64>().unwrap())
                .collect();

            // source before destination, the other way is way too confusing
            let nums = RemapRule::new(nums_vec[1], nums_vec[0], nums_vec[2]);

            category_maps.get_mut(last_cat).unwrap().push(nums);
        }

        return Self {
            seeds,
            category_remaps: category_maps,
        };
    }

    pub fn get_seeds(&self) -> &Vec<u64> {
        return &self.seeds;
    }

    pub fn get_seed_ranges(&self) -> Vec<Range<u64>> {
        self.seeds
            .chunks(2)
            .map(|chunk| chunk[0]..(chunk[0] + chunk[1]))
            .collect()
    }

    pub fn get_sorted_remaps(&self) -> Vec<&Vec<RemapRule>> {
        let categories = [
            "seed-to-soil",
            "soil-to-fertilizer",
            "fertilizer-to-water",
            "water-to-light",
            "light-to-temperature",
            "temperature-to-humidity",
            "humidity-to-location",
        ];

        categories
            .into_iter()
            .map(|cat| self.category_remaps.get(cat).unwrap())
            .collect::<Vec<&Vec<RemapRule>>>()
    }
}

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

    static TEST_INPUT: &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_seeds() {
        let inp = Input::new(TEST_INPUT);
        let seeds = inp.get_seeds();
        assert_eq!(*seeds, vec![79, 14, 55, 13]);
    }

    #[test]
    fn test_maps() {
        let inp = Input::new(TEST_INPUT);
        let ranges = inp.get_sorted_remaps();
        let expected_ranges = vec![
            vec![RemapRule::new(98, 50, 2), RemapRule::new(50, 52, 48)],
            vec![
                RemapRule::new(15, 0, 37),
                RemapRule::new(52, 37, 2),
                RemapRule::new(0, 39, 15),
            ],
            vec![
                RemapRule::new(53, 49, 8),
                RemapRule::new(11, 0, 42),
                RemapRule::new(0, 42, 7),
                RemapRule::new(7, 57, 4),
            ],
            vec![RemapRule::new(18, 88, 7), RemapRule::new(25, 18, 70)],
            vec![
                RemapRule::new(77, 45, 23),
                RemapRule::new(45, 81, 19),
                RemapRule::new(64, 68, 13),
            ],
            vec![RemapRule::new(69, 0, 1), RemapRule::new(0, 1, 69)],
            vec![RemapRule::new(56, 60, 37), RemapRule::new(93, 56, 4)],
        ];

        assert!(ranges.iter().zip(&expected_ranges).all(|(&x, y)| x == y));
    }
}

ranges.rs

use std::{
    cmp::{max, min},
    collections::HashSet,
    ops::Range,
};

use crate::parser::RemapRule;

impl RemapRule {
    fn remap_range(&self, range: Range<u64>) -> (Vec<Range<u64>>, Option<Range<u64>>) {
        let src_range = self.source_range();
        let dst_range = self.destination_range();

        // Case 1: No overlap with the source range
        if range.end <= src_range.start || range.start >= src_range.end {
            return (vec![range], None);
        }

        let mut leftover_ranges = Vec::new();

        // Case 2: Partial overlap - before the source range
        if range.start < src_range.start {
            leftover_ranges.push(range.start..src_range.start);
        }

        // Calculate the offset for remapping
        let offset = dst_range.start as i64 - src_range.start as i64;

        // Case 3: Overlap - remap the overlapping part
        let overlap_start = max(range.start, src_range.start);
        let overlap_end = min(range.end, src_range.end);
        let remapped_start = (overlap_start as i64 + offset) as u64;
        let remapped_end = (overlap_end as i64 + offset) as u64;
        let remapped_range = Some(remapped_start..remapped_end);

        // Case 4: Partial overlap - after the source range
        if range.end > src_range.end {
            leftover_ranges.push(src_range.end..range.end);
        }

        (leftover_ranges, remapped_range)
    }
}

pub fn apply_ruleset_remaps(
    input_range: Range<u64>,
    rule_sets: &[Vec<RemapRule>],
) -> HashSet<Range<u64>> {
    rule_sets.iter().fold(
        HashSet::from([input_range]),
        |mut current_ranges, rule_set| {
            let mut new_ranges = HashSet::new();

            for rule in rule_set {
                current_ranges = current_ranges
                    .into_iter()
                    .flat_map(|range| {
                        let (leftover, remapped) = rule.remap_range(range);
                        if let Some(remapped_range) = remapped {
                            new_ranges.insert(remapped_range);
                        }
                        leftover.into_iter()
                    })
                    .collect();
            }

            current_ranges.extend(new_ranges);
            current_ranges
        },
    )

    // let mut current_ranges = vec![input_range];
    //
    // for rule_set in rule_sets {
    //     let mut remapped_ranges = HashSet::new();
    //
    //     for rule in rule_set {
    //         let mut remaining_ranges = Vec::new();
    //
    //         for range in &current_ranges {
    //             let (leftover, remapped) = rule.remap_range(range.clone());
    //
    //             if let Some(remapped_range) = remapped {
    //                 remapped_ranges.insert(remapped_range);
    //             }
    //
    //             remaining_ranges.extend(leftover);
    //         }
    //
    //         current_ranges = remaining_ranges;
    //     }
    //
    //     current_ranges.extend(remapped_ranges)
    // }
    //
    // return current_ranges.into_iter().collect();
}

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

    #[test]
    fn no_overlap() {
        let rule = RemapRule::new(30, 50, 10);
        let range = 0..15;
        let expected = (vec![0..15], None);
        assert_eq!(rule.remap_range(range), expected);
    }

    #[test]
    fn partial_overlap_from_left() {
        let rule = RemapRule::new(0, 50, 10);
        let range = 0..20;
        let expected = (vec![10..20], Some(50..60));
        assert_eq!(rule.remap_range(range), expected);
    }

    #[test]
    fn partial_overlap_from_right() {
        let rule = RemapRule::new(10, 50, 10);
        let range = 0..20;
        let expected = (vec![0..10], Some(50..60));
        assert_eq!(rule.remap_range(range), expected);
    }

    #[test]
    fn full_overlap_same_length() {
        let rule = RemapRule::new(5, 25, 10);
        let range = 5..15;
        let expected = (Vec::new(), Some(25..35));
        assert_eq!(rule.remap_range(range), expected);
    }

    #[test]
    fn full_overlap_starts_before() {
        let rule = RemapRule::new(0, 25, 15);
        let range = 5..15;
        let expected = (Vec::new(), Some(30..40));
        assert_eq!(rule.remap_range(range), expected);
    }

    #[test]
    fn full_overlap_ends_after() {
        let rule = RemapRule::new(5, 25, 20);
        let range = 5..15;
        let expected = (Vec::new(), Some(25..35));
        assert_eq!(rule.remap_range(range), expected);
    }

    #[test]
    fn full_overlap_starts_before_and_ends_after() {
        let rule = RemapRule::new(0, 25, 20);
        let range = 5..15;
        let expected = (Vec::new(), Some(30..40));
        assert_eq!(rule.remap_range(range), expected);
    }

    #[test]
    fn contained_within_range() {
        let rule = RemapRule::new(5, 50, 5);
        let range = 0..20;
        let expected = (vec![0..5, 10..20], Some(50..55));
        assert_eq!(rule.remap_range(range), expected);
    }
}

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

    #[test]
    fn empty_rule_sets() {
        let input_range = 0..100;
        let rule_sets = vec![];
        let expected = HashSet::from([0..100]);
        assert_eq!(apply_ruleset_remaps(input_range, &rule_sets), expected);
    }

    #[test]
    fn single_rule_single_set() {
        let input_range = 0..100;
        let rule_sets = vec![
            vec![RemapRule::new(10, 100, 20)], // Remaps 10..30 to 100..120
        ];
        let expected = HashSet::from([0..10, 100..120, 30..100]);
        assert_eq!(apply_ruleset_remaps(input_range, &rule_sets), expected);
    }

    #[test]
    fn multiple_sets_non_overlapping() {
        let input_range = 0..100;
        let rule_sets = vec![
            vec![RemapRule::new(0, 100, 50)],  // Remaps 0..50 to 100..150
            vec![RemapRule::new(50, 200, 50)], // Remaps 50..100 to 200..250
        ];
        let expected = HashSet::from([100..150, 200..250]);
        assert_eq!(apply_ruleset_remaps(input_range, &rule_sets), expected);
    }

    #[test]
    fn multiple_sets_overlapping() {
        let input_range = 0..100;
        let rule_sets = vec![
            vec![RemapRule::new(0, 200, 50)], // Remaps 0..50 to 200..250 -> 200..250, 50..100
            vec![RemapRule::new(25, 100, 50)], // Remaps 25..75 to 100..150 -> 200..250, 50..75 -> 125..150, 75..100
        ];
        let expected = HashSet::from([200..250, 125..150, 75..100]);
        assert_eq!(apply_ruleset_remaps(input_range, &rule_sets), expected);
    }

    #[test]
    fn sets_with_unmatched_ranges() {
        let input_range = 0..100;
        let rule_sets = vec![
            vec![RemapRule::new(100, 200, 50)], // No matching range
            vec![RemapRule::new(200, 300, 50)], // No matching range
        ];
        let expected = HashSet::from([0..100]); // Input range should remain unchanged
        assert_eq!(apply_ruleset_remaps(input_range, &rule_sets), expected);
    }

    #[test]
    fn complex_scenario_multiple_sets() {
        let input_range = 0..200;
        let rule_sets = vec![
            vec![
                RemapRule::new(0, 300, 50), // Remaps 0..50 to 300..350 -> 300..350, rem 50..200
                RemapRule::new(100, 400, 50), // Remaps 100..150 to 400..450 -> 400..450, rem 50..100, 150..200
            ], // -> 300..350, 400..450, 50..100, 150..200
            vec![
                RemapRule::new(350, 500, 25), // Remaps 350..375 to 500..525 -> None, rem 300..350, 400..450, 50..100, 150..200
            ], // -> 300..350, 400..450, 50..100, 150..200
            vec![
                RemapRule::new(400, 600, 25), // Remaps 400..425 to 600..625 -> 600..625, rem 300..350, 425..450, 50..100, 150..200
                RemapRule::new(425, 800, 25), // Remaps 425..450 to 800..825 -> 800..825, rem 300..350, 50..100, 150..200
            ], // -> 600..625, 800..825, 300..350, 50..100, 150..200
        ];
        let expected = HashSet::from([600..625, 800..825, 300..350, 50..100, 150..200]);
        assert_eq!(apply_ruleset_remaps(input_range, &rule_sets), expected);
    }
}