diff options
| -rw-r--r-- | input/day_05.txt | 247 | ||||
| -rw-r--r-- | src/day_05.rs | 195 | ||||
| -rw-r--r-- | src/lib.rs | 2 | ||||
| -rw-r--r-- | src/main.rs | 3 |
4 files changed, 446 insertions, 1 deletions
diff --git a/input/day_05.txt b/input/day_05.txt new file mode 100644 index 0000000..2c3808e --- /dev/null +++ b/input/day_05.txt @@ -0,0 +1,247 @@ +seeds: 487758422 524336848 2531594804 27107767 1343486056 124327551 1117929819 93097070 3305050822 442320425 2324984130 87604424 4216329536 45038934 1482842780 224610898 115202033 371332058 2845474954 192579859 + +seed-to-soil map: +152560994 173671324 63296280 +22185606 1527272669 123700133 +1331635416 297391996 25501160 +2532562923 236967604 60424392 +145885739 854580877 6675255 +696074404 427174664 330582271 +0 1407203152 22185606 +1174684019 152310608 21360716 +2679050525 3516671293 482421092 +1227353908 322893156 104281508 +1077860077 757756935 96823942 +3161471617 3999092385 22763615 +1509447184 1650972802 82059456 +4170512486 2802241718 1263617 +1196044735 1495963496 31309173 +1357136576 0 152310608 +4171776103 2679050525 123191193 +1731875772 1733032258 319590386 +282432012 1001625264 405577888 +215857274 1429388758 66574738 +1026656675 2541783913 51203402 +1591506640 861256132 140369132 +688009900 2052622644 8064504 +3457346528 2803505335 713165958 +3184235232 4021856000 273111296 +2051466158 2060687148 481096765 + +soil-to-fertilizer map: +2587123207 1612631011 14556918 +425896400 1627187929 180219453 +974395525 3228073255 181091940 +606115853 2482605187 15274968 +621390821 1843957593 329096619 +4269010275 3749182981 25957021 +2601680125 1807407382 36550211 +3749182981 3775140002 91697225 +3337986166 2411426158 71179029 +2306503017 631361705 276943999 +0 205465305 425896400 +950487440 181557220 23908085 +1155487465 1188132368 424498643 +1579986108 2497880155 726516909 +2583447016 3224397064 3676191 +3840880206 3866837227 428130069 +3099614220 2173054212 238371946 +2918057000 0 181557220 +2638230336 908305704 279826664 + +fertilizer-to-water map: +0 226390191 111676682 +342717440 10141562 176981703 +3507713259 629378619 187481170 +3695194429 3739990160 60489319 +2747106431 4155961766 11528550 +2120906094 2661985654 77106422 +3983043532 1233406588 239832885 +3045388563 4287081612 7885684 +529840705 187123265 39266926 +2198012516 1102191084 16615097 +3053274247 4167490316 104130064 +2564366436 2756374717 129809025 +3331241613 816859789 87383675 +3418625288 3536806097 36187146 +1239632010 3393454292 143351805 +1147966039 1776147938 91665971 +1382983815 2230578660 82475007 +4222876417 1045170068 57021016 +3455914127 2313053667 4640764 +2835800762 3800479479 42590884 +4279897433 1473239473 15069863 +3780709534 2342720217 202333998 +1753297424 3902953503 253008263 +1465458822 1488309336 287838602 +3454812434 2588893134 1101693 +3287402694 2545054215 43838919 +2704024450 1002088087 43081981 +629378619 2589994827 71990827 +3189558071 904243464 97844623 +2214627613 2886183742 264407413 +2006305687 1118806181 114600407 +3460554891 1867813909 47158368 +3755683748 2317694431 25025786 +111676682 338066873 231040758 +519699143 0 10141562 +2479035026 3313735125 69870178 +2548905204 4271620380 15461232 +2775917622 3843070363 59883140 +3157404311 2198424900 32153760 +864513416 1914972277 283452623 +2758634981 2739092076 17282641 +701369446 3150591155 163143970 +2878391646 3572993243 166996917 +2694175461 3383605303 9848989 + +water-to-light map: +1222332482 2306154207 322881400 +3721269109 3329751112 30895612 +4157109606 3191893422 137857690 +2602036554 3676681423 255279159 +2293973174 3078247260 113646162 +1208052724 2246358310 14279758 +1835200232 1597610395 302070784 +3118371905 1208052724 389557671 +2137271016 3519979265 156702158 +2501933666 1952285487 54586749 +3753874345 1899681179 52604308 +3806478653 3931960582 7636192 +3973340148 2006872236 24436917 +3814114845 2629035607 159225303 +3507929576 2031309153 213339533 +3752164721 2244648686 1709624 +2857315713 3939596774 261056192 +3997777065 3360646724 159332541 +2556520415 2260638068 45516139 +2407619336 4200652966 94314330 +1545213882 2788260910 289986350 + +light-to-temperature map: +40645637 589707204 89929230 +2331703372 3634092968 247989827 +375013050 880330876 388603146 +959059361 861524497 18806379 +3081535248 2703807387 671456921 +2080450790 1678532701 100545991 +1520717011 1522300302 156232399 +3801827392 4285326304 9640992 +2834731556 1990942492 115059472 +2949791028 2566169187 71005535 +3020796563 4224587619 60738685 +4159346802 1855321998 135620494 +977865740 0 297257755 +3811468384 3375264308 157802817 +2304295289 1779078692 27408083 +3752992169 1806486775 48835223 +2579693199 3882082795 255038357 +130574867 328095764 236983298 +4081903724 3533067125 77443078 +367558165 310812857 7454885 +3969271201 3610510203 23582765 +4080320433 1520717011 1583291 +777171298 679636434 181888063 +2180996781 2106001964 56665843 +3992853966 4137121152 87466467 +0 1268934022 6189473 +30817615 318267742 9828022 +1676949410 2162667807 403501380 +763616196 297257755 13555102 +6189473 565079062 24628142 +2237662624 2637174722 66632665 + +temperature-to-humidity map: +3854764317 3086190444 332386294 +2110554705 1096342109 65650849 +3236082645 1211923153 20175736 +846106827 1853452836 60731419 +596073066 1972015961 100470927 +1202254149 2647779239 280062599 +2176205554 2107199879 422980149 +2943801812 432921932 58618218 +1824616452 1161992958 3317671 +1201112206 2106057936 1141943 +1840640266 1631373972 178403432 +2767591984 62542954 155027747 +2743880612 491540150 8409669 +62542954 1273100182 24571446 +4208015516 3772661112 86951780 +3477752908 217570701 215351231 +2019043698 3681150105 91511007 +1482316748 4027597725 172205397 +766244356 4199803122 79862471 +950513678 665972626 23438579 +89279871 1232098889 41001293 +1654522145 1914184255 36130017 +3002420030 3660808941 20341164 +452765307 1525178112 98766078 +551531385 840194947 44541681 +1827934123 2072486888 12706143 +87114400 3859612892 2165471 +1091551468 3873351076 109560738 +2714852730 884736628 29027882 +906838246 1809777404 43675432 +760232399 1297671628 6011957 +696543993 3861778363 11572713 +3693104139 633914109 32058517 +1690652162 499949819 133964290 +151982853 3418576738 142433848 +2922619731 689411205 21182081 +2599185703 1165310629 46612524 +2752290281 4279665593 15301703 +3022761194 913764510 182577599 +2645798227 3561010586 69054503 +130281164 1950314272 21701689 +973952257 2530180028 117599211 +715546488 3982911814 44685911 +4187150611 2085193031 20864905 +3256258381 1303683585 221494527 +3725162656 710593286 129601661 +708116706 1623944190 7429782 +3205338793 3630065089 30743852 +294416701 2927841838 158348606 + +humidity-to-location map: +3745579304 2724582328 81388084 +2201043082 981698567 150857305 +456470998 689872919 41258774 +2351900387 2312761976 47825019 +497729772 314502888 115122928 +4036836228 4279991461 14975835 +784121118 3255986437 5687937 +612852700 0 118278993 +3894168411 842107405 27168107 +3127730376 4061803810 218187651 +1230572305 1958697503 125808488 +304425981 163566931 106757079 +789809055 3790646012 241507252 +1777374448 1871672054 39148062 +1816522510 1504159194 367512860 +235721965 621168903 68704016 +4051812063 1480547431 14406303 +3826967388 1228960483 58471320 +411183060 118278993 45287938 +3921336518 869275512 103693352 +4025029870 2304659906 8102070 +2838210137 1132555872 96404611 +2934614748 1287431803 193115628 +1414367080 3422182046 363007368 +3345918027 1494953734 9205460 +2184035370 2805970412 17007712 +2631131158 2088210279 207078979 +1356380793 784121118 57986287 +2399725406 2493176576 231405752 +1031316307 3261674374 160507672 +44178878 429625816 191543087 +4195166765 3165556554 90429883 +4285596648 2295289258 9370648 +3403000874 2822978124 342578430 +1191823979 3785189414 5456598 +1197280577 2459884848 33291728 +4066218366 4032153264 29650546 +3355123487 1910820116 47877387 +3885438708 972968864 8729703 +0 270324010 44178878 +4095868912 2360586995 99297853 +4033131940 2084505991 3704288 diff --git a/src/day_05.rs b/src/day_05.rs new file mode 100644 index 0000000..e9d0b92 --- /dev/null +++ b/src/day_05.rs @@ -0,0 +1,195 @@ +use std::{ops::Range, str::FromStr}; + +use crate::{Problem, Solution}; + +pub struct Day05; + +impl Problem for Day05 { + const DAY: u8 = 5; + + const INPUT: &'static str = include_str!("../input/day_05.txt"); +} + +impl Solution for Day05 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> anyhow::Result<Self::Answer1> { + let (first, rest) = input + .trim() + .split_once('\n') + .ok_or(anyhow::format_err!("Missing value map label"))?; + + let mut values = first + .strip_prefix("seeds: ") + .ok_or(anyhow::format_err!("Failed to get seeds"))? + .split_whitespace() + .map(FromStr::from_str) + .try_collect::<Vec<usize>>()?; + + let value_maps = rest + .trim() + .split("\n\n") + .map(parse_value_maps) + .try_collect::<Vec<_>>()?; + + for value_map in value_maps { + values.iter_mut().for_each(|value| { + if let Some(v) = value_map.iter().find_map(|v| v.map_value(*value)) { + *value = v + } + }) + } + + values + .into_iter() + .min() + .ok_or(anyhow::format_err!("No values found")) + } + + fn part_2(input: &str) -> anyhow::Result<Self::Answer2> { + let (first, rest) = input + .trim() + .split_once('\n') + .ok_or(anyhow::format_err!("Missing value map label"))?; + + let seeds: Vec<Range<usize>> = first + .strip_prefix("seeds: ") + .ok_or(anyhow::format_err!("Failed to get seeds"))? + .split_whitespace() + .map(FromStr::from_str) + .try_collect::<Vec<usize>>()? + .into_iter() + .array_chunks() + .map(|[n, len]| Range { + start: n, + end: n + len, + }) + .collect(); + + let max = seeds + .iter() + .map(|r| r.end) + .max() + .ok_or(anyhow::format_err!("Failed to get max seed"))?; + + let value_maps = rest + .trim() + .split("\n\n") + .map(parse_value_maps) + .try_collect::<Vec<_>>()?; + + (0..=max) + .find(|location| { + let mut value = *location; + for value_map in value_maps.iter().rev() { + if let Some(v) = value_map.iter().find_map(|v| v.r_map_value(value)) { + value = v; + } + } + seeds.iter().any(|s| s.contains(&value)) + }) + .ok_or(anyhow::format_err!("Failed to find min seed")) + } +} + +fn parse_value_maps(s: &str) -> anyhow::Result<Vec<ValueMap>> { + s.trim() + .lines() + .skip(1) + .map(FromStr::from_str) + .try_collect::<Vec<ValueMap>>() +} + +#[derive(Debug, PartialEq, Eq, Hash)] +struct ValueMap { + source: Range<usize>, + destination: Range<usize>, + offset: isize, +} + +impl ValueMap { + fn map_value(&self, value: usize) -> Option<usize> { + self.source + .contains(&value) + .then_some((value as isize + self.offset) as usize) + } + + fn r_map_value(&self, value: usize) -> Option<usize> { + self.destination + .contains(&value) + .then_some((value as isize - self.offset) as usize) + } +} + +impl FromStr for ValueMap { + type Err = anyhow::Error; + + fn from_str(s: &str) -> Result<Self, Self::Err> { + let mut iter = s.trim().splitn(3, ' ').map(FromStr::from_str); + + let (Some(Ok(destination_start)), Some(Ok(source_start)), Some(Ok(length))) = + (iter.next(), iter.next(), iter.next()) + else { + anyhow::bail!("Invalid value map range"); + }; + + Ok(Self { + source: source_start..source_start + length, + destination: destination_start..destination_start + length, + offset: isize::try_from(destination_start)? - isize::try_from(source_start)?, + }) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + const INPUT: &str = indoc::indoc! {" + 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_part_1() -> anyhow::Result<()> { + Ok(assert_eq!(35, Day05::part_1(INPUT)?)) + } + + #[test] + fn test_part_2() -> anyhow::Result<()> { + Ok(assert_eq!(46, Day05::part_2(INPUT)?)) + } +} @@ -1,9 +1,11 @@ #![feature(iterator_try_collect)] +#![feature(iter_array_chunks)] pub mod day_01; pub mod day_02; pub mod day_03; pub mod day_04; +pub mod day_05; pub trait Problem { const DAY: u8; diff --git a/src/main.rs b/src/main.rs index 3f47fac..feae755 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,10 +1,11 @@ -use aoc_2023::{day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, Solution}; +use aoc_2023::{day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, Solution, day_05::Day05}; fn main() -> anyhow::Result<()> { Day01::solve()?; Day02::solve()?; Day03::solve()?; Day04::solve()?; + Day05::solve()?; Ok(()) } |