hades

Rust

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

use itertools::Itertools;

fn neighbours_of(i: usize, j: usize, side: usize) -> impl Iterator<Item = (usize, usize)> {
    [
        (i, j.wrapping_sub(1)),
        (i, j + 1),
        (
            if (i + j) % 2 == 0 {
                i.wrapping_sub(1)
            } else {
                i + 1
            },
            j,
        ),
    ]
    .into_iter()
    .filter(move |&(i, j)| i < side && j >= i && j < (2 * side - i - 1))
}

pub fn solve_part_1(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let side = data.len();
    let mut queue = VecDeque::new();
    queue.push_back((0, 0));
    let mut pairs = 0;
    let mut visited = HashSet::new();
    while let Some((i, j)) = queue.pop_front() {
        if visited.contains(&(i, j)) {
            continue;
        }
        for (ni, nj) in neighbours_of(i, j, side) {
            if visited.contains(&(ni, nj)) {
                continue;
            }
            if data[i][j] == 'T' && data[ni][nj] == 'T' {
                pairs += 1;
            }
            queue.push_back((ni, nj));
        }
        visited.insert((i, j));
    }
    pairs.to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let side = data.len();
    let mut front = (0..data.len())
        .cartesian_product(0..data[0].len())
        .filter(|&(i, j)| data[i][j] == 'S')
        .collect::<HashSet<_>>();
    let mut visited = HashSet::new();
    let mut steps = 0;
    while !front.is_empty() {
        let mut next_front = HashSet::new();
        for (i, j) in front.drain() {
            if data[i][j] == 'E' {
                return steps.to_string();
            }
            visited.insert((i, j));
            for (ni, nj) in neighbours_of(i, j, side) {
                if (data[ni][nj] == 'T' || data[ni][nj] == 'E') && !visited.contains(&(ni, nj)) {
                    next_front.insert((ni, nj));
                }
            }
        }
        steps += 1;
        front = next_front;
    }
    panic!("exit not found");
}

pub fn rotate(data: &[Vec<char>]) -> Vec<Vec<char>> {
    let mut result = vec![vec!['.'; data[0].len()]; data.len()];
    let side = data.len();
    for i in 0..data.len() {
        for j in i..(data[0].len() - i) {
            if (i + j) % 2 == 0 {
                result[i][j] = data[side - (i + j) / 2 - 1][i * 2 + side - (i + j) / 2 - 1];
            } else {
                result[i][j] = data[side - (i + j).div_ceil(2) - 1][side - (j - i).div_ceil(2) + i];
            }
        }
    }
    result
}

pub fn solve_part_3(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let side = data.len();
    let data = [data.clone(), rotate(&data), rotate(&rotate(&data))];
    let mut front = (0..data[0].len())
        .cartesian_product(0..data[0][0].len())
        .filter(|&(i, j)| data[0][i][j] == 'S')
        .map(|(i, j)| (i, j, 0))
        .collect::<HashSet<_>>();
    let mut visited = HashSet::new();
    let mut steps = 0;
    while !front.is_empty() {
        let mut next_front = HashSet::new();
        for (i, j, rotation) in front.drain() {
            if data[rotation][i][j] == 'E' {
                return steps.to_string();
            }
            visited.insert((i, j, rotation));
            let next_rotation = (rotation + 1) % 3;
            for (ni, nj) in neighbours_of(i, j, side) {
                if (data[next_rotation][ni][nj] == 'T' || data[next_rotation][ni][nj] == 'E')
                    && !visited.contains(&(ni, nj, next_rotation))
                {
                    next_front.insert((ni, nj, next_rotation));
                }
            }
            if (data[next_rotation][i][j] == 'T' || data[next_rotation][i][j] == 'E')
                && !visited.contains(&(i, j, next_rotation))
            {
                next_front.insert((i, j, next_rotation));
            }
        }
        steps += 1;
        front = next_front;
    }
    panic!("exit not found");
}

Ah, makes sense. Here's a link to this comment so you can view it on the web: https://programming.dev/post/41427600/20744400

I think the "how can we tell if we've been around the volcano already" is the most interesting part of this puzzle.

Rust

Shortest solution so far.

use std::collections::{BTreeMap};

use interval::{
    IntervalSet,
    ops::Range,
    prelude::{Bounded, Empty, Intersection, Union},
};

