summaryrefslogtreecommitdiffstats
path: root/2015/rs
diff options
context:
space:
mode:
authoralyx <alyx@aleteoryx.me>2023-11-20 15:31:45 -0500
committeralyx <alyx@aleteoryx.me>2023-11-20 15:31:45 -0500
commit4810e24657a5931ea79be3fc3ee3e108fe40282e (patch)
tree901949b947b608402a9e9ac049929895dcd9471f /2015/rs
parent4e158659f8b222e8815d06fcbbd34f1e7cbc1d46 (diff)
downloadadventofcode-4810e24657a5931ea79be3fc3ee3e108fe40282e.tar.gz
adventofcode-4810e24657a5931ea79be3fc3ee3e108fe40282e.tar.bz2
adventofcode-4810e24657a5931ea79be3fc3ee3e108fe40282e.zip
2015.9
Diffstat (limited to '2015/rs')
-rw-r--r--2015/rs/Cargo.toml4
-rw-r--r--2015/rs/src/nine.rs53
-rw-r--r--2015/rs/src/nine.txt28
3 files changed, 85 insertions, 0 deletions
diff --git a/2015/rs/Cargo.toml b/2015/rs/Cargo.toml
index e50e704..e35c00b 100644
--- a/2015/rs/Cargo.toml
+++ b/2015/rs/Cargo.toml
@@ -35,5 +35,9 @@ path = "src/seven.rs"
name = "eight"
path = "src/eight.rs"
+[[bin]]
+name = "nine"
+path = "src/nine.rs"
+
[dependencies]
md-5 = "0.10.6"
diff --git a/2015/rs/src/nine.rs b/2015/rs/src/nine.rs
new file mode 100644
index 0000000..bc716c2
--- /dev/null
+++ b/2015/rs/src/nine.rs
@@ -0,0 +1,53 @@
+#![feature(iter_next_chunk)]
+
+use std::collections::{HashSet, HashMap};
+use std::io::Write;
+
+static INPUT: &'static str = include_str!("nine.txt");
+
+fn main() {
+ let valueified = INPUT.split('\n').filter(|s| !s.is_empty())
+ .flat_map(|s| {
+ let [rhs, dist] = s.split(" = ").next_chunk::<2>().unwrap();
+ let [from, to] = rhs.split(" to ").next_chunk::<2>().unwrap();
+ let dist = dist.parse::<usize>().unwrap();
+ [(from, to, dist), (to, from, dist)]
+ });
+
+ let paths: HashMap<&'static str, Vec<(&'static str, usize)>> = valueified
+ .map(|(a,b,c)| (a, (b, c)))
+ .fold(HashMap::new(), |mut map, (k, v)| {map.entry(k).or_default().push(v); map});
+ let mut path = Vec::new();
+ let mut bestpath = Vec::new();
+ let mut bestdist = usize::MAX;
+ let mut worstpath = Vec::new();
+ let mut worstdist = 0;
+ for start in paths.keys() {
+ path.clear();
+ path.push(*start);
+ walk_steps(&mut path, 0, &mut bestpath, &mut bestdist, &mut worstpath, &mut worstdist, &paths);
+ }
+ println!("Best route: {} with dist = {bestdist}", bestpath.join(" => "));
+ println!("Worst route: {} with dist = {worstdist}", worstpath.join(" => "));
+}
+
+fn walk_steps(path: &mut Vec<&'static str>, dist: usize, bestpath: &mut Vec<&'static str>, bestdist: &mut usize, worstpath: &mut Vec<&'static str>, worstdist: &mut usize, steps: &HashMap<&'static str, Vec<(&'static str, usize)>>) {
+ if path.len() != steps.len() {
+ let prev = path.last().unwrap();
+ for (step, stepdist) in &steps[prev] {
+ if path.contains(step) { continue; }
+ path.push(step);
+ walk_steps(path, dist + stepdist, bestpath, bestdist, worstpath, worstdist, steps);
+ path.pop();
+ }
+ } else {
+ if dist < *bestdist {
+ *bestpath = path.clone();
+ *bestdist = dist;
+ }
+ else if dist > *worstdist {
+ *worstpath = path.clone();
+ *worstdist = dist;
+ }
+ }
+}
diff --git a/2015/rs/src/nine.txt b/2015/rs/src/nine.txt
new file mode 100644
index 0000000..97a6b63
--- /dev/null
+++ b/2015/rs/src/nine.txt
@@ -0,0 +1,28 @@
+Faerun to Tristram = 65
+Faerun to Tambi = 129
+Faerun to Norrath = 144
+Faerun to Snowdin = 71
+Faerun to Straylight = 137
+Faerun to AlphaCentauri = 3
+Faerun to Arbre = 149
+Tristram to Tambi = 63
+Tristram to Norrath = 4
+Tristram to Snowdin = 105
+Tristram to Straylight = 125
+Tristram to AlphaCentauri = 55
+Tristram to Arbre = 14
+Tambi to Norrath = 68
+Tambi to Snowdin = 52
+Tambi to Straylight = 65
+Tambi to AlphaCentauri = 22
+Tambi to Arbre = 143
+Norrath to Snowdin = 8
+Norrath to Straylight = 23
+Norrath to AlphaCentauri = 136
+Norrath to Arbre = 115
+Snowdin to Straylight = 101
+Snowdin to AlphaCentauri = 84
+Snowdin to Arbre = 96
+Straylight to AlphaCentauri = 107
+Straylight to Arbre = 14
+AlphaCentauri to Arbre = 46