you could say that, yeah, it downloads the inputs, submits the answers, and keeps track of wrong answers. You can grab my entire repository here: https://github.com/hades/aoc25/tree/master
comments
comment on
๐ - 2025 DAY 1 SOLUTIONS -๐
comment on
๐ - 2025 DAY 1 SOLUTIONS -๐
How could I run this code? Do you use some kind of framework for AoC?
comment on
๐ - 2025 DAY 1 SOLUTIONS -๐
Rust
#[derive(Default)]
pub struct Day1Solver {
input: Vec<i64>,
}
impl Solver for Day1Solver {
fn presolve(&mut self, input: &str) {
self.input = input
.trim()
.split("\n")
.map(|line| {
if let Some(n) = line.strip_prefix('L') {
-n.parse::<i64>().unwrap()
} else if let Some(n) = line.strip_prefix('R') {
n.parse().unwrap()
} else {
panic!("what: {line}");
}
})
.collect();
}
fn solve_part_one(&mut self) -> String {
let mut p = 50;
let mut count = 0;
for n in self.input.clone() {
p += n;
if p % 100 == 0 {
count += 1;
}
}
count.to_string()
}
fn solve_part_two(&mut self) -> String {
let mut count = 0;
let mut p = 1000000000050;
for i in self.input.clone() {
if p % 100 == 0 {
count += (i / 100).abs();
} else {
count += ((p + i) / 100 - p / 100).abs();
if i < 0 && (p + i) % 100 == 0 {
count += 1;
}
}
p += i;
}
count.to_string()
}
}
comment on
๐ - 2025 DAY 1 SOLUTIONS -๐
comment on
๐ - 2025 DAY 1 SOLUTIONS -๐
The struggled with a counting solution for a long time. I submitted with a simple enumerative solution in the end but managed to get it right after some pause time:
Haskell
Fast to Run, Stepwise Solution
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE OrPatterns #-}
module Main (main) where
import Control.Monad ( (<$!>) )
import qualified Data.List as List
main :: IO ()
main = do
rotations <- (fmap parseRotation . init . lines) <$!> getContents
print $ part1 rotations
print $ part2 rotations
part2 :: [Either Int Int] -> Int
part2 rotations = let
foldRotation (position, zeroCount) operation = case operation of
Left y -> let
(zeroPasses, y') = y `divMod` 100
position' = (position - y') `mod` 100
zeroCount' = zeroPasses + zeroCount + if position <= y' then fromEnum $ position /= 0 else 0
in (position', zeroCount')
Right y -> let
(zeroPasses, y') = y `divMod` 100
position' = (position + y') `mod` 100
zeroCount' = zeroPasses + zeroCount + if y' + position >= 100 then 1 else 0
in (position', zeroCount')
in snd $ List.foldl' foldRotation (50, 0) rotations
part1 :: [Either Int Int] -> Int
part1 rotations = let
positions = List.scanl applyRotation 50 rotations
in List.length . filter (== 0) $ positions
applyRotation :: Int -> Either Int Int -> Int
applyRotation x = \case
Left y -> (x - y) `mod` 100
Right y -> (x + y) `mod` 100
parseRotation :: String -> Either Int Int
parseRotation = \case
'R':rest -> Right $ read rest
'L':rest -> Left $ read rest
bad -> error $ "invalid rotation operation: " ++ bad
Fast to Code, Exhaustively Enumerating Solution
-- | Old solution enumerating all the numbers
part2' :: [Either Int Int] -> Int
part2' rotations = let
intermediatePositions _ [] = []
intermediatePositions x (op:ops) = case op of
Left 0; Right 0 -> intermediatePositions x ops
Left y -> let x' = pred x `mod` 100 in x' : intermediatePositions x' (Left (pred y) : ops)
Right y -> let x' = succ x `mod` 100 in x' : intermediatePositions x' (Right (pred y) : ops)
in List.length . List.filter (== 0) . intermediatePositions 50 $ rotations
comment on
๐ - 2025 DAY 1 SOLUTIONS -๐
A straightforward day 1 for a Javascript / NodeJS solution.
Poorly Optimized JS Solution
let position = 50;
let answer1 = 0;
let answer2 = 0;
const sequence = require('fs').readFileSync('input-day1.txt', 'utf-8');
sequence.split('\n').forEach(instruction => {
const turn = instruction.charAt(0);
let distance = parseInt(instruction.slice(1), 10);
while (distance > 0) {
distance -= 1;
if (turn === 'L') {
position -= 1;
} else if (turn === 'R') {
position += 1;
}
if (position >= 100) {
position -= 100;
} else if (position < 0) {
position += 100;
}
if (position === 0) {
answer2 += 1;
}
}
if (position === 0) {
answer1 += 1;
}
});
console.log(`Part 1 Answer: ${answer1}`);
console.log(`Part 2 Answer: ${answer2}`);
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");
}
comment on
Advent of Code 2025
Is the join code somewhere central / could you share it here?
Edit: My client hides read post, it's literally a pinned post in this community: https://programming.dev/post/6631465
Ah, makes sense. Here's a link to this comment so you can view it on the web: https://programming.dev/post/41427600/20744400
@hades My client is called mastodon. I assume it is official in some way.I don't read a lot of code here.I don't think there's a link to a site. Oh wait, found it.
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)
}
Python
Just putting the solution to part 3 here, because these solutions are pretty long. Took me a while to figure out that an optimal return path from the bottom of the volcano burn can bleed into the left quadrant.
from collections import deque
import heapq as hq
import re
DIRECTIONS_CARDINAL = [(-1, 0), (0, 1), (1, 0), (0, -1)]
DIRECTIONS_ALL = [
*DIRECTIONS_CARDINAL, # cardinal
(-1, -1), (-1, 1), (1, -1), (1, 1) # diagonal
]
# yields all 8 possible neighbors
# lava spreads in all 8 directions
def yield_all_neighbors(i, j, m, n):
for di, dj in DIRECTIONS_ALL:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n:
yield ni, nj
# yields only the 4 possible cardinal neighbors
# the dragonduck can only move in cardinal directions
def yield_cardinal_neighbors(i, j, m, n):
for di, dj in DIRECTIONS_CARDINAL:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n:
yield ni, nj
# finds a special character in the grid
def find_char(data: str, ch: str):
i = 0
for row in data.splitlines():
j = row.find(ch)
if j != -1:
return (i, j)
i += 1
assert False, f"Character {ch} not found in grid"
# returns squared distance between two points
def get_dist_sq(a, b):
x1, y1 = a
x2, y2 = b
return (x2 - x1) ** 2 + (y2 - y1) ** 2
# Generator to burn cells permanently one step at a time
def bfs_burn(grid, volcano):
m, n = len(grid), len(grid[0])
queue = deque([volcano])
visited = set()
step = 0
while queue:
nq = len(queue)
for _ in range(nq):
i, j = queue.popleft()
if (i, j) in visited:
continue
# skip cells outside the current step radius
# but do not mark them as visited yet
if get_dist_sq((i, j), volcano) > (step * step):
continue
visited.add((i, j))
# burn cell permanently
grid[i][j] = -1
for ni, nj in yield_all_neighbors(i, j, m, n):
if (ni, nj) in visited:
continue
queue.append((ni, nj))
step += 1
# yield here to allow enclosing the volcano after each step
yield step
def part3(data: str):
# initialize variables
start = find_char(data, 'S')
volcano = find_char(data, '@')
data = re.sub(r'[@S]', '0', data)
grid = [[int(c) for c in row] for row in data.splitlines()]
m, n = len(grid), len(grid[0])
# initialize lava generator
lava_spreader = bfs_burn(grid, volcano)
# Finds shortest path from start to dest within time limit
# Dijkstra's algorithm with constraints
def find_shortest_path(start: tuple[int, int], dest: tuple[int, int], volcano_col: int, time_limit, map_half):
candidates = [(0, start[0], start[1])]
visited = set()
while candidates:
cost, i, j = hq.heappop(candidates)
if (i, j) in visited:
continue
visited.add((i, j))
if (i, j) == dest:
# if we are processing the destination, we have found the shortest path to it
return cost
if cost > time_limit:
# if we have exceeded the time limit, prune this path
continue
# remember: the dragonduck can only move in cardinal directions
for ni, nj in yield_cardinal_neighbors(i, j, m, n):
# skip visited or burned cells
if (ni, nj) in visited or grid[ni][nj] == -1:
continue
# if processing left half, skip paths going to the right of the volcano
if map_half == 'left' and nj > volcano_col:
continue
# if processing right half, skip paths going to the left of the volcano (ONLY for bottom quadrant)
# allow moving into the left half in the top quadrant (!!!)
elif map_half == 'right' and (ni > m // 2 and nj < volcano_col):
continue
# add new candidate path
hq.heappush(candidates, (cost + grid[ni][nj], ni, nj))
# we couldn't reach the destination within time limit
# fail by returning the maximum possible cost
return 9 * m * n
# try increasing lava spreads
while True:
# spread lava one more step
step = next(lava_spreader)
# calculate time limit
time = step * 30
# our paths from the start must connect at the bottom of the lava burn
burn_bottom_boundary = (volcano[0] + step, volcano[1])
time_taken = find_shortest_path(start, burn_bottom_boundary, volcano[1], time, 'left')
if time_taken >= time:
# if we already exceeded time, quit early
continue
time_taken += find_shortest_path(burn_bottom_boundary, start, volcano[1], time - time_taken, 'right')
if time_taken >= time:
# if we exceeded time, try next lava spread
continue
# we successfully enclosed the volcano within time
burn_radius = step - 1
return time_taken * burn_radius
Python
def part1(data: str):
elements = map(int, data.split(','))
total = 0
for ele in elements:
# a spell element will add (90 // number) bricks for 90 columns
total += 90 // ele
return total
assert part1("1,2,3,5,9") == 193
# Gets all spell elements needed to build a wall
# Useful for part 2 and part 3
def get_elements(data: str):
wall = map(int, data.split(','))
elements = [] # spell elements
for col_idx, fragments in enumerate(wall):
# fix for 1-based indexing
col = col_idx + 1
# account bricks for recorded elements
for ele in elements:
if col % ele == 0:
fragments -= 1
# if we still have fragments, we need to add a new element with that column number
if fragments > 0:
elements.append(col)
return elements
def part2(data: str):
# Get all spell elements needed to build the wall
elements = get_elements(data)
# return product of all elements
ans = 1
for ele in elements:
ans *= ele
return ans
assert part2("1,2,2,2,2,3,1,2,3,3,1,3,1,2,3,2,1,4,1,3,2,2,1,3,2,2") == 270
# Part 3: Binary Search for maximum full columns
def part3(data: str):
BRICKS = 202520252025000
elements = get_elements(data)
# Check if we can build 'cols' full columns within BRICKS bricks
def can_build(cols: int) -> bool:
bricks_used = 0
for ele in elements:
bricks_used += cols // ele
if bricks_used > BRICKS:
return False
return True
# binary search: break on first column size we cannot build
lo = 1
hi = BRICKS
while lo < hi:
mid = lo + (hi - lo) // 2
if can_build(mid):
lo = mid + 1
else:
hi = mid
# if lo is the first we cannot build, lo - 1 is the maximum we can build
return lo - 1
assert part3("1,2,2,2,2,3,1,2,3,3,1,3,1,2,3,2,1,4,1,3,2,2,1,3,2,2") == 94439495762954
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(¶ms);
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()
}
That and the else (no-break) clause for loops are some of my favorite features.
Yeah, it's an easy way to make sure everything is working correctly when I refactor or optimize. I used to keep samples in their own text files before but EC samples are small enough to include directly.
Yes, I'm not sure how to prove it but I had a hunch that was the case. So I initially wrote some code to print the grid right after the cycle is detected and lo and behold, it was the initial state.
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.