Advent of Code 2022: Days 16 and 17

Well, it’s slow going. I was getting less than a day per day done, and now I’m back at work, so that’ll likely be even slower going forward. I’m retargeting mid-January for the end. But here are the next couple days’ worth!

Day 16

Not a particularly efficient implementation, but it works. We do a brute-force breadth first search here, and come up with an answer in just under two seconds, so I’m not too worried about optimization here. Both this and part 2 were run with -O for a fairly reasonable speedup.

$ time ./day16
2119
./day16  1.45s user 0.43s system 99% cpu 1.890 total

Part 1 source code

use std::collections::{HashMap, HashSet, VecDeque};
use std::fs;

#[derive(Debug)]
struct Valve {
    connections: Vec<String>,
    flow_rate: usize,
}

fn find_shortest_path<'a>(
    valves: &'a HashMap<&'a str, Valve>,
    origin: &'a str,
    destination: &str,
) -> Vec<&'a str> {
    // breadth-first search
    let mut nodes_to_check = VecDeque::new();
    nodes_to_check.push_back((origin, vec![]));
    while nodes_to_check.len() > 0 {
        let (current_node, path_to_current_node) = nodes_to_check.pop_front().unwrap();
        for connection in valves[&current_node].connections.iter() {
            let mut path_to_connection = path_to_current_node.clone();
            path_to_connection.push(connection.as_str());
            if connection == destination {
                return path_to_connection;
            }
            nodes_to_check.push_back((&connection, path_to_connection));
        }
    }
    panic!(
        "Could not find a route between {} and {}",
        origin, destination
    );
}

// Note that this only finds paths between nodes with non-zero flow rate
fn find_shortest_paths<'a>(
    valves: &'a HashMap<&'a str, Valve>,
) -> HashMap<(&'a str, &'a str), Vec<&str>> {
    let mut shortest_paths = HashMap::new();
    for (origin, _valve) in valves
        .iter()
        .filter(|(n, v)| v.flow_rate > 0 || **n == "AA")
    {
        for (destination, _valve) in valves.iter().filter(|(_, v)| v.flow_rate > 0) {
            if origin == destination {
                continue;
            }
            shortest_paths.insert(
                (*origin, *destination),
                find_shortest_path(valves, origin, destination),
            );
        }
    }
    shortest_paths
}

fn parse(data: &str) -> HashMap<&str, Valve> {
    let mut valves = HashMap::new();
    for line in data.split("\n") {
        let valve_name = &line[6..8];
        let (flow_rate, mut rest) = line[23..].split_once(';').unwrap();
        let flow_rate = flow_rate.parse().unwrap();
        // Curse you single path with single tunnel for breaking my parsing
        if rest.chars().nth(7).unwrap() == 's' {
            rest = &rest[24..]; // " tunnels lead to valves "
        } else {
            rest = &rest[23..]; // " tunnel leads to valve "
        }
        let connections = rest.split(", ").map(|s| s.to_owned()).collect();
        valves.insert(
            valve_name,
            Valve {
                connections: connections,
                flow_rate: flow_rate,
            },
        );
    }
    valves
}

fn process(data: &str) -> usize {
    let valves = parse(data);
    let mut starting_closed_flowing_valves: HashSet<&str> = valves
        .iter()
        .filter(|(_, v)| v.flow_rate > 0)
        .map(|(k, _)| *k)
        .collect();
    let shortest_paths = find_shortest_paths(&valves);

    let mut most_pressure_released = 0;

    // breadth-first search
    let mut nodes_to_check = VecDeque::new(); // (current_node, remaining_closed_valves, pressure_released, minutes_elapsed)
    if starting_closed_flowing_valves.contains("AA") {
        starting_closed_flowing_valves.remove("AA");
        nodes_to_check.push_back((
            "AA",
            starting_closed_flowing_valves,
            29 * valves["AA"].flow_rate,
            1,
        ));
    } else {
        nodes_to_check.push_back(("AA", starting_closed_flowing_valves, 0, 0));
    }
    while let Some((current_node, remaining_closed_valves, pressure_released, minutes_elapsed)) =
        nodes_to_check.pop_front()
    {
        for target_node in remaining_closed_valves.iter() {
            // can we reach it before 30 minutes is up?
            let opened_at =
                minutes_elapsed + shortest_paths[&(current_node, *target_node)].len() + 1;
            if opened_at < 30 {
                let new_pressure_released =
                    pressure_released + (30 - opened_at) * valves[target_node].flow_rate;
                let mut new_remaining_closed_valves = remaining_closed_valves.clone();
                new_remaining_closed_valves.remove(target_node);
                nodes_to_check.push_back((
                    target_node,
                    new_remaining_closed_valves,
                    new_pressure_released,
                    opened_at,
                ));
                if new_pressure_released > most_pressure_released {
                    most_pressure_released = new_pressure_released;
                }
            }
        }
    }
    most_pressure_released
}

