easters

sunday.c (3708B)

---

 #include <stdio.h>
 #include <stdbool.h>
 #include "cputime.h"
 #define LEN(x) (sizeof(x)/sizeof(*x))
 
 typedef struct {
     char grid[12][12];
     int w;
     int h;
     int xmines[12];
     int ymines[12];
 } Map;
 
 typedef struct {
     int x;
     int y;
 } Vec2;
 
 typedef struct {
     Vec2 data[4];
     int len;
 } ArVec2;
 
 static Vec2 mine_area[] = {
     {.x= 0,.y=-1},
     {.x=-1,.y= 0},
     {.x= 1,.y= 0},
     {.x= 0,.y= 1},
 };
 
 static Vec2 heat_area[] = {
     {.x=-1,.y=-1},{.x=0,.y=-1},{.x=1,.y=-1},
     {.x=-1,.y= 0},             {.x=1,.y= 0},
     {.x=-1,.y= 1},{.x=0,.y= 1},{.x=1,.y= 1}
 };
 
 ArVec2 findPossibleMines(Map *m, Vec2 nodule) {
     ArVec2 mines = {0};
     for (size_t 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<m->w&&p.y>=0&&p.y<m->h&&m->grid[p.y][p.x]=='.') {
             bool ok = true;
             for (size_t 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<m->w&&h.y>=0&&h.y<m->h&&m->grid[h.y][h.x]=='M') {
                     ok = false;
                     break;
                 }
             }
             if (ok) mines.data[mines.len++] = p;
         }
     }
     return mines;
 }
 
 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;
 }
 
 bool validateMap(Map *m, int mul) {
     bool ok = true;
     for (int x=0;x<m->w;++x) {
         if (countMinesX(m, x)!=m->xmines[x]*mul) {
             ok = false;
             break;
         }
     }
     if (!ok) return false;
     for (int y=0;y<m->h;++y) {
         if (countMinesY(m, y)!=m->ymines[y]*mul) {
             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, int mul) {
     if (nodules_s==0&&validateMap(m, mul)) {
         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, mul);
         if (csum!=0) return csum;
     }
     return 0;
 }
 
 int main(void) {
     Map map = {0};
     for (int c=getchar();c!=EOF;c=getchar()) {
         if (c>='0'&&c<='9') {
             if (map.h==0) {
                 map.xmines[map.w++]=c-'0';
             } else {
                 map.ymines[map.h-1]=c-'0';
                 map.w=0;
             }
         } else if (c=='.'||c=='O'||c=='G') {
             map.grid[map.h-1][map.w++]=c;
         } else if (c=='\n'&&map.w>0) {
             map.h++;
         }
     }
     map.h-=1;
     Vec2 nodules1[32] = {0};
     Vec2 nodules2[32] = {0};
     int nodules1_s = 0;
     int nodules2_s = 0;
     for (int y=0;y<map.h;++y) {
         for (int x=0;x<map.w;++x) {
             char c = map.grid[y][x];
             if (c=='O') {
                 nodules1[nodules1_s++] = (Vec2){ .x=x,.y=y };
                 nodules2[nodules2_s++] = (Vec2){ .x=x,.y=y };
             }
             if (c=='G') {
                 nodules2[nodules2_s++] = (Vec2){ .x=x,.y=y };
             }
         }
     }
 
     printf("part 1: %d\n", findMines(&map, nodules1, nodules1_s, 1));
     printf("part 2: %d\n", findMines(&map, nodules2, nodules2_s, 2));
     return 0;
 }