advent2021

puzzle.c (4804B)

---

 #define _DEFAULT_SOURCE
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
 #include <string.h>
 #include <strings.h>
 #include <assert.h>
 #include <ctype.h>
 #include <stdbool.h>
 #include <math.h>
 
 #include "util.h"
 
 #define STR_LEN 1024
 
 struct cache_t {
 	long p1, p2, p1s, p2s;
 	long long p1w;
 	long long p2w;
 	bool p1t;
 };
 
 struct result_t {
 	long long p1w;
 	long long p2w;
 };
 
 long long calc_result1(long p1, long p2);
 long long calc_result2(long p1, long p2);
 struct result_t roll_turn(struct array_t *cache, bool pp1t, long pp1, long pp2, long pp1s, long pp2s, long long p1w, long long p2w);
 struct cache_t * get_cache(struct array_t *cache, bool p1t, long p1, long p2, long p1s, long p2s);
 void set_cache(struct array_t *cache, bool p1t, long p1, long p2, long p1s, long p2s, long long p1w, long long p2w);
 
 void puzzle(const char *filename, long long *result1, long long *result2) {
 	FILE *infile = fopen(filename, "r");
 	if (infile == NULL) {
 		fprintf(stderr, "fopen() error: %s\n", strerror(errno));
 		return;
 	}
 
 	char buf[STR_LEN] = {0};
 	unsigned int line_num = 0;
 
 	long p1 = 0;
 	long p2 = 0;
 
 	while (fgets(buf, STR_LEN, infile) != NULL) {
 		int len = strlen(buf);
 		assert(len > 2);
 		if (line_num == 0) { // player 1
 			p1 = buf[len-2] - '0';
 		} else if (line_num == 1) { // player 2
 			p2 = buf[len-2] - '0';
 		}
 		++line_num;
 		bzero(buf, STR_LEN);
 	}
 
 	assert(p1 != 0 && p2 != 0);
 
 	*result1 = calc_result1(p1, p2);
 	*result2 = calc_result2(p1, p2);
 
 	// mutiny! ignoring feof/ferror.
 	fclose(infile);
 }
 
 long long calc_result1(long p1, long p2) {
 	long p1s = 0; // player 1 score
 	long p2s = 0; // player 2 score
 	long d = 1; // dice value
 	long rc = 0; // real rolls count
 
 	while (1) {
 		if (d == 1) {
 			p1 += 6;
 			d += 3;
 		} else if (d >= 98) {
 			if (d == 98) {
 				p1 += 297;
 				d = 1;
 			} else if (d == 99) {
 				p1 += 200;
 				d = 2;
 			} else if (d == 100) {
 				p1 += 103;
 				d = 3;
 			} else {
 				d = (d + 3) % 100;
 				p1 += d * 3 + 3;
 			}
 		} else {
 			p1 += d * 3 + 3;
 			d += 3;
 		}
 		p1 = p1 > 10 ? (p1 % 10) : p1;
 		p1 = p1 == 0 ? 10 : p1;
 		p1s += p1;
 		rc += 3;
 
 		if (p1s >= 1000) break;
 
 		if (d == 1) {
 			p2 += 6;
 			d += 3;
 		} else if (d >= 98) {
 			if (d == 98) {
 				p2 += 297;
 				d = 1;
 			} else if (d == 99) {
 				p2 += 200;
 				d = 2;
 			} else if (d == 100) {
 				p2 += 103;
 				d = 3;
 			} else {
 				d = (d + 3) % 100;
 				p2 += d * 3 + 3;
 			}
 		} else {
 			p2 += d * 3 + 3;
 			d += 3;
 		}
 		p2 = p2 > 10 ? (p2 % 10) : p2;
 		p2 = p2 == 0 ? 10 : p2;
 		p2s += p2;
 		rc += 3;
 
 		if (p2s >= 1000) break;
 	}
 
 	return fmin(p1s, p2s) * rc;
 }
 
 long long calc_result2(long p1, long p2) {
 	struct array_t cache = { .data = NULL };
 	array_init(&cache, sizeof(struct cache_t), 1000);
 	struct result_t result = roll_turn(&cache, true, p1, p2, 0, 0, 0, 0);
 	return fmaxl(result.p1w, result.p2w);
 }
 
 struct cache_t * get_cache(struct array_t *cache, bool p1t, long p1, long p2, long p1s, long p2s) {
 	struct cache_t *cache_data = cache->data;
 	for (size_t i = 0; i < cache->count; ++i) {
 		struct cache_t *c = &cache_data[i];
 		if (c->p1t == p1t && c->p1 == p1 && c->p2 == p2 && c->p1s == p1s && c->p2s == p2s) {
 			return c;
 		}
 	}
 	return NULL;
 }
 
 void set_cache(struct array_t *cache, bool p1t, long p1, long p2, long p1s, long p2s, long long p1w, long long p2w) {
 	if (cache->count >= cache->cap) array_expand(cache);
 	struct cache_t *cache_data = cache->data;
 
 	struct cache_t *c = get_cache(cache, p1t, p1, p2, p1s, p2s);
 	assert(c == NULL);
 	c = &cache_data[cache->count++];
 	c->p1t = p1t;
 	c->p1 = p1;
 	c->p2 = p2;
 	c->p1s = p1s;
 	c->p2s = p2s;
 	c->p1w = p1w;
 	c->p2w = p2w;
 }
 
 
 struct result_t roll_turn(struct array_t *cache, bool pp1t, long pp1, long pp2, long pp1s, long pp2s, long long p1w, long long p2w) {
 
 	struct result_t result = {0};
 	if (pp1s >= 21) {
 		result.p1w = 1;
 		return result;
 	}
 	if (pp2s >= 21) {
 		result.p2w = 1;
 		return result;
 	}
 
 	struct cache_t *c = get_cache(cache, pp1t, pp1, pp2, pp1s, pp2s);
 	if (c != NULL) {
 		result.p1w = c->p1w;
 		result.p2w = c->p2w;
 		return result;
 	}
 
 	for (int d1 = 1; d1 <= 3; ++d1) {
 	for (int d2 = 1; d2 <= 3; ++d2) {
 	for (int d3 = 1; d3 <= 3; ++d3) {
 
 		long dice = d1+d2+d3;
 		long p1 = pp1;
 		long p2 = pp2;
 		long p1s = pp1s;
 		long p2s = pp2s;
 		bool p1t = pp1t;
 
 		if (p1t) {
 			// player 1 turn
 			p1t = false;
 			p1 += dice;
 			p1 = p1 > 10 ? (p1 % 10) : p1;
 			p1 = (p1 == 0) ? 10 : p1;
 			p1s += p1;
 
 		} else {
 			// player 2 turn
 			p1t = true;
 			p2 += dice;
 			p2 = p2 > 10 ? (p2 % 10) : p2;
 			p2 = p2 == 0 ? 10 : p2;
 			p2s += p2;
 
 		}
 		struct result_t res = roll_turn(cache, p1t, p1, p2, p1s, p2s, p1w, p2w);
 		result.p1w += res.p1w;
 		result.p2w += res.p2w;
 	}
 	}
 	}
 	set_cache(cache, pp1t, pp1, pp2, pp1s, pp2s, result.p1w, result.p2w);
 	return result;
 }