pub fn solve_part_1(input: &str) -> String {
    let mut data = BTreeMap::new();
    for v in input.lines().map(|l| {
        l.split(",")
            .map(|v| v.parse().unwrap())
            .collect::<Vec<i64>>()
    }) {
        data.entry(v[0]).or_insert(vec![]).push((v[1], v[2]));
    }
    let mut y_ranges = IntervalSet::new(0, 0);
    let mut x = 0;
    for (wall_x, openings) in data.into_iter() {
        let dx = wall_x - x;
        let mut new_ranges = IntervalSet::empty();
        for interval in y_ranges.into_iter() {
            new_ranges = new_ranges.union(&IntervalSet::new(
                interval.lower() - dx,
                interval.upper() + dx,
            ));
        }
        let mut openings_intervalset = IntervalSet::empty();
        for (opening_start, opening_size) in openings {
            openings_intervalset = openings_intervalset.union(&IntervalSet::new(
                opening_start,
                opening_start + opening_size - 1,
            ));
        }
        y_ranges = new_ranges.intersection(&openings_intervalset);
        x = wall_x;
    }
    let y = y_ranges
        .iter()
        .flat_map(|i| (i.lower()..=i.upper()))
        .find(|y| y % 2 == x % 2)
        .unwrap();
    ((y + x) / 2).to_string()
}

pub fn solve_part_2(input: &str) -> String {
    solve_part_1(input)
}
pub fn solve_part_3(input: &str) -> String {
    solve_part_1(input)
}

Rust

use regex::Regex;
use z3::{
    Optimize, Params,
    ast::{Bool, Int},
};

#[derive(Default)]
struct Plant {
    thickness: i64,
    free: Option<i64>,
    connected: Vec<(usize, i64)>,
}

fn parse_plant_spec(input: &str) -> Plant {
    let mut result = Plant::default();
    let first_re = Regex::new(r"Plant \d+ with thickness (\d+):").unwrap();
    let free_re = Regex::new(r"- free branch with thickness (\d+)").unwrap();
    let branch_re = Regex::new(r"- branch to Plant (\d+) with thickness (-?\d+)").unwrap();
    for line in input.lines() {
        if let Some((_, [thickness])) = first_re.captures(line).map(|c| c.extract()) {
            result.thickness = thickness.parse().unwrap();
        } else if let Some((_, [thickness])) = free_re.captures(line).map(|c| c.extract()) {
            result.free = Some(thickness.parse().unwrap());
        } else if let Some((_, [plant, thickness])) = branch_re.captures(line).map(|c| c.extract())
        {
            result
                .connected
                .push((plant.parse().unwrap(), thickness.parse().unwrap()));
        } else {
            panic!("cannot parse line: {line}");
        }
    }
    result
}

fn eval_plant(plants: &[Plant], number: usize, free_branches: &[i64]) -> i64 {
    let plant = &plants[number - 1];
    if plant.free.is_some() {
        assert_eq!(1, plant.thickness);
        assert_eq!(1, plant.free.unwrap());
        free_branches[number - 1]
    } else {
        let incoming = plant
            .connected
            .iter()
            .map(|&(plant_number, branch_thickness)| {
                eval_plant(plants, plant_number, free_branches) * branch_thickness
            })
            .sum::<i64>();
        if incoming >= plant.thickness {
            incoming
        } else {
            0
        }
    }
}

pub fn solve_part_1(input: &str) -> String {
    let plants = input
        .split("\n\n")
        .map(parse_plant_spec)
        .collect::<Vec<_>>();
    eval_plant(&plants, plants.len(), &vec![1; plants.len()]).to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let (plants, tests) = input.split_once("\n\n\n").unwrap();
    let plants = plants
        .split("\n\n")
        .map(parse_plant_spec)
        .collect::<Vec<_>>();
    tests
        .lines()
        .map(|test| {
            eval_plant(
                &plants,
                plants.len(),
                &test
                    .split(" ")
                    .map(|v| v.parse().unwrap())
                    .collect::<Vec<i64>>(),
            )
        })
        .sum::<i64>()
        .to_string()
}

