Advent of Code 2022: Days 18 and 19

I’ve been recovering from a rough bout of COVID-19, which really knocked me out for a few days, and (in combination with a tough couple problems) set my AoC progress back a few more days. But I’m back at it! Today: getting acquainted with magit.

Day 18

Today, I installed and tried out magit. Installation was straightforward: M-x package-install <RET> magit <RET>. Usage was…a bit more complex. I skimmed the manual, but didn’t have time for the in-depth read it probably merits. Instead, I read the Getting Started section and looked up key combinations as I needed them. The built-in help was, for me, more than sufficient for my basic use. I expect that (at least for now) I’ll still be dropping to a command line to do anything more advanced than the usual git add -p; git commit; git push, but the integration for that basic workflow has been easy to use and nicely integrated.

Oh, and I solved some AoC problems, too!

Source code

use std::collections::HashSet;
use std::fs;

// TODO: this should be calculable via something like the number of
// points to the (2/3) power over 2 times a constant I'm too lazy to
// work out for this comment, since that would occur if the points
// formed a rough sphere around the air bubble. But I don't wanna, so
// I'm just setting it to something arbitrary and large.
const MAX_AIR_BUBBLE_SIZE: usize = 10000;

fn is_air_bubble(droplets: &HashSet<(i32, i32, i32)>, start: (i32, i32, i32)) -> bool {
    let mut queue = Vec::new();
    let mut bubble = HashSet::new();
    queue.push(start);
    while queue.len() > 0 {
        if bubble.len() >= MAX_AIR_BUBBLE_SIZE {
            return false;
        }
        let current = queue.pop().unwrap();
        bubble.insert(current);
        for offset in [
            (-1, 0, 0),
            (0, -1, 0),
            (0, 0, -1),
            (0, 0, 1),
            (0, 1, 0),
            (1, 0, 0),
        ] {
            let neighbor = (
                current.0 + offset.0,
                current.1 + offset.1,
                current.2 + offset.2,
            );
            if !droplets.contains(&neighbor)
                && !queue.contains(&neighbor)
                && !bubble.contains(&neighbor)
            {
                bubble.insert(neighbor);
                queue.push(neighbor);
            }
        }
    }
    true
}

fn process(data: &str, include_air_bubbles: bool) -> usize {
    let droplets: HashSet<(i32, i32, i32)> = data
        .split('\n')
        .map(|line| {
            let mut nums = line.split(',').map(|i| i.parse().unwrap());
            (
                nums.next().unwrap(),
                nums.next().unwrap(),
                nums.next().unwrap(),
            )
        })
        .collect();

    let mut surface_area = 0;
    for droplet in droplets.iter() {
        for offset in [
            (-1, 0, 0),
            (0, -1, 0),
            (0, 0, -1),
            (0, 0, 1),
            (0, 1, 0),
            (1, 0, 0),
        ] {
            let neighbor = (
                droplet.0 + offset.0,
                droplet.1 + offset.1,
                droplet.2 + offset.2,
            );
            if !droplets.contains(&neighbor)
                && (include_air_bubbles || !is_air_bubble(&droplets, neighbor))
            {
                surface_area += 1;
            }
        }
    }
    surface_area
}

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

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

    const DATA: &str = "2,2,2
1,2,2
3,2,2
2,1,2
2,3,2
2,2,1
2,2,3
2,2,4
2,2,6
1,2,5
3,2,5
2,1,5
2,3,5";

    #[test]
    fn trivial_part1() {
        assert_eq!(process("1,1,1\n2,1,1", true), 10);
    }

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

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

Day 19

A few minor optimizations here, to get the program to complete in a slightly more reasonable time:

Aborting a branch early if it’s not going to produce sufficient numbers of geodes. Specifically, the maximum number of geodes I could possibly produce is the number I have now, plus the number I can gather with the robots I have, plus the number I can gather with additional robots if I made one more per minute. This is the possible_geodes calculated below. If that’s less than the maximum number of geodes I’ve already attained by another path, I can give up; there’s no way this branch will prove fruitful. One note is that originally I’d had my branching functions reversed (so I tried building an ore-gathering robot first, then a clay-gathering robot, and so on). It turns out that spending all your resources building ore-gathering robots is a terrible strategy, while “build the most advanced robot you can” is quite a bit better. So I reversed the order, which got me a pretty high score early on in the process, and lets me prune quite a bit more aggressively later.
Not producing more robots of a given type than I’d need. For example, clay is only used in the production of obsidian-collecting robots, which cost, say, X clay. I can only build one robot per minute, so I use at most X clay per minute, so there’s no point in gathering more than X clay per minute, so I should never construct an X+1th clay-gathering robot.

A few more optimizations I didn’t try, but might have considered if I needed additional performance:

