Finished part2 with rayon with brute force solution

3 files changed, 134 insertions, 15 deletions

diff --git a/2023/Rust/Cargo.lock b/2023/Rust/Cargo.lock
index 34373bc..e9cb66a 100644
--- a/2023/Rust/Cargo.lock
+++ b/2023/Rust/Cargo.lock
@@ -5,3 +5,92 @@ version = 3
 [[package]]
 name = "Rust"
 version = "0.1.0"
+dependencies = [
+ "rayon",
+]
+
+[[package]]
+name = "autocfg"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa"
+
+[[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
+name = "crossbeam-deque"
+version = "0.8.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ce6fd6f855243022dcecf8702fef0c297d4338e226845fe067f6341ad9fa0cef"
+dependencies = [
+ "cfg-if",
+ "crossbeam-epoch",
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "crossbeam-epoch"
+version = "0.9.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ae211234986c545741a7dc064309f67ee1e5ad243d0e48335adc0484d960bcc7"
+dependencies = [
+ "autocfg",
+ "cfg-if",
+ "crossbeam-utils",
+ "memoffset",
+ "scopeguard",
+]
+
+[[package]]
+name = "crossbeam-utils"
+version = "0.8.16"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5a22b2d63d4d1dc0b7f1b6b2747dd0088008a9be28b6ddf0b1e7d335e3037294"
+dependencies = [
+ "cfg-if",
+]
+
+[[package]]
+name = "either"
+version = "1.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07"
+
+[[package]]
+name = "memoffset"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5a634b1c61a95585bd15607c6ab0c4e5b226e695ff2800ba0cdccddf208c406c"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "rayon"
+version = "1.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9c27db03db7734835b3f53954b534c91069375ce6ccaa2e065441e07d9b6cdb1"
+dependencies = [
+ "either",
+ "rayon-core",
+]
+
+[[package]]
+name = "rayon-core"
+version = "1.12.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5ce3fb6ad83f861aac485e76e1985cd109d9a3713802152be56c3b1f0e0658ed"
+dependencies = [
+ "crossbeam-deque",
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "scopeguard"
+version = "1.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "94143f37725109f92c262ed2cf5e59bce7498c01bcc1502d7b9afe439a4e9f49"
diff --git a/2023/Rust/Cargo.toml b/2023/Rust/Cargo.toml
index 0f912fe..5595980 100644
--- a/2023/Rust/Cargo.toml
+++ b/2023/Rust/Cargo.toml
@@ -3,10 +3,6 @@ name = "Rust"
 version = "0.1.0"
 edition = "2021"
 
-# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
-
-[dependencies]
-
 
 [[bin]]
 name = "day1"
@@ -76,4 +72,7 @@ path = "src/day16.rs"
 name = "day17"
 path = "src/day17.rs"
 
+[dependencies]
+rayon = "1.8.0"
+
 
diff --git a/2023/Rust/src/day5.rs b/2023/Rust/src/day5.rs
index 36011f4..27a9c41 100644
--- a/2023/Rust/src/day5.rs
+++ b/2023/Rust/src/day5.rs
@@ -1,4 +1,5 @@
-use std::{collections::HashSet, ops::Add, ops::AddAssign};
+use rayon::prelude::*;
+use std::collections::HashSet;
 
 #[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Hash)]
 struct Range {
@@ -36,19 +37,51 @@ impl Range {
 }
 
 fn solve_part_one(data: &str) -> u32 {
+    use std::cmp::min;
     let almanac = Almanac::from(data);
-    let mut seeds = almanac.seeds.clone();
-    for (_, maps) in almanac.maps.iter() {
-        for seed in seeds.iter_mut() {
-            let tmp = seed.clone();
+    let seeds = almanac.seeds.clone();
+    let mut ans = i64::MAX;
+    for seed in seeds.iter() {
+        let mut mn = seed.clone();
+        for (_, maps) in almanac.maps.iter() {
+            let tmp = mn.clone();
             for seed_map in maps.iter() {
                 if seed_map.contains(tmp) {
-                    *seed += (seed_map.dest as i64 - seed_map.src as i64) as i64;
+                    mn = mn + seed_map.dest as i64 - seed_map.src as i64;
                 }
             }
         }
+        ans = min(ans, mn);
     }
-    *seeds.iter().min().unwrap() as u32
+    ans as u32
+}
+
+fn solve_part_two_slow(data: &str) -> u64 {
+    use std::cmp::min;
+    let almanac = Almanac::from(data);
+    let seeds = Vec::from_iter(almanac.seeds.clone().into_iter());
+    let mut pars = seeds
+        .iter()
+        .enumerate()
+        .step_by(2)
+        .map(|(i, _)| (i, i64::MAX))
+        .collect::<Vec<_>>();
+    // let n = seeds.len();
+    pars.par_iter_mut().for_each(|(i, ans)| {
+        for seed in seeds[*i]..seeds[*i] + seeds[*i + 1] {
+            let mut mn = seed.clone();
+            for (_, maps) in almanac.maps.iter() {
+                let tmp = mn.clone();
+                for seed_map in maps.iter() {
+                    if seed_map.contains(tmp) {
+                        mn = mn + seed_map.dest as i64 - seed_map.src as i64;
+                    }
+                }
+            }
+            *ans = min(*ans, mn)
+        }
+    });
+    *pars.iter().map(|(x, ans)| ans).min().unwrap() as u64
 }
 
 fn solve_part_two(data: &str) -> u64 {
@@ -61,7 +94,6 @@ fn solve_part_two(data: &str) -> u64 {
         ))
     }
     for (_, maps) in almanac.maps.iter() {
-        dbg!(&seeds);
         let mut new_seeds: HashSet<Range> = HashSet::from_iter(seeds.clone().into_iter());
         for seed in seeds.iter_mut() {
             let tmp = seed.clone();
@@ -78,7 +110,6 @@ fn solve_part_two(data: &str) -> u64 {
         }
         seeds = Vec::from_iter(new_seeds.into_iter());
     }
-    // dbg!(&seeds);
     (*seeds).iter().map(|rng| rng.start).min().unwrap() as u64
 }
 
@@ -154,6 +185,6 @@ fn main() {
     let prod = include_str!("../input/day5.prod");
     println!("part_1 test: {:?}", solve_part_one(test));
     println!("part_1 prod {:?}", solve_part_one(prod));
-    println!("part_2 test: {:?}", solve_part_two(test));
-    // println!("part_2 prod {:?}", solve_part_two(prod));
+    println!("part_2 test: {:?}", solve_part_two_slow(test));
+    println!("part_2 prod {:?}", solve_part_two_slow(prod));
 }