advent-of-code-2025/day04.c

#include <limits.h>
#include <stdlib.h>
#define RT_CORE_IMPLEMENTATION
#include "rtcore.h"

#include "aoc.h"

enum
{
  F_EMPTY = '.',
  F_PAPER = '@',
};

typedef struct
{
  char *fields;
  int *weights;
  int rows;
  int cols;
} grid;

typedef struct
{
  int x;
  int y;
} cell_coord;

force_inline char GetField(const grid *g, int x, int y)
{
  if (x < 0 || x >= g->cols || y < 0 || y >= g->rows)
    return F_EMPTY; 
  return g->fields[y * g->cols + x];
}

force_inline int *GetWeight(const grid *g, int x, int y)
{
  if (x < 0 || x >= g->cols || y < 0 || y >= g->rows)
    return 0; 
  return &g->weights[y * g->cols + x];
}

internal void CountInputRes(s8 input, int *x, int *y)
{
  split_result split = S8Split(input, '\n');
  int rows = 0;
  int cols = 0;
  while (split.second.data)
  {
    if (cols == 0)
      cols = (int)split.first.length;
    ++rows;
    split = S8Split(split.second, '\n');
  }
  *x = cols;
  *y = rows;
}

internal grid FillGrid(s8 input, arena *a)
{
  grid grid = {0};
  CountInputRes(input, &grid.cols, &grid.rows);
  grid.fields = alloc(a, char, grid.cols * grid.rows);
  grid.weights = alloc(a, int, grid.cols * grid.rows);
  split_result split = S8Split(input, '\n');
  int y = 0;
  while (split.second.data)
  {
    memcpy(&grid.fields[y * grid.cols], split.first.data, grid.cols);
    ++y;
    split = S8Split(split.second, '\n');
  }
  for (int y = 0; y < grid.rows; ++y)
  {
    for (int x = 0; x < grid.cols; ++x)
    {
      if (GetField(&grid, x, y) == F_PAPER)
      {
        int p = (GetField(&grid, x - 1, y - 1) == F_PAPER) +
                (GetField(&grid, x, y - 1) == F_PAPER) +
                (GetField(&grid, x + 1, y - 1) == F_PAPER) +
                (GetField(&grid, x - 1, y) == F_PAPER) +
                (GetField(&grid, x + 1, y) == F_PAPER) +
                (GetField(&grid, x - 1, y + 1) == F_PAPER) +
                (GetField(&grid, x, y + 1) == F_PAPER) +
                (GetField(&grid, x + 1, y + 1) == F_PAPER);
        *GetWeight(&grid, x, y) = p;
      }
      else
      {
        *GetWeight(&grid, x, y) = INT_MAX;
      }
    }
  }
  return grid;
}

global_variable grid _g;
internal int compare_cells(const void *_a, const void *_b)
{
  // We subtract b - a, so that the lower elements get moved to the back
  // (Ret < 0 -> _a gets placed before _b)
  const cell_coord *a = _a, *b = _b;
  return *GetWeight(&_g, b->x, b->y) - *GetWeight(&_g, a->x, a->y);
}

int
main(int argc, char **argv)
{
  arena arena = CreateArena();
  dataset ds = ParseDatasetOption(argc, argv);
  s8 input = {0};
  if (ds == DS_FULL)
    input = ReadEntireFileS8(S8("inputs/day04_full"), &arena);
  else if (ds == DS_DEMO)
    input = ReadEntireFileS8(S8("inputs/day04_demo"), &arena);
  if (!input.data)
    return 1;

  grid g = FillGrid(input, &arena);
  _g = g;
  cell_coord *paper_coords = alloc(&arena, cell_coord, g.rows * g.cols);
  int num_papers = 0;
  for (int y = 0; y < g.rows; ++y)
  {
    for (int x = 0; x < g.cols; ++x)
    {
      if (GetField(&g, x, y) == F_PAPER)
      {
        paper_coords[num_papers++] = (cell_coord){x, y};
      }
    }
  }
  
  int count = 0;
  while (num_papers > 0)
  {
    qsort(paper_coords, num_papers, sizeof(cell_coord), compare_cells);
    cell_coord lowest = paper_coords[--num_papers];

    int neighbors =
            (GetField(&g, lowest.x - 1, lowest.y - 1) == F_PAPER) +
            (GetField(&g, lowest.x, lowest.y - 1) == F_PAPER) +
            (GetField(&g, lowest.x + 1, lowest.y - 1) == F_PAPER) +
            (GetField(&g, lowest.x - 1, lowest.y) == F_PAPER) +
            (GetField(&g, lowest.x + 1, lowest.y) == F_PAPER) +
            (GetField(&g, lowest.x - 1, lowest.y + 1) == F_PAPER) +
            (GetField(&g, lowest.x, lowest.y + 1) == F_PAPER) +
            (GetField(&g, lowest.x + 1, lowest.y + 1) == F_PAPER);
    // Terminate condition: No paper can be removed
    if (neighbors >= 4)
      break;

    g.fields[lowest.y * g.cols + lowest.x] = F_EMPTY;
    ++count; 

    for (int dy = -1; dy <= 1; ++dy)
    {
      int y = lowest.y + dy;
      if (y >= 0 && y < g.rows)
      {
        for (int dx = -1; dx <= 1; ++dx)
        {
          int x = lowest.x + dx;
          if (x >= 0 && x < g.cols)
          {
            *GetWeight(&g, x, y) -= 1;
          }
        }
      }
    }
   }
  printf("Answer: %d\n", count);
  
  return 0;
}