Day 4: Printing Department

My old utility code already had methods for (1) parsing the input into an array of chars; (2) give you an IEnumerable of all coordinates in the grid; (3) find the coordinates of the eight neighbors of a coordinate; and (4) replace the character at a coordinate. All I had to write is checking if the neighbor count of `@` is less than 4., and write a loop to replace them until we can't anymore. Nothing really challenging here, and the code runs mighty fast without the need for any micro-optimizations.

C# code

defmodule AdventOfCode.Solution.Year2025.Day04 do
  alias AdventOfCode.Grid, as: G

  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input), do: G.from_input(input)

  def part1(grid), do: map_size(forklift_cells(grid))

  def part2(grid) do
    grid
    |> Stream.unfold(&remove_forkliftable/1)
    |> Enum.sum()
  end

  defp forklift_cells(grid) do
    for {coords, ?@} <- grid, forkliftable?(coords, grid), into: %{}, do: {coords, ?.}
  end

  defp forkliftable?(coords, grid) do
    grid
    |> G.adjacent_values(coords)
    |> Enum.count(&(&1 == ?@))
    |> Kernel.<(4)
  end

  defp remove_forkliftable(grid) do
    removals = forklift_cells(grid)

    case map_size(removals) do
      # End the stream.
      0 -> nil
      n -> {n, G.replace(grid, removals)}
    end
  end
end

Name             ips        average  deviation         median         99th %
Parse         526.68        1.90 ms     ±1.87%        1.90 ms        1.97 ms
Part 1        159.39        6.27 ms     ±3.94%        6.27 ms        6.95 ms
Part 2          7.69      130.08 ms     ±0.99%      129.91 ms      134.38 ms

I exported an image of the grid after each forklift pass and assembled a looping animation.

type InputData = boolean[][];

const makeEmptyGridLike = (grid: InputData): InputData => grid.map(row => row.map(() => false));

function formatInput(input: string): InputData {
  const inputArr = input.trim().split('\n');
  return inputArr.map(line => line.split('').map(positionString => positionString === '@'));
}

export function run(input: string): string[] {
  const data = formatInput(input);

  const neighborOffsets = [
    [-1, -1],
    [-1, 0],
    [-1, 1],
    [0, -1],
    [0, 1],
    [1, -1],
    [1, 0],
    [1, 1],
  ];

  const getCellValue = (grid: InputData, row: number, col: number): number => {
    if (row >= 0 && row < grid.length && col >= 0 && col < grid[row].length) {
      return Number(grid[row][col]);
    }
    return 0;
  };

  const countRemovedRollsOnce = (
    sourceGrid: InputData,
    destinationGrid: InputData = makeEmptyGridLike(sourceGrid)
  ): number => {
    let total = 0;

    for (let row = 0; row < sourceGrid.length; row++) {
      const sourceRow = sourceGrid[row];
      const destRow = destinationGrid[row];
      for (let col = 0; col < sourceRow.length; col++) {
        const cell = sourceRow[col];
        if (!cell) {
          destRow[col] = false;
          continue;
        }
        let neighborCount = 0;
        for (const [rowOffset, colOffset] of neighborOffsets) {
          neighborCount += getCellValue(sourceGrid, row + rowOffset, col + colOffset);
        }
        destRow[col] = neighborCount >= 4;
        !destRow[col] && total++;
      }
    }

    return total;
  };

  const countRemovedRollsUntilStable = (grid: InputData): number => {
    let currentGrid = grid.map(row => [...row]);
    let nextGrid = makeEmptyGridLike(grid);
    let totalRemoved = 0;
    let removedThisIteration: number;

    do {
      removedThisIteration = countRemovedRollsOnce(currentGrid, nextGrid);
      if (removedThisIteration > 0) {
        totalRemoved += removedThisIteration;
        [currentGrid, nextGrid] = [nextGrid, currentGrid];
      }
    } while (removedThisIteration > 0);

    return totalRemoved;
  };

  return [`${countRemovedRollsOnce(data)}`, `${countRemovedRollsUntilStable(data)}`];
}

:- ['src/util.pl'].
:- table contains_paper/3.

contains_paper(Grid, 0, Position):-
    Position = (RowIndex, ColIndex),
    nth0(RowIndex, Grid, Row),
    string_chars(Row, RowChars),
    nth0(ColIndex, RowChars, Char),
    Char = '@'.

contains_paper(Grid, Step, Position):-
    succ(Step1, Step),
    contains_paper(Grid, Step1, Position),
    not(forkliftable(Grid, Step1, Position)).