fn eval_plant_z3(plants: &[Plant], number: usize, free_branches: &[Option<Bool>]) -> Int {
    let plant = &plants[number - 1];
    if plant.free.is_some() {
        assert_eq!(1, plant.thickness);
        assert_eq!(1, plant.free.unwrap());
        free_branches[number - 1]
            .as_ref()
            .unwrap()
            .ite(&Int::from_i64(1), &Int::from_i64(0))
    } else {
        let incoming = plant
            .connected
            .iter()
            .map(|&(plant_number, branch_thickness)| {
                eval_plant_z3(plants, plant_number, free_branches) * Int::from_i64(branch_thickness)
            })
            .reduce(|a, b| a + b);
        let incoming = incoming.unwrap_or_else(|| Int::from_i64(0));
        incoming
            .ge(Int::from_i64(plant.thickness))
            .ite(&incoming, &Int::from_i64(0))
    }
}

fn maximum_achievable_brightness(plants: &[Plant]) -> i64 {
    let mut free_branches = vec![None; plants.len()];
    plants.iter().enumerate().for_each(|(i, p)| {
        if p.free.is_some() {
            free_branches[i] = Some(Bool::fresh_const("free"));
        }
    });
    let solver = Optimize::new();
    let mut params = Params::new();
    params.set_symbol("opt.maxsat_engine", "wmax");
    solver.set_params(&params);
    let brightness = eval_plant_z3(plants, plants.len(), &free_branches);
    solver.maximize(&brightness);
    match solver.check(&[]) {
        z3::SatResult::Sat => solver
            .get_model()
            .unwrap()
            .eval(&brightness, true)
            .unwrap()
            .as_i64()
            .unwrap(),
        _ => panic!("unsat"),
    }
}

pub fn solve_part_3(input: &str) -> String {
    let (plants, tests) = input.split_once("\n\n\n").unwrap();
    let plants = plants
        .split("\n\n")
        .map(parse_plant_spec)
        .collect::<Vec<_>>();
    let maximum = maximum_achievable_brightness(&plants);
    tests
        .lines()
        .map(|test| {
            eval_plant(
                &plants,
                plants.len(),
                &test
                    .split(" ")
                    .map(|v| v.parse().unwrap())
                    .collect::<Vec<i64>>(),
            )
        })
        .map(|v| if v > 0 { maximum - v } else { 0 })
        .sum::<i64>()
        .to_string()
}

Rust

use std::{
    cmp::Reverse,
    collections::{HashMap, HashSet},
    f64::consts::PI,
};

use itertools::Itertools;
use libm::atan2;
use priority_queue::PriorityQueue;

fn l2(i: usize, j: usize) -> usize {
    i * i + j * j
}

fn erupt(data: &[Vec<char>], vi: usize, vj: usize, r: usize) -> usize {
    let r2 = r * r;
    data.iter()
        .enumerate()
        .flat_map(|(i, l)| {
            l.iter()
                .enumerate()
                .filter(move |&(j, v)| *v != '@' && l2(vi.abs_diff(i), vj.abs_diff(j)) <= r2)
        })
        .map(|(_, v)| (*v as u8 - b'0') as usize)
        .sum::<usize>()
}

fn find(data: &[Vec<char>], c: char) -> (usize, usize) {
    data.iter()
        .enumerate()
        .flat_map(|(i, l)| {
            l.iter()
                .enumerate()
                .filter(|&(_, v)| *v == c)
                .map(move |(j, _)| (i, j))
        })
        .exactly_one()
        .unwrap()
}

