advent2025

Advent of Code 2025 Solutions
git clone git://bsandro.tech/advent2025
Log | Files | Refs | README | LICENSE

day10.c (4039B)

      1 #include <stdio.h>
      2 #include <stdbool.h>
      3 #include <stdlib.h>
      4 #include <limits.h>
      5 #include <inttypes.h>
      6 #include <glpk.h>
      7 #include "cputime.h"
      8 
      9 #define BUF_SIZE 256
     10 #define MAX_TRIES 20
     11 
     12 static int btoi(int bufl, char buf[bufl]) {
     13     int num = 0;
     14     for (int i=0;i<bufl;++i) num = num*10+(buf[i]-'0');
     15     return num;
     16 }
     17 
     18 typedef struct {
     19     uint16_t indicators;
     20     int buttons_l;
     21     uint16_t buttons[16];
     22     int joltages_l;
     23     int joltages[16];
     24 } Machine;
     25 
     26 static void m_indicators_add(Machine *m, int bufl, char buf[bufl]) {
     27     for (int i=0;i<bufl;++i)
     28         if (buf[i]=='#')
     29             m->indicators |= 1<<i;
     30 }
     31 
     32 static void m_buttons_add(Machine *m, int bufl, char buf[bufl]) {
     33     int b = m->buttons_l++;
     34     for (int i=0;i<bufl;++i)
     35         m->buttons[b] |= 1<<(buf[i]-'0');
     36 }
     37 
     38 static void m_joltage_add(Machine *m, int jolt) {
     39     m->joltages[m->joltages_l++] = jolt;
     40 }
     41 
     42 static bool try_combination(Machine *m, int comb_l, uint16_t comb[comb_l], int p) {
     43     if (p==comb_l) {
     44         uint16_t c = 0;
     45         for (int i=0;i<comb_l;++i) c ^= comb[i];
     46         return m->indicators==c;
     47     }
     48     for (int i=0;i<m->buttons_l;++i) {
     49         uint16_t btn = m->buttons[i];
     50         if (p>0&&comb[p-1]==btn) continue; // do not press same button twice in a row
     51         comb[p] = btn;
     52         if (try_combination(m, comb_l, comb, p+1)) return true;
     53     }
     54     return false;
     55 }
     56 
     57 static int64_t solve_glpk(Machine *m) {
     58     int btnl = m->buttons_l;
     59     int cntl = m->joltages_l;
     60     int matbc[btnl][cntl]; // matrix of buttons/counters
     61     for (int b=0;b<btnl;++b) {
     62         for (int c=0;c<cntl;++c) {
     63             uint16_t i = 1<<c;
     64             matbc[b][c] = (m->buttons[b]&i)==0 ? 0 : 1;
     65         }
     66     }
     67 
     68     glp_prob *prob = glp_create_prob();
     69     glp_set_prob_name(prob, "aoc2025_d10p2");
     70     glp_set_obj_dir(prob, GLP_MIN);
     71 
     72     glp_add_rows(prob, cntl);
     73     for (int i=0;i<cntl;++i) {
     74         glp_set_row_bnds(prob, i+1, GLP_FX, m->joltages[i], 0);
     75     }
     76     glp_add_cols(prob, btnl);
     77     for (int i=0;i<btnl;++i) {
     78         glp_set_col_bnds(prob, i+1, GLP_LO, 0.0, 0.0);
     79         glp_set_col_kind(prob, i+1, GLP_IV);
     80         glp_set_obj_coef(prob, i+1, 1.0);
     81     }
     82     int ia[btnl*cntl+1]; // GLPK counts arrays from 1
     83     int ja[btnl*cntl+1];
     84     double ar[btnl*cntl+1];
     85     int k = 1;
     86     for (int i=1;i<=cntl;++i) {
     87         for (int j=1;j<=btnl;++j) {
     88             ia[k] = i;
     89             ja[k] = j;
     90             ar[k++] = matbc[j-1][i-1];
     91         }
     92     }
     93     glp_load_matrix(prob, btnl*cntl, ia, ja, ar);
     94     glp_iocp param;
     95     glp_init_iocp(&param);
     96     param.msg_lev = GLP_MSG_OFF;
     97     param.presolve = GLP_ON;
     98     glp_intopt(prob, &param);
     99     int64_t ret = glp_mip_obj_val(prob);
    100     glp_delete_prob(prob);
    101     return ret;
    102 }
    103 
    104 int main(void) {
    105     Machine machines[180] = {0};
    106     int machines_l = 0;
    107     char buf[BUF_SIZE] = {0};
    108     int bufl = 0;
    109     bool parse_joltages = false;
    110     for (int c=getchar();c!=EOF;c=getchar()) {
    111         if (c==']') {
    112             m_indicators_add(&machines[machines_l], bufl, buf);
    113             bufl = 0;
    114         }
    115         else if (c==')') {
    116             m_buttons_add(&machines[machines_l], bufl, buf);
    117             bufl = 0;
    118         }
    119         else if ((c>='0'&&c<='9')||c=='.'||c=='#') {
    120             buf[bufl++] = c;
    121         } else if (c=='\n') {
    122             machines_l++;
    123             bufl = 0;
    124             parse_joltages = false;
    125         } else if (c=='{') {
    126             parse_joltages = true;
    127         } else if (parse_joltages&&(c==','||c=='}')) {
    128             int jolt = btoi(bufl, buf);
    129             m_joltage_add(&machines[machines_l], jolt);
    130             bufl = 0;
    131         }
    132     }
    133     int64_t part1 = 0;
    134     int64_t part2 = 0;
    135     for (int i=0;i<machines_l;++i) {
    136         for (int j=1;j<=MAX_TRIES;++j) {
    137             uint16_t comb[j];
    138             if (try_combination(&machines[i], j, comb, 0)) {
    139                 part1 += j;
    140                 break;
    141             }
    142         }
    143         part2 += solve_glpk(&machines[i]);
    144     }
    145     printf("p1: %"PRIi64"\np2: %"PRIi64"\n", part1, part2);
    146     return 0;
    147 }