aboutsummaryrefslogtreecommitdiff
path: root/2022
diff options
context:
space:
mode:
Diffstat (limited to '2022')
-rw-r--r--2022/16/a.rs112
-rw-r--r--2022/16/b.rs243
2 files changed, 187 insertions, 168 deletions
diff --git a/2022/16/a.rs b/2022/16/a.rs
index d6f3569..da9a881 100644
--- a/2022/16/a.rs
+++ b/2022/16/a.rs
@@ -10,14 +10,16 @@ struct Node {
10 10
11#[derive(Debug, Copy, Clone)] 11#[derive(Debug, Copy, Clone)]
12struct MapState { 12struct MapState {
13 max_pos: usize,
13 valves: usize, 14 valves: usize,
14 pos_ind: usize, 15 pub pos: usize
15 max_pos: usize
16} 16}
17 17
18#[derive(Debug, Clone)] 18#[derive(Debug, Clone)]
19struct Map { 19struct Map {
20 index: HashMap<u16, usize>, 20 index: HashMap<u16, usize>,
21 state_index: HashMap<u16, usize>,
22 pressure: Vec<usize>,
21 nodes: Vec<Node> 23 nodes: Vec<Node>
22} 24}
23 25
@@ -44,9 +46,34 @@ impl Node {
44 } 46 }
45} 47}
46 48
49impl 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
47impl Map { 72impl Map {
48 fn from_stdin() -> Map { 73 fn from_stdin() -> Map {
49 let mut line = String::new(); 74 let mut line = String::new();
75
76 // Get the nodes
50 let mut nodes = Vec::<Node>::new(); 77 let mut nodes = Vec::<Node>::new();
51 while std::io::stdin().read_line(&mut line).unwrap() > 0 { 78 while std::io::stdin().read_line(&mut line).unwrap() > 0 {
52 let node = Node::from_line(&line); 79 let node = Node::from_line(&line);
@@ -58,78 +85,81 @@ impl Map {
58 } 85 }
59 line.clear(); 86 line.clear();
60 } 87 }
61 let index = nodes.iter()
62 .enumerate()
63 .map(|(i, n)| (n.name, i))
64 .collect::<HashMap<_, _>>();
65 Map { index, nodes }
66 }
67 88
68 fn state_max(&self) -> usize { 89 // Compute the node-name-to-index tables
69 let mut i: usize = 0; 90 let mut j = 0;
70 let mut tot: usize = 0; 91 let mut index = HashMap::<u16, usize>::new();
71 for n in &self.nodes { 92 let mut state_index = HashMap::<u16, usize>::new();
72 if n.rate == 0 { continue; } 93 let mut pressure = vec![0];
73 tot += 1 << i; 94 for i in 0..nodes.len() {
74 i += 1; 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 }
75 } 105 }
76 let len = self.nodes.len(); 106
77 tot * len + len 107 Map { index, state_index, pressure, nodes }
78 } 108 }
79 109
80 fn released_pressure(&self) -> usize { 110 fn state_max(&self) -> usize {
81 self.nodes.iter() 111 self.index.len() * (1 << self.state_index.len())
82 .map(|n| if n.valve_on { n.rate } else { 0 })
83 .sum()
84 } 112 }
85 113
86 fn most_pressure(&self, minutes: usize) -> usize { 114 fn most_pressure(&self, minutes: usize) -> usize {
87 let n = self.state_max(); 115 let n = self.state_max();
88 let mut t = vec![0 as usize; n]; 116 let mut t = vec![0 as usize; n];
89 let mut u = vec![0 as usize; n]; 117 let mut u = vec![0 as usize; n];
90 let mut map = self.clone();
91 118
92 // Setup table for last minute 119 // Setup table for last minute
93 for s in 0..n { 120 for s in 0..n {
94 map.set_state(s); 121 t[s] = self.pressure[MapState::from_usize(s, self).valves];
95 t[s] = map.released_pressure(); 122 u[s] = t[s];
96 } 123 }
97 124
98 // Dynamic programming counting back to 0 minutes 125 // Dynamic programming counting back to 0 minutes
99 for i in (0..minutes).rev() { 126 for i in 0..minutes-1 {
100 // Double buffer technique so we don't have to swap vectors 127 // Double buffer technique so we don't have to swap vectors
101 let (current, next) = if i % 2 == minutes % 2 { 128 let (current, next) = if i % 2 == 0 {
102 (&mut t, &mut u) 129 (&mut t, &u)
103 } else { 130 } else {
104 (&mut u, &mut t) 131 (&mut u, &t)
105 }; 132 };
106 for s in 0..n { 133 for s in 0..n {
107 map.set_state(s); 134 let mut state = MapState::from_usize(s, self);
108 let pos = map.pos;
109 let mut k = 0; 135 let mut k = 0;
110 let ind = map.index[&pos]; 136 let ind = self.index[&self.nodes[state.pos].name];
111 let p = map.released_pressure(); 137 let p = self.pressure[state.valves];
112 138
113 // Try turning on the valve 139 // Try turning on the valve
114 if map.nodes[ind].rate > 0 && !map.nodes[ind].valve_on { 140 if self.nodes[ind].rate > 0 {
115 map.nodes[ind].valve_on = true; 141 let si = self.state_index[&self.nodes[ind].name];
116 k = max(k, p + next[map.get_state()]); 142 if !state.get_valve(si) {
117 map.nodes[ind].valve_on = false; 143 state.toggle_valve(si);
144 k = max(k, p + next[state.to_usize()]);
145 state.toggle_valve(si);
146 }
118 } 147 }
119 148
120 // Try moving to a neighbor 149 // Try moving to a neighbor
121 for v in &map.nodes[ind].neighbors { 150 for v in &self.nodes[ind].neighbors {
122 map.pos = *v; 151 state.pos = self.index[v];
123 k = max(k, p + next[map.get_state()]); 152 k = max(k, p + next[state.to_usize()]);
124 } 153 }
125 current[s] = k; 154 current[s] = k;
126 } 155 }
127 } 156 }
128 if 0 == minutes % 2 { t[0] } else { u[0] } 157 if 0 == minutes % 2 { t[0] } else { u[0] } // Initial state = 0
129 } 158 }
130} 159}
131 160
132fn main() { 161fn main() {
133 let map = Map::from_stdin(); 162 let map = Map::from_stdin();
134 println!("{}", map.most_pressure(29)); 163 let result = map.most_pressure(30);
164 println!("{result}");
135} 165}
diff --git a/2022/16/b.rs b/2022/16/b.rs
index defd5d1..3e2f65e 100644
--- a/2022/16/b.rs
+++ b/2022/16/b.rs
@@ -1,20 +1,29 @@
1use std::cmp::{max, Eq, PartialEq}; 1// This code is slow, about 5 minutes on my laptop
2
3use std::cmp::max;
2use std::collections::HashMap; 4use std::collections::HashMap;
3use std::hash::{Hash, Hasher};
4 5
5#[derive(Debug, Clone)] 6#[derive(Debug, Clone)]
6struct Node { 7struct Node {
7 name: u16, 8 name: u16,
8 rate: usize, 9 rate: usize,
9 neighbors: Vec<u16>, 10 neighbors: Vec<u16>
10 valve_on: bool 11}
12
13#[derive(Debug, Copy, Clone)]
14struct MapState {
15 max_pos: usize,
16 valves: usize,
17 pub pos1: usize,
18 pub pos2: usize
11} 19}
12 20
13#[derive(Debug, Clone)] 21#[derive(Debug, Clone)]
14struct Map { 22struct Map {
15 index: HashMap<u16, usize>, 23 index: HashMap<u16, usize>,
16 nodes: Vec<Node>, 24 state_index: HashMap<u16, usize>,
17 pos: u16 25 pressure: Vec<usize>,
26 nodes: Vec<Node>
18} 27}
19 28
20fn getname(line: &str) -> u16 { 29fn getname(line: &str) -> u16 {
@@ -36,13 +45,39 @@ impl Node {
36 neighbors.push(getname(&line[i..])); 45 neighbors.push(getname(&line[i..]));
37 i += 4; 46 i += 4;
38 } 47 }
39 Node { name, rate, neighbors, valve_on: false } 48 Node { name, rate, neighbors }
49 }
50}
51
52impl 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;
40 } 73 }
41} 74}
42 75
43impl Map { 76impl Map {
44 fn from_stdin() -> Map { 77 fn from_stdin() -> Map {
45 let mut line = String::new(); 78 let mut line = String::new();
79
80 // Get the nodes
46 let mut nodes = Vec::<Node>::new(); 81 let mut nodes = Vec::<Node>::new();
47 while std::io::stdin().read_line(&mut line).unwrap() > 0 { 82 while std::io::stdin().read_line(&mut line).unwrap() > 0 {
48 let node = Node::from_line(&line); 83 let node = Node::from_line(&line);
@@ -54,163 +89,117 @@ impl Map {
54 } 89 }
55 line.clear(); 90 line.clear();
56 } 91 }
57 let index = nodes.iter()
58 .enumerate()
59 .map(|(i, n)| (n.name, i))
60 .collect::<HashMap<_, _>>();
61 Map { index, nodes, pos: getname("AA") }
62 }
63 92
64 fn get_state(&self) -> usize { 93 // Compute the node-name-to-index tables
65 let mut i: usize = 0; 94 let mut j = 0;
66 let mut tot: usize = 0; 95 let mut index = HashMap::<u16, usize>::new();
67 for n in &self.nodes { 96 let mut state_index = HashMap::<u16, usize>::new();
68 if n.rate == 0 { continue; } 97 let mut pressure = vec![0];
69 if n.valve_on { tot += 1 << i; } 98 for i in 0..nodes.len() {
70 i += 1; 99 index.insert(nodes[i].name, i);
71 } 100 if nodes[i].rate != 0 {
72 tot * self.nodes.len() + self.index[&self.pos] 101 state_index.insert(nodes[i].name, j);
73 } 102 j += 1;
74 103
75 fn set_state(&mut self, state: usize) { 104 // Pre-compute flow rate for all states with node[i] turned on
76 let mut s = state; 105 for k in 0..pressure.len() {
77 let len = self.nodes.len(); 106 pressure.push(pressure[k] + nodes[i].rate);
78 self.pos = self.nodes[s%len].name; 107 }
79 s /= len; 108 }
80 for i in 0..len {
81 if self.nodes[i].rate == 0 { continue; }
82 self.nodes[i].valve_on = s % 2 == 1;
83 s /= 2;
84 } 109 }
85 }
86 110
87 fn state_max(&self) -> usize { 111 Map { index, state_index, pressure, nodes }
88 let mut i: usize = 0;
89 let mut tot: usize = 0;
90 for n in &self.nodes {
91 if n.rate == 0 { continue; }
92 tot += 1 << i;
93 i += 1;
94 }
95 let len = self.nodes.len();
96 tot * len + len
97 } 112 }
98 113
99 fn released_pressure(&self) -> usize { 114 fn state_max(&self) -> usize {
100 self.nodes.iter() 115 self.index.len() * self.index.len() * (1 << self.state_index.len())
101 .map(|n| if n.valve_on { n.rate } else { 0 })
102 .sum()
103 } 116 }
104 117
105/*
106 fn most_pressure(&self, minutes: usize) -> usize { 118 fn most_pressure(&self, minutes: usize) -> usize {
107 let n = self.state_max(); 119 let n = self.state_max();
108 let mut t = vec![0 as usize; n]; 120 let mut t = vec![0 as usize; n];
109 let mut u = vec![0 as usize; n]; 121 let mut u = vec![0 as usize; n];
110 let mut map = self.clone();
111 122
112 // Setup table for last minute 123 // Setup table for last minute
113 for s in 0..n { 124 for s in 0..n {
114 map.set_state(s); 125 t[s] = self.pressure[MapState::from_usize(s, self).valves];
115 t[s] = map.released_pressure(); 126 u[s] = t[s];
116 } 127 }
117 128
118 // Dynamic programming counting back to 0 minutes 129 // Dynamic programming counting back to 0 minutes
119 for i in (0..minutes).rev() { 130 for i in 0..minutes-1 {
120 // Double buffer technique so we don't have to swap vectors 131 // Double buffer technique so we don't have to swap vectors
121 let (current, next) = if i % 2 == minutes % 2 { 132 let (current, next) = if i % 2 == 0 {
122 (&mut t, &mut u) 133 (&mut t, &u)
123 } else { 134 } else {
124 (&mut u, &mut t) 135 (&mut u, &t)
125 }; 136 };
126 for s in 0..n { 137 for s in 0..n {
127 map.set_state(s); 138 let mut state = MapState::from_usize(s, self);
128 let pos = map.pos; 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;
129 let mut k = 0; 143 let mut k = 0;
130 let ind = map.index[&pos];
131 let p = map.released_pressure();
132 144
133 // Try turning on the valve 145 // Try turning on valve at pos1
134 if map.nodes[ind].rate > 0 && !map.nodes[ind].valve_on { 146 if self.nodes[ind1].rate > 0 {
135 map.nodes[ind].valve_on = true; 147 let si = self.state_index[&self.nodes[ind1].name];
136 k = max(k, p + next[map.get_state()]); 148 if !state.get_valve(si) {
137 map.nodes[ind].valve_on = false; 149 state.toggle_valve(si);
138 }
139 150
140 // Try moving to a neighbor 151 // Try turning on valve at pos2
141 for v in &map.nodes[ind].neighbors { 152 if self.nodes[ind2].rate > 0 {
142 map.pos = *v; 153 let sj = self.state_index[&self.nodes[ind2].name];
143 k = max(k, p + next[map.get_state()]); 154 if !state.get_valve(sj) {
144 } 155 state.toggle_valve(sj);
145 current[s] = k; 156 k = max(k, p + next[state.to_usize()]);
146 } 157 state.toggle_valve(sj);
147 } 158 }
148 if 0 == minutes % 2 { t[0] } else { u[0] } 159 }
149 }
150*/
151 160
152 fn most_pressure(&self, minutes: usize) -> usize { 161 // Try moving pos2
153 let n = self.state_max(); 162 for w in &self.nodes[ind2].neighbors {
154 let mut t = vec![0 as usize; n]; 163 state.pos2 = self.index[w];
155 let mut u = vec![0 as usize; n]; 164 k = max(k, p + next[state.to_usize()]);
156 let mut map = self.clone(); 165 }
166 state.pos2 = pos2backup;
157 167
158 // Setup table for last minute 168 state.toggle_valve(si);
159 for s in 0..n { 169 }
160 map.set_state(s); 170 }
161 t[s] = map.released_pressure();
162 }
163 171
164 // Dynamic programming counting back to 0 minutes 172 // Try moving pos1
165 for i in (0..minutes).rev() { 173 for v in &self.nodes[ind1].neighbors {
166 // Double buffer technique so we don't have to swap vectors 174 state.pos1 = self.index[v];
167 let (current, next) = if i % 2 == minutes % 2 {
168 (&mut t, &mut u)
169 } else {
170 (&mut u, &mut t)
171 };
172 for s in 0..n {
173 map.set_state(s);
174 let pos = map.pos;
175 let mut k = 0;
176 let ind = map.index[&pos];
177 let p = map.released_pressure();
178 175
179 // Try turning on the valve 176 // Try turning on valve at pos2
180 if map.nodes[ind].rate > 0 && !map.nodes[ind].valve_on { 177 if self.nodes[ind2].rate > 0 {
181 map.nodes[ind].valve_on = true; 178 let sj = self.state_index[&self.nodes[ind2].name];
182 k = max(k, p + next[map.get_state()]); 179 if !state.get_valve(sj) {
183 map.nodes[ind].valve_on = false; 180 state.toggle_valve(sj);
184 } 181 k = max(k, p + next[state.to_usize()]);
182 state.toggle_valve(sj);
183 }
184 }
185 185
186 // Try moving to a neighbor 186 // Try moving pos2
187 for v in &map.nodes[ind].neighbors { 187 for w in &self.nodes[ind2].neighbors {
188 map.pos = *v; 188 state.pos2 = self.index[w];
189 k = max(k, p + next[map.get_state()]); 189 k = max(k, p + next[state.to_usize()]);
190 }
191 state.pos2 = pos2backup;
190 } 192 }
193
191 current[s] = k; 194 current[s] = k;
192 } 195 }
193 } 196 }
194 if 0 == minutes % 2 { t[0] } else { u[0] } 197 if 0 == minutes % 2 { t[0] } else { u[0] } // Initial state = 0
195 }
196}
197
198impl PartialEq for Map {
199 fn eq(&self, other: &Self) -> bool {
200 self.get_state() == other.get_state()
201 }
202}
203
204impl Eq for Map {}
205
206impl Hash for Map {
207 fn hash<H: Hasher>(&self, hasher: &mut H) {
208 hasher.write_usize(self.get_state());
209 } 198 }
210} 199}
211 200
212fn main() { 201fn main() {
213 let map = Map::from_stdin(); 202 let map = Map::from_stdin();
214 let mut t = HashMap::<Map, usize>::new(); 203 let result = map.most_pressure(26);
215 println!("{}", map.most_pressure(29, t)); 204 println!("{result}");
216} 205}

Generated with cgit - Back to sebastiano.tronto.net