pub fn solve_part_1(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let (vi, vj) = find(&data, '@');
    erupt(&data, vi, vj, 10).to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let (vi, vj) = find(&data, '@');
    let h = data.len();
    let w = data[0].len();
    let max_r = vi.max(vj).max(h - vi - 1).max(w - vj - 1);
    let mut last_eruption = 0;
    let mut max_eruption = 0;
    let mut max_eruption_r = 0;
    for r in 1..=max_r {
        let eruption = erupt(&data, vi, vj, r);
        let de = eruption - last_eruption;
        if de > max_eruption {
            max_eruption = de;
            max_eruption_r = r;
        }
        last_eruption = eruption;
    }
    (max_eruption_r * max_eruption).to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let data = input
        .lines()
        .map(|l| l.chars().collect::<Vec<_>>())
        .collect::<Vec<_>>();
    let width = data[0].len();
    let height = data.len();
    let (vi, vj) = find(&data, '@');
    let (si, sj) = find(&data, 'S');

    let azimuth = |i: usize, j: usize| atan2(i as f64 - vi as f64, j as f64 - vj as f64);

    let small_rot = |az1: f64, az2: f64| {
        let d = az1 - az2;
        if d > PI {
            d - 2. * PI
        } else if d < -PI {
            d + 2. * PI
        } else {
            d
        }
    };

    let solve = |radius: usize| {
        let r2 = radius * radius;
        let time_limit = ((radius + 1) * 30) as i64;
        let mut queue = PriorityQueue::new();
        let mut rotations = HashMap::new();
        rotations.insert((si, sj, false), 0f64);
        let mut visited = HashSet::new();
        queue.push((si, sj, false), Reverse(0));
        while let Some(((i, j, rotated), Reverse(time))) = queue.pop() {
            if time >= time_limit {
                break;
            }
            visited.insert((i, j, rotated));
            let az = azimuth(i, j);
            let rotation = rotations[&(i, j, rotated)];
            for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
                let (ni, nj) = (i.wrapping_add_signed(di), j.wrapping_add_signed(dj));
                if ni >= height || nj >= width {
                    continue;
                }
                if l2(ni.abs_diff(vi), nj.abs_diff(vj)) <= r2 {
                    continue;
                }
                let is_rotated = if let Some(previous_rotation) = rotations.get(&(ni, nj, false)) {
                    let rotation = rotation + small_rot(azimuth(ni, nj), az);
                    (rotation - previous_rotation).abs() > 6.
                } else {
                    false
                };
                if (ni, nj, is_rotated) == (si, sj, true) {
                    return Some(time);
                }
                if visited.contains(&(ni, nj, is_rotated)) {
                    continue;
                }
                let new_time: i64 = time + (data[ni][nj] as i8 - '0' as i8) as i64;
                let should_update =
                    match queue.push_increase((ni, nj, is_rotated), Reverse(new_time)) {
                        None => true,
                        Some(Reverse(t)) => t > new_time,
                    };
                if should_update {
                    rotations.insert(
                        (ni, nj, is_rotated),
                        rotation + small_rot(azimuth(ni, nj), az),
                    );
                };
            }
        }
        None
    };
    let (radius, time) = (1..(width.min(height) / 2))
        .map(|radius| (radius, solve(radius)))
        .filter(|(_, s)| s.is_some())
        .min()
        .unwrap();
    (radius as i64 * time.unwrap()).to_string()
}

Rust

use std::collections::{BTreeSet, HashMap};

use array2d::Array2D;
use priority_queue::PriorityQueue;

type Point = (i64, i64);

