AoC 2022 Day 16 part 1

input.txt

IK 6 EU XY AD SC CH
YW 11 HD MW ID JD BJ
HD 0 YW AA
LZ 0 CR IT
LO 0 CH YB
PM 0 EN YB
ME 0 VP TX
CK 0 MD LL
RM 0 TX AA
MU 0 MD BX
WK 0 HG IP
MT 0 ZZ CR
EN 0 JE PM
AD 0 JE IK
IT 8 RY LZ KC
JD 0 MD YW
RY 0 IT YB
FS 10 QQ IP VG VP LL
VT 0 TX MW
WF 0 JE HJ
CH 0 LO IK
PZ 17 NZ HJ
SS 18 BJ
MW 0 YW VT
JE 16 AD JG EN ZZ WF
AA 0 LQ NG RM CA HD
DS 21 PB
QQ 0 FS ID
HG 20 QF WK
ID 0 QQ YW
WL 0 KI EU
OT 0 CR KI
KI 14 OT UN WL XU KC
ZZ 0 MT JE
VD 0 CR RI
PB 0 DS MD
XU 0 KI SQ
CR 7 OT MT XY VD LZ
QF 0 HG NZ
JG 0 JE QL
VP 0 FS ME
HJ 0 WF PZ
MD 12 CK MU CA JD PB
SQ 22 XU
XY 0 CR IK
VG 0 LQ FS
YB 13 RI RY LO UN PM
LQ 0 AA VG
BX 0 MU TX
KC 0 IT KI
IP 0 FS WK
SC 0 NG IK
BJ 0 SS YW
NZ 0 QF PZ
TX 3 RM QL BX ME VT
EU 0 WL IK
QL 0 TX JG
CA 0 MD AA
LL 0 FS CK
UN 0 KI YB
RI 0 YB VD
NG 0 SC AA

main.rs

use std::{
    collections::{BTreeSet, HashMap},
    fs,
    time::SystemTime,
};

#[derive(Debug)]
struct Valve {
    rate: u32,
    adjs: Vec<usize>,
}

impl Valve {
    fn with_filename(filename: &str) -> Vec<Self> {
        let mut valves = vec![];
        let contents = fs::read_to_string(filename).unwrap();
        let mut lines = contents
            .lines()
            .collect::<BTreeSet<_>>()
            .into_iter()
            .map(str::split_ascii_whitespace)
            .collect::<Vec<_>>();

        let mut label_to_index = HashMap::new();
        for (index, line) in lines.iter_mut().enumerate() {
            label_to_index.insert(line.next().unwrap(), index);
        }

        for mut line in lines {
            let rate = line.next().unwrap().parse().unwrap();
            let adjs: Vec<_> = line.map(|label| label_to_index[label]).collect();
            valves.push(Self { rate, adjs });
        }

        valves
    }
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct State {
    valve_states: Vec<bool>,
    position: usize,
    rate: u32,
    released_pressure: u32,
}

impl State {
    fn new(valves: &[Valve]) -> Self {
        // let valve_states: Vec<bool> = valves.iter().map(|valve| valve.rate == 0).collect(); // Slow

        let mut valve_states = Vec::with_capacity(valves.len()); // Fast
        for valve in valves {
            valve_states.push(valve.rate == 0);
        }

        State {
            valve_states,
            position: 0,
            rate: 0,
            released_pressure: 0,
        }
    }

    fn tick(&mut self) {
        self.released_pressure += self.rate;
    }

    fn open_valve(&self, valves: &[Valve]) -> Self {
        assert!(!self.valve_states[self.position]);

        let mut next = self.clone();
        next.tick();
        next.valve_states[self.position] = true;
        next.rate += valves[next.position].rate;
        next
    }

    fn move_to(&self, dest: usize) -> Self {
        let mut next = self.clone();
        next.tick();
        next.position = dest;
        next
    }
}

static mut COUNT: u64 = 0;
static mut HIT: u64 = 0;
static mut INSERT: u64 = 0;

fn solve(
    current_state: &State,
    valves: &[Valve],
    remaining_time: u32,
    last_position: usize,
    cache: &mut HashMap<State, (u32, u32)>,
) -> u32 {
    unsafe {
        COUNT += 1;
    }

    if let Some((time, total)) = cache.get(current_state) {
        if *time >= remaining_time {
            unsafe {
                HIT += 1;
            }
            return *total;
        }
    }

    if remaining_time == 0 {
        let total = current_state.released_pressure;
        cache.insert(current_state.clone(), (remaining_time, total));
        unsafe {
            INSERT += 1;
        }
        return total;
    }

    if current_state.valve_states.iter().all(|x| *x) {
        let total = current_state.released_pressure + current_state.rate * remaining_time;
        cache.insert(current_state.clone(), (remaining_time, total));
        unsafe {
            INSERT += 1;
        }
        return total;
    }

    let mut result = 0;

    if !current_state.valve_states[current_state.position] {
        result = result.max(solve(
            &current_state.open_valve(valves),
            valves,
            remaining_time - 1,
            current_state.position,
            cache,
        ));
    }

    for dest in &valves[current_state.position].adjs {
        if *dest == last_position {
            continue;
        }

        result = result.max(solve(
            &current_state.move_to(*dest),
            valves,
            remaining_time - 1,
            current_state.position,
            cache,
        ));
    }

    cache.insert(current_state.clone(), (remaining_time, result));
    unsafe {
        INSERT += 1;
    }
    result
}

fn main() {
    let start = SystemTime::now();

    let valves = Valve::with_filename("input.txt");

    let after_parse = SystemTime::now();

    let state = State::new(&valves);
    let mut cache = HashMap::new();

    println!("{}", solve(&state, &valves, 30, 0, &mut cache));

    let after_solve = SystemTime::now();

    println!("{} {}", cache.len(), cache.capacity());

    unsafe {
        println!("call count: {COUNT}");
        println!("cache hits: {HIT}");
        println!("cache insert: {INSERT}");
    }

    println!("{:?}", after_parse.duration_since(start));
    println!("{:?}", after_solve.duration_since(after_parse));
}

map.svg

push.svg