DataWraith's recent activity
-
Comment on Day 20: Race Condition in ~comp.advent_of_code
-
Comment on Day 19: Linen Layout in ~comp.advent_of_code
DataWraith LinkVery nice and relaxing puzzle. Part 1 (Rust) pub fn part1(input: &PuzzleInput) -> String { possible_patterns(input).len().to_string() } pub fn possible_patterns(input: &PuzzleInput) ->...Very nice and relaxing puzzle.
Part 1 (Rust)
pub fn part1(input: &PuzzleInput) -> String { possible_patterns(input).len().to_string() } pub fn possible_patterns(input: &PuzzleInput) -> HashSet<String> { let mut q = BTreeSet::new(); let mut c = HashSet::new(); for (i, design) in input.desired_designs.iter().enumerate() { q.insert((i, design.as_str())); } while let Some(design) = q.pop_first() { for pattern in input.patterns.iter() { if design.1.starts_with(pattern) { if design.1.len() == pattern.len() { c.insert(input.desired_designs[design.0].clone()); q.retain(|d| d.0 != design.0); } else { q.insert((design.0, &design.1[pattern.len()..])); } } } } c }Part 2 (Rust)
pub fn part2(input: &PuzzleInput) -> String { let possible = possible_patterns(input); let mut c = 0; for design in possible.iter() { c += count_possibilities(input, design); } c.to_string() } pub fn count_possibilities(input: &PuzzleInput, design: &str) -> usize { let mut c = 0; let mut q = BTreeMap::new(); q.insert(design, 1); while let Some((design, paths)) = q.pop_first() { if design.len() == 0 { c += paths; continue; } for pattern in input.patterns.iter() { if design.starts_with(pattern) { q.entry(&design[pattern.len()..]) .and_modify(|p| *p += paths) .or_insert(paths); } } } c } -
Comment on Day 18: RAM Run in ~comp.advent_of_code
DataWraith (edited )LinkOh my god, somehow I fall for every single trap and/or nerd-snipe in AoC this year... Rust (Part 1) A straightforward Breadth-First Search to find the path. pub fn part1(input: &PuzzleInput) ->...Oh my god, somehow I fall for every single trap and/or nerd-snipe in AoC this year...
Rust (Part 1)
A straightforward Breadth-First Search to find the path.
pub fn part1(input: &PuzzleInput) -> String { let mut memory = Grid2D::new(input.width, input.height, '.'); // Mark the fallen bytes for c in input.bytes.iter().take(input.to_simulate) { memory.set(*c, '#'); } // And find the shortest path to the bottom right using Breadth-First Search let mut q = VecDeque::new(); q.push_back((Coordinate::new(0, 0), 0)); while let Some((c, cost)) = q.pop_front() { if c == Coordinate::new(input.width as i32 - 1, input.height as i32 - 1) { return cost.to_string(); } for nc in c.neighbors() { if memory.get(nc) == Some(&'.') { memory.set(nc, 'o'); q.push_back((nc, cost + 1)); } } } unreachable!() }Part 2
That's where the trap hit. I tried to compute the set of all valid paths as a Dijkstra-Map, and then tried to repair it when an obstacle appears. I'm sure this is possible somehow (there are decremental-connectivity data structures, after all), but it is entirely unnecessary for this problem. You just A* repeatedly whenever a new obstacle falls onto the previous best path...
pub fn part2(input: &PuzzleInput) -> String { let mut memory = Grid2D::new(input.width, input.height, false); let mut path: Option<HashSet<Coordinate>> = None; // Simulate the falling bytes for byte_coord in input.bytes.iter() { // If the byte falls on our exit, we're trapped! if byte_coord.x == input.width as i32 - 1 && byte_coord.y == input.height as i32 - 1 { return format!("{},{}", byte_coord.x, byte_coord.y); } // Mark the byte as fallen memory.set(*byte_coord, true); // If we don't have a valid path (either because this is the first invocation, or because a byte fell onto our path), // find the shortest path to the bottom right using A* if path.is_none() || path.clone().unwrap().contains(byte_coord) { let start = Coordinate::new(0, 0); let end = Coordinate::new(input.width as i32 - 1, input.height as i32 - 1); let mut visited = memory.map(|_| false); // This is a bit ugly, but it appeases the borrow checker let m2 = memory.clone(); // Define the successors function that returns the valid neighbors of the current coordinate let successors = move |c: &Coordinate| { if *c == end { return vec![]; } let neighbors = c .neighbors() .filter(|n| m2.get(*n).is_some()) .filter(|n| *m2.get(*n).unwrap() == false) .filter(|n| *visited.get(*n).unwrap() == false) .map(|n| (n, 1)) .collect_vec(); // Mark the neighbors as visited neighbors.iter().for_each(|n| { visited.set(n.0, true); }); neighbors }; // And then just A* and convert the path into a set of coordinates path = astar( &start, successors, |c| *c == end, |c| c.manhattan_distance(end), ) .map(|(path, cost)| path.iter().cloned().collect::<HashSet<_>>()); } // If we don't have a valid path, the last byte that fell is our puzzle answer. if path.is_none() { return format!("{},{}", byte_coord.x, byte_coord.y); } } unreachable!() }The
astarfunction is from my AoC helper library, but you could just as well use a different implementation (e.g. thepathfindingcrate's).Non-stupid way to do Part 2
pub fn part2(input: &PuzzleInput) -> String { // This solution uses UnionFind again. I thought of trying this myself, but // concluded that it wouldn't work -- and it doesn't in the forward // direction. But I later found out on Reddit that you can just reverse // everything, and it works marvelously. // Step 1: Find all obstacle coordinates and make a map let mut grid = Grid2D::new(input.width, input.height, '.'); for b in input.bytes.iter() { grid.set(*b, '#'); } // Step 2: Prepare the UnionFind datastructure let mut union_find = UnionFind::default(); let mut sets = grid.map(|_| 0); for (c, _) in grid.iter() { sets[c] = union_find.make_set(); } // Step 3: Union all coordinates that never have obstacles for (c, _) in grid.iter() { if grid.get(c) != Some(&'.') { continue; } for dir in [Direction::Right, Direction::Down] { let n = c.neighbor(dir); if grid.get(n) == Some(&'.') { union_find.union(sets[c], sets[n]).unwrap(); } } } // Step 4: Iterate over the obstacles in reverse, and union the coordinates. // This is the non-obvious part. Instead of adding obstacles one by one, // we start with all obstacles and then remove them one by one, unioning // the free space. let start = Coordinate::new(0, 0); let end = Coordinate::new(input.width as i32 - 1, input.height as i32 - 1); for b in input.bytes.iter().rev() { grid.set(*b, '.'); for n in b.neighbors() { if grid.get(n) == Some(&'.') { union_find.union(sets[*b], sets[n]).unwrap(); } } // Step 5: If the start and end coordinates are connected, the last // obstacle we removed must have been the one blocking the path. if union_find.find(sets[start]) == union_find.find(sets[end]) { return format!("{},{}", b.x, b.y); } } unreachable!() }This runs about twice as fast on my machine as using a binary search, 150µs vs. ~300µs.
-
Comment on Day 17: Chronospatial Computer in ~comp.advent_of_code
DataWraith LinkGod. Part 2 was time-consuming, but I'm kind of proud that I solved it without help. Rust (Part 1) Part 1 was very boring; everything worked on the 2nd try -- The Sokoban puzzle was much more...God. Part 2 was time-consuming, but I'm kind of proud that I solved it without help.
Rust (Part 1)
Part 1 was very boring; everything worked on the 2nd try -- The Sokoban puzzle was much more interesting.
pub fn part1(input: &PuzzleInput) -> String { let machine = run_machine(input); machine.output.iter().join(",").to_string() } pub fn run_machine(input: &PuzzleInput) -> Machine { let mut machine = Machine { a: input.register_a, b: input.register_b, c: input.register_c, program: input.program.clone(), instr_ptr: 0, output: vec![], }; while let Some(_) = machine.step() {} machine } #[derive(Debug, Clone)] pub struct Machine { pub a: u64, pub b: u64, pub c: u64, pub program: Vec<u64>, pub instr_ptr: usize, pub output: Vec<u64>, } impl Machine { pub fn step(&mut self) -> Option<()> { let instr: Instruction = self.read()?.into(); match instr { Instruction::Adv => self.adv(), Instruction::Bxl => self.bxl(), Instruction::Bst => self.bst(), Instruction::Jnz => self.jnz(), Instruction::Bxc => self.bxc(), Instruction::Out => self.out(), Instruction::Bdv => self.bdv(), Instruction::Cdv => self.cdv(), }; Some(()) } pub fn read(&mut self) -> Option<u64> { if self.instr_ptr >= self.program.len() { return None; } let val = self.program[self.instr_ptr]; self.instr_ptr += 1; Some(val) } pub fn adv(&mut self) -> Option<()> { let numerator = self.a as f64; let denominator = (1 << self.combo_operand()?) as f64; self.a = (numerator / denominator).trunc() as u64; Some(()) } pub fn bxl(&mut self) -> Option<()> { let operand = self.literal_operand()?; self.b ^= operand; Some(()) } pub fn bst(&mut self) -> Option<()> { let operand = self.combo_operand()?; self.b = operand % 8; Some(()) } pub fn jnz(&mut self) -> Option<()> { let o = self.literal_operand()?; if self.a == 0 { return Some(()); } self.instr_ptr = o as usize; Some(()) } pub fn bxc(&mut self) -> Option<()> { let _ = self.literal_operand()?; let r = self.b ^ self.c; self.b = r; Some(()) } pub fn out(&mut self) -> Option<()> { let o = self.combo_operand()? % 8; self.output.push(o); Some(()) } pub fn bdv(&mut self) -> Option<()> { let numerator = self.a as f64; let denominator = (1 << self.combo_operand()?) as f64; self.b = (numerator / denominator).trunc() as u64; Some(()) } pub fn cdv(&mut self) -> Option<()> { let numerator = self.a as f64; let denominator = (1 << self.combo_operand()?) as f64; self.c = (numerator / denominator).trunc() as u64; Some(()) } pub fn literal_operand(&mut self) -> Option<u64> { let x = *self.program.get(self.instr_ptr)?; self.instr_ptr += 1; Some(x) } pub fn combo_operand(&mut self) -> Option<u64> { let x = self.program.get(self.instr_ptr)?; self.instr_ptr += 1; match x { 0..=3 => return Some(*x), 4 => return Some(self.a), 5 => return Some(self.b), 6 => return Some(self.c), 7 => unreachable!("Reserved operand"), _ => panic!("Invalid operand"), } } } #[derive(Debug, PartialEq, Eq)] pub enum Instruction { Adv, Bxl, Bst, Jnz, Bxc, Out, Bdv, Cdv, } impl From<u64> for Instruction { fn from(value: u64) -> Self { match value { 0 => Instruction::Adv, 1 => Instruction::Bxl, 2 => Instruction::Bst, 3 => Instruction::Jnz, 4 => Instruction::Bxc, 5 => Instruction::Out, 6 => Instruction::Bdv, 7 => Instruction::Cdv, _ => panic!("Invalid instruction"), } } }Part 2
Part 2 took a long time. I transcribed the machine code back into a more high-level representation and noticed that
ais only ever divided by eight.It would probably be possible to just derive the bit pattern for the registers if you stare at it hard enough, but I took this as an opportunity to play with Z3.
After a few skill issues with getting it to do XOR and 2**X operations (not to mention the sidequest of translating the entire fucking VM into Python because the Rust bindings aren't complete for Z3), I had an answer that produced a quine; however, it was too high. Then I was left scratching my head, because Z3 refused to find answers below it, and if I gave it a constraint not to exceed the known result, it produced even higher numbers. Finally, after fiddling with the number of bits in theBitVecs, it finally spit out an answer that the AoC site accepted -- though I'm not sure if I just got lucky there. :( -
Comment on Day 16: Reindeer Maze in ~comp.advent_of_code
DataWraith LinkThis one was a lot of fun to puzzle through. Did I mention that I love pathfinding puzzles? Rust (Part 1) This is a fairly basic application of A* search. In retrospect, there was nothing really...This one was a lot of fun to puzzle through. Did I mention that I love pathfinding puzzles?
Rust (Part 1)
This is a fairly basic application of A* search. In retrospect, there was nothing really difficult about this, but I still managed to break it in seven hundred different ways because I thought I could code pathfinding up from scratch by now, instead of using a library or even reference material. Ah, the programmer virtue of hubris strikes again.
#[derive(Debug, Clone, PartialEq, Eq)] pub struct State { pub position: Coordinate, pub direction: Direction, pub heuristic: usize, pub straight_steps: usize, pub number_of_turns: usize, pub waypoints: Vec<Coordinate>, } impl State { pub fn score(&self) -> usize { self.straight_steps + self.number_of_turns * 1000 } } impl PartialOrd for State { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) } } // Ordering function for the priority queue -- we want to prioritize states with // lower scores + heuristic values to get the A* algorithm. Since BinaryHeap is // a max-heap, we invert the comparison. impl Ord for State { fn cmp(&self, other: &Self) -> Ordering { (other.score() + other.heuristic).cmp(&(self.score() + self.heuristic)) } } // Follows a given straight path until it either hits a junction, the end, or a wall. pub fn follow_path( cur: Coordinate, dir: Direction, grid: &Grid2D<char>, junctions: &HashSet<Coordinate>, ) -> (Coordinate, usize) { let mut cur = cur; let mut len = 1; loop { let next = cur + dir; if junctions.contains(&next) { return (next, len); } if grid.get(next) == Some(&'E') { return (next, len); } if grid.get(next) == Some(&'#') { return (cur, len - 1); } len += 1; cur = next; } } // Heuristic function for the A* algorithm. // // We need to take at least manhattan_distance(end) straight steps, but since the end // is in the top-right corner, we need to turn at least once if we are currently looking // leftwards or downwards. fn heuristic(cur: Coordinate, dir: Direction, end: Coordinate) -> usize { let mut h = cur.manhattan_distance(end) as usize; if dir == Direction::Left { h += 1000; } if dir == Direction::Down { h += 1000; } h } // Runs the A* algorithm to find the shortest path from start to end. pub fn search(input: &PuzzleInput) -> Vec<State> { let junctions = junctions(&input.maze); let start = input.maze.iter().find(|(_, &c)| c == 'S').unwrap().0; let end = input.maze.iter().find(|(_, &c)| c == 'E').unwrap().0; let mut q = BinaryHeap::new(); let mut visited = BTreeMap::new(); // Starting states q.push(State { position: start, direction: Direction::Right, straight_steps: 0, number_of_turns: 0, waypoints: vec![start], heuristic: heuristic(start, Direction::Right, end), }); let mut best: Vec<State> = vec![]; while let Some(state) = q.pop() { // Skip if we've already seen this state with a better score if let Some(prev_g) = visited.get(&(state.position, state.direction)) { if state.score() > *prev_g { continue; } } // Mark this state as visited visited.insert((state.position, state.direction), state.score()); // If we've reached the end, add this state to the best list. We are guaranteed // to only add shortest paths to the best list because we are using a priority queue // and an admissible heuristic. Also, we break out of the loop below if we've found // all shortest paths, so we can't reach this point if we've already found all // shortest paths. if state.position == end { if best.len() == 0 || state.score() == best[0].score() { best.push(state.clone()); } continue; } // Follow the current corridor until we hit a junction, the end, or a wall. let (next, len) = follow_path(state.position, state.direction, &input.maze, &junctions); // Did we hit a wall? let hit_a_wall = len == 0; // If we didn't hit a wall, this is a junction, and we can proceed forwards. if !hit_a_wall { // Update the list of waypoints let mut waypoints = state.waypoints.clone(); waypoints.push(next); // Add the new state to the queue let fwd = State { position: next, straight_steps: state.straight_steps + len, heuristic: heuristic(next, state.direction, end), waypoints, ..state.clone() }; q.push(fwd); } // If we are at a junction or corner, we can try to turn left or right. if junctions.contains(&state.position) || hit_a_wall { let left_dir = state.direction.turn_left_90(); let right_dir = state.direction.turn_right_90(); let left_coord = state.position.neighbor(left_dir); let right_coord = state.position.neighbor(right_dir); let left_free = input.maze.get(left_coord) == Some(&'.') || input.maze.get(left_coord) == Some(&'E'); let right_free = input.maze.get(right_coord) == Some(&'.') || input.maze.get(right_coord) == Some(&'E'); if left_free { let turn_left = State { direction: left_dir, number_of_turns: state.number_of_turns + 1, ..state.clone() }; q.push(turn_left); } if right_free { let turn_right = State { direction: right_dir, number_of_turns: state.number_of_turns + 1, ..state.clone() }; q.push(turn_right); } } // If the current state is worse than the best state we've found, we can stop early, // because we are guaranteed to have found all shortest paths (due to the properties // of A* and the admissable heuristic). if !best.is_empty() && state.score() > best[0].score() { break; } } best } // Finds all junctions in the maze. pub fn junctions(maze: &Grid2D<char>) -> HashSet<Coordinate> { let mut junctions = HashSet::new(); junctions.insert(maze.iter().find(|(_, &c)| c == 'S').unwrap().0); for (coord, &c) in maze.iter() { if c != '.' { continue; } let mut count = 0; for neighbors in coord.neighbors() { if maze.get(neighbors) == Some(&'.') { count += 1; } } if count > 2 { junctions.insert(coord); } } junctions } pub fn part1(input: &PuzzleInput) -> String { search(input)[0].score().to_string() }Rust (Part 2)
Part 2 was fairly easy, because all you have to do is wait until A* delivers you all shortest paths. By the properties of priority queues ordered by an adissable heuristic, you get all shortest paths before all longer paths. If your A* is subtly broken, though, you may need a long time to recover...
pub fn part2(input: &PuzzleInput) -> String { let best = search(input); covered(input, &best).to_string() } // Counts the number of positions covered by the best path by following the // waypoints in the best paths. fn covered(input: &PuzzleInput, best: &[State]) -> usize { let mut covered = input.maze.map(|_| false); for b in best.iter() { for path in b.waypoints.windows(2) { let towards = path[0].towards(path[1]); covered.set(path[0], true); for c in successors(Some(path[0]), |&c| Some(c.neighbor(towards))) { covered.set(c, true); if c == path[1] { break; } } } } covered.iter().filter(|(_, &c)| c).count() }Benchmark
Pretty slow, because I have to lug around all those waypoints. :/
day_16 fastest │ slowest │ median │ mean │ samples │ iters ├─ part1 175.1 ms │ 267.8 ms │ 182.3 ms │ 186.9 ms │ 100 │ 100 ╰─ part2 174.8 ms │ 226.1 ms │ 181.7 ms │ 183.5 ms │ 100 │ 100 -
Comment on Day 15: Warehouse Woes in ~comp.advent_of_code
DataWraith (edited )LinkGonna agree with @Hello that this wasn't particularly interesting from a how-do-i-do-this perspective, but I felt like it was a nice programming exercise -- after all Advent of Code is supposed to...Gonna agree with @Hello that this wasn't particularly interesting from a how-do-i-do-this perspective, but I felt like it was a nice programming exercise -- after all Advent of Code is supposed to make you a better programmer.
That said, it also took me about 40 minutes to fiddle with part 2, and my code ended up kind of ugly and, as usual, verbose. I'm always amazed what you guys can accomplish with code that is so much shorter and, often, simpler.
Edit: After a refactoring pass, it's not quite as bad anymore.
Part 2 (Rust)
pub fn part2(input: &PuzzleInput) -> String { let mut warehouse = Grid2D::new(input.warehouse.width() * 2, input.warehouse.height(), '.'); // Double the warehouse width input.warehouse.iter().for_each(|(coord, c)| { let x = coord.x * 2; let y = coord.y; if *c == 'O' { warehouse.set((x, y).into(), '['); warehouse.set((x + 1, y).into(), ']'); } else if *c == '@' { warehouse.set((x, y).into(), '@'); warehouse.set((x + 1, y).into(), '.'); } else { warehouse.set((x, y).into(), *c); warehouse.set((x + 1, y).into(), *c); } }); let result = run_robot(&PuzzleInput { warehouse, robot_moves: input.robot_moves.clone(), }); println!("{}", result); // GPS coordinates let mut sum = 0; for (coord, c) in result.iter() { if c == &'[' { sum += 100 * coord.y + coord.x; } } sum.to_string() } pub fn can_push_box(grid: &mut Grid2D<char>, box_pos: Coordinate, dir: Direction) -> bool { if grid[box_pos] == '.' { return true; } if grid[box_pos] == '#' { return false; } match dir { Direction::Left | Direction::Right => { let next = box_pos + dir.into(); return can_push_box(grid, next, dir); } Direction::Up | Direction::Down => { let next_pos1 = box_pos + dir.into(); let next_pos2 = box_pos + dir.into() + if grid[box_pos] == '[' { Direction::Right.into() } else { Direction::Left.into() }; return can_push_box(grid, next_pos1, dir) && can_push_box(grid, next_pos2, dir); } _ => false, } } pub fn push_box(grid: &mut Grid2D<char>, box_pos: Coordinate, dir: Direction) { if grid[box_pos] == '.' { return; } if grid[box_pos] == '#' { return; } if dir == Direction::Left || dir == Direction::Right { let mut cur = box_pos; let mut next; loop { next = cur + dir.into(); if grid[next] == '.' { break; } cur = next; } while next != box_pos { grid.set(next, grid[cur]); grid.set(cur, '.'); next = cur; cur = cur.neighbor(dir.opposite()); } } else { let second_half_dir = if grid[box_pos] == '[' { Direction::Right } else { Direction::Left }; let opposite_bracket = if grid[box_pos] == '[' { ']' } else { '[' }; // Recursively push the boxes push_box(grid, box_pos + dir.into(), dir); push_box(grid, box_pos + dir.into() + second_half_dir.into(), dir); // Move the box itself grid.set(box_pos + dir.into(), grid[box_pos]); grid.set( box_pos + dir.into() + second_half_dir.into(), opposite_bracket, ); grid.set(box_pos, '.'); grid.set(box_pos + second_half_dir.into(), '.'); } } pub fn run_robot(input: &PuzzleInput) -> Grid2D<char> { let mut grid = input.warehouse.clone(); let mut robot_pos = grid.iter().find(|(_, c)| **c == '@').unwrap().0; for robot_move in input.robot_moves.iter() { let dir: Direction = (*robot_move).try_into().unwrap(); if can_push_box(&mut grid, robot_pos + dir.into(), dir) { push_box(&mut grid, robot_pos + dir.into(), dir); grid.set(robot_pos, '.'); grid.set(robot_pos + dir.into(), '@'); robot_pos = robot_pos + dir.into(); } } grid } -
Comment on Day 14: Restroom Redoubt in ~comp.advent_of_code
DataWraith Link ParentThat's an interesting way to do it -- it's also the fastest one among the several I tested after looking up how other people did this, running in 6-ish milliseconds. That no robot overlaps in the...so tried a few conditions before settling on "no robots on the same space".
That's an interesting way to do it -- it's also the fastest one among the several I tested after looking up how other people did this, running in 6-ish milliseconds. That no robot overlaps in the target image makes sense, because the puzzle input was likely generated by running the velocities in reverse, but to me it is not obvious why every other frame has at least one overlapping robot. I guess the input must have been prepared to specifically have this property.
As an aside, for something that seems like it needs manual inspection, there seem to be a lot of different ways to solve this automatically, from just checking for adjacent robots to working with entropies and robot spread variances. It's also possible to filter for the minimum safety scores from part 1 in order to find the tree, which seems like the intended way to do it.
-
Comment on Day 14: Restroom Redoubt in ~comp.advent_of_code
DataWraith LinkHaha, this one was nice. Finally managed to get a rank below 1000 for part 2. Part 1 (Rust) pub fn part1(input: &PuzzleInput) -> String { let mut robot_grid = Grid2D::new(101, 103, 0usize); for...Haha, this one was nice. Finally managed to get a rank below 1000 for part 2.
Part 1 (Rust)
pub fn part1(input: &PuzzleInput) -> String { let mut robot_grid = Grid2D::new(101, 103, 0usize); for robot in input.robots.iter() { let pos = robot.position + robot.velocity * 100; let final_pos = Coordinate::new( pos.x.rem_euclid(robot_grid.width), pos.y.rem_euclid(robot_grid.height), ); robot_grid[final_pos] += 1; } let counts = count_robots(&robot_grid); let safety_factor = counts[0] * counts[1] * counts[2] * counts[3]; safety_factor.to_string() } pub fn count_robots(grid: &Grid2D<usize>) -> [usize; 4] { let x_center = grid.width / 2; let y_center = grid.height / 2; let mut counts = [0; 4]; for x in 0..x_center { for y in 0..y_center { counts[0] += grid[(x, y).into()]; } for y in (y_center + 1)..grid.height { counts[1] += grid[(x, y).into()]; } } for x in (x_center + 1)..grid.width { for y in 0..y_center { counts[2] += grid[(x, y).into()]; } for y in (y_center + 1)..grid.height { counts[3] += grid[(x, y).into()]; } } counts }Part 2 (Rust)
Just eyeball it.
pub fn part2(input: &PuzzleInput) -> String { for i in 0..=6446 { let mut robot_grid = Grid2D::new(101, 103, '.'); for robot in input.robots.iter() { let pos = robot.position + robot.velocity * i; let final_pos = Coordinate::new( pos.x.rem_euclid(robot_grid.width), pos.y.rem_euclid(robot_grid.height), ); robot_grid[final_pos] = '#'; } let picture = format!("{}\ni: {}", robot_grid, i); if picture.contains("###############################") { println!("{}", picture); // Wait for user to press enter let mut buf = String::new(); std::io::stdin().read_line(&mut buf).unwrap(); } } "".to_string() } -
Comment on Day 12: Garden Groups in ~comp.advent_of_code
DataWraith LinkThis one was extremely frustrating. I had all the examples for Part 2 passing hours ago, but somehow the actual input did not work, so I had to scrap my initial approach and try something else....This one was extremely frustrating. I had all the examples for Part 2 passing hours ago, but somehow the actual input did not work, so I had to scrap my initial approach and try something else.
Part 1 (Rust)
My solution to Part 1 relies on a UnionFind data structure, which I had prepared in advance of AoC. UnionFind allows you to efficiently find the area for each plant in the input by 'merging' adjacent plants.
Then it's a simple matter of finding the border tiles around a set of plants and counting them up.pub fn part1(input: &PuzzleInput) -> String { let mut sum = 0; for region in find_regions(&input.garden).into_iter() { let mut border = HashMap::new(); for coord in region.iter() { for neighbor in coord.neighbors() { if !region.contains(&neighbor) { border.entry(coord).and_modify(|c| *c += 1).or_insert(1); } } } sum += border.values().sum::<i32>() * region.len() as i32; } sum.to_string() } pub fn find_regions(input: &Grid2D<char>) -> Vec<HashSet<Coordinate>> { let mut union_find = UnionFind::default(); let mut sets = HashMap::new(); let mut result = vec![]; for (coord, &plant) in input.iter() { let set = union_find.make_set(); sets.insert(coord, set); } for (coord, &plant) in input.iter() { for neighbor in coord.neighbors() { if let Some(neighbor_plant) = input.get(neighbor) { if *neighbor_plant == plant { let _ = union_find.union(sets[&coord], sets[&neighbor]); } } } } for root in union_find.roots() { let mut plot = HashSet::new(); for (coord, &set) in sets.iter() { if union_find.find(set) == Some(root) { plot.insert(*coord); } } result.push(plot); } result }Part 2 (Rust)
I initially tried to walk along the edges of the plots. Doing so naively doesn't work with plots contained in other plots, but eventually I got all the test inputs passing. It just didn't work on the actual input.
So after hours of frustration, I instead fell back on UnionFind again to merge adjacent border tiles (which is really the more obvious way to do this, I guess, but it didn't work for me initially so I abandoned the idea). This needs to be done separately for horizontal and vertical borders, because those 'sides' are counted separately.
pub fn part2(input: &PuzzleInput) -> String { let mut sum = 0; // Replace every tile with 16 new tiles. This is probably overkill, but that's what worked. let input = input.garden.zoom(4); for region in find_regions(&input).into_iter() { let mut union_find_horizontal = UnionFind::default(); let mut union_find_vertical = UnionFind::default(); let mut sets_horizontal = HashMap::new(); let mut sets_vertical = HashMap::new(); let id = input[*region.iter().next().unwrap()]; let mut border = HashSet::new(); for coord in region.iter() { for neighbor in coord.moore_neighbors() { if !region.contains(&neighbor) { border.insert(neighbor); } } } for coord in border.iter() { let set_h = union_find_horizontal.make_set(); let set_v = union_find_vertical.make_set(); sets_horizontal.insert(**coord, set_h); sets_vertical.insert(**coord, set_v); } for coord in border.iter() { let right = coord.neighbor(Direction::Right); if border.contains(&right) { union_find_horizontal .union(sets_horizontal[&coord], sets_horizontal[&right]) .expect("Foo"); } let down = coord.neighbor(Direction::Down); if border.contains(&down) { union_find_vertical .union(sets_vertical[&coord], sets_vertical[&down]) .expect("Foo"); } } let mut horizontal_count = 0; let mut horizontal_counted = HashSet::new(); for (coord, set_h) in sets_horizontal.iter() { let root = union_find_horizontal.find(*set_h).unwrap(); let size = union_find_horizontal.size_of_set(root).unwrap_or(0); if !horizontal_counted.insert(root) { continue; } if size > 1 { horizontal_count += 1; } } let mut vertical_count = 0; let mut vertical_counted = HashSet::new(); for (coord, set_v) in sets_vertical.iter() { let root = union_find_vertical.find(*set_v).unwrap(); let size = union_find_vertical.size_of_set(root).unwrap_or(0); if !vertical_counted.insert(root) { continue; } if size > 1 { vertical_count += 1; } } sum += (horizontal_count + vertical_count) * region.len() / 16; } return sum.to_string(); }Helpers
I'm omitting the UnionFind code. It's easy to write the data structure by following the Wikipedia article.
-
Comment on Day 11: Plutonian Pebbles in ~comp.advent_of_code
DataWraith (edited )LinkThis one is my favourite puzzle so far this year. Very simple, but a lot of fun. Edit: Updated the stuff below after refactoring the code. Part 1 (Rust) I should have solved this properly from the...This one is my favourite puzzle so far this year. Very simple, but a lot of fun.
Edit: Updated the stuff below after refactoring the code.
Part 1 (Rust)
I should have solved this properly from the start, but the experience so far this year has been that the first part can be solved naively. Somehow I always get that the wrong way around, thinking I need a proper Part 1 when I don't, and not thinking properly about part 2 when I need to. I hate how I go into 'hacking' mode immediately instead of taking a minute to think things through.
I initially just used a linked list to iterate on the 'blinks', but after solving part 2 properly, part 1 became a lot simpler as well.
pub fn part1(input: &PuzzleInput) -> String { blink_many(&input.stones, 25).to_string() } pub fn blink_many(input: &[u64], count: usize) -> usize { let states = Counter::from(input.iter().cloned()); let counts = (0..count).fold(states, |states, _| { state_iteration(&states, |input, _| blink(*input), ()) }); counts.count_sum() } pub gen fn blink(stone: u64) -> u64 { if stone == 0 { yield 1; return; } let num_digits = stone.ilog10() + 1; if num_digits % 2 == 0 { yield stone / 10u64.pow(num_digits / 2); yield stone % 10u64.pow(num_digits / 2); return; } yield stone * 2024; }Part 2 (Rust)
pub fn part2(input: &PuzzleInput) -> String { blink_many(&input.stones, 75).to_string() }Helpers
/// Iterates a state function once. /// /// The idea is to have a HashMap containing the current states. Then a /// transition function (which may take an input value) is applied to each /// state, and the resulting state(s) are collected in a new HashMap. /// /// The HashMap keeps track of how often a given state has occurred. This can be /// used to, for example, count how often a state is visited in a finite state /// machine after n iterations. /// /// For example, given a non-deterministic finite state machine, you can count /// how often you end up in the `accept` state after iterating the machine for /// n steps. This was useful for AoC 2023, day 12 in order to count the number of /// valid strings. /// pub fn state_iteration<S, FN, IS, IN>( states: &Counter<S>, mut transition: FN, input: IN, ) -> Counter<S> where S: Eq + Hash, FN: FnMut(&S, &IN) -> IS, IS: IntoIterator<Item = S>, { let mut new_states = Counter::new(); for (state, count) in states.iter() { for new_state in transition(state, &input) { new_states.add_many(new_state, *count); } } new_states }Benchmark
day_11 fastest │ slowest │ median │ mean │ samples │ iters ├─ part1 133.5 µs │ 170.3 µs │ 136.3 µs │ 137 µs │ 100 │ 100 ╰─ part2 5.305 ms │ 5.812 ms │ 5.418 ms │ 5.465 ms │ 100 │ 100 -
Comment on Day 10: Hoof It in ~comp.advent_of_code
DataWraith LinkI love pathfinding puzzles! Part 1 (Rust) pub fn part1(input: &PuzzleInput) -> String { let heads = trail_heads(input); let mut scores = Vec::new(); for head in heads { let score =...I love pathfinding puzzles!
Part 1 (Rust)
pub fn part1(input: &PuzzleInput) -> String { let heads = trail_heads(input); let mut scores = Vec::new(); for head in heads { let score = trail_head_score(input, head); scores.push(score); } scores.iter().sum::<usize>().to_string() } fn trail_head_score(input: &PuzzleInput, head: Coordinate) -> usize { let start = head; let mut seen = HashSet::new(); let mut successors = move |p: &Coordinate| { let mut result = Vec::new(); if input.map.get(*p) == Some(&9) { return result; } for dir in Direction::cardinal() { let neighbor = p.neighbor(dir); if let Some(n) = input.map.get(neighbor) { if *n == input.map.get(*p).unwrap() + 1 { if seen.insert(neighbor) { result.push(neighbor); } } } } result }; let mut score = 0; let mut bfs = BrFS::new(vec![start]); while let Some(next) = bfs.next(&mut successors) { if input.map.get(next) == Some(&9) { score += 1; } } score } pub fn trail_heads(input: &PuzzleInput) -> Vec<Coordinate> { input .map .iter() .filter(|(_, &c)| c == 0) .map(|(p, _)| p) .collect_vec() }Part 2 (Rust)
pub fn part2(input: &PuzzleInput) -> String { let heads = trail_heads(input); let mut scores = Vec::new(); for head in heads { let score = trail_destination_score(input, head); scores.push(score); } scores.iter().sum::<usize>().to_string() } fn destinations(input: &PuzzleInput) -> Vec<Coordinate> { input .map .iter() .filter(|(_, &c)| c == 9) .map(|(p, _)| p) .collect_vec() } fn trail_destination_score(input: &PuzzleInput, head: Coordinate) -> usize { let destinations = destinations(input); let mut successors = move |p: &(Coordinate, Vec<Coordinate>)| { let (current, trail) = p; let mut result = Vec::new(); if *current == head { return result; } for dir in Direction::cardinal() { let neighbor = current.neighbor(dir); if let Some(n) = input.map.get(neighbor) { if *n + 1 == *input.map.get(*current).unwrap() { let mut trail = trail.clone(); trail.push(neighbor); //if seen.insert((neighbor, trail.clone())) { result.push((neighbor, trail)); //} } } } result }; let mut score = 0; let mut bfs = BrFS::new(destinations.iter().map(|d| (*d, vec![*d])).collect_vec()); while let Some((next, _d)) = bfs.next(&mut successors) { if next == head { score += 1; } } score }Helpers
pub struct BrFS<N> where N: Clone, { queue: VecDeque<N>, } impl<N> BrFS<N> where N: Clone, { pub fn new<IN>(start: IN) -> Self where IN: IntoIterator<Item = N>, { let mut queue = VecDeque::new(); for s in start.into_iter() { queue.push_back(s.clone()); } Self { queue } } pub fn next<S, IN>(&mut self, mut successors: S) -> Option<N> where S: FnMut(&N) -> IN, IN: IntoIterator<Item = N>, { if let Some(cur) = self.queue.pop_front() { for next in successors(&cur) { self.queue.push_back(next.clone()); } return Some(cur); } None } }Benchmark
day_10 fastest │ slowest │ median │ mean │ samples │ iters ├─ part1 259.1 µs │ 287.9 µs │ 261.1 µs │ 264 µs │ 100 │ 100 ╰─ part2 148.3 ms │ 172.6 ms │ 151 ms │ 155.6 ms │ 100 │ 100 -
Comment on Day 9: Disk Fragmenter in ~comp.advent_of_code
DataWraith (edited )LinkFor how simple the task seemed, this took an exorbitant amount of time to get right. Process At first I didn't want to materialize the disk in memory, because I was fairly sure that part 2 would...For how simple the task seemed, this took an exorbitant amount of time to get right.
Process
At first I didn't want to materialize the disk in memory, because I was fairly sure that part 2 would be something like "now don't use single digits but runs of six digits to denote the ranges". That took up a long time unnecessarily. Part 1 was easy after deciding to materialize the disk, but part 2 took a very long time until all edge cases were handled... I think this was the worst puzzle so far for me, from a time-taken to enjoyment ratio.
Part 1 (Rust)
pub fn make_disk(input: &PuzzleInput) -> Vec<u64> { let mut disk: Vec<u64> = vec![]; for (i, &d) in input.disk.iter().enumerate() { if i % 2 == 0 { for _ in 0..d { disk.push(i as u64 / 2); } } else { for _ in 0..d { disk.push(u64::MAX); } } } disk } pub fn part1(input: &PuzzleInput) -> String { let disk = make_disk(input); let mut fwd = 0; let mut bwd = disk.len() - 1; let mut defrag = Vec::with_capacity(disk.len()); while fwd <= bwd { if disk[fwd] == u64::MAX { defrag.push(disk[bwd]); fwd += 1; loop { bwd -= 1; if disk[bwd] != u64::MAX { break; } } } else { defrag.push(disk[fwd]); fwd += 1; } } checksum(&defrag).to_string() } fn checksum(defrag: &[u64]) -> u64 { defrag.iter().enumerate().map(|(i, &d)| d * i as u64).sum() }Part 2 (Rust)
The algorithm basically works by scanning forward from the start for blanks, and then backwards from the end for something to fill them with. Then I just move the file into position. If the file is smaller than the blank space, I add the remaining blanks back to the front of the scan -- this works because the original array is contiguous and alternates between files and blanks -- or maybe it doesn't and the input is just benign, I'm too tired to fully analyze it now.
pub fn part2(input: &PuzzleInput) -> String { let disk = make_disk(input); let mut contiguous = vec![]; let mut current_run = vec![]; for i in 0..(disk.len() - 1) { current_run.push(disk[i]); if disk[i] != disk[i + 1] { contiguous.push(current_run); current_run = vec![]; } } current_run.push(disk[disk.len() - 1]); if !current_run.is_empty() { contiguous.push(current_run); } let mut result = vec![]; loop { if contiguous.is_empty() { break; } let xs = contiguous.remove(0); if xs.is_empty() { continue; } if xs[0] != u64::MAX { result.push(xs); continue; } let mut found = false; for idx in (0..contiguous.len()).rev() { let ks = &contiguous[idx]; if ks.is_empty() { continue; } if ks[0] == u64::MAX { continue; } if ks.len() == xs.len() { result.push(ks.clone()); contiguous[idx] = vec![u64::MAX; ks.len()]; found = true; break; } if ks.len() < xs.len() { let diff = xs.len() - ks.len(); result.push(ks.clone()); contiguous[idx] = vec![u64::MAX; ks.len()]; contiguous.insert(0, vec![u64::MAX; diff]); found = true; break; } } if !found { result.push(xs); } } result .iter() .flatten() .enumerate() .fold(0, |acc, (i, x)| { if *x != u64::MAX { acc + i * *x as usize } else { acc } }) .to_string() }Benchmark
day_09 fastest │ slowest │ median │ mean │ samples │ iters ├─ part1 569.5 µs │ 771.4 µs │ 625.5 µs │ 619.7 µs │ 100 │ 100 ╰─ part2 138.9 ms │ 156.9 ms │ 146.9 ms │ 147.4 ms │ 100 │ 100 -
Comment on Day 7: Bridge Repair in ~comp.advent_of_code
DataWraith (edited )Link ParentI always love reading these write-ups when they show up in my RSS reader. :) You misspelt "unacceptable" as "unnacaptible" in this one (unless that was deliberate to be whimsical); and while I'm...I always love reading these write-ups when they show up in my RSS reader. :)
You misspelt "unacceptable" as "unnacaptible" in this one (unless that was deliberate to be whimsical); and while I'm at it, I've always been bothered that Day 19 of 2022 (which is my favorite AoC puzzle) has the algorithm name wrong. What you've described is called Beam search -- branch and bound generally does not limit the number of solutions considered unless a to-be-discarded solution can be proven inferior to the current best.
-
Comment on Day 8: Resonant Collinearity in ~comp.advent_of_code
DataWraith LinkPart 1 (Rust) pub fn part1(input: &PuzzleInput) -> String { let antennas = frequencies(&input.grid); let mut total = HashSet::new(); for frequency in antennas { let coordinates =...Part 1 (Rust)
pub fn part1(input: &PuzzleInput) -> String { let antennas = frequencies(&input.grid); let mut total = HashSet::new(); for frequency in antennas { let coordinates = antenna_coordinates(&input.grid, frequency); let antinodes = antinodes( input.grid.width() as i32, input.grid.height() as i32, &coordinates, ); total.extend(antinodes); } total.len().to_string() } pub fn frequencies(grid: &Grid2D<char>) -> HashSet<char> { grid.iter() // Don't forget to filter out the '#' signs in the test input, // otherwise those count as antennas too... .filter(|(_, c)| **c != '.' && **c != '#') .map(|(_, c)| c.clone()) .collect() } pub fn antenna_coordinates(grid: &Grid2D<char>, antenna: char) -> HashSet<Coordinate> { grid.iter() .filter(|(_, c)| **c == antenna) .map(|(coord, _)| coord.clone()) .collect() } pub fn antinode(a: &Coordinate, b: &Coordinate) -> [Coordinate; 2] { let dx = a.x - b.x; let dy = a.y - b.y; [ Coordinate::new(a.x + dx as i32, a.y + dy as i32), Coordinate::new(b.x - dx as i32, b.y - dy as i32), ] } pub fn antinodes(w: i32, h: i32, coordinates: &HashSet<Coordinate>) -> HashSet<Coordinate> { coordinates .iter() .cloned() .combinations(2) .flat_map(|x| antinode(&x[0], &x[1])) .filter(|c| c.x >= 0 && c.x < w && c.y >= 0 && c.y < h) .collect() }Part 2 (Rust)
The only change was to the antinode function.
pub fn antinode(a: &Coordinate, b: &Coordinate, width: i32, height: i32) -> Vec<Coordinate> { let dx = a.x - b.x; let dy = a.y - b.y; let mut result = Vec::new(); for i in 0.. { let c = Coordinate::new(a.x + dx * i as i32, a.y + dy * i as i32); if c.x >= 0 && c.x < width && c.y >= 0 && c.y < height { result.push(c); } else { break; } } for i in 0.. { let c = Coordinate::new(b.x - dx * i as i32, b.y - dy * i as i32); if c.x >= 0 && c.x < width && c.y >= 0 && c.y < height { result.push(c); } else { break; } } result } -
Comment on Day 7: Bridge Repair in ~comp.advent_of_code
DataWraith LinkThoughts This one took about an hour to solve, twice as long as yesterday's, but bone-headed mistakes are gonna happen. I just have to accept that. After the Hot Springs puzzle last year, I kind...Thoughts
This one took about an hour to solve, twice as long as yesterday's, but bone-headed mistakes are gonna happen. I just have to accept that.
After the Hot Springs puzzle last year, I kind of assumed you had to memoize the recursive equation solve in part 2, but adding memoization added so much overhead that the runtime was 10x what it is without it. Now part 2 runs in about 0.8 seconds.
Part 1 (Rust)
pub fn part1(input: &PuzzleInput) -> String { input .equations .iter() .map(|(target, numbers)| { let mut n: Vec<i64> = numbers.clone(); let first = n.remove(0); let soln = solve_equation(first, *target, n); if soln { *target } else { 0 } }) .sum::<i64>() .to_string() } fn solve_equation(current: i64, target: i64, remainder: Vec<i64>) -> bool { if current == target && remainder.is_empty() { return true; } if remainder.is_empty() { return false; } let next = remainder.first().unwrap(); let next_remainder = remainder[1..].to_vec(); solve_equation(current + next, target, next_remainder.clone()) || solve_equation(current * next, target, next_remainder) }Part 2 (Rust)
fn solve_equation(current: i64, target: i64, remainder: Vec<i64>) -> bool { if current == target && remainder.is_empty() { return true; } if remainder.is_empty() { return false; } let mut next_remainder = remainder.clone(); let next = next_remainder.pop().unwrap(); if solve_equation(current + next, target, next_remainder.clone()) || solve_equation(current * next, target, next_remainder.clone()) { return true; } let left = current.to_string(); let right = next.to_string(); let concated = left + &right; let concated_num = concated.parse::<i64>().unwrap(); solve_equation(concated_num, target, next_remainder) } -
Comment on Day 6: Guard Gallivant in ~comp.advent_of_code
DataWraith (edited )LinkThis one was simple and quick. Why couldn't the previous ones be so nice? Brute-forcing part 2 runs a bit slow, but eh. Edit: Did a bit of optimization on part 2, now runs in 0.35 seconds. The...This one was simple and quick. Why couldn't the previous ones be so nice?
Brute-forcing part 2 runs a bit slow, but eh.
Edit: Did a bit of optimization on part 2, now runs in 0.35 seconds. The speed-up mostly comes from not cloning a HashSet every time the guard takes a step.
Part 1 (Rust)
pub fn part1(input: &PuzzleInput) -> String { let coord = guard_starting_position(&input.grid); let mut visited = Vec::new(); let mut state = GuardState { coordinate: coord, direction: Direction::Up, }; visited.push((state.coordinate, state.direction)); while let Some(next_state) = state.next_state(&input.grid) { visited.push((next_state.coordinate, next_state.direction)); state = next_state; } let mut v = visited.iter().map(|(c, _)| c).collect::<Vec<_>>(); v.sort(); v.dedup(); v.len().to_string() } #[derive(Debug)] pub struct GuardState { pub coordinate: Coordinate, pub direction: Direction, } impl GuardState { pub fn next_state(&self, grid: &Grid2D<char>) -> Option<GuardState> { let next_coord = self.coordinate + self.direction.into(); if let Some(c) = grid.get(next_coord) { if *c == '#' { let new_direction = self.direction.turn_right_90(); return Some(GuardState { coordinate: self.coordinate, direction: new_direction, }); } return Some(GuardState { coordinate: next_coord, direction: self.direction, }); } None } } pub fn guard_starting_position(grid: &Grid2D<char>) -> Coordinate { grid.iter() .find(|(c, x)| **x == '^') .map(|(c, x)| c) .unwrap() }Part 2 (Rust)
pub fn part2(input: &PuzzleInput) -> String { let coord = guard_starting_position(&input.grid); let mut state = GuardState { coordinate: coord, direction: Direction::Up, }; let mut visited = Vec::new(); visited.push((state.coordinate, state.direction)); while let Some(next_state) = state.next_state(&input.grid) { visited.push((next_state.coordinate, next_state.direction)); state = next_state; } let mut loops_found = HashSet::new(); let mut obstacles = HashSet::new(); for (pos, dir) in visited.iter() { let obstacle = *pos + (*dir).into(); if obstacle == coord { continue; } if input.grid.get(obstacle).is_none() { continue; } if input.grid.get(obstacle).unwrap() == &'#' { continue; } obstacles.insert(obstacle); } for obstacle in obstacles.iter() { let mut g2 = input.grid.clone(); g2.set(*obstacle, '#'); let mut state = GuardState { coordinate: coord, direction: Direction::Up, }; let mut visited = HashSet::new(); while let Some(next_state) = state.next_state(&g2) { state = next_state; if !visited.insert((state.coordinate, state.direction)) { break; } } if g2.get(state.coordinate + state.direction.into()).is_some() { loops_found.insert(obstacle); } } loops_found.len().to_string() } -
Comment on Day 3: Mull It Over in ~comp.advent_of_code
DataWraith Link ParentI actually went back to regular expressions after seeing @tjf's solution; now both parts are like 5 lines of code each, which I think is more elegant than having two screen-fulls of manual parsing... -
Comment on Day 4: Ceres Search in ~comp.advent_of_code
DataWraith (edited )LinkAdvent of Code has a way of making you feel stupid, and, well, today I feel really, really stupid. For how simple the puzzle was, it took an embarrassingly long time to solve (almost 90 minutes)....Advent of Code has a way of making you feel stupid, and, well, today I feel really, really stupid. For how simple the puzzle was, it took an embarrassingly long time to solve (almost 90 minutes).
Musings
I have a
Grid2Dhelper class and tried to be fancy with it -- instead of just looping through the grid in eight different directions, I tried to get away with rotating and mirroring the grid, because I have helper methods for that sort of thing. That would have been faster if it had worked, but it didn't (because I had an off-by-one error in the actual counting), so I wasted 15 minutes on that before using the naive approach.Then I got stuck for a very long time on Part 2, because apparently bending the
MASaround the corner isn't allowed, i.e.S M A M Sis invalid, and the puzzle description did not make that clear. Unfortunately it didn't appear in the test input either (which might have been deliberate), so I was left scratching my head for a good long while.
Part 1 (Rust)
pub fn part1(input: &PuzzleInput) -> String { let mut count = 0; let xmas = ['X', 'M', 'A', 'S']; for col in 0..input.grid.width { for row in 0..input.grid.height { for dx in [-1i32, 0, 1] { 'outer: for dy in [-1i32, 0, 1] { if dx == 0 && dy == 0 { continue; } for (i, &x) in xmas.iter().enumerate() { let c = input .grid .get((col + dx * i as i32, row + dy * i as i32).into()) .unwrap_or(&'.'); if c != &x { continue 'outer; } } count += 1; } } } } count.to_string() }Part 2 (Rust)
pub fn part2(input: &PuzzleInput) -> String { let mut count = 0; for col in 1..(input.grid.width - 1) { for row in 1..(input.grid.height - 1) { let center = *input.grid.get((col, row).into()).unwrap(); let tl = *input.grid.get((col - 1, row - 1).into()).unwrap(); let tr = *input.grid.get((col + 1, row - 1).into()).unwrap(); let bl = *input.grid.get((col - 1, row + 1).into()).unwrap(); let br = *input.grid.get((col + 1, row + 1).into()).unwrap(); if center == 'A' { let x = (tl, tr, bl, br); if x == ('M', 'S', 'M', 'S') || x == ('S', 'M', 'S', 'M') || x == ('M', 'M', 'S', 'S') || x == ('S', 'S', 'M', 'M') { count += 1; } } } } count.to_string() } -
Comment on Day 2: Red-Nosed Reports in ~comp.advent_of_code
DataWraith Link ParentYou could be regretting your choices come day 18 or so, though. ;-)You could be regretting your choices come day 18 or so, though. ;-)
-
Comment on Day 3: Mull It Over in ~comp.advent_of_code
DataWraith LinkIt's always fun to see how the inputs have traps that seem tailored for different ways of approaching the puzzle -- I implemented this twice, because I was curious which approach was nicer, and...It's always fun to see how the inputs have traps that seem tailored for different ways of approaching the puzzle -- I implemented this twice, because I was curious which approach was nicer, and both times had different problems crop up that weren't a problem for the other approach. The only trap that was missing was a
mulof the formmul(1234,5678).Rust
I first did this using RegEx, but that solution was kind of boring (even though it took me longer than it should have), so here's the hand-rolled evaluator for part 2 I came up with just now:
pub fn parse2(input: &str) -> PuzzleInput { let mut input = input; let mut enabled = true; let mut muls = Vec::new(); while !input.is_empty() { if input.starts_with("do()") { input = &input[4..]; enabled = true; continue; } if input.starts_with("don't()") { input = &input[7..]; enabled = false; continue; } if !enabled || !input.starts_with("mul(") { input = &input[1..]; continue; } // Skip "mul(" input = &input[4..]; let Some((a, b)) = input.split_once(")") else { // Unclosed parenthesis, skip the rest of the input break; }; if a.len() > 7 { // Too many digits (also generally caused by unclosed or mismatched parentheses) input = &input[1..]; continue; } let Some((x, y)) = a.split_once(",") else { // No comma -- skip past the parenthesis input = b; continue; }; let x = x.parse::<usize>().unwrap(); let y = y.parse::<usize>().unwrap(); muls.push(x * y); input = b; } PuzzleInput { muls } }Doing it this way actually took less time to implement than installing a regex crate and figuring out how to properly escape everything, though of course, doing it for the second time avoids the stupid mistakes you make when you rush.
Holy off-by-one errors, Batman!
Part 1 (Rust)
Part 2 (Rust)
This runs for almost 3 seconds, I'll need to improve that later.