aboutsummaryrefslogtreecommitdiff
path: root/10
diff options
context:
space:
mode:
Diffstat (limited to '10')
-rw-r--r--10/Makefile2
-rw-r--r--10/part2.c550
2 files changed, 551 insertions, 1 deletions
diff --git a/10/Makefile b/10/Makefile
index 7d325ba..5cf877b 100644
--- a/10/Makefile
+++ b/10/Makefile
@@ -4,7 +4,7 @@ part1: part1.c
gcc -Wall -g part1.c -o part1 -lalgds
part2: part2.c
- gcc -Wall -g part2.c -o part2 -lalgds
+ gcc -march=native -O3 -Wall -g part2.c -o part2 -lalgds
1: part1
cat input | ./part1
diff --git a/10/part2.c b/10/part2.c
new file mode 100644
index 0000000..0cbc2d5
--- /dev/null
+++ b/10/part2.c
@@ -0,0 +1,550 @@
+#include <algds/sort.h>
+#include <algds/type_alias.h>
+#include <errno.h>
+#include <ctype.h>
+#include <algds/vec.h>
+#include <algds/str.h>
+#include <limits.h>
+#include <stdint.h>
+#include <stdio.h>
+
+
+#define PANIC do { \
+ fprintf(stderr, "panic at %s:%d\n", __FILE__, __LINE__); \
+ abort(); \
+} while (0)
+
+void expect_char(char e) {
+ int c = fpeek(stdin);
+ if (c != e) {
+ PANIC;
+ }
+ fgetc(stdin);
+}
+
+bool string2long(const char *s, long *num) {
+ char *end;
+ errno = 0;
+ *num = strtol(s, &end, 10);
+ if (end == s) {
+ return false;
+ }
+ if (errno != 0) {
+ return false;
+ }
+ return true;
+}
+
+int64_t parse_integer() {
+ long ret;
+ StrBuilder sb;
+ StrBuilder_init(&sb);
+ while (1) {
+ int c = fpeek(stdin);
+ if (isdigit(c)) {
+ fgetc(stdin);
+ StrBuilder_append_char(&sb, c);
+ } else {
+ break;
+ }
+ }
+ if (strlen(sb.buf) == 0) {
+ PANIC;
+ }
+ StrBuilder_append_char(&sb, '\0');
+ if (!string2long(sb.buf, &ret)) {
+ PANIC;
+ }
+ free(sb.buf);
+ return ret;
+}
+
+uint32_t parse_indicator() {
+ expect_char('[');
+ uint32_t ret = 0;
+ int n = 0;
+ while (1) {
+ int c = fpeek(stdin);
+ if (c == '.') {
+ getchar();
+ } else if (c == '#') {
+ getchar();
+ // printf("n=%d\n", n);
+ ret |= (1 << n);
+ // printf("ret=%d\n", ret);
+ } else {
+ break;
+ }
+ n++;
+ }
+ expect_char(']');
+ return ret;
+}
+
+
+typedef struct {
+ int16_t val[16];
+} Joltage;
+
+Joltage parse_button() {
+ Joltage j;
+ memset(&j, 0, sizeof(j));
+ expect_char('(');
+ while (1) {
+ long num = parse_integer();
+ j.val[num] = 1;
+ int c = fpeek(stdin);
+ if (c == ',') {
+ getchar();
+ } else {
+ break;
+ }
+ }
+ expect_char(')');
+ return j;
+}
+
+void skip_indicator() {
+ expect_char('[');
+ while (1) {
+ int c = getchar();
+ if (c == ']') break;
+ }
+}
+
+void skip_space() {
+ while (1) {
+ int c = fpeek(stdin);
+ if (c == EOF) return;
+ if (isspace(c)) {
+ fgetc(stdin);
+ } else {
+ return;
+ }
+ }
+}
+void Joltage_show(Joltage self, FILE *fp) {}
+
+VECTOR_DEF(Joltage)
+VECTOR_IMPL(Joltage)
+
+JoltageVector parse_buttons() {
+ skip_space();
+ JoltageVector ret;
+ JoltageVector_init(&ret);
+ while (1) {
+ int c = fpeek(stdin);
+ if (c == '(') {
+ Joltage btn = parse_button();
+ JoltageVector_push_back(&ret, btn);
+ skip_space();
+ } else {
+ break;
+ }
+ }
+ return ret;
+}
+
+Joltage parse_joltage(int *targetlen) {
+ int len = 0;
+ skip_space();
+ Joltage j;
+ memset(&j, 0, sizeof(j));
+ int i = 0;
+ expect_char('{');
+ while (1) {
+ if (i >= 16) PANIC;
+ int16_t n = parse_integer();
+ j.val[i] = n;
+ len++;
+ int c = fpeek(stdin);
+ if (c == ',') {
+ getchar();
+ } else {
+ break;
+ }
+ i++;
+ }
+ expect_char('}');
+ skip_space();
+ *targetlen = len;
+ return j;
+}
+
+typedef struct {
+ int a;
+ int b;
+} Frac;
+
+int gcd(int a, int b) {
+ a = abs(a);
+ b = abs(b);
+ while (b) {
+ a %= b;
+ int tmp = a;
+ a = b;
+ b = tmp;
+ }
+ return a;
+}
+
+Frac Frac_new(int a, int b) {
+ if (b == 0) {
+ PANIC;
+ }
+ int common = gcd(a, b);
+ Frac res;
+ res.a = a / common;
+ res.b = b / common;
+ if (res.b < 0) {
+ res.a = -res.a;
+ res.b = -res.b;
+ }
+ return res;
+}
+
+Frac Frac_add(Frac a, Frac b) {
+ return Frac_new(a.a * b.b + b.a * a.b, a.b * b.b);
+}
+
+Frac Frac_sub(Frac a, Frac b) {
+ return Frac_new(a.a * b.b - b.a * a.b, a.b * b.b);
+}
+
+Frac Frac_mul(Frac a, Frac b) {
+ return Frac_new(a.a * b.a, a.b * b.b);
+}
+
+Frac frac_div(Frac a, Frac b) {
+ if (b.a == 0) {
+ PANIC;
+ }
+ return Frac_new(a.a * b.b, a.b * b.a);
+}
+
+int frac_is_zero(Frac f) {
+ return f.a == 0;
+}
+
+void Frac_show(Frac f, FILE *fp) {
+ if (f.b == 1) fprintf(fp, "%d", f.a);
+ else fprintf(fp, "%d/%d", f.a, f.b);
+}
+
+typedef struct {
+ int size;
+ Frac *buf;
+} FracVec;
+
+typedef struct {
+ int height;
+ int width;
+ Frac *buf;
+} FracMat;
+
+FracVec FracVec_new(int size) {
+ FracVec v;
+ v.size = size;
+ v.buf = (Frac *)malloc(size * sizeof(Frac));
+ for (int i = 0; i < size; i++) v.buf[i] = Frac_new(0, 1);
+ return v;
+}
+
+void FracVec_free(FracVec *v) {
+ if (v->buf) {
+ free(v->buf);
+ v->buf = NULL;
+ }
+ v->size = 0;
+}
+
+void FracVec_show(FracVec v, FILE *fp) {
+ fprintf(fp, "[ ");
+ for (int i = 0; i < v.size; i++) {
+ Frac_show(v.buf[i], fp);
+ if (i < v.size - 1) printf(", ");
+ }
+ fprintf(fp, " ]");
+}
+
+Frac FracVec_get(FracVec v, int x) {
+ if (x < 0 || x >= v.size) PANIC;
+ return v.buf[x];
+}
+
+void FracVec_set(FracVec v, int x, Frac val) {
+ if (x >= v.size || x < 0) PANIC;
+ v.buf[x] = val;
+}
+
+FracMat FracMat_new(int height, int width) {
+ FracMat m;
+ m.height = height;
+ m.width = width;
+ if (height == 0 || width == 0) {
+ m.buf = NULL;
+ return m;
+ }
+ m.buf = (Frac *)malloc(height * width * sizeof(Frac));
+ for (int i = 0; i < height * width; i++) m.buf[i] = Frac_new(0, 1);
+ return m;
+}
+
+void FracMat_free(FracMat *m) {
+ if (m->buf) {
+ free(m->buf);
+ m->buf = NULL;
+ }
+ m->height = m->width = 0;
+}
+
+Frac FracMat_get(FracMat m, int row, int col) {
+ if (row >= m.height || row < 0) PANIC;
+ if (col >= m.width || col < 0) PANIC;
+ return m.buf[row * m.width + col];
+}
+
+void FracMat_show(FracMat m, FILE *fp) {
+ for (int i = 0; i < m.height; i++) {
+ fprintf(fp, "| ");
+ for (int j = 0; j < m.width; j++) {
+ Frac_show(FracMat_get(m, i, j), fp);
+ fprintf(fp, "\t");
+ }
+ fprintf(fp, "|\n");
+ }
+}
+
+void FracMat_set(FracMat m, int row, int col, Frac val) {
+ if (row >= m.height || row < 0) PANIC;
+ if (col >= m.width || col < 0) PANIC;
+ m.buf[row * m.width + col] = val;
+}
+
+void FracMat_swap_rows(FracMat m, int r1, int r2) {
+ if (r1 == r2) return;
+ for (int j = 0; j < m.width; j++) {
+ Frac val1 = FracMat_get(m, r1, j);
+ Frac val2 = FracMat_get(m, r2, j);
+ FracMat_set(m, r1, j, val2);
+ FracMat_set(m, r2, j, val1);
+ }
+}
+
+FracVec FracMat_muladd(FracMat A, FracVec x, FracVec b) {
+ if (A.width != x.size) {
+ PANIC;
+ }
+ if (A.height != b.size) {
+ PANIC;
+ }
+ FracVec res = FracVec_new(A.height);
+ for (int i = 0; i < A.height; i++) {
+ for (int j = 0; j < A.width; j++) {
+ FracVec_set(res, i, Frac_add(res.buf[i], Frac_mul(FracMat_get(A, i, j), x.buf[j])));
+ }
+ }
+ for (int i = 0; i < A.height; i++) {
+ FracVec_set(res, i, Frac_add(res.buf[i], b.buf[i]));
+ }
+ return res;
+}
+
+int gauss_elim(FracMat A, FracVec b, FracMat *sA, FracVec *sb) {
+ if (A.height != b.size) {
+ fprintf(stderr, "Error: Dimension mismatch.\n");
+ PANIC;
+ }
+
+ FracMat aug = FracMat_new(A.height, A.width + 1);
+ for (int i = 0; i < A.height; i++) {
+ for (int j = 0; j < A.width; j++) {
+ FracMat_set(aug, i, j, FracMat_get(A, i, j));
+ }
+ FracMat_set(aug, i, A.width, FracVec_get(b, i));
+ }
+ int pivot_count = 0;
+ for (int i = 0; i < A.width; i++) {
+ int pivot_row = pivot_count;
+ while (pivot_row < A.height && FracMat_get(aug, pivot_row, i).a == 0) {
+ pivot_row++;
+ }
+
+ if (pivot_row == A.height) {
+ continue;
+ }
+ // FracMat_show(aug, stdout); puts("");
+ FracMat_swap_rows(aug, pivot_count, pivot_row);
+ // FracMat_show(aug, stdout); puts("");
+ Frac pivot = FracMat_get(aug, pivot_count, i);
+ for (int j = i; j <= A.width; j++) {
+ Frac val = FracMat_get(aug, pivot_count, j);
+ FracMat_set(aug, pivot_count, j, frac_div(val, pivot));
+ }
+
+ for (int k = 0; k < A.height; k++) {
+ if (k != pivot_count) {
+ Frac factor = FracMat_get(aug, k, i);
+ if (factor.a != 0) {
+ for (int j = i; j <= A.width; j++) {
+ Frac curr = FracMat_get(aug, k, j);
+ Frac subval = Frac_mul(factor, FracMat_get(aug, pivot_count, j));
+ FracMat_set(aug, k, j, Frac_sub(curr, subval));
+ }
+ }
+ }
+ }
+ pivot_count++;
+ }
+ // FracMat_show(aug, stdout); puts("");
+
+ for (int i = 0; i < aug.height; i++) {
+ int all_zeros = 1;
+ for (int j = 0; j < aug.width - 1; j++) {
+ if (!frac_is_zero(FracMat_get(aug, i, j))) {
+ all_zeros = 0;
+ break;
+ }
+ }
+ if (all_zeros && !frac_is_zero(FracMat_get(aug, i, aug.width - 1))) {
+ FracMat_free(&aug);
+ return 0;
+ }
+ }
+ int rank = 0;
+ for (int i = 0; i < aug.height; i++) {
+ int is_zero_row = 1;
+ for (int j = 0; j < aug.width - 1; j++) {
+ if (!frac_is_zero(FracMat_get(aug, i, j))) {
+ is_zero_row = 0;
+ break;
+ }
+ }
+ if (!is_zero_row) rank++;
+ }
+ int free_var_count = A.width - rank;
+ if (free_var_count == 0) {
+ *sb = FracVec_new(rank);
+ for (int i = 0; i < rank; i++) {
+ FracVec_set(*sb, i, FracMat_get(aug, i, aug.width - 1));
+ }
+ return 1;
+ }
+ *sA = FracMat_new(rank, free_var_count);
+ int rank_count = 0;
+ free_var_count = 0;
+ for (int i = 0; i < A.width; i++) {
+ if (rank_count >= aug.height || FracMat_get(aug, rank_count, i).a == 0) {
+ for (int j = 0; j < rank; j++) {
+ Frac y = FracMat_get(aug, j, i);
+ y.a = -y.a;
+ FracMat_set(*sA, j, free_var_count, y);
+ }
+ free_var_count++;
+ } else {
+ rank_count++;
+ }
+ }
+ *sb = FracVec_new(rank);
+ for (int i = 0; i < rank; i++) {
+ FracVec_set(*sb, i, FracMat_get(aug, i, aug.width - 1));
+ }
+ // puts("sA=");
+ // FracMat_show(*sA, stdout); puts("");
+ // puts("sb=");
+ // FracVec_show(*sb, stdout); puts("");
+ // fflush(stdout);
+
+ return 2;
+}
+
+static void enum_impl(FracMat A, FracVec b, FracVec *x, int range, int cur, int *minsum) {
+ if (cur == x->size) {
+ FracVec res = FracMat_muladd(A, *x, b);
+ int sum = 0;
+ for (int i = 0; i < res.size; i++) {
+ if (FracVec_get(res, i).b != 1) goto end;
+ if (FracVec_get(res, i).a < 0) goto end;
+ sum += FracVec_get(res, i).a;
+ }
+ for (int i = 0; i < x->size; i++) {
+ sum += FracVec_get(*x, i).a;
+ }
+ if (sum < *minsum) {
+ // FracVec_show(*x, stdout); FracVec_show(res, stdout); puts("");
+ *minsum = sum;
+ }
+ end:
+ FracVec_free(&res);
+ return;
+ }
+ for (int i = 0; i <= range; i++) {
+ FracVec_set(*x, cur, Frac_new(i, 1));
+ enum_impl(A, b, x, range, cur + 1, minsum);
+ }
+}
+
+int enum_free_var(FracMat A, FracVec b, int range) {
+ int minsum = INT_MAX;
+ FracVec x = FracVec_new(A.width);
+ enum_impl(A, b, &x, range, 0, &minsum);
+ return minsum;
+}
+
+int solve(int targetlen, Joltage target, JoltageVector *buttons) {
+ int height = targetlen;
+ int width = buttons->size;
+ FracMat A = FracMat_new(height, width);
+ for (int i = 0; i < width; i++) {
+ for (int j = 0; j < height; j++) {
+ FracMat_set(A, j, i, Frac_new(buttons->buffer[i].val[j], 1));
+ }
+ }
+ FracVec b = FracVec_new(height);
+ for (int i = 0; i < height; i++) {
+ FracVec_set(b, i, Frac_new(target.val[i], 1));
+ }
+ FracMat sA;
+ FracVec sb;
+ int type = gauss_elim(A, b, &sA, &sb);
+ if (type == 0) PANIC;
+ if (type == 1) {
+ int minsum = 0;
+ for (int i = 0; i < sb.size; i++) {
+ Frac x = FracVec_get(sb, i);
+ if (x.b != 1) PANIC;
+ if (x.a < 0) PANIC;
+ minsum += x.a;
+ }
+ return minsum;
+ }
+
+ int range = 0;
+ for (int i = 0; i < 16; i++) {
+ if (target.val[i] > range) range = target.val[i];
+ }
+ int minsum = enum_free_var(sA, sb, range);
+ // printf("%d\n", minsum);
+ return minsum;
+}
+
+int main() {
+ int r = 0;
+ while (1) {
+ int c = fpeek(stdin);
+ if (c == '[') {
+ skip_indicator();
+ JoltageVector buttons = parse_buttons();
+ int targetlen;
+ Joltage j = parse_joltage(&targetlen);
+ int solution = solve(targetlen, j, &buttons);
+ // printf("%d\n", solution);
+ r += solution;
+ // fflush(stdout);
+ } else {
+ break;
+ }
+ }
+ printf("%d\n", r);
+ return 0;
+} \ No newline at end of file
generated by cgit v1.0 at 2025-12-29 17:43:59 +0000