I do a lot of copying around of 32-bit ints in structs. Most of them are tiny; I’d had a lot of them (e.g. the Blueprint costs) as u8s for a while before consolidating everything to u32s to save on tons of extra type casts everywhere, as well as save me some reasoning about whether I’d need the extra space. This was probably the wrong move for performance reasons; now I’m copying a bunch of zero bytes around unnecessarily. I could go back to u8s.
I could probably do some more logicking to more aggressively prune branches that I can eliminate any possibility of bearing fruit. That said, I do feel like I got several of the easiest wins here.
This program is probably a reasonable candidate for some form of parallel processing, and on my 8-core processor I could probably expect a speedup of somewhere between 4 and 8 times, if the locks don’t get too heavily contended.

With these optimizations, and compiling with optimizations (-O), the first part takes just under two seconds to run, and the second part takes just over two minutes.

Source code

use std::fs;

#[derive(Debug, Eq, PartialEq, Copy, Clone)]
struct Blueprint {
    id: u8,
    ore_robot_ore_cost: u32,
    clay_robot_ore_cost: u32,
    obsidian_robot_ore_cost: u32,
    obsidian_robot_clay_cost: u32,
    geode_robot_ore_cost: u32,
    geode_robot_obsidian_cost: u32,
}

#[derive(Debug, Copy, Clone)]
struct Inventory {
    ore: u32,
    clay: u32,
    obsidian: u32,
    geodes: u32,
}

#[derive(Debug, Copy, Clone)]
struct Robots {
    ore_collecting: u32,
    clay_collecting: u32,
    obsidian_collecting: u32,
    geode_cracking: u32,
}

fn parse_blueprint(data: &str) -> Blueprint {
    let (id, remaining) = data[10..].split_once(": ").unwrap();
    let id = id.parse().unwrap();
    let (ore_robot_ore_cost, remaining) = remaining[21..].split_once(" ").unwrap();
    let ore_robot_ore_cost = ore_robot_ore_cost.parse().unwrap();
    let (clay_robot_ore_cost, remaining) = remaining[27..].split_once(" ").unwrap();
    let clay_robot_ore_cost = clay_robot_ore_cost.parse().unwrap();
    let (obsidian_robot_ore_cost, remaining) = remaining[31..].split_once(" ").unwrap();
    let obsidian_robot_ore_cost = obsidian_robot_ore_cost.parse().unwrap();
    let (obsidian_robot_clay_cost, remaining) = remaining[8..].split_once(" ").unwrap();
    let obsidian_robot_clay_cost = obsidian_robot_clay_cost.parse().unwrap();
    let (geode_robot_ore_cost, remaining) = remaining[29..].split_once(" ").unwrap();
    let geode_robot_ore_cost = geode_robot_ore_cost.parse().unwrap();
    let (geode_robot_obsidian_cost, _remaining) = remaining[8..].split_once(" ").unwrap();
    let geode_robot_obsidian_cost = geode_robot_obsidian_cost.parse().unwrap();
    Blueprint {
        id: id,
        ore_robot_ore_cost: ore_robot_ore_cost,
        clay_robot_ore_cost: clay_robot_ore_cost,
        obsidian_robot_ore_cost: obsidian_robot_ore_cost,
        obsidian_robot_clay_cost: obsidian_robot_clay_cost,
        geode_robot_ore_cost: geode_robot_ore_cost,
        geode_robot_obsidian_cost: geode_robot_obsidian_cost,
    }
}

fn geodes_opened(blueprint: Blueprint, remaining_time: usize) -> usize {
    let robots = Robots {
        ore_collecting: 1,
        clay_collecting: 0,
        obsidian_collecting: 0,
        geode_cracking: 0,
    };
    let inventory = Inventory {
        ore: 0,
        clay: 0,
        obsidian: 0,
        geodes: 0,
    };
    rec_geodes_opened(blueprint, remaining_time, robots, inventory, &mut 0)
}

