aoc-2023/d05/main.rs
Ian Fijolek 71309f3672 Day 5
Brute force solution in rust to power through part 2 faster
2023-12-05 17:25:22 -08:00

215 lines
6.1 KiB
Rust

#![feature(iter_array_chunks)]
// use std::thread;
use std::collections::HashMap;
use std::fs;
use std::thread;
// use iterchunks::IterChunk
#[derive(Clone)]
struct RangePart {
dest_start: i64,
source_start: i64,
length: i64,
}
impl RangePart {
fn contains(&self, val: i64) -> bool {
return self.source_start <= val && val < self.source_start + self.length;
}
fn get(&self, val: i64) -> i64 {
if !self.contains(val) {
return val;
}
let delta = self.source_start - self.dest_start;
return val - delta;
}
}
#[derive(Clone)]
struct RangeMap {
parts: Vec<RangePart>,
}
impl RangeMap {
fn new(parts: Vec<RangePart>) -> RangeMap {
RangeMap { parts }
}
fn get(&self, val: i64) -> i64 {
for range in self.parts.iter() {
if range.contains(val.clone()) {
return range.get(val.clone());
}
}
return val;
}
}
fn min_loc(maps: HashMap<&str, RangeMap>, seeds: Vec<i64>) -> i64 {
let mut min_location: i64 = i64::MAX;
for seed in seeds.iter() {
let soil = maps["seed-to-soil"].get(*seed);
let fertilizer = maps["soil-to-fertilizer"].get(soil);
let water = maps["fertilizer-to-water"].get(fertilizer);
let light = maps["water-to-light"].get(water);
let temperature = maps["light-to-temperature"].get(light);
let humidity = maps["temperature-to-humidity"].get(temperature);
let location = maps["humidity-to-location"].get(humidity);
if location < min_location {
min_location = location
}
}
return min_location;
}
fn min_loc_threads(maps: HashMap<&str, RangeMap>, seeds: &Vec<i64>, threads: usize) -> i64 {
// let maps = maps.clone();
// let seeds = seeds.clone();
thread::scope(|s| -> i64 {
let mut children = vec![];
for chunk in seeds.chunks(seeds.len() / threads) {
let maps = maps.clone();
let chunk = chunk.clone();
children.push(s.spawn(|| -> i64 { min_loc(maps, chunk.to_vec()) }));
}
children
.into_iter()
.map(|c| -> i64 { c.join().unwrap() })
.min()
.unwrap()
})
}
fn main() {
// let file_contents = fs::read_to_string("sample.txt").expect("No input found");
let file_contents = fs::read_to_string("input.txt").expect("No input found");
let mut lines = file_contents.lines();
// let start = 1;
// let len = 2;
// let r = (start..start+len).collect();
let mut windows = lines
.next()
.expect("No line found")
.strip_prefix("seeds: ")
.expect("No seeds prefix")
.split_whitespace()
.map(|value| {
value
.parse::<i64>()
.expect(format!("Expected value to be an int but got : {}", value).as_str())
})
.array_chunks::<2>()
.map(|r| vec![r[0], r[0] + r[1]])
.collect::<Vec<Vec<i64>>>();
windows.sort_by(|a, b| a[0].cmp(&b[0]));
let mut merged_windows: Vec<Vec<i64>> = Vec::new();
merged_windows.push(windows[0].clone());
for i in 1..windows.len() {
let j: usize = merged_windows.len() - 1;
if windows[i][0] > merged_windows.last().unwrap()[1] {
merged_windows.push(windows[i].clone());
continue;
}
if windows[i][1] > merged_windows.last().unwrap()[1] {
merged_windows[j][1] = windows[i][1];
}
}
let seeds = merged_windows
.iter()
.map(|r| {
// println!("range {} to {}", r[0], r[1]);
(r[0]..r[1]).collect::<Vec<i64>>()
})
.flatten()
.collect::<Vec<i64>>();
/*
* let seed_set: HashSet<&i64> = HashSet::from_iter(seeds.iter());
* println!("seeds {}", seed_set.len());
*/
let mut maps: HashMap<&str, RangeMap> = HashMap::new();
let mut map_name = "";
let mut ranges: Vec<RangePart> = vec![];
for line in lines.map(|l| l.trim()) {
if line == "" {
if map_name != "" {
maps.insert(map_name, RangeMap::new(ranges));
map_name = "";
ranges = vec![];
}
continue;
}
if map_name == "" {
map_name = line.split_whitespace().next().unwrap();
// println!("map {}", map_name);
continue;
}
let mut parts = line.split_whitespace();
let dest_start = parts.next().unwrap().parse::<i64>().unwrap();
let source_start = parts.next().unwrap().parse::<i64>().unwrap();
let length = parts.next().unwrap().parse::<i64>().unwrap();
ranges.push(RangePart {
dest_start,
source_start,
length,
});
// println!("adding range {} {} {}", dest_start, source_start, length)
}
maps.insert(map_name, RangeMap::new(ranges));
/*
* let mut min_location: i64 = i64::MAX;
* for seed in seeds.iter() {
* let soil = maps["seed-to-soil"].get(*seed);
* let fertilizer = maps["soil-to-fertilizer"].get(soil);
* let water = maps["fertilizer-to-water"].get(fertilizer);
* let light = maps["water-to-light"].get(water);
* let temperature = maps["light-to-temperature"].get(light);
* let humidity = maps["temperature-to-humidity"].get(temperature);
* let location = maps["humidity-to-location"].get(humidity);
*
* if location < min_location {
* min_location = location
* }
*
* #<{(|
* * println!(
* * "Seed {} to soil {} to fertilizer {} to water {} to light {} to temperature {} to humidity {} to location {}",
* * seed,
* * soil,
* * fertilizer,
* * water,
* * light,
* * temperature,
* * humidity,
* * location,
* * )
* |)}>#
* }
*/
let min_location = min_loc_threads(maps, &seeds, 4);
println!("answer {}", min_location);
}