- commit
- 04348834a32d318307642ed814c794f007ecd8b5
- parent
- 150ed5b49297d8847c67da395af813b348ce750d
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-16 10:43
2022-12-16 part 1
Diffstat
| A | 2022/16/input.txt | 57 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/16/solution.rs | 144 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/16/test.txt | 10 | ++++++++++ |
3 files changed, 211 insertions, 0 deletions
diff --git a/2022/16/input.txt b/2022/16/input.txt
@@ -0,0 +1,57 @@ -1 1 Valve TM has flow rate=3; tunnels lead to valves WB, PE, DX, TK, CH -1 2 Valve ST has flow rate=21; tunnels lead to valves NS, DE, UX, XU -1 3 Valve IX has flow rate=0; tunnels lead to valves DK, LR -1 4 Valve OG has flow rate=0; tunnels lead to valves MN, FK -1 5 Valve FR has flow rate=0; tunnels lead to valves JQ, GS -1 6 Valve HU has flow rate=0; tunnels lead to valves TJ, XX -1 7 Valve WC has flow rate=15; tunnel leads to valve TJ -1 8 Valve JT has flow rate=0; tunnels lead to valves OV, AA -1 9 Valve DW has flow rate=0; tunnels lead to valves FK, AA -1 10 Valve RG has flow rate=0; tunnels lead to valves PS, DK -1 11 Valve JQ has flow rate=14; tunnels lead to valves VM, FR -1 12 Valve XX has flow rate=5; tunnels lead to valves GP, MN, WB, LM, HU -1 13 Valve IN has flow rate=11; tunnels lead to valves OK, GS, DU -1 14 Valve LR has flow rate=7; tunnels lead to valves IX, NR, YY, HZ, PR -1 15 Valve TK has flow rate=0; tunnels lead to valves TM, OV -1 16 Valve VM has flow rate=0; tunnels lead to valves KQ, JQ -1 17 Valve IC has flow rate=0; tunnels lead to valves FK, DU -1 18 Valve CH has flow rate=0; tunnels lead to valves EZ, TM -1 19 Valve OV has flow rate=10; tunnels lead to valves YW, JT, NN, TK -1 20 Valve KQ has flow rate=17; tunnels lead to valves VM, YW, CY -1 21 Valve NR has flow rate=0; tunnels lead to valves FK, LR -1 22 Valve MN has flow rate=0; tunnels lead to valves OG, XX -1 23 Valve YY has flow rate=0; tunnels lead to valves LR, LM -1 24 Valve OK has flow rate=0; tunnels lead to valves CY, IN -1 25 Valve DK has flow rate=20; tunnels lead to valves FA, RG, IX -1 26 Valve CY has flow rate=0; tunnels lead to valves KQ, OK -1 27 Valve PR has flow rate=0; tunnels lead to valves DX, LR -1 28 Valve DE has flow rate=0; tunnels lead to valves ST, EL -1 29 Valve TJ has flow rate=0; tunnels lead to valves WC, HU -1 30 Valve NS has flow rate=0; tunnels lead to valves WU, ST -1 31 Valve PE has flow rate=0; tunnels lead to valves TM, XO -1 32 Valve DU has flow rate=0; tunnels lead to valves IN, IC -1 33 Valve DX has flow rate=0; tunnels lead to valves TM, PR -1 34 Valve EQ has flow rate=0; tunnels lead to valves AA, GP -1 35 Valve AA has flow rate=0; tunnels lead to valves JT, EZ, HZ, DW, EQ -1 36 Valve WB has flow rate=0; tunnels lead to valves TM, XX -1 37 Valve PF has flow rate=23; tunnels lead to valves BP, WU -1 38 Valve FJ has flow rate=19; tunnels lead to valves DO, TY, NN, PS -1 39 Valve GP has flow rate=0; tunnels lead to valves XX, EQ -1 40 Valve FK has flow rate=4; tunnels lead to valves DW, XO, OG, IC, NR -1 41 Valve DO has flow rate=0; tunnels lead to valves XU, FJ -1 42 Valve XO has flow rate=0; tunnels lead to valves FK, PE -1 43 Valve PS has flow rate=0; tunnels lead to valves RG, FJ -1 44 Valve MD has flow rate=25; tunnel leads to valve BP -1 45 Valve EZ has flow rate=0; tunnels lead to valves CH, AA -1 46 Valve GS has flow rate=0; tunnels lead to valves IN, FR -1 47 Valve XU has flow rate=0; tunnels lead to valves DO, ST -1 48 Valve WU has flow rate=0; tunnels lead to valves PF, NS -1 49 Valve YW has flow rate=0; tunnels lead to valves OV, KQ -1 50 Valve HZ has flow rate=0; tunnels lead to valves LR, AA -1 51 Valve TY has flow rate=0; tunnels lead to valves FJ, EL -1 52 Valve BP has flow rate=0; tunnels lead to valves MD, PF -1 53 Valve EL has flow rate=18; tunnels lead to valves DE, TY -1 54 Valve UX has flow rate=0; tunnels lead to valves FA, ST -1 55 Valve FA has flow rate=0; tunnels lead to valves UX, DK -1 56 Valve NN has flow rate=0; tunnels lead to valves OV, FJ -1 57 Valve LM has flow rate=0; tunnels lead to valves XX, YY
diff --git a/2022/16/solution.rs b/2022/16/solution.rs
@@ -0,0 +1,144 @@
-1 1 use std::collections::HashMap;
-1 2 use std::collections::HashSet;
-1 3
-1 4 #[path = "../lib.rs"] mod lib;
-1 5
-1 6 #[derive(Clone)]
-1 7 struct Valve {
-1 8 rate: u64,
-1 9 tunnels: HashMap<String, u64>,
-1 10 }
-1 11
-1 12 struct QueueEntry {
-1 13 pos: String,
-1 14 open: HashSet<String>,
-1 15 time: u64,
-1 16 pressure: u64,
-1 17 potential: u64,
-1 18 }
-1 19
-1 20 fn get_input() -> HashMap<String, Valve> {
-1 21 let mut map = HashMap::new();
-1 22
-1 23 for line in lib::iter_input() {
-1 24 let (line1, line2) = lib::split_once(line.as_str(), ';').unwrap();
-1 25 let (line11, line12) = lib::split_once(line1, '=').unwrap();
-1 26 let name = line11[6..8].to_string();
-1 27 let tunnels_s = match line2.strip_prefix(" tunnels lead to valves ") {
-1 28 Some(s) => s,
-1 29 _ => line2.strip_prefix(" tunnel leads to valve ").unwrap(),
-1 30 };
-1 31 let mut tunnels = HashMap::new();
-1 32 for s in tunnels_s.split(", ") {
-1 33 tunnels.insert(s.to_string(), 1);
-1 34 }
-1 35 map.insert(name, Valve {
-1 36 rate: line12.parse().unwrap(),
-1 37 tunnels: tunnels,
-1 38 });
-1 39 }
-1 40
-1 41 return map;
-1 42 }
-1 43
-1 44 fn make_entry(valves: &HashMap<String, Valve>, pos: String, open: HashSet<String>, time: u64, pressure: u64) -> QueueEntry {
-1 45 let mut rates = valves.iter()
-1 46 .filter(|(key, _valve)| !open.contains(*key))
-1 47 .map(|(_key, valve)| valve.rate)
-1 48 .collect::<Vec<u64>>();
-1 49 rates.sort();
-1 50 rates.reverse();
-1 51
-1 52 let mut potential = pressure;
-1 53 let mut i = 0;
-1 54 let mut t = time;
-1 55 while i < rates.len() && t > 1 {
-1 56 potential += rates[i] * (t - 1);
-1 57 i += 1;
-1 58 t -= 2;
-1 59 }
-1 60
-1 61 return QueueEntry { pos, open, time, pressure, potential };
-1 62 }
-1 63
-1 64 fn get_next(queue: &mut Vec<QueueEntry>) -> Option<QueueEntry> {
-1 65 // let (i, _) = queue.iter()
-1 66 // .enumerate()
-1 67 // .max_by_key(|(_, entry)| entry.pressure)?;
-1 68 // return Some(queue.remove(i));
-1 69 return queue.pop();
-1 70 }
-1 71
-1 72 fn part1(valves: &HashMap<String, Valve>) -> u64 {
-1 73 let mut max_pressure = 0;
-1 74 let mut queue = vec![make_entry(valves, "AA".to_string(), HashSet::new(), 30, 0)];
-1 75
-1 76 while let Some(entry) = get_next(&mut queue) {
-1 77 // PERF: stop early if there is no way to reach max_pressure
-1 78 if entry.potential <= max_pressure {
-1 79 continue;
-1 80 }
-1 81
-1 82 println!("{} {} {} {} {} {}", entry.pos, entry.time, entry.pressure, entry.potential, max_pressure, queue.len());
-1 83
-1 84 if !entry.open.contains(&entry.pos) && valves[&entry.pos].rate > 0 {
-1 85 let pressure = entry.pressure + valves[&entry.pos].rate * (entry.time - 1);
-1 86 if pressure > max_pressure {
-1 87 max_pressure = pressure;
-1 88 }
-1 89
-1 90 let mut open = entry.open.clone();
-1 91 open.insert(entry.pos.clone());
-1 92 queue.push(make_entry(valves, entry.pos.clone(), open, entry.time - 1, pressure));
-1 93 }
-1 94
-1 95 for (name, len) in valves[&entry.pos].tunnels.iter() {
-1 96 if entry.time >= *len {
-1 97 queue.push(make_entry(valves, name.clone(), entry.open.clone(), entry.time - len, entry.pressure));
-1 98 }
-1 99 }
-1 100 }
-1 101
-1 102 return max_pressure;
-1 103 }
-1 104
-1 105 fn optimize_tunnels(valves: &HashMap<String, Valve>, name: &String, path: &Vec<String>) -> HashMap<String, u64> {
-1 106 let mut tunnels = HashMap::new();
-1 107 let mut p = path.clone();
-1 108 p.push(name.clone());
-1 109
-1 110 for (tunnel_name, d) in valves[name].tunnels.iter() {
-1 111 if valves[tunnel_name].rate > 0 || tunnel_name == "AA" {
-1 112 if *tunnels.get(tunnel_name).unwrap_or(&u64::MAX) > *d {
-1 113 tunnels.insert(tunnel_name.clone(), *d);
-1 114 }
-1 115 } else if !p.contains(tunnel_name) {
-1 116 for (tunnel_name2, d2) in optimize_tunnels(valves, tunnel_name, &p).iter() {
-1 117 if !p.contains(tunnel_name2) {
-1 118 if *tunnels.get(tunnel_name2).unwrap_or(&u64::MAX) > *d + *d2 {
-1 119 tunnels.insert(tunnel_name2.clone(), *d + *d2);
-1 120 }
-1 121 }
-1 122 }
-1 123 }
-1 124 }
-1 125
-1 126 return tunnels;
-1 127 }
-1 128
-1 129 fn main() {
-1 130 let valves = get_input();
-1 131
-1 132 let mut optimized = HashMap::new();
-1 133 for (name, valve) in valves.iter() {
-1 134 if valve.rate > 0 || name == "AA" {
-1 135 optimized.insert(name.clone(), Valve {
-1 136 rate: valve.rate,
-1 137 tunnels: optimize_tunnels(&valves, name, &vec![]),
-1 138 });
-1 139 }
-1 140 }
-1 141
-1 142 println!("part1: {}", part1(&optimized));
-1 143 println!("part2: {}", 0);
-1 144 }
diff --git a/2022/16/test.txt b/2022/16/test.txt
@@ -0,0 +1,10 @@ -1 1 Valve AA has flow rate=0; tunnels lead to valves DD, II, BB -1 2 Valve BB has flow rate=13; tunnels lead to valves CC, AA -1 3 Valve CC has flow rate=2; tunnels lead to valves DD, BB -1 4 Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE -1 5 Valve EE has flow rate=3; tunnels lead to valves FF, DD -1 6 Valve FF has flow rate=0; tunnels lead to valves EE, GG -1 7 Valve GG has flow rate=0; tunnels lead to valves FF, HH -1 8 Valve HH has flow rate=22; tunnel leads to valve GG -1 9 Valve II has flow rate=0; tunnels lead to valves AA, JJ -1 10 Valve JJ has flow rate=21; tunnel leads to valve II