From 10ef3d47f4501af20d9e8e63823bda38e2fd4017 Mon Sep 17 00:00:00 2001 From: Jordan Doyle Date: Thu, 7 Dec 2023 00:32:05 +0000 Subject: [PATCH] Add day 5 --- 5.rs | 257 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 257 insertions(+) create mode 100755 5.rs diff --git a/5.rs b/5.rs new file mode 100755 index 0000000..65839c4 --- /dev/null +++ b/5.rs @@ -0,0 +1,257 @@ +#!/usr/bin/env nix-shell +//! ```cargo +//! [dependencies] +//! rangemap = "1.4" +//! strum = { version = "0.25", features = ["derive"] } +//! nom = "7" +//! itertools = "0.12" +//! ``` +/* +#!nix-shell -i rust-script -p rustc -p rust-script -p cargo +*/ + +use itertools::Itertools; +use nom::IResult; +use rangemap::RangeMap; +use std::{collections::HashMap, io::Read, ops::Range, str::FromStr, time::Instant}; + +const TRANSLATION_PATH: &[MapKind] = &[ + MapKind::Soil, + MapKind::Fertilizer, + MapKind::Water, + MapKind::Light, + MapKind::Temperature, + MapKind::Humidity, + MapKind::Location, +]; + +fn main() { + let mut input = Vec::new(); + std::io::stdin().lock().read_to_end(&mut input).unwrap(); + let input = std::str::from_utf8(&input).unwrap(); + + let (rest, input) = parse_input(input).unwrap(); + assert!(rest.is_empty()); + + let i = Instant::now(); + let answer = part1(&input); + eprintln!("part 1: {answer} ({:?})", i.elapsed()); + + let i = Instant::now(); + let answer = part2(&input); + eprintln!("part 2: {answer} ({:?})", i.elapsed()); +} + +fn part1(input: &Input) -> u64 { + let mut lowest_location = u64::MAX; + + for seed in &input.seeds { + let mut source = *seed; + let mut from = MapKind::Seed; + + for to in TRANSLATION_PATH { + let Some(translation) = input.maps.get(&Translation { from, to: *to }) else { + panic!("invalid path {from:?} to {to:?}"); + }; + + if let Some((source_range, destination_base)) = translation.get_key_value(&source) { + source = destination_base + (source - source_range.start); + } + + from = *to; + } + + assert_eq!(from, MapKind::Location); + lowest_location = lowest_location.min(source); + } + + lowest_location +} + +fn part2(input: &Input) -> u64 { + let seed_ranges: Vec<_> = input + .seeds + .iter() + .tuples() + .map(|(start, len)| (*start)..(*start) + len) + .collect(); + + let mut lowest_bound_seen = u64::MAX; + + for seed_range in seed_ranges { + let lowest_for_seed = traverse_path(input, TRANSLATION_PATH, MapKind::Seed, seed_range); + lowest_bound_seen = lowest_bound_seen.min(lowest_for_seed); + } + + lowest_bound_seen +} + +fn traverse_path(input: &Input, path: &[MapKind], from: MapKind, source_range: Range) -> u64 { + let mut lowest_bound_seen = u64::MAX; + + let Some((next_path, rest)) = path.split_first() else { + return source_range.start; + }; + + let Some(translation) = input.maps.get(&Translation { + from, + to: *next_path, + }) else { + panic!("invalid path {from:?} to {next_path:?}"); + }; + + for (new_source_range, destination_base) in translation.overlapping(&source_range) { + // determine intersection between the source range and destination range + let start = source_range.start.max(new_source_range.start); + let end = source_range.end.min(new_source_range.end); + let offset = start.saturating_sub(new_source_range.start); + let length = end.saturating_sub(start); + + let destination_range = (*destination_base + offset)..(*destination_base + offset + length); + + let lowest_in_tree = traverse_path(input, rest, *next_path, destination_range); + + lowest_bound_seen = lowest_bound_seen.min(lowest_in_tree); + } + + // traverse any uncovered sources, which the spec allows us to use our + // destination number directly for + for uncovered_range in split_range( + source_range.clone(), + translation + .overlapping(&source_range) + .map(|v| v.0.clone()) + .collect(), + ) { + let current_range = traverse_path(input, rest, *next_path, uncovered_range); + lowest_bound_seen = lowest_bound_seen.min(current_range); + } + + lowest_bound_seen +} + +/// Splits `main_range` into multiple ranges not covered by `ranges`. +fn split_range(main_range: Range, mut ranges: Vec>) -> Vec> { + let mut non_intersecting_ranges = Vec::new(); + let mut current_start = main_range.start; + + ranges.sort_by_key(|r| r.start); + + for range in ranges { + if range.start > current_start { + non_intersecting_ranges.push(current_start..range.start); + } + + if range.end > current_start { + current_start = range.end; + } + } + + if current_start < main_range.end { + non_intersecting_ranges.push(current_start..main_range.end); + } + + non_intersecting_ranges +} + +#[derive(strum::EnumString, Copy, Clone, Debug, Hash, PartialEq, Eq)] +#[strum(serialize_all = "kebab-case")] +enum MapKind { + Seed, + Soil, + Fertilizer, + Water, + Light, + Temperature, + Humidity, + Location, +} + +#[derive(Debug, Hash, Copy, Clone, PartialEq, Eq)] +struct Translation { + from: MapKind, + to: MapKind, +} + +impl From<(MapKind, MapKind)> for Translation { + fn from((from, to): (MapKind, MapKind)) -> Self { + Self { from, to } + } +} + +#[derive(Debug)] +struct Input { + seeds: Vec, + maps: HashMap>, +} + +/// parse entire input +fn parse_input(rest: &str) -> IResult<&str, Input> { + use nom::{ + bytes::complete::tag, character::complete::digit1, combinator::map_res, + multi::separated_list1, sequence::delimited, + }; + + let (rest, seeds) = delimited( + tag("seeds: "), + separated_list1(tag(" "), map_res(digit1, u64::from_str)), + tag("\n\n"), + )(rest)?; + let (rest, maps) = separated_list1(tag("\n"), parse_single_map)(rest)?; + + Ok(( + rest, + Input { + seeds, + maps: maps.into_iter().collect(), + }, + )) +} + +/// parse header along with each map line +fn parse_single_map(rest: &str) -> IResult<&str, (Translation, RangeMap)> { + use nom::multi::many1; + + let (rest, header) = parse_header(rest)?; + let (rest, lines) = many1(parse_map_line)(rest)?; + + Ok((rest, (header, lines.into_iter().collect()))) +} + +/// parse `803774611 641364296 1132421037` line +fn parse_map_line(rest: &str) -> IResult<&str, (Range, u64)> { + use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::digit1, + combinator::{eof, map_res}, + sequence::terminated, + }; + + let (rest, destination) = terminated(map_res(digit1, u64::from_str), tag(" "))(rest)?; + let (rest, source) = terminated(map_res(digit1, u64::from_str), tag(" "))(rest)?; + let (rest, size) = terminated(map_res(digit1, u64::from_str), alt((tag("\n"), eof)))(rest)?; + + Ok((rest, (source..source + size, destination))) +} + +/// parse `seed-to-soil map:` line +fn parse_header(rest: &str) -> IResult<&str, Translation> { + use nom::{ + bytes::complete::{tag, take_until}, + combinator::{map, map_res}, + sequence::{separated_pair, terminated}, + }; + + map( + terminated( + separated_pair( + map_res(take_until("-"), MapKind::from_str), + tag("-to-"), + map_res(take_until(" "), MapKind::from_str), + ), + tag(" map:\n"), + ), + Translation::from, + )(rest) +} -- libgit2 1.7.2