forkliftable(Grid, Step, Position):-
    contains_paper(Grid, Step, Position),
    findall(Pos, neighbor(Position, Pos), Neighbors),
    count(contains_paper(Grid, Step), Neighbors, NeighborPaper),
    NeighborPaper < 4.

neighbor(Position1, Position2):-
    Position1 = (Row1, Col1),
    between(-1, 1, DR),
    between(-1, 1, DC),
    (DR, DC) \= (0, 0),
    Row2 is Row1 + DR,
    Col2 is Col1 + DC,
    Position2 = (Row2, Col2).

paper_removed(Grid, Step, PaperRemoved):-
    findall(Pos, contains_paper(Grid, 0, Pos), OriginalPaper),
    findall(Pos, contains_paper(Grid, Step, Pos), FinalPaper),
    length(OriginalPaper, OriginalCount),
    length(FinalPaper, FinalCount),
    PaperRemoved is OriginalCount - FinalCount.

main:-
    Filename = 'inputs/day04.txt',
    read_file_to_strings(Filename, Grid),
    paper_removed(Grid, 1, Result1),
    write("Part 1: "), write(Result1), nl,
    paper_removed(Grid, 100, Result2),
    write("Part 2: "), write(Result2), nl,
    halt.

:- initialization(main).

The mistake was that I was counting all grid cells that had less than 4 paper roll neighbors, when I actually needed to count only the grid cells that contained a paper roll and had less than 4 neighbors. Here's my solution for part 2, in Python today:

def get_pos(s, x, y, dim):
    if not x in range(dim) or not y in range(dim): return False
    return s[x][y] == "@"

def count_adjacent(s, x, y, dim):
    count = 0
    MATRIX = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
    for (x2,y2) in MATRIX:
        if get_pos(s, x+x2, y+y2, dim):
            count += 1
    return count

def count(s):
    dim = len(s)
    count = 0
    for x in range(0,dim):
        for y in range(0,dim):
            if s[x][y] == "@" and count_adjacent(s, x, y, dim)<4:
                count += 1
                s[x][y] = "."
    return count, s

def count_recursive(s):
    s = [list(x) for x in s.split("\n")]
    total = 0
    while True:
        num, s = count(s)
        if num == 0: break
        total += num
    return total

print(count_recursive(open("./input.txt").read()))

use std::io;
use std::ops::Range;
use std::vec::Vec;

fn neighbor_ints(x: usize, max: usize) -> Range<usize> {
  let start = if x > 0 { x - 1 } else { 0 };
  let end = (x + 2).min(max);
  return start..end;
}

struct Map {
  data: Vec<Vec<char>>,
  height: usize,
  width: usize,
}

fn make_map(data: Vec<Vec<char>>) -> Map {
  let height = data.len();
  assert!(height > 0);
  let width = data[0].len();
  for x in 1..height {
    assert_eq!(data[x].len(), width, "line {}", x)
  }
  Map {
    data: data,
    height,
    width,
  }
}

impl Map {
  fn foreach_pos<F: FnMut(usize, usize)>(&self, mut f: F) {
    for x in 0..self.height {
      for y in 0..self.width {
        f(x, y);
      }
    }
  }

  fn foreach_neighbor<F: FnMut(usize, usize)>(&self, x: usize, y: usize, mut f: F) {
    for nx in neighbor_ints(x, self.height) {
      for ny in neighbor_ints(y, self.width) {
        if nx != x || ny != y {
          f(nx, ny);
        }
      }
    }
  }

  fn num_neighbor_rolls(&self, x: usize, y: usize) -> u8 {
    let mut num_rolls = 0;
    self.foreach_neighbor(x, y, |nx: usize, ny: usize| {
      if self.data[nx][ny] == '@' {
        num_rolls += 1;
      }
    });
    num_rolls
  }
}

fn part1(map: &Map) -> u64 {
  let mut ret = 0;
  map.foreach_pos(|x: usize, y: usize| {
    if map.data[x][y] == '@' && map.num_neighbor_rolls(x, y) < 4 {
      ret += 1;
    }
  });
  ret
}

fn part2(map: &Map) -> u64 {
  let mut ret = 0;
  let mut to_remove = Vec::<(usize, usize)>::new();
  let mut num_neighbor_rolls = vec![vec![0 as u8; map.width]; map.height];
  map.foreach_pos(|x: usize, y: usize| {
    if map.data[x][y] == '.' {
      return;
    }
    let num_rolls = map.num_neighbor_rolls(x, y);
    num_neighbor_rolls[x][y] = num_rolls;
    if num_rolls < 4 {
      to_remove.push((x, y));
    }
  });
  while !to_remove.is_empty() {
    let (x, y) = to_remove.pop().unwrap();
    ret += 1;
    map.foreach_neighbor(x, y, |nx: usize, ny: usize| {
      let nr = &mut num_neighbor_rolls[nx][ny];
      *nr -= 1;
      if *nr == 3 {
        to_remove.push((nx, ny));
      }
    });
  }
  ret
}

