advent2021

Advent of Code 2021 Solutions
git clone git://bsandro.tech/advent2021
Log | Files | Refs | README | LICENSE

puzzle.c (4218B)


      1 #define _DEFAULT_SOURCE
      2 
      3 #include <stdio.h>
      4 #include <stdlib.h>
      5 #include <errno.h>
      6 #include <string.h>
      7 #include <strings.h>
      8 #include <assert.h>
      9 #include <ctype.h>
     10 #include <stdbool.h>
     11 #include <math.h>
     12 #include <unistd.h>
     13 
     14 #include "util.h"
     15 
     16 #define STR_LEN 1024
     17 
     18 struct cucumber_t {
     19 	enum direction_t { SOUTH, EAST } direction;
     20 	bool stuck;
     21 	uint64_t step;
     22 };
     23 
     24 struct tile_t {
     25 	struct cucumber_t *cucumber;
     26 };
     27 
     28 struct map_t {
     29 	struct tile_t *tiles;
     30 	int width;
     31 	int height;
     32 };
     33 
     34 void print_map(struct map_t *map);
     35 int step(struct map_t *map, uint64_t step);
     36 
     37 void puzzle(const char *filename, long long *result1, long long *result2) {
     38 	FILE *infile = fopen(filename, "r");
     39 	if (infile == NULL) {
     40 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
     41 		return;
     42 	}
     43 
     44 	char buf[STR_LEN] = {0};
     45 	size_t line = 0;
     46 	struct map_t map = {0};
     47 
     48 	while (fgets(buf, STR_LEN, infile) != NULL) {
     49 		int len = strlen(buf);
     50 		assert(len > 0);
     51 		if (map.width > 0 && map.width != len-1) {
     52 			printf("invalid input\n");
     53 			exit(1);
     54 		}
     55 		map.width = len-1;
     56 		line = map.height++;
     57 		map.tiles = realloc(map.tiles, sizeof(struct tile_t) * map.width * map.height);
     58 		for (int i = 0; i < len-1; ++i) {
     59 			char c = buf[i];
     60 			if (c == '>' || c == 'v') {
     61 				struct cucumber_t *cucumber = malloc(sizeof(struct cucumber_t));
     62 				assert(cucumber != NULL);
     63 				cucumber->direction = (c == '>') ? EAST : SOUTH;
     64 				cucumber->stuck = false;
     65 				cucumber->step = 0;
     66 				map.tiles[line*map.width+i].cucumber = cucumber;
     67 			} else {
     68 				map.tiles[line*map.width+i].cucumber = NULL;
     69 			}
     70 		}
     71 		bzero(buf, STR_LEN);
     72 	}
     73 
     74 	//printf("map width: %d, height: %d\n", map.width, map.height);
     75 	//print_map(&map);
     76 	for (uint64_t i = 1;; ++i) {
     77 		if (step(&map, i) == 0) {
     78 			*result1 = i;
     79 			break;
     80 		}
     81 	}
     82 	//print_map(&map);
     83 	*result2 = 0;
     84 
     85 	// mutiny! ignoring feof/ferror.
     86 	fclose(infile);
     87 }
     88 
     89 void print_map(struct map_t *map) {
     90 	assert(map != NULL);
     91 	printf("----------\n");
     92 	for (int y = 0; y < map->height; ++y) {
     93 		for (int x = 0; x < map->width; ++x) {
     94 			struct tile_t *tile = &map->tiles[y*map->width+x];
     95 			if (tile->cucumber != NULL) {
     96 				printf("%c", tile->cucumber->direction == SOUTH ? 'v' : '>');
     97 			} else {
     98 				printf(".");
     99 			}
    100 		}
    101 		printf("\n");
    102 	}
    103 	printf("\n");
    104 }
    105 
    106 int step(struct map_t *map, uint64_t step) {
    107 	int moved = 0;
    108 	// eastbound cucumbers
    109 	for (int y = 0; y < map->height; ++y) {
    110 		for (int x = 0; x < map->width; ++x) {
    111 			int nx = (x == map->width-1) ? 0 : x+1;
    112 			struct tile_t *tile = &map->tiles[map->width*y+x];
    113 			struct tile_t *next = &map->tiles[map->width*y+nx];
    114 			if (tile->cucumber != NULL && tile->cucumber->direction == EAST && tile->cucumber->step != step) {
    115 				tile->cucumber->stuck = next->cucumber != NULL;
    116 			}
    117 		}
    118 	}
    119 	for (int y = 0; y < map->height; ++y) {
    120 		for (int x = 0; x < map->width; ++x) {
    121 			int nx = (x == map->width-1) ? 0 : x+1;
    122 			struct tile_t *tile = &map->tiles[map->width*y+x];
    123 			struct tile_t *next = &map->tiles[map->width*y+nx];
    124 			if (tile->cucumber != NULL && tile->cucumber->direction == EAST && !tile->cucumber->stuck && tile->cucumber->step != step) {
    125 				assert(next->cucumber == NULL);
    126 				tile->cucumber->step = step;
    127 				next->cucumber = tile->cucumber;
    128 				tile->cucumber = NULL;
    129 				moved++;
    130 			}
    131 		}
    132 	}
    133 	// southbound cucumbers
    134 	for (int y = 0; y < map->height; ++y) {
    135 		int ny = (y == map->height-1) ? 0 : y+1;
    136 		for (int x = 0; x < map->width; ++x) {
    137 			struct tile_t *tile = &map->tiles[map->width*y+x];
    138 			struct tile_t *next = &map->tiles[map->width*ny+x];
    139 			if (tile->cucumber != NULL && tile->cucumber->direction == SOUTH && tile->cucumber->step != step) {
    140 				tile->cucumber->stuck = next->cucumber != NULL;
    141 			}
    142 		}
    143 	}
    144 	for (int y = 0; y < map->height; ++y) {
    145 		int ny = (y == map->height-1) ? 0 : y+1;
    146 		for (int x = 0; x < map->width; ++x) {
    147 			struct tile_t *tile = &map->tiles[map->width*y+x];
    148 			struct tile_t *next = &map->tiles[map->width*ny+x];
    149 			if (tile->cucumber != NULL && tile->cucumber->direction == SOUTH && !tile->cucumber->stuck && tile->cucumber->step != step) {
    150 				assert(next->cucumber == NULL);
    151 				tile->cucumber->step = step;
    152 				next->cucumber = tile->cucumber;
    153 				tile->cucumber = NULL;
    154 				moved++;
    155 			}
    156 		}
    157 	}
    158 	return moved;
    159 }