aoc-2019-c

Advent of Code 2019 Solutions in C
git clone https://git.sinitax.com/sinitax/aoc-2019-c
Log | Files | Refs | README | sfeed.txt

part1.c (2679B)

      1#include "allocator.h"
      2#include "aoc.h"
      3#include "vec_s.h"
      4#include "dvec_s.h"
      5#include "util.h"
      6
      7#include <assert.h>
      8#include <stdint.h>
      9#include <stdlib.h>
     10
     11static char *
     12load_map(size_t *maxx, size_t *h)
     13{
     14	const char *lpos, *lend;
     15	size_t rows, cols, len;
     16	char line[256];
     17	char *map;
     18
     19	map = NULL;
     20	rows = 0;
     21	cols = 0;
     22
     23	lpos = aoc.input;
     24	lend = lpos + aoc.input_size;
     25	while (readtok(line, sizeof(line), '\n', &lpos, lend)) {
     26		len = strlen(line);
     27		if (!len) continue;
     28		if (!cols) cols = len;
     29		assert(len == cols);
     30		map = realloc(map, cols * (rows + 1) + 1);
     31		memcpy(map + cols * rows, line, cols);
     32		rows += 1;
     33	}
     34	map[rows * cols] = '\0';
     35
     36	*maxx = cols;
     37	*h = rows;
     38
     39	return map;
     40}
     41
     42static void
     43print_map(char *map, size_t w, size_t h)
     44{
     45	size_t y;
     46
     47	for (y = 0; y < h; y++)
     48		aoc_debug("%.*s\n", w, &map[y * w]);
     49}
     50
     51static uint64_t
     52map_id(char *map, size_t w, size_t h)
     53{
     54	size_t x, y, b;
     55	uint64_t id;
     56
     57	b = 0;
     58	id = 0;
     59	for (y = 0; y < h; y++) {
     60		for (x = 0; x < w; x++) {
     61			if (map[y * w + x] == '#')
     62				id |= 1 << b;
     63			b += 1;
     64		}
     65	}
     66
     67	return id;
     68}
     69
     70static void
     71step(char *prev, char *next, size_t w, size_t h)
     72{
     73	struct vec2i pos, npos;
     74	size_t i, k, count;
     75
     76	for (pos.y = 0; (size_t) pos.y < h; pos.y++) {
     77		for (pos.x = 0; (size_t) pos.x < w; pos.x++) {
     78			count = 0;
     79			for (i = 0; i < 4; i++) {
     80				vec2i_add(&npos, &pos, &adj[i]);
     81				if (npos.x < 0 || (size_t) npos.x >= w)
     82					continue;
     83				if (npos.y < 0 || (size_t) npos.y >= h)
     84					continue;
     85				k = (size_t) npos.y * w + (size_t) npos.x;
     86				if (prev[k] == '#') count += 1;
     87			}
     88			k = (size_t) pos.y * w + (size_t) pos.x;
     89			if (prev[k] == '#' && count != 1) {
     90				next[k] = '.';
     91			} else if (prev[k] == '.' && (count == 1 || count == 2)) {
     92				next[k] = '#';
     93			} else {
     94				next[k] = prev[k];
     95			}
     96		}
     97	}
     98}
     99
    100void
    101part1(void)
    102{
    103	struct dvec ids;
    104	char *map, *next, *tmp;
    105	uint64_t *slot, id;
    106	size_t w, h, i;
    107	uint64_t answer;
    108
    109	map = load_map(&w, &h);
    110	next = memdup(map, w * h + 1);
    111
    112	dvec_init(&ids, sizeof(uint64_t), 0, &stdlib_strict_heap_allocator);
    113	slot = dvec_add_slot(&ids);
    114	*slot = map_id(map, w, h);
    115
    116	aoc_debug("INIT\n");
    117	print_map(map, w, h);
    118
    119	answer = 0;
    120	while (!answer) {
    121		step(map, next, w, h);
    122		tmp = map;
    123		map = next;
    124		next = tmp;
    125
    126		aoc_debug("$ %i\n", ids.len);
    127		print_map(map, w, h);
    128
    129		id = map_id(map, w, h);
    130		for (i = 0; i < ids.len; i++) {
    131			aoc_debug("%lu vs %lu\n", id, *(uint64_t *)dvec_at(&ids, i));
    132			if (*(uint64_t *)dvec_at(&ids, i) == id) {
    133				answer = id;
    134				break;
    135			}
    136		}
    137
    138		slot = dvec_add_slot(&ids);
    139		*slot = id;
    140	}
    141
    142	aoc.answer = aprintf("%lu", answer);
    143	aoc.solution = "30446641";
    144
    145	dvec_deinit(&ids);
    146	free(next);
    147	free(map);
    148}