From 3806a46e668c8f69db75c920471648571d31e7eb Mon Sep 17 00:00:00 2001 From: alex Date: Wed, 6 Dec 2023 00:31:13 +0100 Subject: [PATCH] Day05 - part 2 --- src/day05.rs | 219 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 211 insertions(+), 8 deletions(-) diff --git a/src/day05.rs b/src/day05.rs index 78e039c..20829e5 100644 --- a/src/day05.rs +++ b/src/day05.rs @@ -57,7 +57,210 @@ fn run_part1(input: &str) -> Result> { fn run_part2(input: &str) -> Result> { println!("Running day05 - part 2"); - let res = 0; + + // on récupère la liste des valeurs de seeds + let values: Vec = input.lines().next().unwrap() + .split_once(": ").unwrap().1 + .split(' ') + .map(|v| v.parse().unwrap()) + .collect(); + + // on crée un vecteur de tuple Vec<(start, len)> + let mut seeds: Vec<(usize, usize)> = Vec::new(); + (0..values.len()).step_by(2) + .for_each(|i| { + let (start, len) = (values[i], values[i + 1]); + seeds.push((start, len)); + }); + seeds.sort_by(|a, b| { + a.0.cmp(&b.0) + }); + + // on repart de la partie 1 avec les même hypothèses + // cette fois-ci on ne travaille plus sur chaque graine mais sur un ensemble + // de graines + input.split("\n\n").skip(1) + .for_each(|bloc| { + //println!("seeds: {:?}", seeds); + // on stocke chaque mapping dans un tuple de la forme + // (src, dst, len) + // qui correspond aux bornes incluses des sous ensembles + let mut map: Vec<(usize, usize, usize)> = bloc.split("\n").skip(1) + .filter(|l| !l.is_empty()) + .map(|l| { + let values: Vec = l.split_whitespace() + .map(|s| s.parse().unwrap()) + .collect(); + (values[1], values[0], values[2]) + }) + .collect(); + + // on trie les entrées par ordre croissant de src + map.sort_by(|a, b| { + a.0.cmp(&b.0) + }); + //println!("map: {:?}", map); + + // + // -------[----------]------- -> -------[----------]------ + // a ^ ^ b a' ^ ^ b' + // seed_start seed_end seed_start seed_end + // + // -------[----------|-----|- -> -------[----------|----|- + // a ^ b ^ c a' ^ b' ^ c' + // seed_start seed_end seed_start seed_end + // + // + + // autre approche + // chaque ligne correspond à une fonction + // f: x -> x' + // + // y aurait-il un intérêt à prendre chaque segment et à chercher les + // graines qui sont dedans ? + // + // pour chaque segment (map x->x') + // rechercher les lots de graines qui sont dedans + // appliquer et stocker la transformation + + // nouvel ensemble de graines (seed_start, len) + let mut new_seeds: Vec<(usize, usize)> = Vec::new(); + + let mut found_all = false; + while !found_all { + // on met de côté le reste des intersections entre les ensembles + // (dans le cas où on travaille sur les graines) + // et on boucle tant qu'il y a qqch de côté + let mut new_seeds_tmp: Vec<(usize, usize)> = Vec::new(); + + // check que le lot de graines n'a pas été déjà vue pour ce bloc + let mut seed_seen: Vec = (0..seeds.len()).map(|_| false).collect(); + + map.clone().into_iter() + .for_each(|(src_start, dst_start, len)| { + let src_end = src_start + len - 1; + // rechercher le lot de graines qui est dans ce segment + seeds.iter().enumerate() + .for_each(|(i, (seed_start, seed_len))| { + if seed_seen[i] { + return; + } + seed_seen[i] = true; + let seed_end = seed_start + seed_len - 1; + // plusieurs cas de figures + + // tout d'abord par rapport à l'ensemble source + let range = src_start..=src_end; + if range.contains(&seed_start) + && range.contains(&seed_end) + { + new_seeds.push(( + dst_start + seed_start - src_start, + *seed_len + )); + } + else if range.contains(&seed_start) + && !range.contains(&seed_end) + { + new_seeds.push(( + dst_start + seed_start - src_start, + src_end - seed_start + 1 + )); + new_seeds_tmp.push(( + src_end + 1, + seed_end - src_end + )); + } + else if !range.contains(&seed_start) + && range.contains(&seed_end) + { + new_seeds.push(( + dst_start, + seed_end - src_start + 1 + )); + new_seeds_tmp.push(( + *seed_start, + src_start - seed_start + )); + } + else if !range.contains(&seed_start) + && !range.contains(&seed_end) + { + // l'ensemble source est inclus dans l'ensemble des graines + let range = seed_start..=&seed_end; + if range.contains(&&src_start) + && range.contains(&&src_end) + { + new_seeds.push(( + dst_start, + len + )); + new_seeds_tmp.push(( + *seed_start, + src_start - seed_start + )); + new_seeds_tmp.push(( + src_end + 1, + seed_end - src_end + )); + } + else if range.contains(&&src_start) + && !range.contains(&&src_end) + { + new_seeds.push(( + dst_start, + seed_end - src_start + 1 + )); + new_seeds_tmp.push(( + *seed_start, + src_start - seed_start + )); + } + else if !range.contains(&&src_start) + && range.contains(&&src_end) + { + new_seeds.push(( + dst_start + seed_start, + src_end - seed_start + 1 + )); + new_seeds_tmp.push(( + src_end + 1, + seed_end - src_end + )); + } + else if !range.contains(&&src_start) + && !range.contains(&&src_end) + { + // les ensembles sont disjoints + // ATTENTION on ne pousse pas à ce moment là + seed_seen[i] = false; + } + else { + unreachable!(); + } + } + }); + }); + + // récupération des lots qui n'intersectent aucun ensemble + seed_seen.into_iter().enumerate() + .filter(|(_,b)| !*b) + .for_each(|(i,_)| new_seeds.push(seeds[i])); + if new_seeds_tmp.is_empty() { + found_all = true; + } + seeds.clear(); + seeds = new_seeds_tmp; + } + seeds = new_seeds.into_iter().collect(); + seeds.sort_by(|a, b| { + a.0.cmp(&b.0) + }); + //println!("new seeds: {:?}", seeds); + + }); + + let res = seeds[0].0; Ok(res) } @@ -65,9 +268,7 @@ fn run_part2(input: &str) -> Result> { mod tests { use super::*; - #[test] - fn day05_part1() { - let input = "\ + static TEXT_INPUT: &str = "\ seeds: 79 14 55 13 seed-to-soil map: @@ -101,14 +302,16 @@ temperature-to-humidity map: humidity-to-location map: 60 56 37 56 93 4"; - let res = run_part1(&input); + + #[test] + fn day05_part1() { + let res = run_part1(TEXT_INPUT); assert_eq!(35, res.unwrap()); } #[test] fn day05_part2() { - let input = ""; - let res = run_part2(&input); - assert_eq!(0, res.unwrap()); + let res = run_part2(TEXT_INPUT); + assert_eq!(46, res.unwrap()); } } -- 2.39.5