common.c (6720B)
1 #include "common.h" 2 3 static size_t norder = 4; 4 static char order[4] = "NSWE"; 5 6 space make_space(const size_t npos) { 7 space r; 8 r.h = 2 * (npos + 200); 9 r.w = 2 * (npos + 200); 10 r.hoffs = npos + 100; 11 r.woffs = npos + 100; 12 13 r.data = malloc(r.h * r.w * sizeof(*r.data)); 14 15 return r; 16 } 17 18 void set_space(space s, const int64_t x, const int64_t y, const uint8_t val) { 19 assert((y + ((int64_t)s.hoffs)) >= 0); 20 assert((y + ((int64_t)s.hoffs)) < s.h); 21 assert((x + ((int64_t)s.woffs)) >= 0); 22 assert((x + ((int64_t)s.woffs)) < s.w); 23 s.data[(y + ((int64_t)s.hoffs)) * s.w + (x + ((int64_t)s.woffs))] = val; 24 } 25 26 static inline void inc_space(space s, const int64_t x, const int64_t y) { 27 assert((y + ((int64_t)s.hoffs)) >= 0); 28 assert((y + ((int64_t)s.hoffs)) < s.h); 29 assert((x + ((int64_t)s.woffs)) >= 0); 30 assert((x + ((int64_t)s.woffs)) < s.w); 31 s.data[(y + ((int64_t)s.hoffs)) * s.w + (x + ((int64_t)s.woffs))]++; 32 } 33 34 uint8_t get_space(space s, const int64_t x, const int64_t y) { 35 assert((y + ((int64_t)s.hoffs)) >= 0); 36 assert((y + ((int64_t)s.hoffs)) < s.h); 37 assert((x + ((int64_t)s.woffs)) >= 0); 38 assert((x + ((int64_t)s.woffs)) < s.w); 39 return s.data[(y + ((int64_t)s.hoffs)) * s.w + (x + ((int64_t)s.woffs))]; 40 } 41 42 static inline void clear_spaces(space s, const pos *p, const size_t npos) { 43 size_t i; 44 for (i = 0; i < npos; i++) { 45 set_space(s, p[i].x - 1, p[i].y - 1, 0); 46 set_space(s, p[i].x - 1, p[i].y, 0); 47 set_space(s, p[i].x - 1, p[i].y + 1, 0); 48 49 set_space(s, p[i].x, p[i].y - 1, 0); 50 set_space(s, p[i].x, p[i].y, 0); 51 set_space(s, p[i].x, p[i].y + 1, 0); 52 53 set_space(s, p[i].x + 1, p[i].y - 1, 0); 54 set_space(s, p[i].x + 1, p[i].y, 0); 55 set_space(s, p[i].x + 1, p[i].y + 1, 0); 56 } 57 58 for (i = 0; i < npos; i++) { 59 set_space(s, p[i].x, p[i].y, 128); 60 } 61 } 62 63 int none_around(space s, pos p) { 64 assert(get_space(s, p.x, p.y) == 128); 65 return get_space(s, p.x - 1, p.y - 1) < 128 && 66 get_space(s, p.x, p.y - 1) < 128 && 67 get_space(s, p.x + 1, p.y - 1) < 128 && 68 get_space(s, p.x - 1, p.y) < 128 && get_space(s, p.x + 1, p.y) < 128 && 69 get_space(s, p.x - 1, p.y + 1) < 128 && 70 get_space(s, p.x, p.y + 1) < 128 && 71 get_space(s, p.x + 1, p.y + 1) < 128; 72 } 73 74 void propose_moves(space s, char *mvs, const pos *p, const size_t npos, 75 const size_t round) { 76 clear_spaces(s, p, npos); 77 78 size_t i, j; 79 for (i = 0; i < npos; i++) { 80 if (none_around(s, p[i])) { 81 mvs[i] = 'X'; 82 continue; 83 } 84 mvs[i] = 'X'; 85 for (j = 0; j < norder; j++) { 86 char dir = order[(j + round) % norder]; 87 if (dir == 'N') { 88 if (get_space(s, p[i].x - 1, p[i].y - 1) != 128 && 89 get_space(s, p[i].x, p[i].y - 1) != 128 && 90 get_space(s, p[i].x + 1, p[i].y - 1) != 128) { 91 inc_space(s, p[i].x, p[i].y - 1); 92 assert(get_space(s, p[i].x, p[i].y - 1) <= 4); 93 mvs[i] = dir; 94 break; 95 } 96 } else if (dir == 'S') { 97 if (get_space(s, p[i].x - 1, p[i].y + 1) != 128 && 98 get_space(s, p[i].x, p[i].y + 1) != 128 && 99 get_space(s, p[i].x + 1, p[i].y + 1) != 128) { 100 inc_space(s, p[i].x, p[i].y + 1); 101 assert(get_space(s, p[i].x, p[i].y + 1) <= 4); 102 mvs[i] = dir; 103 break; 104 } 105 } else if (dir == 'E') { 106 if (get_space(s, p[i].x + 1, p[i].y - 1) != 128 && 107 get_space(s, p[i].x + 1, p[i].y) != 128 && 108 get_space(s, p[i].x + 1, p[i].y + 1) != 128) { 109 inc_space(s, p[i].x + 1, p[i].y); 110 assert(get_space(s, p[i].x + 1, p[i].y) <= 4); 111 mvs[i] = dir; 112 break; 113 } 114 } else if (dir == 'W') { 115 if (get_space(s, p[i].x - 1, p[i].y - 1) != 128 && 116 get_space(s, p[i].x - 1, p[i].y) != 128 && 117 get_space(s, p[i].x - 1, p[i].y + 1) != 128) { 118 inc_space(s, p[i].x - 1, p[i].y); 119 assert(get_space(s, p[i].x - 1, p[i].y) <= 4); 120 mvs[i] = dir; 121 break; 122 } 123 } else { 124 fprintf(stderr, "ERROR! Unknown dir %c\n", dir); 125 exit(1); 126 } 127 } 128 assert(mvs[i] == 'N' || mvs[i] == 'S' || mvs[i] == 'E' || mvs[i] == 'W' || 129 mvs[i] == 'X'); 130 } 131 } 132 133 int make_moves(pos *p, const space s, const char *mvs, const size_t npos) { 134 int moved = 0; 135 size_t i; 136 for (i = 0; i < npos; i++) { 137 if (mvs[i] != 'X') { 138 switch (mvs[i]) { 139 case 'N': 140 if (get_space(s, p[i].x, p[i].y - 1) == 1) { 141 p[i].y--; 142 moved = 1; 143 } 144 break; 145 case 'S': 146 if (get_space(s, p[i].x, p[i].y + 1) == 1) { 147 p[i].y++; 148 moved = 1; 149 } 150 break; 151 case 'E': 152 if (get_space(s, p[i].x + 1, p[i].y) == 1) { 153 p[i].x++; 154 moved = 1; 155 } 156 break; 157 case 'W': 158 if (get_space(s, p[i].x - 1, p[i].y) == 1) { 159 p[i].x--; 160 moved = 1; 161 } 162 break; 163 default: 164 fprintf(stderr, "ERROR! Unknown dir (in make_moves) %c\n", mvs[i]); 165 exit(1); 166 } 167 } 168 } 169 170 return moved; 171 } 172 173 void print_board(const space s, const pos *p, const size_t npos) { 174 size_t i, j, k; 175 for (i = 0; i < s.h; i++) { 176 for (j = 0; j < s.w; j++) { 177 int64_t y = (int64_t)i - s.hoffs; 178 int64_t x = (int64_t)j - s.woffs; 179 int occup = 0; 180 for (k = 0; k < npos; k++) { 181 if (x == p[k].x && y == p[k].y) { 182 occup = k + 1; 183 break; 184 } 185 } 186 187 if (occup) { 188 printf("#"); 189 } else { 190 printf("."); 191 } 192 } 193 printf("\n"); 194 } 195 } 196 197 static inline void getminmax(int64_t *vals, const pos *p, const size_t npos) { 198 size_t i; 199 vals[0] = INT64_MAX; 200 vals[1] = INT64_MIN; 201 vals[2] = INT64_MAX; 202 vals[3] = INT64_MIN; 203 for (i = 0; i < npos; i++) { 204 if (p[i].x < vals[0]) 205 vals[0] = p[i].x; 206 if (p[i].x > vals[1]) 207 vals[1] = p[i].x; 208 if (p[i].y < vals[2]) 209 vals[2] = p[i].y; 210 if (p[i].y > vals[3]) 211 vals[3] = p[i].y; 212 } 213 } 214 215 int64_t count_empty(const pos *p, const size_t npos) { 216 int64_t bounds[4]; 217 getminmax(bounds, p, npos); 218 219 return (bounds[1] - bounds[0] + 1) * (bounds[3] - bounds[2] + 1) - 220 ((int64_t)npos); 221 } 222 223 pos *parse(size_t *npos, char **lines, size_t nlines) { 224 size_t i, j; 225 size_t cols = strlen(lines[0]) - 1; 226 227 size_t ntmp = 0; 228 pos tmp[nlines * cols]; 229 230 for (i = 0; i < nlines; i++) { 231 for (j = 0; j < cols; j++) { 232 if (lines[i][j] == '#') { 233 tmp[ntmp].x = (int64_t)j; 234 tmp[ntmp].y = (int64_t)i; 235 ntmp++; 236 } 237 } 238 } 239 240 pos *r = malloc(ntmp * sizeof(*r)); 241 memcpy(r, tmp, ntmp * sizeof(*r)); 242 *npos = ntmp; 243 244 return r; 245 }