pub fn solve_part_1(input: &str) -> String {
    let mut vertical_walls = Vec::<(Point, Point)>::new();
    let mut horizontal_walls = Vec::<(Point, Point)>::new();
    let dirs = [(0, -1), (1, 0), (0, 1), (-1, 0)];
    let mut dir = 0;
    let (mut x, mut y) = (0, 0);
    let mut interesting_points_x = BTreeSet::new();
    let mut interesting_points_y = BTreeSet::new();
    for instr in input.split(",") {
        let dist = if let Some(dist) = instr.strip_prefix("L") {
            dir = (dir + 3) % 4;
            dist
        } else if let Some(dist) = instr.strip_prefix("R") {
            dir = (dir + 1) % 4;
            dist
        } else {
            panic!("unparseable instruction {instr}");
        };
        let dist = dist.parse::<i64>().unwrap() - 1;
        let (endx, endy) = (x + dirs[dir].0 * dist, y + dirs[dir].1 * dist);
        let insert_to_walls = match dirs[dir] {
            (_, 0) => &mut horizontal_walls,
            (0, _) => &mut vertical_walls,
            _ => panic!("unexpected direction"),
        };
        let wall = ((x.min(endx), y.min(endy)), (x.max(endx), y.max(endy)));
        interesting_points_x.insert(wall.0.0 - 1);
        interesting_points_x.insert(wall.1.0 + 1);
        interesting_points_y.insert(wall.0.1 - 1);
        interesting_points_y.insert(wall.1.1 + 1);
        insert_to_walls.push(wall);
        x = endx + dirs[dir].0;
        y = endy + dirs[dir].1;
    }
    let (endx, endy) = (x, y);
    interesting_points_x.insert(endx);
    interesting_points_y.insert(endy);
    interesting_points_x.insert(0);
    interesting_points_y.insert(0);
    let x_lower_bound = *interesting_points_x.iter().min().unwrap() - 1;
    let x_upper_bound = *interesting_points_x.iter().max().unwrap() + 1;
    let y_lower_bound = *interesting_points_y.iter().min().unwrap() - 1;
    let y_upper_bound = *interesting_points_y.iter().max().unwrap() + 1;
    interesting_points_x.insert(x_lower_bound);
    interesting_points_x.insert(x_upper_bound);
    interesting_points_y.insert(y_lower_bound);
    interesting_points_y.insert(y_upper_bound);
    let mut interesting_points = Array2D::filled_with(
        (0, 0),
        interesting_points_x.len(),
        interesting_points_y.len(),
    );
    let mut interesting_points_reverse = HashMap::new();
    for (i, x) in interesting_points_x.iter().enumerate() {
        for (j, y) in interesting_points_y.iter().enumerate() {
            interesting_points[(i, j)] = (*x, *y);
            interesting_points_reverse.insert((*x, *y), (i, j));
        }
    }
    let mut gscore = HashMap::<Point, i64>::new();
    let mut queue = PriorityQueue::new();
    queue.push((0, 0), 0);
    gscore.insert((0, 0), 0);
    while let Some(((x, y), _)) = queue.pop() {
        if (x, y) == (endx, endy) {
            return gscore[&(x, y)].to_string();
        }
        let current_gscore = gscore[&(x, y)];
        let (i, j) = interesting_points_reverse.get(&(x, y)).unwrap();
        for (ni, nj) in [
            (i + 1, *j),
            (i.wrapping_sub(1), *j),
            (*i, j + 1),
            (*i, j.wrapping_sub(1)),
        ] {
            if ni >= interesting_points.num_rows() || nj >= interesting_points.num_columns() {
                continue;
            }
            let (nx, ny) = interesting_points[(ni, nj)];
            let mut intersects_with_a_wall = false;
            if nj == *j {
                let (leftx, rightx) = if nx > x { (x + 1, nx) } else { (nx, x - 1) };
                intersects_with_a_wall |= horizontal_walls.iter().any(|(from, to)| {
                    assert_eq!(from.1, to.1);
                    from.1 == ny
                        && (leftx <= from.0 && from.0 <= rightx || leftx <= to.0 && to.0 <= rightx)
                });
                intersects_with_a_wall |= vertical_walls.iter().any(|(from, to)| {
                    assert_eq!(from.0, to.0);
                    (leftx <= from.0 && from.0 <= rightx) && (from.1 <= ny && ny <= to.1)
                });
            } else {
                let (lefty, righty) = if ny > y { (y + 1, ny) } else { (ny, y - 1) };
                intersects_with_a_wall |= vertical_walls.iter().any(|(from, to)| {
                    assert_eq!(from.0, to.0);
                    from.0 == nx
                        && (lefty <= from.1 && from.1 <= righty || lefty <= to.1 && to.1 <= righty)
                });
                intersects_with_a_wall |= horizontal_walls.iter().any(|(from, to)| {
                    assert_eq!(from.1, to.1);
                    (lefty <= from.1 && from.1 <= righty) && (from.0 <= nx && nx <= to.0)
                });
            }
            if intersects_with_a_wall {
                continue;
            }
            let new_dist = current_gscore
                .wrapping_add_unsigned(nx.abs_diff(x))
                .wrapping_add_unsigned(ny.abs_diff(y));
            if new_dist < *gscore.get(&(nx, ny)).unwrap_or(&i64::MAX) {
                gscore.insert((nx, ny), new_dist);
                queue.push(
                    (nx, ny),
                    (-new_dist)
                        .wrapping_sub_unsigned(nx.abs_diff(endx))
                        .wrapping_sub_unsigned(ny.abs_diff(ny)),
                );
            }
        }
    }
    panic!("exit not found");
}

pub fn solve_part_2(input: &str) -> String {
    solve_part_1(input)
}

pub fn solve_part_3(input: &str) -> String {
    solve_part_1(input)
}

The "is between" operator in Python is perhaps the thing I miss the most from Python :)

I just noticed that you're probably the first person I've seen to include tests.

Are you assuming that the cycle will always include the initial state? It does, as it turns out, but that's not really obvious (at least to me) from the problem.

Wow, your interviews were tough. I was never asked anything even remotely this difficult.

Sadly, every client renders code blocks differently :/ Yours apparently doesn't keep line breaks for some reason. I assume this happens to other posts on programming.dev with code blocks, not just mine, right?

Either way, you can open it on the web to read the code.