fn rec_geodes_opened(
    blueprint: Blueprint,
    remaining_time: usize,
    robots: Robots,
    inventory: Inventory,
    max_overall_geodes: &mut usize,
) -> usize {
    if remaining_time > 26 {
        println!("{}", remaining_time);
    }
    let starting_inventory = inventory;

    let mut inventory = inventory;
    inventory.ore += robots.ore_collecting as u32;
    inventory.clay += robots.clay_collecting as u32;
    inventory.obsidian += robots.obsidian_collecting as u32;
    inventory.geodes += robots.geode_cracking as u32;

    let possible_geodes: usize = inventory.geodes as usize
        + (robots.geode_cracking as usize * remaining_time)
        + (remaining_time * (remaining_time - 1) / 2);

    let mut max_geodes = 0;

    let mut ore_costs = [
        blueprint.ore_robot_ore_cost,
        blueprint.clay_robot_ore_cost,
        blueprint.obsidian_robot_ore_cost,
        blueprint.geode_robot_ore_cost,
    ];
    ore_costs.sort();
    let max_ore_cost = ore_costs[ore_costs.len() - 1];

    if remaining_time > 1 && possible_geodes >= *max_overall_geodes {
        if blueprint.geode_robot_ore_cost <= starting_inventory.ore
            && blueprint.geode_robot_obsidian_cost <= starting_inventory.obsidian
        {
            let mut robots = robots.clone();
            let mut inventory = inventory.clone();
            inventory.ore -= blueprint.geode_robot_ore_cost;
            inventory.obsidian -= blueprint.geode_robot_obsidian_cost;
            robots.geode_cracking += 1;
            let geodes = rec_geodes_opened(
                blueprint,
                remaining_time - 1,
                robots,
                inventory,
                max_overall_geodes,
            );
            if geodes > max_geodes {
                max_geodes = geodes;
            }
        }
        if blueprint.obsidian_robot_ore_cost <= starting_inventory.ore
            && blueprint.obsidian_robot_clay_cost <= starting_inventory.clay
            && robots.obsidian_collecting < blueprint.geode_robot_obsidian_cost
        {
            let mut robots = robots.clone();
            let mut inventory = inventory.clone();
            inventory.ore -= blueprint.obsidian_robot_ore_cost;
            inventory.clay -= blueprint.obsidian_robot_clay_cost;
            robots.obsidian_collecting += 1;
            let geodes = rec_geodes_opened(
                blueprint,
                remaining_time - 1,
                robots,
                inventory,
                max_overall_geodes,
            );
            if geodes > max_geodes {
                max_geodes = geodes;
            }
        }
        if blueprint.clay_robot_ore_cost <= starting_inventory.ore
            && robots.clay_collecting < blueprint.obsidian_robot_clay_cost
        {
            let mut robots = robots.clone();
            let mut inventory = inventory.clone();
            inventory.ore -= blueprint.clay_robot_ore_cost;
            robots.clay_collecting += 1;
            let geodes = rec_geodes_opened(
                blueprint,
                remaining_time - 1,
                robots,
                inventory,
                max_overall_geodes,
            );
            if geodes > max_geodes {
                max_geodes = geodes;
            }
        }
        if blueprint.ore_robot_ore_cost <= starting_inventory.ore
            && robots.ore_collecting < max_ore_cost
        {
            let mut robots = robots.clone();
            let mut inventory = inventory.clone();
            inventory.ore -= blueprint.ore_robot_ore_cost;
            robots.ore_collecting += 1;
            let geodes = rec_geodes_opened(
                blueprint,
                remaining_time - 1,
                robots,
                inventory,
                max_overall_geodes,
            );
            if geodes > max_geodes {
                max_geodes = geodes;
            }
        }
        let geodes = rec_geodes_opened(
            blueprint,
            remaining_time - 1,
            robots,
            inventory,
            max_overall_geodes,
        );
        if geodes > max_geodes {
            max_geodes = geodes;
        }
    } else {
        return inventory.geodes as usize;
    }

    if max_geodes > *max_overall_geodes {
        *max_overall_geodes = max_geodes;
    }
    max_geodes
}

fn process(data: &str) -> usize {
    let blueprints: Vec<Blueprint> = data.split("\n").map(|s| parse_blueprint(s)).collect();

    blueprints
        .iter()
        .map(|b| b.id as usize * geodes_opened(*b, 24) as usize)
        .sum()
}

fn process2(data: &str) -> usize {
    let blueprints: Vec<Blueprint> = data
        .split("\n")
        .take(3)
        .map(|s| parse_blueprint(s))
        .collect();

    blueprints
        .iter()
        .map(|b| geodes_opened(*b, 32) as usize)
        .product()
}

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

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

    const DATA: &str = "Blueprint 1: Each ore robot costs 4 ore. Each clay robot costs 2 ore. Each obsidian robot costs 3 ore and 14 clay. Each geode robot costs 2 ore and 7 obsidian.
Blueprint 2: Each ore robot costs 2 ore. Each clay robot costs 3 ore. Each obsidian robot costs 3 ore and 8 clay. Each geode robot costs 3 ore and 12 obsidian.";

    #[test]
    fn test_parse() {
        let mut lines = DATA.split("\n");
        let line_1 = Blueprint {
            id: 1,
            ore_robot_ore_cost: 4,
            clay_robot_ore_cost: 2,
            obsidian_robot_ore_cost: 3,
            obsidian_robot_clay_cost: 14,
            geode_robot_ore_cost: 2,
            geode_robot_obsidian_cost: 7,
        };
        let line_2 = Blueprint {
            id: 2,
            ore_robot_ore_cost: 2,
            clay_robot_ore_cost: 3,
            obsidian_robot_ore_cost: 3,
            obsidian_robot_clay_cost: 8,
            geode_robot_ore_cost: 3,
            geode_robot_obsidian_cost: 12,
        };
        assert_eq!(parse_blueprint(lines.next().unwrap()), line_1);
        assert_eq!(parse_blueprint(lines.next().unwrap()), line_2);
    }

    #[test]
    fn test_find_largest_number_of_geodes_that_can_be_opened() {
        let mut lines = DATA.split("\n");
        assert_eq!(geodes_opened(parse_blueprint(lines.next().unwrap()), 24), 9);
        assert_eq!(
            geodes_opened(parse_blueprint(lines.next().unwrap()), 24),
            12
        );
    }

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

Soundtrack

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!