fn main() {
  let map = make_map(
    io::stdin()
      .lines()
      .map(|l| l.unwrap().chars().collect::<Vec<char>>())
      .collect(),
  );
  println!("Part 1: {}", part1(&map));
  println!("Part 2: {}", part2(&map));
}

from common import load_input
input = load_input()

# def grid_at(grid, x, y)

relative = [
    (-1, -1), (0, -1), (1, -1),
    (-1, 0),           (1, 0),
    (-1, 1),  (0, 1),  (1, 1),
]

grid = list(map(lambda x: list(x), input.splitlines()))
w, h = len(grid[0]), len(grid)

total = 0
for y in range(h):
    for x in range(w):
        if grid_at(grid, x, y) != '@':
            continue
        res = list(map(lambda d: grid_at(grid, x + d[0], y + d[1]), relative))
        if res.count('@') < 4:
            total += 1

print(total)

from common import load_input
input = load_input()

# def grid_at(grid, x, y)

relative = [
    (-1, -1), (0, -1), (1, -1),
    (-1, 0),           (1, 0),
    (-1, 1),  (0, 1),  (1, 1),
]

grid = list(map(lambda x: list(x), input.splitlines()))
w, h = len(grid[0]), len(grid)

total = 0

while True:
    to_remove = []
    local_total = 0
    for y in range(h):
        for x in range(w):
            if grid_at(grid, x, y) != '@':
                continue
            res = list(map(lambda d: grid_at(grid, x + d[0], y + d[1]), relative))
            if res.count('@') < 4:
                to_remove.append((x, y))
                local_total += 1
    if local_total == 0:
        break
    total += local_total
    for (x, y) in to_remove:
        grid[y][x] = '.'

print(total)

import (Set, integer_pair_hash) "modules/set"

var lines = File.read_to_string("inputs/day_04.txt").split("\n")

var width = lines[0].size()
var height = lines.size()

var adjacent = List.fill(height, (|_| List.repeat(width, -1)))

for y, line in lines: {
    for x, char in line: {
        if char != '@': {
            continue
        }

        var count = 0

        for delta_y in -1...1: {
            var adjacent_y = y + delta_y
            if adjacent_y < 0 || adjacent_y >= height: {
                continue
            }

            for delta_x in -1...1: {
                if delta_y == 0 && delta_x == 0: {
                    continue
                }

                var adjacent_x = x + delta_x
                if adjacent_x < 0 || adjacent_x >= width: {
                    continue
                }

                if lines[adjacent_y][adjacent_x] == '@': {
                    count += 1
                }
            }
        }

        adjacent[y][x] = count
    }
}

var to_remove: Set[Tuple[Integer, Integer]] = Set(integer_pair_hash)
for y, row in adjacent: {
    for x, count in row: {
        if count >= 0 && count < 4: {
            to_remove.add(<[x, y]>)
        }
    }
}

print("Part 1: {}".format(to_remove.size()))

var total_rolls_removed = 0

do: {
    var to_remove_new: Set[Tuple[Integer, Integer]] = Set(integer_pair_hash)

    to_remove.each(|position| adjacent[position[1]][position[0]] = -1)
    to_remove.each(|position|
        var x = position[0]
        var y = position[1]

        for delta_y in -1...1: {
            var adjacent_y = y + delta_y
            if adjacent_y < 0 || adjacent_y >= height: {
                continue
            }

            for delta_x in -1...1: {
                if delta_y == 0 && delta_x == 0: {
                    continue
                }

                var adjacent_x = x + delta_x
                if adjacent_x < 0 || adjacent_x >= width: {
                    continue
                }

                var row = adjacent[adjacent_y]

                if row[adjacent_x] < 0: {
                    continue
                }

                row[adjacent_x] -= 1

                if row[adjacent_x] < 4: {
                    to_remove_new.add(<[adjacent_x, adjacent_y]>)
                }
            }
        }
    )

    total_rolls_removed += to_remove.size()
    to_remove = to_remove_new
} while to_remove.size()

print("Part 2: {}".format(total_rolls_removed))

class Set[A](private var @hash_function: Function(A => Integer)) {
    private var @hashes: Hash[Integer, Unit] = []
    private var @values: List[A] = []

    public define size: Integer {
        return @hashes.size()
    }

