aoc_omni/c/2024/6/guard_gallivant.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#include "../../lib/aoc.h"

#define MAX_LOOP_LENGTH 8000

typedef enum Direction { RIGHT, UP, LEFT, DOWN } Direction;

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

typedef struct Game {
  char *map;
  int width;
  int height;
  Position guard;
  Direction guard_direction;
  Position guard_start;
  Direction guard_start_direction;
  int positions[10000];
  int position_count;
} Game;

Position position_from_index(Game *game, int index) {
  Position p = { index % game->width, index / game->width };
  return p;
}

int index_from_position(Game *game, Position p) {
  return p.x + (game->width * p.y);
}

bool position_inbounds(Game *game, Position p) {
  return p.x >= 0 && p.y >= 0 && p.x < game->width && p.y < game->height;
}

bool guard_inbounds(Game *game) {
  return position_inbounds(game, game -> guard);
}

bool position_has_obstacle(Game *game, Position p) {
  return game->map[index_from_position(game, p)] == '#';
}

void turn_guard(Game *game) {
  Direction new_direction;
  switch (game->guard_direction) {
  case RIGHT:
    new_direction = DOWN;
    break;
  case UP:
    new_direction = RIGHT;
    break;
  case LEFT:
    new_direction = UP;
    break;
  case DOWN:
    new_direction = LEFT;
    break;
  }
  game->guard_direction = new_direction;
}

void move_guard(Game *game, bool deface) {
  Position target;
  target.x = game->guard.x;
  target.y = game->guard.y;
  switch (game->guard_direction) {
  case RIGHT:
    target.x++;
    break;
  case UP:
    target.y--;
    break;
  case LEFT:
    target.x--;
    break;
  case DOWN:
    target.y++;
    break;
  }

  if (position_has_obstacle(game, target)) turn_guard(game);
  else {
    int index = index_from_position(game, game->guard);
    if (deface && game->map[index] == '.') {
      game->map[index] = 'X';
      game->positions[game->position_count++] = index;
    }
      
    game->guard.x = target.x;
    game->guard.y = target.y;
  }
}

int main() {
  char *dirty_map = aoc_read_input();

  Game game;
  game.map = dirty_map;
  game.width = strchr(game.map, '\n') - game.map + 1;
  game.height = strlen(game.map) / game.width;
  game.position_count = 0;
  for (int i = 0; i < strlen(game.map); i++) {
    if (game.map[i] == '^') {
      game.map[i] = '.';
      game.guard = position_from_index(&game, i);
      game.guard_direction = UP;
      game.guard_start = game.guard;
      game.guard_start_direction = game.guard_direction;
      break;
    }
  }
  char *clean_map = malloc(strlen(dirty_map) + 1);
  strcpy(clean_map, dirty_map);

  Game time_travel_game;
  time_travel_game.map = clean_map;
  time_travel_game.width = game.width;
  time_travel_game.height = game.height;
  time_travel_game.position_count = 0;
  time_travel_game.guard = game.guard;
  time_travel_game.guard_direction = game.guard_direction;
  time_travel_game.guard_start = game.guard;
  time_travel_game.guard_start_direction = game.guard_direction;

  while (guard_inbounds(&game)) {
    move_guard(&game, true);
  }
  printf("Part 1: %d\n", game.position_count);

  int loop_count = 0;
  for (int i = 0; i < game.position_count; i++) {
    time_travel_game.map[game.positions[i]] = '#';
    int gsx = time_travel_game.guard_start.x;
    int gsy = time_travel_game.guard_start.y;
    int gsd = time_travel_game.guard_start_direction;
    time_travel_game.guard = time_travel_game.guard_start;
    time_travel_game.guard_direction = time_travel_game.guard_start_direction;
    int j = 0;
    while (guard_inbounds(&time_travel_game)) {
      move_guard(&time_travel_game, false);
      if (time_travel_game.guard.x == gsx &&
	  time_travel_game.guard.y == gsy &&
	  time_travel_game.guard_direction == gsd) {
	loop_count++;
	break;
      }
      j++;
      if (j % MAX_LOOP_LENGTH == 0) {
	gsx = time_travel_game.guard.x;
	gsy = time_travel_game.guard.y;
	gsd = time_travel_game.guard_direction;
      }
    }
    time_travel_game.map[game.positions[i]] = '.';
  }

  printf("Part 2: %d\n", loop_count);

  aoc_free();
  return 0;
}