b.rs (6401B)
1 // This code is slow, about 5 minutes on my laptop 2 3 use std::cmp::max; 4 use std::collections::HashMap; 5 6 #[derive(Debug, Clone)] 7 struct Node { 8 name: u16, 9 rate: usize, 10 neighbors: Vec<u16> 11 } 12 13 #[derive(Debug, Copy, Clone)] 14 struct MapState { 15 max_pos: usize, 16 valves: usize, 17 pub pos1: usize, 18 pub pos2: usize 19 } 20 21 #[derive(Debug, Clone)] 22 struct Map { 23 index: HashMap<u16, usize>, 24 state_index: HashMap<u16, usize>, 25 pressure: Vec<usize>, 26 nodes: Vec<Node> 27 } 28 29 fn getname(line: &str) -> u16 { 30 100 * (line.chars().nth(0).unwrap() as u16) + 31 (line.chars().nth(1).unwrap() as u16) 32 } 33 34 impl Node { 35 fn from_line(line: &str) -> Node { 36 let name = getname(&line[6..]); 37 let j = line.find(';').unwrap(); 38 let rate = line[23..j].parse::<usize>().unwrap(); 39 let mut neighbors = vec![]; 40 let mut i = j+24; 41 // "tunnels lead to valves" vs "tunnel lead to valve" 42 // What kind of sadistic animal made these inputs? 43 if line.chars().nth(i).unwrap() == ' ' { i += 1; } 44 while i < line.len() { 45 neighbors.push(getname(&line[i..])); 46 i += 4; 47 } 48 Node { name, rate, neighbors } 49 } 50 } 51 52 impl MapState { 53 fn from_usize(i: usize, map: &Map) -> MapState { 54 let max_pos = map.index.len(); 55 MapState { 56 max_pos, 57 valves: i / (max_pos * max_pos), 58 pos1: i % max_pos, 59 pos2: (i / max_pos) % max_pos 60 } 61 } 62 63 fn to_usize(&self) -> usize { 64 self.max_pos * (self.max_pos * self.valves + self.pos2) + self.pos1 65 } 66 67 fn get_valve(&self, i: usize) -> bool { 68 self.valves & (1 << i) != 0 69 } 70 71 fn toggle_valve(&mut self, i: usize) { 72 self.valves ^= 1 << i; 73 } 74 } 75 76 impl Map { 77 fn from_stdin() -> Map { 78 let mut line = String::new(); 79 80 // Get the nodes 81 let mut nodes = Vec::<Node>::new(); 82 while std::io::stdin().read_line(&mut line).unwrap() > 0 { 83 let node = Node::from_line(&line); 84 if nodes.len() > 0 && node.name == getname("AA") { 85 nodes.push(nodes[0].clone()); 86 nodes[0] = node; 87 } else { 88 nodes.push(node); 89 } 90 line.clear(); 91 } 92 93 // Compute the node-name-to-index tables 94 let mut j = 0; 95 let mut index = HashMap::<u16, usize>::new(); 96 let mut state_index = HashMap::<u16, usize>::new(); 97 let mut pressure = vec![0]; 98 for i in 0..nodes.len() { 99 index.insert(nodes[i].name, i); 100 if nodes[i].rate != 0 { 101 state_index.insert(nodes[i].name, j); 102 j += 1; 103 104 // Pre-compute flow rate for all states with node[i] turned on 105 for k in 0..pressure.len() { 106 pressure.push(pressure[k] + nodes[i].rate); 107 } 108 } 109 } 110 111 Map { index, state_index, pressure, nodes } 112 } 113 114 fn state_max(&self) -> usize { 115 self.index.len() * self.index.len() * (1 << self.state_index.len()) 116 } 117 118 fn most_pressure(&self, minutes: usize) -> usize { 119 let n = self.state_max(); 120 let mut t = vec![0 as usize; n]; 121 let mut u = vec![0 as usize; n]; 122 123 // Setup table for last minute 124 for s in 0..n { 125 t[s] = self.pressure[MapState::from_usize(s, self).valves]; 126 u[s] = t[s]; 127 } 128 129 // Dynamic programming counting back to 0 minutes 130 for i in 0..minutes-1 { 131 // Double buffer technique so we don't have to swap vectors 132 let (current, next) = if i % 2 == 0 { 133 (&mut t, &u) 134 } else { 135 (&mut u, &t) 136 }; 137 for s in 0..n { 138 let mut state = MapState::from_usize(s, self); 139 let p = self.pressure[state.valves]; 140 let ind1 = self.index[&self.nodes[state.pos1].name]; 141 let ind2 = self.index[&self.nodes[state.pos2].name]; 142 let pos2backup = state.pos2; 143 let mut k = 0; 144 145 // Try turning on valve at pos1 146 if self.nodes[ind1].rate > 0 { 147 let si = self.state_index[&self.nodes[ind1].name]; 148 if !state.get_valve(si) { 149 state.toggle_valve(si); 150 151 // Try turning on valve at pos2 152 if self.nodes[ind2].rate > 0 { 153 let sj = self.state_index[&self.nodes[ind2].name]; 154 if !state.get_valve(sj) { 155 state.toggle_valve(sj); 156 k = max(k, p + next[state.to_usize()]); 157 state.toggle_valve(sj); 158 } 159 } 160 161 // Try moving pos2 162 for w in &self.nodes[ind2].neighbors { 163 state.pos2 = self.index[w]; 164 k = max(k, p + next[state.to_usize()]); 165 } 166 state.pos2 = pos2backup; 167 168 state.toggle_valve(si); 169 } 170 } 171 172 // Try moving pos1 173 for v in &self.nodes[ind1].neighbors { 174 state.pos1 = self.index[v]; 175 176 // Try turning on valve at pos2 177 if self.nodes[ind2].rate > 0 { 178 let sj = self.state_index[&self.nodes[ind2].name]; 179 if !state.get_valve(sj) { 180 state.toggle_valve(sj); 181 k = max(k, p + next[state.to_usize()]); 182 state.toggle_valve(sj); 183 } 184 } 185 186 // Try moving pos2 187 for w in &self.nodes[ind2].neighbors { 188 state.pos2 = self.index[w]; 189 k = max(k, p + next[state.to_usize()]); 190 } 191 state.pos2 = pos2backup; 192 } 193 194 current[s] = k; 195 } 196 } 197 if 0 == minutes % 2 { t[0] } else { u[0] } // Initial state = 0 198 } 199 } 200 201 fn main() { 202 let map = Map::from_stdin(); 203 let result = map.most_pressure(26); 204 println!("{result}"); 205 }