uppga.c (5089B)
1 #include "common.h" 2 3 static inline void read_stack(stack_u64 *s, char *line) { 4 char *cp = line; 5 uint64_t t; 6 7 while ((cp = sread_next_u64(&t, cp)) != NULL) { 8 stack_u64_push(s, t); 9 } 10 } 11 12 static inline size_t patlen(char *line) { 13 size_t c = 0; 14 while (line[c] == '.' || line[c] == '#' || line[c] == '?') 15 c++; 16 return c; 17 } 18 19 /** 20 * Check if it is possible for pattern in string s of length 21 * n to end with exactly a '#'s. 22 */ 23 static inline int can_end_with(int a, char *s, size_t n) { 24 if (a > (int)n) 25 return 0; 26 27 if (a == 0) { 28 if (n == 0 || s[n - 1] == '.' || s[n - 1] == '?') 29 return 1; 30 return 0; 31 } 32 33 if (s[n - 1] != '?' && s[n - 1] != '#') 34 return 0; 35 36 assert(a > 0); 37 38 return can_end_with(a - 1, s, n - 1); 39 } 40 41 /** 42 * Check if it is possible for pattern in string s of length 43 * n to begin with exactly a '#'s. 44 */ 45 static inline int can_beg_with(int a, char *s, size_t n) { 46 if (a > (int)n) 47 return 0; 48 49 if (a == 0) { 50 if (n == 0 || s[0] == '.' || s[0] == '?') 51 return 1; 52 return 0; 53 } 54 55 if (s[0] != '?' && s[0] != '#') 56 return 0; 57 58 assert(a > 0); 59 60 return can_beg_with(a - 1, &s[1], n - 1); 61 } 62 63 static uint64_t counter(char *t, size_t l, uint64_t *s, size_t n) { 64 size_t i; 65 uint64_t r = UINT64_MAX; 66 67 if (n == 0) { 68 if (l == 0) { 69 r = 1; 70 goto endit; 71 } else { 72 for (i = 0; i < l; i++) { 73 if (t[i] != '.' && t[i] != '?') { 74 r = 0; 75 goto endit; 76 } 77 } 78 r = 1; 79 goto endit; 80 } 81 } 82 83 if (l < 2) { 84 if (l == 0) { 85 assert(n != 0); 86 r = 0; 87 goto endit; 88 } else { 89 assert(l == 1); 90 switch (t[0]) { 91 case '#': 92 if (n == 1 && s[0] == 1) { 93 r = 1; 94 goto endit; 95 } else { 96 r = 0; 97 goto endit; 98 } 99 break; 100 case '.': 101 assert(n != 0); 102 r = 0; 103 goto endit; 104 break; 105 case '?': 106 assert(n != 0); 107 t[0] = '.'; 108 r = counter(t, l, s, n); 109 t[0] = '#'; 110 r += counter(t, l, s, n); 111 t[0] = '?'; 112 goto endit; 113 break; 114 default: 115 assert(t[0] == '#' || t[0] == '.' || t[0] == '?'); 116 } 117 } 118 } 119 120 size_t centrum = (l >> 1); 121 int k, a, b; 122 uint64_t left, right; 123 r = 0; 124 switch (t[centrum]) { 125 case '?': 126 t[centrum] = '.'; 127 r += counter(t, l, s, n); 128 t[centrum] = '#'; 129 r += counter(t, l, s, n); 130 t[centrum] = '?'; // prolly not needed 131 goto endit; 132 break; 133 case '.': 134 for (k = 0; k <= (int)n; k++) { 135 left = counter(t, centrum, s, k); 136 if (left != 0) { 137 r += left * counter(&t[centrum + 1], l - (centrum + 1), &s[k], n - k); 138 } 139 } 140 goto endit; 141 break; 142 case '#': 143 /* DEBUG 144 printf("---> bradgard (l = %zu, n = %zu)\n", l, n); 145 */ 146 for (k = 0; k < (int)n; k++) { 147 // a + b == s[k]-1 148 for (a = 0; a < (int)s[k]; a++) { 149 b = s[k] - 1 - a; 150 151 /* DEBUG 152 printf(">> a = %d, b = %d (KAA = %d, ELL = %zu) \n", a, b, k, l); 153 int cew = can_end_with(a, t, centrum); 154 int cbw = can_beg_with(b, &t[centrum+1], l-(centrum+1)); 155 printf(">> cew = %d, cbw = %d\n", cew, cbw); 156 */ 157 158 if (can_end_with(a, t, centrum) && 159 can_beg_with(b, &t[centrum + 1], l - (centrum + 1))) { 160 if (a < (int)centrum) { 161 left = counter(t, centrum - (a + 1), s, k); 162 } else { 163 assert(a == (int)centrum); 164 left = counter(t, 0, s, k); 165 } 166 167 if (left != 0) { 168 if (b < (int)(l - (centrum + 1))) { 169 right = 170 counter(&t[centrum + 1 + b + 1], l - (centrum + 1 + b + 1), 171 &s[k + 1], n - (k + 1)); 172 } else { 173 assert(b == (int)(l - (centrum + 1))); 174 right = 175 counter(&t[centrum + 1 + b + 1], 0, &s[k + 1], n - (k + 1)); 176 } 177 } 178 179 r += left * right; 180 } 181 } 182 } 183 goto endit; 184 break; 185 default: 186 assert(t[centrum] == '?' || t[centrum] == '.' || t[centrum] == '#'); 187 } 188 189 endit: 190 /* DEBUG 191 for(i = 0; i < l; i++) { 192 printf("%c", t[i]); 193 } 194 if(centrum < l) { 195 printf(" <%zu, %zu> ", centrum, l); 196 } 197 printf(" ["); 198 for(i = 0; i < n; i++) { 199 printf(" %llu", s[i]); 200 } 201 printf("]"); 202 printf(" -> %llu\n", r); 203 */ 204 return r; 205 } 206 207 int main(int argc, char **argv) { 208 char **lines; 209 size_t nlines = readlines(&lines, "input"); 210 printf("#lines: %zu\n", nlines); 211 212 size_t i; 213 stack_u64 tmp; 214 stack_u64_init(&tmp); 215 uint64_t summa = 0; 216 for (i = 0; i < nlines; i++) { 217 // for(i = 0; i < 1; i++) { 218 while (tmp.nmemb > 0) 219 stack_u64_pop(&tmp); 220 221 size_t l = patlen(lines[i]); 222 read_stack(&tmp, lines[i]); 223 224 uint64_t cs = counter(lines[i], l, tmp.data, tmp.nmemb); 225 printf("RESULT = %llu\n", cs); 226 summa += cs; 227 } 228 229 /** 230 * Todo: Optimize by having second branch to be conditional 231 * on the result of the first when product is to be 232 * calculated. 233 */ 234 235 printf("%llu\n", summa); 236 }