fn main() {
    let data = fs::read_to_string("input.txt").unwrap();
    let data = data.trim();
    println!("{}", process(data));
}

#[cfg(test)]
mod test {
    use super::*;

    const DATA: &str = "Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve II";

    #[test]
    fn test_part1() {
        assert_eq!(process(DATA), 1651);
    }
}

For part 2, I wasn’t really sure what optimization I needed to do, if any. I ended up spending the better part of a day getting some very subtle bugs worked out of this one, so after that I was happy enough that it did terminate, eventually. (Notably, after running for about twelve hours!) I think there’s likely some fairly low-hanging fruit if I prune some of the possible paths that won’t work out, but…I give up!

$ /usr/bin/time -v ./day16b
[...]
-1583300000
-1583200000
-1583100000
2615
	Command being timed: "./day16b"
	User time (seconds): 40460.91
	System time (seconds): 0.66
	Percent of CPU this job got: 99%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 11:15:26
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 739120
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 221124
	Voluntary context switches: 1
	Involuntary context switches: 125204
	Swaps: 0
	File system inputs: 0
	File system outputs: 0
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0

Oh, and notice that I had an uncaught integer overflow here— I pretty quickly tried more than 2**31 routes, so that resulted in the negative numbers seen above.

Part 2 source code

use std::collections::{HashMap, HashSet, VecDeque};
use std::fs;

#[derive(Debug)]
struct Valve {
    connections: Vec<String>,
    flow_rate: usize,
}

fn find_shortest_path<'a>(
    valves: &'a HashMap<&'a str, Valve>,
    origin: &'a str,
    destination: &str,
) -> Vec<&'a str> {
    // breadth-first search
    let mut nodes_to_check = VecDeque::new();
    nodes_to_check.push_back((origin, vec![]));
    while nodes_to_check.len() > 0 {
        let (current_node, path_to_current_node) = nodes_to_check.pop_front().unwrap();
        for connection in valves[&current_node].connections.iter() {
            let mut path_to_connection = path_to_current_node.clone();
            path_to_connection.push(connection.as_str());
            if connection == destination {
                return path_to_connection;
            }
            nodes_to_check.push_back((&connection, path_to_connection));
        }
    }
    panic!(
        "Could not find a route between {} and {}",
        origin, destination
    );
}

// Note that this only finds paths between nodes with non-zero flow rate, plus the starting node
fn find_shortest_paths<'a>(
    valves: &'a HashMap<&'a str, Valve>,
) -> HashMap<(&'a str, &'a str), Vec<&str>> {
    let mut shortest_paths = HashMap::new();
    for (origin, _valve) in valves
        .iter()
        .filter(|(n, v)| v.flow_rate > 0 || **n == "AA")
    {
        for (destination, _valve) in valves.iter().filter(|(_, v)| v.flow_rate > 0) {
            if origin == destination {
                continue;
            }
            shortest_paths.insert(
                (*origin, *destination),
                find_shortest_path(valves, origin, destination),
            );
        }
    }
    shortest_paths
}

