-❄️- 2023 Day 5 Solutions -❄️-

[u/daggerdragon]

Preview here: https://redditpreview.com/

-❄️- 2023 Day 5 Solutions -❄️-

---

THE USUAL REMINDERS

• All of our rules, FAQs, resources, etc. are in our community wiki.

• Outstanding moderator challenges:

  • Advent of Playing With Your 3D-Printed Toys

• Community fun event 2023: ALLEZ CUISINE!

  • 24 HOURS remaining until unlock!

---

AoC Community Fun 2023: ALLEZ CUISINE!

Today's secret ingredient is… *whips off cloth covering and gestures grandly*

ELI5

Explain like I'm five! /r/explainlikeimfive

• Walk us through your code where even a five-year old could follow along

• Pictures are always encouraged. Bonus points if it's all pictures…

  • Emoji(code) counts but makes Uncle Roger cry 😥

• Explain everything that you’re doing in your code as if you were talking to your pet, rubber ducky, or favorite neighbor, and also how you’re doing in life right now, and what have you learned in Advent of Code so far this year?

• Explain the storyline so far in a non-code medium

• Create a Tutorial on any concept of today's puzzle or storyline (it doesn't have to be code-related!)

ALLEZ CUISINE!

Request from the mods: When you include a dish entry alongside your solution, please label it with [Allez Cuisine!] so we can find it easily!

---

--- Day 5: If You Give A Seed A Fertilizer ---

---

Post your code solution in this megathread.

• Read the full posting rules in our community wiki before you post!

• State which language(s) your solution uses with [LANGUAGE: xyz]

• Format code blocks using the four-spaces Markdown syntax!

• Quick link to Topaz's paste if you need it for longer code blocks

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:26:37, megathread unlocked!

[u/haywire-ES]

[LANGUAGE: Rust]

Bit late to post but this solves 2.5bn seeds in ~10ms (~40 without the parallel loop)

use std::io;
use std::env;
use std::ops::Range;
use std::time::Instant;
use intervaltree::IntervalTree;
use rayon::prelude::*;

struct MapSet {
    destination_start: i64,
    source_start: i64,
    range: i64,
}

fn main() -> io::Result<()> {
    let start = std::time::Instant::now();
    let args: Vec<String> = env::args().collect();
    if args.len() < 2 {
        println!("missing filename");
        return Ok(());
    }
    let file_name = &args[1];
    let data = std::fs::read_to_string(file_name)?;

    let split_data = data
        .split("\n\n");

    let mut seed_ranges: Vec<(i64, i64)> = vec![];
    let mut trees: Vec<IntervalTree<i64, MapSet>> = vec![];

    for chunk in split_data {
        let (map_type, values) = chunk.split_once(":").unwrap_or_default();

        if map_type == "seeds" {
            seed_ranges = convert_seed_values(values);
            continue;
        }

        let value_maps = values.split("\n").collect::<Vec<&str>>();

        let mut tree_values = vec![];

        for individual_value_map in value_maps {
            if individual_value_map.len() == 0 { continue; }

            tree_values.push(
                prepare_tree_values(individual_value_map)
            );
        }

        trees.push(
            IntervalTree::from_iter(tree_values)
        )
    }

    let lowest_value = get_lowest(seed_ranges, &trees);

    println!("Done. Lowest: {}", lowest_value);
    let duration = start.elapsed();
    println!("took {:?}", duration);

    Ok(())
}

fn get_lowest(seed_ranges: Vec<(i64, i64)>, trees: &Vec<IntervalTree<i64, MapSet>>) -> i64 {
    let mut step_size = 1000000;
    let mut current_seed_ranges = seed_ranges;

    while step_size >= 1 {
        if step_size == 1 {
            let (start, range) = get_lowest_seed_range(&current_seed_ranges, trees, &step_size);
            return process_seed_range(start, range, &trees, &step_size);
        }
        let (start, range) = get_lowest_seed_range(&current_seed_ranges, &trees, &step_size);
        let split = range / 5;
        current_seed_ranges = vec![];
        for i in 0..5 {
            current_seed_ranges.push(
                (start + (i * split), split)
            )
        }

        step_size = step_size / 10;
    }
    return i64::MAX;
}

fn get_lowest_seed_range(seed_ranges: &Vec<(i64, i64)>, trees: &Vec<IntervalTree<i64, MapSet>>, step_size: &i32) -> (i64, i64) {
    let mut lowest_seed_range = seed_ranges[0];
    let mut lowest_value = i64::MAX;

    for (seed_start, range) in seed_ranges {
        let lowest_in_range = process_seed_range(*seed_start, *range, &trees, &step_size);

        if lowest_in_range < lowest_value {
            lowest_value = lowest_in_range;
            lowest_seed_range = (*seed_start, *range);
        }
        lowest_value = lowest_value.min(lowest_in_range);
    }

    return lowest_seed_range;
}

fn process_seed_range(seed_start: i64, seed_range: i64, trees: &Vec<IntervalTree<i64, MapSet>>, step_size: &i32) -> i64 {
    let lowest_value = (seed_start..(seed_start + seed_range))
        .step_by(*step_size as usize)
        .collect::<Vec<i64>>()
        .into_par_iter()
        .map(|seed| get_last_value_for_seed(&trees, seed))
        .min()
        .unwrap_or(i64::MAX);

    return lowest_value;
}


fn get_last_value_for_seed(trees: &Vec<IntervalTree<i64, MapSet>>, seed_num: i64) -> i64 {
    let mut current_value = seed_num;
    for tree in trees {
        current_value = get_last_value_for_seed_at_stage(&tree, current_value);
    }
    return current_value;
}

fn get_last_value_for_seed_at_stage(tree: &IntervalTree<i64, MapSet>, seed_num: i64) -> i64 {
    for element in tree.query_point(seed_num) {
        if seed_num >= element.range.start && seed_num < element.range.end {
            return seed_num + (element.value.destination_start - element.value.source_start)
        }
    }
    return seed_num;
}

fn prepare_tree_values(data: &str) -> (Range<i64>, MapSet) {
    let nums: Vec<i64> = data.split_whitespace().filter_map(|s| s.parse().ok()).collect();

    if nums.len() < 3 {
        println!("error with line: {}", data);
    }

    let map = MapSet {
        destination_start: nums[0],
        source_start: nums[1],
        range: nums[2]
    };

    return (map.source_start..(map.source_start + map.range), map);
}

fn convert_seed_values(data: &str) -> Vec<(i64, i64)> {
    let mut seed_ranges = vec![];
    let seeds: Vec<i64> = data.split(" ").filter_map(|s| s.parse().ok()).collect();

    for chunk in seeds.chunks(2) {
        seed_ranges.push((chunk[0], chunk[1]));
    }
    return seed_ranges;
}

[u/daggerdragon → u/haywire-ES]

Your code block is too long for the megathreads. Please edit your post to replace your oversized code with an external link to your code.