    public define add(value: A) {
        var hash = @hash_function(value)
        if !@hashes.has_key(hash): {
            @hashes[hash] = unit
            @values.push(value)
        }
    }

    public define remove(value: A) {
        @hashes.delete(@hash_function(value))
    }

    public define contains(value: A): Boolean {
        return @hashes.has_key(@hash_function(value))
    }

    public define each(fn: Function(A)) {
        @values.each(fn)
    }
}

define integer_pair_hash(pair: Tuple[Integer, Integer]): Integer {
    var first = pair[0]
    var second = pair[1]

    return (
        first >= second
        ? first * first + first + second
        : first + second * second
    )
}

Position: TypeAlias = tuple[int, int]


def solve(input: str) -> int:
    roll_positions = set(positions_with_rolls(input))
    adjacent_roll_count = Counter(adjacent_positions(roll_positions))
    return len([
        position
        for position in roll_positions
        if adjacent_roll_count[position] < 4
    ])


def positions_with_rolls(input: str) -> Iterator[Position]:
    for row, rolls in enumerate(input.split()):
        for column, roll in enumerate(rolls):
            if roll == "@":
                yield row, column


def adjacent_positions(positions: Iterable[Position]) -> Iterator[Position]:
    for row, column in positions:
        yield from (
            (row - 1, column - 1),
            (row - 1, column),
            (row - 1, column + 1),
            (row, column - 1),
            # (row, column),
            (row, column + 1),
            (row + 1, column - 1),
            (row + 1, column),
            (row + 1, column + 1),
        )

Position: TypeAlias = tuple[int, int]


def solve(input: str) -> int:
    roll_positions = set(positions_with_rolls(input))
    adjacent_roll_count = Counter(adjacent_positions(roll_positions))
    removed_roll_count = 0

    while positions_to_remove := set(
        position
        for position in roll_positions
        if adjacent_roll_count[position] < 4
    ):
        roll_positions.difference_update(positions_to_remove)
        adjacent_roll_count.subtract(adjacent_positions(positions_to_remove))
        removed_roll_count += len(positions_to_remove)

    return removed_roll_count


def positions_with_rolls(input: str) -> Iterator[Position]:
    for row, rolls in enumerate(input.split()):
        for column, roll in enumerate(rolls):
            if roll == "@":
                yield row, column


def adjacent_positions(positions: Iterable[Position]) -> Iterator[Position]:
    for row, column in positions:
        yield from (
            (row - 1, column - 1),
            (row - 1, column),
            (row - 1, column + 1),
            (row, column - 1),
            # (row, column),
            (row, column + 1),
            (row + 1, column - 1),
            (row + 1, column),
            (row + 1, column + 1),
        )

use std::{
    env,
    fs::File,
    io::{BufReader, Read},
    time::Instant,
};

const SQUARE_SIZE: usize = 139;
const BIGGER_SQUARE: usize = SQUARE_SIZE + 2;

fn main() {
    let now = Instant::now();
    let mut sum: i32 = 0;
    let args: Vec<String> = env::args().collect();

    let reader = BufReader::new(File::open(&args[1]).expect("Failure to open file"));
    let mut grid = [[0u8; BIGGER_SQUARE]; BIGGER_SQUARE];
    grid[1..BIGGER_SQUARE]
        .iter_mut()
        .flat_map(|x| x[1..BIGGER_SQUARE].iter_mut())
        .zip(reader.bytes())
        .for_each(|(dst, src)| {
            *dst = src.unwrap();
        });

    for x in 1..BIGGER_SQUARE - 1 {
        for y in 1..BIGGER_SQUARE - 1 {
            sum += check_neighbors(&mut grid, x, y)
        }
    }
    println!("Sum {sum}");
    let elapsed = now.elapsed();
    println!("Elapsed: {:.2?}", elapsed);
}

fn check_neighbors(grid: &mut [[u8; BIGGER_SQUARE]; BIGGER_SQUARE], x: usize, y: usize) -> i32 {
    let mut total = 0;
    let mut ret_val = 0;
    let mut cache = vec![];
    if grid[x][y] == b'@' {
        for i in 0..=2 {
            for j in 0..=2 {
                if (i != 1 || j != 1) && grid[x + i - 1][y + j - 1] == b'@' {
                    cache.push((x + i - 1, y + j - 1));
                    total += 1;
                }
            }
        }
        if total <= 3 {
            grid[x][y] = b'x';
            for cache_coord in cache {
                ret_val += check_neighbors(grid, cache_coord.0, cache_coord.1);
            }
            ret_val += 1;
        }
    }
    return ret_val;
}