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