How Does Day 16 Work?

[jjorissen52]

I've been struggling to complete day 16, my part 1 runs but part 2 is just too slow, and I came across this repo while looking for ways to optimize my solution (thanks for making this repository public, BTW)! I've been looking over your solutions trying to understand them. It's mostly clear and concise, very well written, but I don't quite understand how your solution to Day 16 works. Link to Day 16 in case you need a refresher.

I'll copy and paste your solution below with comments that I've added which explain my thoughts

use hashbrown::HashMap;
use itertools::Itertools;

#[aoc::main(16)]
fn main(input: &str) -> (u16, u16) {
  // vec of valve tuples in descending order of flow
  let valves = input.lines()
    .map(|l| {
      let mut words = l.split(|c: char| !c.is_uppercase() && !c.is_ascii_digit()).filter(|w| !w.is_empty()).skip(1);
      let valve = words.next().unwrap();
      let flow = words.next().unwrap().parse::<u16>().unwrap();
      let tunnels = words.collect::<Vec<_>>();
      (valve, flow, tunnels)
    })
    .sorted_by_key(|(_, flow, _)| -(*flow as i32))
    .collect::<Vec<_>>();
  // map of labels to their index in the valves, flow, and adj vectors
  let labels = valves.iter().enumerate().map(|(i, v)| (v.0, i)).collect::<HashMap<_, _>>();
  let flow = valves.iter().map(|(_,flow,_)| *flow).collect::<Vec<_>>();
  // vec of available valves from each valve
  let adj = valves.iter().map(|(_, _, tunnels)| tunnels.iter().map(|t| labels[t]).collect::<Vec<_>>()).collect::<Vec<_>>();
  // index marking ending of all "interesting" valves
  let m = valves.iter().position(|(_, flow, _)| *flow == 0).unwrap();
  // 2^(interesting_valves.len()), number of possible configurations of "interesting" valves ??
  let mm = 1 << m;

  // opt[time][node][available valves]
  let mut opt = vec![vec![vec![0; mm]; valves.len()]; 30];
  for t in 1..30 { // iterate over time...
    for i in 0..valves.len() { // iterate over all valves
      let ii = 1 << i; // 2^i
      for x in 0..mm { // iterate over all possible valve configurations
        let mut tmp = opt[t][i][x]; // should always be 0
        if ii & x != 0 && t >= 2 { // if this valve should be "on" for this particular configuration
          // I don't understand what x - ii is, or why it's flow[i] * t... isn't that backwards if we are progressing forwards in time?
          // how does this take into account the "cost" to get to a new location?
          tmp = tmp.max(opt[t-1][i][x - ii] + flow[i] * t as u16);
        }
        // optimal for this iteration is max(this location, adjacent locations...)
        opt[t][i][x] = tmp.max(adj[i].iter().map(|&j| opt[t-1][j][x]).max().unwrap());
      }
    }
  }

  let start = labels["AA"];
  let p1 = opt[29][start][mm - 1]; // opt[t of interest][starting position][??]
  // ??
  let p2 = (0..mm/2).map(|x| opt[25][start][x] + opt[25][start][mm-1-x]).max().unwrap();
  (p1, p2)
}

I would really appreciate it if you'd take the time to explain this to me. Thank you.