diff options
Diffstat (limited to '2023/Rust')
| -rw-r--r-- | 2023/Rust/Cargo.lock | 89 | ||||
| -rw-r--r-- | 2023/Rust/Cargo.toml | 7 | ||||
| -rw-r--r-- | 2023/Rust/src/day5.rs | 53 |
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)); } |