Discussion on: Advent of Code 2020 Solution Megathread - Day 3: Toboggan Trajectory

[Ryan Palo]

OK! Here's my solution. I wasn't sure how managing the 2D grid was going to go in C since I've historically struggled with them in Rust. But it went pretty easy and ran super fast, so I'm very happy with it :)

I had trouble for a minute because my code was skipping slots in my array because of the newline characters in the input. Once I stopped incrementing my index when I saw a newline, it shaped right up!

Day3.h:

/// Day 3: Taboggan Trajectory
/// 
/// Figure out how many trees you'll have to go past given a 2D grid/slope
/// covered in them.

#ifndef AOC2020_DAY3_H
#define AOC2020_DAY3_H


#include <stdlib.h>

/// All of the possible options for a terrain square in a TreeGrid.
/// OPEN has no trees in it.
/// TREE has a tree in it.
typedef enum {
  OPEN,
  TREE,
} TerrainType;

/// A 2D grid of terrain.
/// Knows how wide and tall it is.
/// Uses a 1D list of cells, and tricky math to index.
typedef struct {
  TerrainType* cells;
  size_t width;
  size_t height;
} TreeGrid;

/// 2D indexing into a TreeGrid
#define CELL(t, x, y) ((t)->cells[y*(t)->width + x])

/// Parse the input file, which is a 2D grid of '.' (free) and '#' (tree)
/// Return a pointer to a TreeGrid.
TreeGrid* parse(const char* filename);

/// Frees a TreeGrid.
void freeTreeGrid(TreeGrid* grid);

/// Part 1 calculates how many trees we'll hit with a slope of 3 right
/// and 1 down.
size_t part1(TreeGrid* grid);

/// Part 2 has us check a few different slopes for trees.  The result
/// is the product of all tree counts.
size_t part2(TreeGrid* grid);

/// Runs both parts and outputs the results.
int day3(void);
#endif

Day3.c:

#include "Day3.h"
#include "parsing.h"

#include <stdio.h>

TreeGrid* parse(const char* filename) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open input file.\n");
    exit(EXIT_FAILURE);
  }

  TreeGrid* grid = malloc(sizeof(TreeGrid));
  GridSize size = measure_grid(fp);
  grid->cells = malloc(sizeof(TerrainType) * size.width * size.height);

  char c;
  for (size_t i = 0; !feof(fp);) {
    switch (c = getc(fp)) {
    case '.':
      grid->cells[i] = OPEN;
      i++;
      break;
    case '#':
      grid->cells[i] = TREE;
      i++;
      break;
    case '\n':
    case EOF:
      // Just consume the newline
      break;
    default:
      printf("Unrecognized character on char (x=%zu, y=%zu): %c.\n",
      i % size.width,
      i / size.width,
      c);
      exit(EXIT_FAILURE);
    }
  }

  fclose(fp);
  grid->height = size.height;
  grid->width = size.width;
  return grid;
}

void freeTreeGrid(TreeGrid* grid) {
  free(grid->cells);
  grid->cells = NULL;
  free(grid);
}

/// Calculates how many trees you'll see on a linear trip down the hill.
/// If you go off the right end of the grid, wraps around infinitely wide.
static size_t calculateTrees(TreeGrid* grid, size_t xShift, size_t yDrop) {
  size_t trees = 0;
  for (size_t x = 0, y = 0; y < grid->height; y += yDrop, x = (x + xShift) % grid->width) {
    switch (CELL(grid, x, y)) {
    case TREE:
      trees++;
      break;
    case OPEN:
      break;
    }
  }
  return trees;
}

size_t part1(TreeGrid* grid) {
  return calculateTrees(grid, 3, 1);
}

size_t part2(TreeGrid* grid) {
  return calculateTrees(grid, 1, 1) *
         calculateTrees(grid, 3, 1) *
         calculateTrees(grid, 5, 1) *
         calculateTrees(grid, 7, 1) *
         calculateTrees(grid, 1, 2);
}

int day3() {
  TreeGrid* grid = parse("data/day3.txt");
  printf("====== Day 3 ======\n");
  printf("Part 1: %zu\n", part1(grid));
  printf("Part 2: %zu\n", part2(grid));

  freeTreeGrid(grid);
  return EXIT_SUCCESS;
}

Additional code to parsing.h:

// ...
/// The height and width of a 2D grid.
typedef struct {
  size_t width;
  size_t height;
} GridSize;

/// Takes in a file containing a 2D grid and returns its width/height.
GridSize measure_grid(FILE* fp);

Aaaand the implementation:

GridSize measure_grid(FILE* fp) {
  size_t lines = 0;
  size_t cols = 0;

  while (getc(fp) != '\n') cols++;
  lines++;
  while (!feof(fp)) {
    if (getc(fp) == '\n') lines++;
  }
  lines++; // Assume no newline after last line.

  rewind(fp);
  return (GridSize) {.width = cols, .height = lines};
}