puzzle.c (4260B)
1 #define _DEFAULT_SOURCE 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <errno.h> 6 #include <string.h> 7 #include <strings.h> 8 #include <assert.h> 9 #include <ctype.h> 10 #include <stdbool.h> 11 #include <math.h> 12 13 #include "util.h" 14 15 #define STR_LEN 1024 16 #define PATTERNS_LEN 512 17 #define PATTERN_SIZE 9 18 #define PATTERN_WIDTH 3 19 20 struct pic_t { 21 char *pic; 22 int w, h; 23 int def; 24 }; 25 26 char * parse_patterns(const char *str); 27 void parse_pic(struct pic_t *pic, const char *str); 28 void print_pic(struct pic_t *pic); 29 struct pic_t * enhance(struct pic_t *pic, const char *patterns); 30 int make_pattern(const char pixels[PATTERN_SIZE]); 31 int get_pattern(struct pic_t *pic, int x, int y, int def); 32 int count_pixels(struct pic_t *pic); 33 34 void puzzle(const char *filename, long long *result1, long long *result2) { 35 FILE *infile = fopen(filename, "r"); 36 if (infile == NULL) { 37 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 38 return; 39 } 40 41 char buf[STR_LEN] = {0}; 42 unsigned int line_num = 0; 43 char *patterns = NULL; 44 struct pic_t *pic = malloc(sizeof(struct pic_t)); 45 bzero(pic, sizeof(struct pic_t)); 46 47 while (fgets(buf, STR_LEN, infile) != NULL) { 48 if (line_num == 0) { 49 // first line is always patterns 50 patterns = parse_patterns(buf); 51 } else if (line_num > 1) { 52 // initial picture is square 53 assert(buf[0] != '\n'); 54 parse_pic(pic, buf); 55 pic->h = line_num-1; 56 } 57 ++line_num; 58 bzero(buf, STR_LEN); 59 } 60 61 assert(pic->w == pic->h); 62 63 for (int i = 0; i < 50; ++i) { 64 pic = enhance(pic, patterns); 65 if (i == 1) { 66 *result1 = count_pixels(pic); 67 } 68 } 69 70 *result2 = count_pixels(pic); 71 72 free(patterns); 73 free(pic); 74 // mutiny! ignoring feof/ferror. 75 fclose(infile); 76 } 77 78 int count_pixels(struct pic_t *pic) { 79 int cnt = 0; 80 for (int i = 0; i < pic->w * pic->h; ++i) { 81 cnt += pic->pic[i]; 82 } 83 return cnt; 84 } 85 86 int make_pattern(const char pixels[PATTERN_SIZE]) { 87 int p = 0; 88 for (int i = 0; i < PATTERN_SIZE; ++i) { 89 int ind = PATTERN_SIZE-i-1; 90 assert(ind >= 0 && ind < PATTERN_SIZE); 91 p |= (pixels[ind] << i); 92 //printf("bit %d = %d, ind=%d, p=%d\n", i, pixels[ind], ind, p); 93 } 94 return p; 95 } 96 97 struct pic_t * enhance(struct pic_t *pic, const char *patterns) { 98 assert(patterns != NULL); 99 assert(pic != NULL); 100 101 struct pic_t *pic1 = malloc(sizeof(struct pic_t)); 102 assert(pic1 != NULL); 103 bzero(pic1, sizeof(struct pic_t)); 104 static const int growth = 1; 105 pic1->w = pic->w + growth*2; 106 pic1->h = pic->h + growth*2; 107 pic1->pic = calloc(pic1->w * pic1->h, sizeof(char)); 108 assert(pic1->pic != NULL); 109 110 for (int y1 = 0; y1 < pic1->h; ++y1) { 111 for (int x1 = 0; x1 < pic1->w; ++x1) { 112 int p = get_pattern(pic, x1 - growth, y1 - growth, pic->def); 113 assert(p < PATTERNS_LEN); 114 pic1->pic[y1 * pic1->w + x1] = patterns[p]; 115 } 116 } 117 if (patterns[0] == 1 && patterns[511] == 0) { 118 pic1->def = !pic->def; 119 } 120 121 free(pic->pic); 122 free(pic); 123 124 return pic1; 125 } 126 127 int get_pattern(struct pic_t *pic, int x, int y, int def) { 128 assert(pic != NULL); 129 assert(pic->pic != NULL); 130 char p[PATTERN_SIZE] = {0}; 131 memset(&p, def, PATTERN_SIZE); 132 133 for (int dy = -1; dy <= 1; ++dy) { 134 for (int dx = -1; dx <= 1; ++dx) { 135 int index = 3*(dy+1) + (dx+1); 136 int x1 = x+dx; 137 int y1 = y+dy; 138 if (x1 >= 0 && y1 >= 0 && x1 < pic->w && y1 < pic->h) { 139 p[index] = pic->pic[y1 * pic->h + x1]; 140 } 141 } 142 } 143 return make_pattern(p); 144 } 145 146 char * parse_patterns(const char *str) { 147 int len = strlen(str); 148 assert(len-1 == PATTERNS_LEN); 149 char *patterns = calloc(len, sizeof(char)); 150 assert(patterns != NULL); 151 for (int i = 0; i < PATTERNS_LEN; ++i) { 152 if (str[i] == '.') patterns[i] = 0; 153 else if (str[i] == '#') patterns[i] = 1; 154 else break; 155 } 156 return patterns; 157 } 158 159 void parse_pic(struct pic_t *pic, const char *str) { 160 assert(pic != NULL); 161 assert(str != NULL); 162 int len = strlen(str) - 1; 163 assert(len > 0); 164 165 if (pic->pic == NULL) { 166 pic->pic = calloc(len*len, sizeof(char)); 167 assert(pic->pic != NULL); 168 pic->w = len; 169 } 170 171 assert(len == pic->w); 172 173 for (int i = 0; i < len; ++i) { 174 if (str[i] == '.') pic->pic[pic->h * len+i] = 0; 175 else if (str[i] == '#') pic->pic[pic->h * len+i] = 1; 176 } 177 } 178 179 void print_pic(struct pic_t *pic) { 180 for (int y = 0; y < pic->h; ++y) { 181 for (int x = 0; x < pic->w; ++x) { 182 printf("%c", pic->pic[y * pic->h + x] == 1 ? '#' : '.'); 183 } 184 printf("\n"); 185 } 186 }