commit a65fa49611fd79f66e5d0aec828864cf6c4a089b
parent 0b96ba14f37aa50c59979169ae476634356c5438
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu, 3 Jul 2025 08:10:28 +0200
16 part 1 works, but I made some changes afterwards
Diffstat:
| A | 2022/16/a.rs | | | 135 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/16/b.rs | | | 216 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/16/input | | | 51 | +++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/16/test | | | 10 | ++++++++++ |
4 files changed, 412 insertions(+), 0 deletions(-)
diff --git a/2022/16/a.rs b/2022/16/a.rs
@@ -0,0 +1,135 @@
+use std::cmp::max;
+use std::collections::HashMap;
+
+#[derive(Debug, Clone)]
+struct Node {
+ name: u16,
+ rate: usize,
+ neighbors: Vec<u16>
+}
+
+#[derive(Debug, Copy, Clone)]
+struct MapState {
+ valves: usize,
+ pos_ind: usize,
+ max_pos: usize
+}
+
+#[derive(Debug, Clone)]
+struct Map {
+ index: HashMap<u16, usize>,
+ nodes: Vec<Node>
+}
+
+fn getname(line: &str) -> u16 {
+ 100 * (line.chars().nth(0).unwrap() as u16) +
+ (line.chars().nth(1).unwrap() as u16)
+}
+
+impl Node {
+ fn from_line(line: &str) -> Node {
+ let name = getname(&line[6..]);
+ let j = line.find(';').unwrap();
+ let rate = line[23..j].parse::<usize>().unwrap();
+ let mut neighbors = vec![];
+ let mut i = j+24;
+ // "tunnels lead to valves" vs "tunnel lead to valve"
+ // What kind of sadistic animal made these inputs?
+ if line.chars().nth(i).unwrap() == ' ' { i += 1; }
+ while i < line.len() {
+ neighbors.push(getname(&line[i..]));
+ i += 4;
+ }
+ Node { name, rate, neighbors }
+ }
+}
+
+impl Map {
+ fn from_stdin() -> Map {
+ let mut line = String::new();
+ let mut nodes = Vec::<Node>::new();
+ while std::io::stdin().read_line(&mut line).unwrap() > 0 {
+ let node = Node::from_line(&line);
+ if nodes.len() > 0 && node.name == getname("AA") {
+ nodes.push(nodes[0].clone());
+ nodes[0] = node;
+ } else {
+ nodes.push(node);
+ }
+ line.clear();
+ }
+ let index = nodes.iter()
+ .enumerate()
+ .map(|(i, n)| (n.name, i))
+ .collect::<HashMap<_, _>>();
+ Map { index, nodes }
+ }
+
+ fn state_max(&self) -> usize {
+ let mut i: usize = 0;
+ let mut tot: usize = 0;
+ for n in &self.nodes {
+ if n.rate == 0 { continue; }
+ tot += 1 << i;
+ i += 1;
+ }
+ let len = self.nodes.len();
+ tot * len + len
+ }
+
+ fn released_pressure(&self) -> usize {
+ self.nodes.iter()
+ .map(|n| if n.valve_on { n.rate } else { 0 })
+ .sum()
+ }
+
+ fn most_pressure(&self, minutes: usize) -> usize {
+ let n = self.state_max();
+ let mut t = vec![0 as usize; n];
+ let mut u = vec![0 as usize; n];
+ let mut map = self.clone();
+
+ // Setup table for last minute
+ for s in 0..n {
+ map.set_state(s);
+ t[s] = map.released_pressure();
+ }
+
+ // Dynamic programming counting back to 0 minutes
+ for i in (0..minutes).rev() {
+ // Double buffer technique so we don't have to swap vectors
+ let (current, next) = if i % 2 == minutes % 2 {
+ (&mut t, &mut u)
+ } else {
+ (&mut u, &mut t)
+ };
+ for s in 0..n {
+ map.set_state(s);
+ let pos = map.pos;
+ let mut k = 0;
+ let ind = map.index[&pos];
+ let p = map.released_pressure();
+
+ // Try turning on the valve
+ if map.nodes[ind].rate > 0 && !map.nodes[ind].valve_on {
+ map.nodes[ind].valve_on = true;
+ k = max(k, p + next[map.get_state()]);
+ map.nodes[ind].valve_on = false;
+ }
+
+ // Try moving to a neighbor
+ for v in &map.nodes[ind].neighbors {
+ map.pos = *v;
+ k = max(k, p + next[map.get_state()]);
+ }
+ current[s] = k;
+ }
+ }
+ if 0 == minutes % 2 { t[0] } else { u[0] }
+ }
+}
+
+fn main() {
+ let map = Map::from_stdin();
+ println!("{}", map.most_pressure(29));
+}
diff --git a/2022/16/b.rs b/2022/16/b.rs
@@ -0,0 +1,216 @@
+use std::cmp::{max, Eq, PartialEq};
+use std::collections::HashMap;
+use std::hash::{Hash, Hasher};
+
+#[derive(Debug, Clone)]
+struct Node {
+ name: u16,
+ rate: usize,
+ neighbors: Vec<u16>,
+ valve_on: bool
+}
+
+#[derive(Debug, Clone)]
+struct Map {
+ index: HashMap<u16, usize>,
+ nodes: Vec<Node>,
+ pos: u16
+}
+
+fn getname(line: &str) -> u16 {
+ 100 * (line.chars().nth(0).unwrap() as u16) +
+ (line.chars().nth(1).unwrap() as u16)
+}
+
+impl Node {
+ fn from_line(line: &str) -> Node {
+ let name = getname(&line[6..]);
+ let j = line.find(';').unwrap();
+ let rate = line[23..j].parse::<usize>().unwrap();
+ let mut neighbors = vec![];
+ let mut i = j+24;
+ // "tunnels lead to valves" vs "tunnel lead to valve"
+ // What kind of sadistic animal made these inputs?
+ if line.chars().nth(i).unwrap() == ' ' { i += 1; }
+ while i < line.len() {
+ neighbors.push(getname(&line[i..]));
+ i += 4;
+ }
+ Node { name, rate, neighbors, valve_on: false }
+ }
+}
+
+impl Map {
+ fn from_stdin() -> Map {
+ let mut line = String::new();
+ let mut nodes = Vec::<Node>::new();
+ while std::io::stdin().read_line(&mut line).unwrap() > 0 {
+ let node = Node::from_line(&line);
+ if nodes.len() > 0 && node.name == getname("AA") {
+ nodes.push(nodes[0].clone());
+ nodes[0] = node;
+ } else {
+ nodes.push(node);
+ }
+ line.clear();
+ }
+ let index = nodes.iter()
+ .enumerate()
+ .map(|(i, n)| (n.name, i))
+ .collect::<HashMap<_, _>>();
+ Map { index, nodes, pos: getname("AA") }
+ }
+
+ fn get_state(&self) -> usize {
+ let mut i: usize = 0;
+ let mut tot: usize = 0;
+ for n in &self.nodes {
+ if n.rate == 0 { continue; }
+ if n.valve_on { tot += 1 << i; }
+ i += 1;
+ }
+ tot * self.nodes.len() + self.index[&self.pos]
+ }
+
+ fn set_state(&mut self, state: usize) {
+ let mut s = state;
+ let len = self.nodes.len();
+ self.pos = self.nodes[s%len].name;
+ s /= len;
+ for i in 0..len {
+ if self.nodes[i].rate == 0 { continue; }
+ self.nodes[i].valve_on = s % 2 == 1;
+ s /= 2;
+ }
+ }
+
+ fn state_max(&self) -> usize {
+ let mut i: usize = 0;
+ let mut tot: usize = 0;
+ for n in &self.nodes {
+ if n.rate == 0 { continue; }
+ tot += 1 << i;
+ i += 1;
+ }
+ let len = self.nodes.len();
+ tot * len + len
+ }
+
+ fn released_pressure(&self) -> usize {
+ self.nodes.iter()
+ .map(|n| if n.valve_on { n.rate } else { 0 })
+ .sum()
+ }
+
+/*
+ fn most_pressure(&self, minutes: usize) -> usize {
+ let n = self.state_max();
+ let mut t = vec![0 as usize; n];
+ let mut u = vec![0 as usize; n];
+ let mut map = self.clone();
+
+ // Setup table for last minute
+ for s in 0..n {
+ map.set_state(s);
+ t[s] = map.released_pressure();
+ }
+
+ // Dynamic programming counting back to 0 minutes
+ for i in (0..minutes).rev() {
+ // Double buffer technique so we don't have to swap vectors
+ let (current, next) = if i % 2 == minutes % 2 {
+ (&mut t, &mut u)
+ } else {
+ (&mut u, &mut t)
+ };
+ for s in 0..n {
+ map.set_state(s);
+ let pos = map.pos;
+ let mut k = 0;
+ let ind = map.index[&pos];
+ let p = map.released_pressure();
+
+ // Try turning on the valve
+ if map.nodes[ind].rate > 0 && !map.nodes[ind].valve_on {
+ map.nodes[ind].valve_on = true;
+ k = max(k, p + next[map.get_state()]);
+ map.nodes[ind].valve_on = false;
+ }
+
+ // Try moving to a neighbor
+ for v in &map.nodes[ind].neighbors {
+ map.pos = *v;
+ k = max(k, p + next[map.get_state()]);
+ }
+ current[s] = k;
+ }
+ }
+ if 0 == minutes % 2 { t[0] } else { u[0] }
+ }
+*/
+
+ fn most_pressure(&self, minutes: usize) -> usize {
+ let n = self.state_max();
+ let mut t = vec![0 as usize; n];
+ let mut u = vec![0 as usize; n];
+ let mut map = self.clone();
+
+ // Setup table for last minute
+ for s in 0..n {
+ map.set_state(s);
+ t[s] = map.released_pressure();
+ }
+
+ // Dynamic programming counting back to 0 minutes
+ for i in (0..minutes).rev() {
+ // Double buffer technique so we don't have to swap vectors
+ let (current, next) = if i % 2 == minutes % 2 {
+ (&mut t, &mut u)
+ } else {
+ (&mut u, &mut t)
+ };
+ for s in 0..n {
+ map.set_state(s);
+ let pos = map.pos;
+ let mut k = 0;
+ let ind = map.index[&pos];
+ let p = map.released_pressure();
+
+ // Try turning on the valve
+ if map.nodes[ind].rate > 0 && !map.nodes[ind].valve_on {
+ map.nodes[ind].valve_on = true;
+ k = max(k, p + next[map.get_state()]);
+ map.nodes[ind].valve_on = false;
+ }
+
+ // Try moving to a neighbor
+ for v in &map.nodes[ind].neighbors {
+ map.pos = *v;
+ k = max(k, p + next[map.get_state()]);
+ }
+ current[s] = k;
+ }
+ }
+ if 0 == minutes % 2 { t[0] } else { u[0] }
+ }
+}
+
+impl PartialEq for Map {
+ fn eq(&self, other: &Self) -> bool {
+ self.get_state() == other.get_state()
+ }
+}
+
+impl Eq for Map {}
+
+impl Hash for Map {
+ fn hash<H: Hasher>(&self, hasher: &mut H) {
+ hasher.write_usize(self.get_state());
+ }
+}
+
+fn main() {
+ let map = Map::from_stdin();
+ let mut t = HashMap::<Map, usize>::new();
+ println!("{}", map.most_pressure(29, t));
+}
diff --git a/2022/16/input b/2022/16/input
@@ -0,0 +1,51 @@
+Valve OS has flow rate=0; tunnels lead to valves EE, CL
+Valve EN has flow rate=0; tunnels lead to valves CL, GV
+Valve RR has flow rate=24; tunnels lead to valves FS, YP
+Valve VB has flow rate=20; tunnels lead to valves UU, EY, SG, ZB
+Valve UU has flow rate=0; tunnels lead to valves OT, VB
+Valve WH has flow rate=0; tunnels lead to valves CS, JS
+Valve OF has flow rate=25; tunnel leads to valve YM
+Valve TY has flow rate=0; tunnels lead to valves AA, GQ
+Valve RV has flow rate=0; tunnels lead to valves BT, YX
+Valve GK has flow rate=0; tunnels lead to valves GD, AA
+Valve EL has flow rate=0; tunnels lead to valves EK, EE
+Valve OT has flow rate=9; tunnels lead to valves YR, BJ, OX, UU, HJ
+Valve DG has flow rate=11; tunnels lead to valves BN, QE
+Valve YR has flow rate=0; tunnels lead to valves OT, YX
+Valve GV has flow rate=0; tunnels lead to valves AA, EN
+Valve BN has flow rate=0; tunnels lead to valves DG, LU
+Valve FS has flow rate=0; tunnels lead to valves TI, RR
+Valve DW has flow rate=0; tunnels lead to valves SS, MS
+Valve DJ has flow rate=0; tunnels lead to valves KY, GD
+Valve BJ has flow rate=0; tunnels lead to valves OT, BT
+Valve KY has flow rate=0; tunnels lead to valves EE, DJ
+Valve YP has flow rate=0; tunnels lead to valves YM, RR
+Valve LU has flow rate=0; tunnels lead to valves BN, CS
+Valve OX has flow rate=0; tunnels lead to valves OT, XD
+Valve ZB has flow rate=0; tunnels lead to valves VB, PP
+Valve CL has flow rate=10; tunnels lead to valves KQ, EN, OS, MQ
+Valve XD has flow rate=0; tunnels lead to valves KR, OX
+Valve YM has flow rate=0; tunnels lead to valves OF, YP
+Valve EY has flow rate=0; tunnels lead to valves MS, VB
+Valve KQ has flow rate=0; tunnels lead to valves CS, CL
+Valve SS has flow rate=0; tunnels lead to valves AA, DW
+Valve SG has flow rate=0; tunnels lead to valves VB, KR
+Valve EE has flow rate=22; tunnels lead to valves XR, OS, KY, EL
+Valve OI has flow rate=0; tunnels lead to valves RE, MS
+Valve QE has flow rate=0; tunnels lead to valves DG, GD
+Valve GD has flow rate=3; tunnels lead to valves GK, DJ, MQ, QE, JS
+Valve EK has flow rate=23; tunnel leads to valve EL
+Valve GQ has flow rate=0; tunnels lead to valves CS, TY
+Valve CS has flow rate=7; tunnels lead to valves GQ, WH, KQ, LU
+Valve MS has flow rate=4; tunnels lead to valves HJ, EY, DW, OI
+Valve XR has flow rate=0; tunnels lead to valves EE, AA
+Valve RE has flow rate=6; tunnels lead to valves TI, PP, OI
+Valve KR has flow rate=17; tunnels lead to valves XD, SG
+Valve BT has flow rate=15; tunnels lead to valves BJ, RV
+Valve PP has flow rate=0; tunnels lead to valves RE, ZB
+Valve TI has flow rate=0; tunnels lead to valves RE, FS
+Valve HJ has flow rate=0; tunnels lead to valves OT, MS
+Valve AA has flow rate=0; tunnels lead to valves GK, GV, SS, XR, TY
+Valve MQ has flow rate=0; tunnels lead to valves GD, CL
+Valve JS has flow rate=0; tunnels lead to valves GD, WH
+Valve YX has flow rate=5; tunnels lead to valves YR, RV
diff --git a/2022/16/test b/2022/16/test
@@ -0,0 +1,10 @@
+Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
+Valve BB has flow rate=13; tunnels lead to valves CC, AA
+Valve CC has flow rate=2; tunnels lead to valves DD, BB
+Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
+Valve EE has flow rate=3; tunnels lead to valves FF, DD
+Valve FF has flow rate=0; tunnels lead to valves EE, GG
+Valve GG has flow rate=0; tunnels lead to valves FF, HH
+Valve HH has flow rate=22; tunnel leads to valve GG
+Valve II has flow rate=0; tunnels lead to valves AA, JJ
+Valve JJ has flow rate=21; tunnel leads to valve II
