easters

commit 5c2bd8c9060975d23627e7152cb4f7889a9be2d9
parent e08587423968f7d701a09f425b39b3841f8b4baf
Author: bsandro <email@bsandro.tech>
Date:   Mon, 12 Jan 2026 20:50:11 +0200

Part 1

Diffstat:
M
sunday.c
 | 
113
++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------------------

1 file changed, 81 insertions(+), 32 deletions(-)
diff --git a/sunday.c b/sunday.c
@@ -7,6 +7,8 @@ typedef struct {
     char grid[12][12];
     int w;
     int h;
+    int xmines[12];
+    int ymines[12];
 } Map;
 
 typedef struct {
@@ -17,7 +19,7 @@ typedef struct {
 typedef struct {
     Vec2 data[4];
     int len;
-} PossibleMines;
+} ArVec2;
 
 static Vec2 mine_area[] = {
     {.x= 0,.y=-1},
@@ -32,15 +34,15 @@ static Vec2 heat_area[] = {
     {.x=-1,.y= 1},{.x=0,.y= 1},{.x=1,.y= 1}
 };
 
-PossibleMines findPossibleMines(Map map, Vec2 nodule) {
-    PossibleMines mines = {0};
+ArVec2 findPossibleMines(Map *m, Vec2 nodule) {
+    ArVec2 mines = {0};
     for (int i=0;i<LEN(mine_area);++i) {
         Vec2 p = { .x=nodule.x+mine_area[i].x, .y=nodule.y+mine_area[i].y };
-        if (p.x>=0&&p.x<map.w&&p.y>=0&&p.y<map.h&&map.grid[p.y][p.x]=='.') {
+        if (p.x>=0&&p.x<m->w&&p.y>=0&&p.y<m->h&&m->grid[p.y][p.x]=='.') {
             bool ok = true;
             for (int j=0;j<LEN(heat_area);++j) {
                 Vec2 h = { .x=p.x+heat_area[j].x, .y=p.y+heat_area[j].y };
-                if (h.x>=0&&h.x<map.w&&h.y>=0&&h.y<map.h&&map.grid[h.y][h.x]=='M') {
+                if (h.x>=0&&h.x<m->w&&h.y>=0&&h.y<m->h&&m->grid[h.y][h.x]=='M') {
                     ok = false;
                     break;
                 }
@@ -55,18 +57,85 @@ void PrintVec2(Vec2 p) {
     printf("{.x:%d,.y:%d}\n", p.x, p.y);
 }
 
+int countMinesX(Map *m, int x) {
+    int r = 0;
+    for (int y=0;y<m->h;++y) {
+        if (m->grid[y][x]=='M') r++;
+    }
+    return r;
+}
+
+int countMinesY(Map *m, int y) {
+    int r = 0;
+    for (int x=0;x<m->w;++x) {
+        if (m->grid[y][x]=='M') r++;
+    }
+    return r;
+}
+
+void printMap(Map *m) {
+    for (int y=0;y<m->h;++y) {
+        for (int x=0;x<m->w;++x) {
+            printf("%c", m->grid[y][x]);
+        }
+        printf("\n");
+    }
+}
+
+bool validateMap(Map *m) {
+    bool ok = true;
+    for (int x=0;x<m->w;++x) {
+        if (countMinesX(m, x)!=m->xmines[x]) {
+            ok = false;
+            break;
+        }
+    }
+    if (!ok) return false;
+    for (int y=0;y<m->h;++y) {
+        if (countMinesY(m, y)!=m->ymines[y]) {
+            ok = false;
+            break;
+        }
+    }
+    return ok;
+}
+
+int calcChecksum(Map *m) {
+    int r = 0;
+    for (int y=0;y<m->h;++y) {
+        for (int x=0;x<m->w;++x) {
+            if (m->grid[y][x]=='M') {
+                r += (y+1)^(x+1);
+            }
+        }
+    }
+    return r;
+}
+
+int findMines(Map *m, Vec2 *nodules, int nodules_s) {
+    if (nodules_s==0&&validateMap(m)) {
+        return calcChecksum(m);
+    }
+    ArVec2 mines = findPossibleMines(m, nodules[0]);
+    for (int i=0;i<mines.len;++i) {
+        Map m1 = *m;
+        m1.grid[mines.data[i].y][mines.data[i].x] = 'M';
+        int csum = findMines(&m1, nodules+1, nodules_s-1);
+        if (csum!=0) return csum;
+    }
+    return 0;
+}
+
 int main(void) {
     Map map = {0};
-    int xmines[12] = {0};
-    int ymines[12] = {0};
     Vec2 nodules[50] = {0};
     int nodules_s = 0;
     for (char c=getchar();c!=EOF;c=getchar()) {
         if (c>='0'&&c<='9') {
             if (map.h==0) {
-                xmines[map.w++]=c-'0';
+                map.xmines[map.w++]=c-'0';
             } else {
-                ymines[map.h-1]=c-'0';
+                map.ymines[map.h-1]=c-'0';
                 map.w=0;
             }
         } else if (c=='.'||c=='O'||c=='G') {
@@ -76,35 +145,15 @@ int main(void) {
         }
     }
     map.h-=1;
-    printf("map w:%d,h:%d\n", map.w, map.h);
     for (int y=0;y<map.h;++y) {
         for (int x=0;x<map.w;++x) {
-            printf("%c", map.grid[y][x]);
             if (map.grid[y][x]=='O') {
                 nodules[nodules_s++] = (Vec2){ .x=x,.y=y };
             }
         }
-        printf("\n");
-    }
-    puts("ymines:");
-    for (int y=0;y<map.h;++y) {
-        printf("%d,", ymines[y]);
-    }
-    printf("\n");
-    puts("xmines:");
-    for (int x=0;x<map.w;++x) {
-        printf("%d,", xmines[x]);
-    }
-    printf("\n");
-    printf("%d nodules:\n", nodules_s);
-    for (int i=0;i<nodules_s;++i) {
-        PrintVec2(nodules[i]);
-    }
-    PossibleMines mines0 = findPossibleMines(map, nodules[0]);
-    printf("%d possible mines for ", mines0.len);
-    PrintVec2(nodules[0]);
-    for (int i=0;i<mines0.len;++i) {
-        PrintVec2(mines0.data[i]);
     }
+
+    int cs = findMines(&map, nodules, nodules_s);
+    printf("part 1: %d\n", cs);
     return 0;
 }