fn parse(data: &str) -> HashMap<&str, Valve> {
    let mut valves = HashMap::new();
    for line in data.split("\n") {
        let valve_name = &line[6..8];
        let (flow_rate, mut rest) = line[23..].split_once(';').unwrap();
        let flow_rate = flow_rate.parse().unwrap();
        // Curse you single path with single tunnel for breaking my parsing
        if rest.chars().nth(7).unwrap() == 's' {
            rest = &rest[24..]; // " tunnels lead to valves "
        } else {
            rest = &rest[23..]; // " tunnel leads to valve "
        }
        let connections = rest.split(", ").map(|s| s.to_owned()).collect();
        valves.insert(
            valve_name,
            Valve {
                connections: connections,
                flow_rate: flow_rate,
            },
        );
    }
    valves
}

fn process(data: &str) -> usize {
    let valves = parse(data);
    let starting_closed_flowing_valves: HashSet<&str> = valves
        .iter()
        .filter(|(_, v)| v.flow_rate > 0)
        .map(|(k, _)| *k)
        .collect();
    let shortest_paths = find_shortest_paths(&valves);

    let mut most_pressure_released = 0;

    // breadth-first search
    let mut nodes_to_check = VecDeque::new();
    nodes_to_check.push_back(("AA", "AA", starting_closed_flowing_valves, 0, 0, 0));
    let mut check_count = 0;
    while let Some((
        current_me_node,
        current_elephant_node,
        remaining_closed_valves,
        pressure_released,
        me_minutes_elapsed,
        elephant_minutes_elapsed,
    )) = nodes_to_check.pop_back()
    // I originally tried `pop_front`, but memory use explodes.
    {
        for target_me_node in remaining_closed_valves.iter() {
            for target_elephant_node in remaining_closed_valves.iter() {
                if target_me_node == target_elephant_node {
                    continue;
                }

                // can we reach them both before 30 minutes is up?
                let me_opened_at = me_minutes_elapsed
                    + shortest_paths[&(current_me_node, *target_me_node)].len()
                    + 1;
                let elephant_opened_at = elephant_minutes_elapsed
                    + shortest_paths[&(current_elephant_node, *target_elephant_node)].len()
                    + 1;
                if me_opened_at >= 26 && elephant_opened_at >= 26 {
                    continue;
                }

                let mut new_pressure_released = pressure_released;
                let mut new_remaining_closed_valves = remaining_closed_valves.clone();
                let me_final_node;
                let elephant_final_node;
                if me_opened_at < 26 {
                    new_remaining_closed_valves.remove(target_me_node);
                    me_final_node = target_me_node;
                    new_pressure_released += (26 - me_opened_at) * valves[target_me_node].flow_rate;
                } else {
                    me_final_node = &current_me_node;
                }

                if elephant_opened_at < 26 {
                    new_remaining_closed_valves.remove(target_elephant_node);
                    elephant_final_node = target_elephant_node;
                    new_pressure_released +=
                        (26 - elephant_opened_at) * valves[target_elephant_node].flow_rate;
                } else {
                    elephant_final_node = &current_elephant_node;
                }

                nodes_to_check.push_back((
                    me_final_node,
                    elephant_final_node,
                    new_remaining_closed_valves,
                    new_pressure_released,
                    me_opened_at,
                    elephant_opened_at,
                ));

                if new_pressure_released > most_pressure_released {
                    most_pressure_released = new_pressure_released;
                }
            }
        }
        check_count += 1;
        if check_count % 100_000 == 0 {
            println!("{}", check_count);
        }
    }
    most_pressure_released
}

fn main() {
    let data = fs::read_to_string("input.txt").unwrap();
    let data = data.trim();
    println!("{}", process(data));
}

#[cfg(test)]
mod test {
    use super::*;

    const DATA: &str = "Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve II";

    #[test]
    fn test_part2() {
        assert_eq!(process(DATA), 1707);
    }
}

Day 17

Part 1 was pretty straightforward. Part 2 would, as is typical, have needed until approximately the heat death of the universe to terminate, so we had to figure out a smarter approach. In this case, I just make note of every state, and if we see it twice, we know that we loop. Then, note that cycle, and keep applying that cycle until we’re near the end, and finish as normal.

