puzzle.c (6785B)
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 <stdbool.h> 9 #include <assert.h> 10 #include <time.h> 11 12 #include "util.h" 13 14 #define STR_LEN 1024 15 #define DIGITS_NUM 10 16 #define SEGMENTS_NUM 8 // technically 7 but we need additional space for '\0' 17 #define PUZZLE_NUMBERS 4 // the amount of puzzle numbers in 2nd part of each string 18 19 #define SEGMENT_A 0b00000001 20 #define SEGMENT_B 0b00000010 21 #define SEGMENT_C 0b00000100 22 #define SEGMENT_D 0b00001000 23 #define SEGMENT_E 0b00010000 24 #define SEGMENT_F 0b00100000 25 #define SEGMENT_G 0b01000000 26 27 struct digit_t { 28 unsigned short segments; // bit mask 29 size_t len; // cached strlen(str) 30 int digit; // deduced digit, -1 is "not known" 31 }; 32 33 struct digit_t make_digit(const char *str); 34 unsigned short make_segments(const char *str); 35 struct digit_t *get_by_digit(struct digit_t *digits, int digit); 36 struct digit_t *get_by_segments(struct digit_t *digits, unsigned short segments); 37 void deduce_digits(struct digit_t *digits); 38 void deduce_simple_digits(struct digit_t *digits); 39 void deduce_three(struct digit_t *digits); 40 void deduce_zero(struct digit_t *digits); 41 void deduce_six(struct digit_t *digits); 42 void deduce_five(struct digit_t *digits); 43 void deduce_nine(struct digit_t *digits); 44 void deduce_two(struct digit_t *digits); 45 46 void puzzle(const char *filename, long long *result1, long long *result2) { 47 FILE *infile = fopen(filename, "r"); 48 if (infile == NULL) { 49 fprintf(stderr, "fopen() error: %s\n", strerror(errno)); 50 return; 51 } 52 53 char buf[STR_LEN] = {0}; 54 unsigned int line_num = 0; 55 56 *result1 = 0; 57 *result2 = 0; 58 59 // lets parse it like it's 19.99 (IQ) 60 while (fgets(buf, STR_LEN, infile) != NULL) { 61 // first 10 strings are encoded digits, last 4 after | are puzzle numbers 62 char *tmp = strndup(buf, STR_LEN); 63 assert(tmp != NULL); 64 char *token = NULL; 65 int digits_num = 0; 66 int puzzle_num = 0; 67 68 struct digit_t digits[DIGITS_NUM]; 69 unsigned short puzzles[PUZZLE_NUMBERS]; 70 71 while ((token = strsep(&tmp, " \n")) != NULL) { 72 if (*token == '|') continue; 73 74 if (digits_num < DIGITS_NUM) { 75 digits[digits_num++] = make_digit(token); 76 } else if (puzzle_num < PUZZLE_NUMBERS) { 77 size_t len = strlen(token); 78 assert(len > 0 && len < SEGMENTS_NUM); 79 puzzles[puzzle_num++] = make_segments(token); 80 } 81 } 82 83 deduce_digits(digits); 84 85 char answers_str[PUZZLE_NUMBERS + 1] = {0}; 86 for (int i = 0; i < PUZZLE_NUMBERS; ++i) { 87 struct digit_t *digit = get_by_segments(digits, puzzles[i]); 88 assert(digit != NULL); 89 answers_str[i] = digit->digit + '0'; 90 if (digit->digit == 1 || digit->digit == 4 || digit->digit == 7 || digit->digit == 8) { 91 (*result1)++; 92 } 93 } 94 unsigned long solution = atol(answers_str); 95 96 *result2 += solution; 97 98 ++line_num; 99 bzero(buf, STR_LEN); 100 free(tmp); 101 } 102 103 // mutiny! ignoring feof/ferror. 104 fclose(infile); 105 } 106 107 struct digit_t make_digit(const char *str) { 108 assert(str != NULL); 109 size_t len = strlen(str); 110 assert(len > 0 && len < SEGMENTS_NUM); 111 struct digit_t digit = { .segments = 0, .len = len, .digit = -1 }; 112 digit.segments = make_segments(str); 113 return digit; 114 } 115 116 unsigned short make_segments(const char *str) { 117 assert(str != NULL); 118 size_t len = strlen(str); 119 assert(len > 0 && len < SEGMENTS_NUM); 120 unsigned short segments = 0; 121 for (size_t i = 0; i < len; ++i) { 122 switch (str[i]) { 123 case 'a': 124 segments |= SEGMENT_A; 125 break; 126 case 'b': 127 segments |= SEGMENT_B; 128 break; 129 case 'c': 130 segments |= SEGMENT_C; 131 break; 132 case 'd': 133 segments |= SEGMENT_D; 134 break; 135 case 'e': 136 segments |= SEGMENT_E; 137 break; 138 case 'f': 139 segments |= SEGMENT_F; 140 break; 141 case 'g': 142 segments |= SEGMENT_G; 143 break; 144 } 145 } 146 return segments; 147 } 148 149 //@todo caching or hashtable 150 struct digit_t *get_by_digit(struct digit_t *digits, int digit) { 151 for (int i = 0; i < DIGITS_NUM; ++i) { 152 if (digits[i].digit == digit) return &digits[i]; 153 } 154 return NULL; 155 } 156 157 struct digit_t *get_by_segments(struct digit_t *digits, unsigned short segments) { 158 for (int i = 0; i < DIGITS_NUM; ++i) { 159 if (digits[i].segments == segments) return &digits[i]; 160 } 161 return NULL; 162 } 163 164 void deduce_digits(struct digit_t *digits) { 165 assert(digits != NULL); 166 167 // 1) simple digits 168 deduce_simple_digits(digits); 169 170 // 2) 6sym string that misses any 2sym segments is 6 171 deduce_six(digits); 172 173 // 3) 5sym string that has all segments from 7 is 3 174 deduce_three(digits); 175 176 // 4) 6sym that doesn't have all segments from 3 is 0 177 deduce_zero(digits); 178 179 // 5) remaining 6sym is 9 180 deduce_nine(digits); 181 182 // 6) 5sym that has all segments from 9 is 5 183 deduce_five(digits); 184 185 // 7) remaining 5sym one is 2 186 deduce_two(digits); 187 188 // 8) profit! 189 } 190 191 void deduce_simple_digits(struct digit_t *digits) { 192 assert(digits != NULL); 193 for (int i = 0; i < DIGITS_NUM; ++i) { 194 if (digits[i].len == 2) digits[i].digit = 1; 195 else if (digits[i].len == 3) digits[i].digit = 7; 196 else if (digits[i].len == 4) digits[i].digit = 4; 197 else if (digits[i].len == 7) digits[i].digit = 8; 198 } 199 } 200 201 //@todo unify? 202 203 void deduce_six(struct digit_t *digits) { 204 assert(digits != NULL); 205 for (int i = 0; i < DIGITS_NUM; ++i) { 206 if (digits[i].len == 6 && digits[i].digit == -1) { 207 struct digit_t *one = get_by_digit(digits, 1); 208 assert(one != NULL); 209 if ((one->segments & digits[i].segments) != one->segments) { 210 digits[i].digit = 6; 211 break; 212 } 213 } 214 } 215 } 216 217 void deduce_three(struct digit_t *digits) { 218 assert(digits != NULL); 219 for (int i = 0; i < DIGITS_NUM; ++i) { 220 if (digits[i].len == 5 && digits[i].digit == -1) { 221 struct digit_t *seven = get_by_digit(digits, 7); 222 if ((digits[i].segments | seven->segments) == digits[i].segments) { 223 digits[i].digit = 3; 224 break; 225 } 226 } 227 } 228 } 229 230 void deduce_zero(struct digit_t *digits) { 231 assert(digits != NULL); 232 for (int i = 0; i < DIGITS_NUM; ++i) { 233 if (digits[i].len == 6 && digits[i].digit == -1) { 234 struct digit_t *three = get_by_digit(digits, 3); 235 if ((digits[i].segments & three->segments) != three->segments) { 236 digits[i].digit = 0; 237 break; 238 } 239 } 240 } 241 } 242 243 void deduce_nine(struct digit_t *digits) { 244 assert(digits != NULL); 245 for (int i = 0; i < DIGITS_NUM; ++i) { 246 if (digits[i].len == 6 && digits[i].digit == -1) { 247 digits[i].digit = 9; 248 break; 249 } 250 } 251 } 252 253 void deduce_five(struct digit_t *digits) { 254 assert(digits != NULL); 255 for (int i = 0; i < DIGITS_NUM; ++i) { 256 if (digits[i].len == 5 && digits[i].digit == -1) { 257 struct digit_t *nine = get_by_digit(digits, 9); 258 if ((nine->segments | digits[i].segments) == nine->segments) { 259 digits[i].digit = 5; 260 break; 261 } 262 } 263 } 264 } 265 266 void deduce_two(struct digit_t *digits) { 267 assert(digits != NULL); 268 for (int i = 0; i < DIGITS_NUM; ++i) { 269 if (digits[i].len == 5 && digits[i].digit == -1) { 270 digits[i].digit = 2; 271 break; 272 } 273 } 274 }