commit 362de4cf2cc8d77ca48705ec134e9c724a1ce81b
parent cdaa9ee3e67d079c3806497cfbb6fe68739a794b
Author: bsandro <[email protected]>
Date: Wed, 22 Dec 2021 21:39:46 +0200
Day 22, puzzle 2
Diffstat:
2 files changed, 124 insertions(+), 20 deletions(-)
diff --git a/day21/Makefile b/day21/Makefile
@@ -2,8 +2,10 @@ NAME=$(shell basename ${PWD})
SRC=$(wildcard *.c ../common/*.c)
DEPS:=$(wildcard *.h ../common/*.h)
OBJ:=$(SRC:.c=.o)
-CFLAGS=-O0 -g -fsanitize=address -fno-omit-frame-pointer -std=c99 -Werror -Wall -Wextra -I. -I../common
-LDFLAGS=-g -lc -lm -fsanitize=address
+#CFLAGS=-O0 -g -fsanitize=address -fno-omit-frame-pointer -std=c99 -Werror -Wall -Wextra -I. -I../common
+#LDFLAGS=-g -lc -lm -fsanitize=address
+CFLAGS=-O2 -std=c99 -Werror -Wall -Wextra -I. -I../common
+LDFLAGS=-lc -lm
all: $(NAME)
diff --git a/day21/puzzle.c b/day21/puzzle.c
@@ -14,6 +14,24 @@
#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) {
@@ -41,14 +59,20 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
assert(p1 != 0 && p2 != 0);
- *result2 = 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) {
- //printf("rc=%3ld, d=%3ld, ", rc, d);
if (d == 1) {
p1 += 6;
d += 3;
@@ -58,10 +82,10 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
d = 1;
} else if (d == 99) {
p1 += 200;
- d = 2; //(d + 3) % 100;
+ d = 2;
} else if (d == 100) {
p1 += 103;
- d = 3; //(d + 3) % 100;
+ d = 3;
} else {
d = (d + 3) % 100;
p1 += d * 3 + 3;
@@ -70,17 +94,13 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
p1 += d * 3 + 3;
d += 3;
}
- //printf("p1=%3ld, ", p1);
p1 = p1 > 10 ? (p1 % 10) : p1;
p1 = p1 == 0 ? 10 : p1;
- //printf("p1(pos)=%3ld, ", p1);
p1s += p1;
- //printf("p1s=%3ld\n", p1s);
rc += 3;
if (p1s >= 1000) break;
- //printf("rc=%3ld, d=%3ld, ", rc, d);
if (d == 1) {
p2 += 6;
d += 3;
@@ -90,10 +110,10 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
d = 1;
} else if (d == 99) {
p2 += 200;
- d = 2; //(d + 3) % 100;
+ d = 2;
} else if (d == 100) {
p2 += 103;
- d = 3; //(d + 3) % 100;
+ d = 3;
} else {
d = (d + 3) % 100;
p2 += d * 3 + 3;
@@ -102,23 +122,105 @@ void puzzle(const char *filename, long long *result1, long long *result2) {
p2 += d * 3 + 3;
d += 3;
}
- //printf("p2=%3ld, ", p2);
p2 = p2 > 10 ? (p2 % 10) : p2;
p2 = p2 == 0 ? 10 : p2;
- //printf("p2(pos)=%3ld, ", p2);
p2s += p2;
- //printf("p2s=%3ld\n\n", p2s);
rc += 3;
if (p2s >= 1000) break;
}
- //printf("\n\n\np1=%3ld, p1s=%3ld, p2=%3ld, p2s=%3ld, rc=%3ld\n", p1, p1s, p2, p2s, rc);
+ return fmin(p1s, p2s) * rc;
+}
- long min_score = fmin(p1s, p2s);
+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);
+}
- *result1 = min_score * rc;
+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;
+}
- // mutiny! ignoring feof/ferror.
- fclose(infile);
+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;
}