One thing I struggled with for a while today was data types. Rust’s errors are excellent for the simplest cases, but can quickly spiral out of control for more complex errors. In my case, I had a lot of type errors, where I was trying to add, say, a usize to a u64 and put it in another u64. When stated like that, the fix is pretty straightforward: Cast the usize to u64 before doing the addition. However, when that type is buried in the middle of a program, and most of the types are inferred anyway, it’s not immediately obvious which variables’ types I need to change to make things work out the way I want.

For a more concrete example, imagine that height returned a u64 instead of a usize¹:

diff --git a/2022/day17/day17.rs b/2022/day17/day17.rs
index bb15c0d..0380e29 100644
--- a/2022/day17/day17.rs
+++ b/2022/day17/day17.rs
@@ -1,11 +1,11 @@
 use std::collections::HashMap;
 use std::fs;
 
-fn height(chamber: &Vec<[bool; 7]>) -> usize {
+fn height(chamber: &Vec<[bool; 7]>) -> u64 {
     for (i, row) in chamber.iter().enumerate().rev() {
         if row.iter().any(|x| *x) {
             // Is there a better function here?
-            return i + 1;
+            return i as u64 + 1;
         }
     }

The error here isn’t too terrible, but it’s not immediately obvious why a u64 was expected. (In this case it’s only a couple lines away, but during this problem I solved some cases where there was an extensive chain of “foo is u64 because it’s added to bar which is u64 because it’s cloned from spam which is u64 because that’s what the frobulate function returns”-esque shenanigans.)

Oh, and every time something went even slightly wrong, the compiler decided to start calling the offsets usizes instead of isizes. I can’t figure out what was going on here, since solving other issues made it go away, but every time any unrelated error popped up, this one would rear its ugly head too. I’m not sure what’s up with that! 🤷‍♂️

error[E0308]: mismatched types
   --> day17.rs:100:37
    |
100 |                 for _ in 0..h + 7 - chamber.len() {
    |                                     ^^^^^^^^^^^^^ expected `u64`, found `usize`

error[E0277]: cannot subtract `usize` from `u64`
   --> day17.rs:100:35
    |
100 |                 for _ in 0..h + 7 - chamber.len() {
    |                                   ^ no implementation for `u64 - usize`
    |
    = help: the trait `Sub<usize>` is not implemented for `u64`
    = help: the following other types implement trait `Sub<Rhs>`:
              <&'a f32 as Sub<f32>>
              <&'a f64 as Sub<f64>>
              <&'a i128 as Sub<i128>>
              <&'a i16 as Sub<i16>>
              <&'a i32 as Sub<i32>>
              <&'a i64 as Sub<i64>>
              <&'a i8 as Sub<i8>>
              <&'a isize as Sub<isize>>
            and 48 others

error[E0277]: the trait bound `usize: Neg` is not satisfied
  --> day17.rs:59:40
   |
59 |                 JetDirection::Left => (-1, 0),
   |                                        ^^ the trait `Neg` is not implemented for `usize`
   |
   = help: the following other types implement trait `Neg`:
             &f32
             &f64
             &i128
             &i16
             &i32
             &i64
             &i8
             &isize
           and 8 others

error: aborting due to 3 previous errors

Some errors have detailed explanations: E0277, E0308.
For more information about an error, try `rustc --explain E0277`.

Source code

use std::collections::HashMap;
use std::fs;

fn height(chamber: &Vec<[bool; 7]>) -> usize {
    for (i, row) in chamber.iter().enumerate().rev() {
        if row.iter().any(|x| *x) {
            // Is there a better function here?
            return i + 1;
        }
    }

    0
}

#[derive(Debug)]
enum JetDirection {
    Left,
    Right,
}

fn process(data: &str, rocks_to_fall: u64) -> u64 {
    // I'd have loved to put rock_shapes as a global constant, but
    // unfortunately since rocks are different sizes, rocks have to be
    // `Vec`s not arrays, and that can't be done statically,
    // apparently. Maybe there's a good workaround for this, but I
    // haven't found it. So, we just put it here instead!
    let rock_shapes = vec![
        vec![(0, 0), (1, 0), (2, 0), (3, 0)],
        vec![(1, 0), (0, 1), (1, 1), (2, 1), (1, 2)],
        vec![(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)],
        vec![(0, 0), (0, 1), (0, 2), (0, 3)],
        vec![(0, 0), (1, 0), (0, 1), (1, 1)],
    ];

    let jets: Vec<JetDirection> = data
        .chars()
        .map(|c| match c {
            '<' => JetDirection::Left,
            '>' => JetDirection::Right,
            _ => panic!("Unknown characters"),
        })
        .collect();

    let mut falling_points = Vec::new();
    let mut chamber = vec![[false; 7]; 4];
    let mut current_falling_rock = 0;
    let mut is_moving_sideways = true;
    for point in &rock_shapes[0] {
        falling_points.push((point.0 + 2, point.1 + 3));
    }
    let mut seen_states: HashMap<([[bool; 7]; 10], usize), (u64, u64)> = HashMap::new();
    let mut jet_index = 0;
    let mut height_offset = 0;
    while current_falling_rock < rocks_to_fall {
        let target_offset;
        if is_moving_sideways {
            let jet_direction = &jets[jet_index];
            target_offset = match jet_direction {
                JetDirection::Left => (-1, 0),
                JetDirection::Right => (1, 0),
            };
            jet_index = (jet_index + 1) % jets.len();
        } else {
            target_offset = (0, -1);
        }
        let can_move = falling_points.iter().all(|(x, y)| {
            let new_x = x + target_offset.0;
            let new_y = y + target_offset.1;
            (0..7).contains(&new_x) && new_y >= 0 && !chamber[new_y as usize][new_x as usize]
        });
        if can_move {
            for point in falling_points.iter_mut() {
                *point = (point.0 + target_offset.0, point.1 + target_offset.1);
            }
        } else if !is_moving_sideways {
            if height_offset == 0 && height(&chamber) > 10 {
                let mut foo = [[false; 7]; 10];
                foo.clone_from_slice(&chamber[chamber.len() - 10..chamber.len()]);
                let state = (foo, jet_index);
                if seen_states.contains_key(&state) {
                    let remaining_falling_rocks = rocks_to_fall - current_falling_rock;
                    let rocks_fall_per_cycle = current_falling_rock - seen_states[&state].0;
                    let height_added_per_cycle = height(&chamber) as u64 - seen_states[&state].1;
                    let cycles = remaining_falling_rocks / rocks_fall_per_cycle;
                    height_offset = cycles * height_added_per_cycle;
                    current_falling_rock += rocks_fall_per_cycle * cycles;
                } else {
                    seen_states.insert(state, (current_falling_rock, height(&chamber) as u64));
                }
            }
            // Convert all falling points into stuck points
            while let Some((x, y)) = falling_points.pop() {
                chamber[y as usize][x as usize] = true;
            }

            current_falling_rock += 1;

            for point in &rock_shapes[current_falling_rock as usize % 5] {
                let h = height(&chamber);
                for _ in 0..h + 7 - chamber.len() {
                    chamber.push([false; 7]);
                }
                falling_points.push((point.0 + 2, point.1 + h as i64 + 3));
            }
        }
        is_moving_sideways = !is_moving_sideways;
    }

    height(&chamber) as u64 + height_offset
}

fn main() {
    let data = fs::read_to_string("input.txt").unwrap();
    let data = data.trim();
    println!("{}", process(data, 1_000_000_000_000)); // 2022 for part 1
}

#[cfg(test)]
mod test {
    use super::*;

    const DATA: &str = ">>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>";

    #[test]
    fn test_part1() {
        assert_eq!(process(DATA, 2022), 3068);
    }

    #[test]
    fn test_part2() {
        assert_eq!(process(DATA, 1_000_000_000_000), 1514285714288);
    }
}

Soundtrack

I did use u64s over usizes in a handful of places to try to write semi-portable code; many of the values in the second part were too large to fit in a 32-bit integer, so 32-bit platforms’ 32-bit usize would overflow, where a u64 is safe on all platforms. Turned out to be more hassle than it was worth, though! ↩︎

I don't have a formal commenting system set up. If you have questions or comments about anything I've written, send me an email and I'd be delighted to hear what you have to say!