advent2025

commit b12e0913cbab876d5f5ff81c3c3713f1065203c9
parent 04e621e3fde91ff77b402949353d6e62f8b2d9c7
Author: bsandro <email@bsandro.tech>
Date:   Fri, 12 Dec 2025 14:03:46 +0200

day10 p2 - with GLPK

Diffstat:
M
Makefile
 | 
4
++++
M
day10.c
 | 
102
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------

2 files changed, 90 insertions(+), 16 deletions(-)
diff --git a/Makefile b/Makefile
@@ -20,6 +20,10 @@ endif
 
 LDFLAGS=-lc -lm
 
+ifeq ($(GLPK),1)
+LDFLAGS=-lglpk
+endif
+
 ifneq ($(shell which clang),)
 CC=clang
 else ifneq ($(shell which gcc-mp-14),)
diff --git a/day10.c b/day10.c
@@ -1,7 +1,9 @@
 #include <stdio.h>
 #include <stdbool.h>
+#include <stdlib.h>
 #include <limits.h>
 #include <inttypes.h>
+#include <glpk.h>
 #include "cputime.h"
 
 #define BUF_SIZE 256
@@ -44,6 +46,15 @@ void m_joltage_add(Machine *m, int jolt) {
     m->joltages[m->joltages_l++] = jolt;
 }
 
+bool btn_lights(Button *btn, int light) {
+    for (int i=0;i<btn->toggles_l;++i) {
+        if (btn->toggles[i]==light) {
+            return true;
+        }
+    }
+    return false;
+}
+
 bool m_lights_on(Machine *m) {
     for (int i=0;i<m->lights_l;++i) {
         if (m->lights[i]!=m->lights1[i]) return false;
@@ -79,19 +90,9 @@ void m_btn_press_many(Machine *m, int comb_l, int comb[comb_l]) {
 
 bool try_combination(Machine *m, int comb_l, int comb[comb_l], int p) {
     if (p==comb_l) {
-        /*printf("combination: ");
-        for (int i=0;i<comb_l;++i) printf("%d", comb[i]);
-        printf("\n");*/
         Machine m1 = *m;
-        //m_print(&m1);
         m_btn_press_many(&m1, comb_l, comb);
-        //puts("after:");
-        //m_print(&m1);
-        if (m_lights_on(&m1)) {
-            //puts("ok");
-            return true;
-        }
-        //return m_lights_on(&m1);
+        if (m_lights_on(&m1)) return true;
         return false;
     }
     for (int i=0;i<m->buttons_l;++i) {
@@ -109,6 +110,76 @@ bool m_try_start(Machine m, int max_presses) {
     return try_combination(&m, max_presses, comb, 0);
 }
 
+int64_t solve_glpk(Machine *m) {
+    int btnl = m->buttons_l;
+    int cntl = m->joltages_l;
+    // matrix of buttons/counters
+    //int *matbc = malloc(sizeof(int) * btnl * cntl);
+    int matbc[btnl][cntl];
+    for (int b=0;b<btnl;++b) {
+        for (int c=0;c<cntl;++c) {
+            matbc[b][c] = btn_lights(&m->buttons[b], c) ? 1 : 0;
+        }
+    }
+
+    for (int b=0;b<btnl;++b) {
+        for (int c=0;c<cntl;++c) {
+            putchar(printf("%2d", matbc[b][c]));
+        }
+        printf("\n");
+    }
+
+    glp_prob *prob = glp_create_prob();
+    glp_set_prob_name(prob, "aoc2025_d10p2");
+    glp_set_obj_dir(prob, GLP_MIN);
+
+    glp_add_rows(prob, cntl);
+    for (int i=0;i<cntl;++i) {
+        glp_set_row_bnds(prob, i+1, GLP_FX, m->joltages[i], 0); // last arg = m->joltages[i] too?
+    }
+    glp_add_cols(prob, btnl);
+    for (int i=0;i<btnl;++i) {
+        glp_set_col_bnds(prob, i+1, GLP_LO, 0.0, 0.0);
+        glp_set_col_kind(prob, i+1, GLP_IV);
+        glp_set_obj_coef(prob, i+1, 1.0);
+    }
+    int ia[btnl*cntl+1]; // GLPK counts arrays from 1
+    int ja[btnl*cntl+1];
+    double ar[btnl*cntl+1];
+    int k = 1;
+    for (int i=1;i<=cntl;++i) {
+        for (int j=1;j<=btnl;++j) {
+            ia[k] = i;
+            ja[k] = j;
+            ar[k++] = matbc[j-1][i-1];
+        }
+    }
+printf("x: %d, y: %d\n", cntl, btnl);
+    printf("k: %d\n", k);
+    printf("ia:");
+    for (int i=1;i<k;++i) printf(" %d", ia[i]);
+    printf("\n");
+    printf("ja:");
+    for (int i=1;i<k;++i) printf(" %d", ja[i]);
+    printf("\n");
+    printf("ar:");
+    for (int i=1;i<k;++i) printf(" %.0f", ar[i]);
+    printf("\n");
+
+    glp_load_matrix(prob, btnl*cntl, ia, ja, ar);
+
+    glp_iocp param;
+    glp_init_iocp(&param);
+    param.msg_lev = GLP_MSG_OFF;
+    param.presolve = GLP_ON;
+
+    glp_intopt(prob, &param);
+    int64_t ret = glp_mip_obj_val(prob);
+    printf("ret: %"PRIi64"\n", ret);
+    glp_delete_prob(prob);
+    return ret;
+}
+
 int main(void) {
     Machine machines[180] = {0};
     int machines_l = 0;
@@ -139,17 +210,16 @@ int main(void) {
     int64_t part1 = 0;
     int64_t part2 = 0;
     for (int i=0;i<machines_l;++i) {
-        printf("---- Machine %p ----\n", &machines[i]);
-        printf("%d buttons\n", machines[i].buttons_l);
-        m_print(&machines[i]);
+        //printf("---- Machine %p ----\n", &machines[i]);
+        //printf("%d buttons\n", machines[i].buttons_l);
+        //m_print(&machines[i]);
         for (int j=1;j<=20;++j) {
-            //printf("try start %i with %d button presses\n", i, j);
             if (m_try_start(machines[i], j)) {
-                //printf("%d presses start ok\n", j);
                 part1 += j;
                 break;
             }
         }
+        part2 += solve_glpk(&machines[i]);
     }
     printf("p1: %"PRIi64"\np2: %"PRIi64"\n", part1, part2);
     return 0;