uppgb.c (3940B)
1 #include "common.h" 2 3 #define MAXNUM 1000 4 #define NITS (1000000000L) 5 6 static inline void move_south(char **grid, size_t nr, size_t nc, size_t r, 7 size_t c) { 8 if (grid[r][c] != 'O') 9 return; 10 if (r == nr - 1) 11 return; 12 13 if (grid[r + 1][c] == '.') { 14 grid[r + 1][c] = 'O'; 15 grid[r][c] = '.'; 16 move_south(grid, nr, nc, r + 1, c); 17 } 18 } 19 20 static inline void tilt_south(char **grid, size_t nr, size_t nc) { 21 int i, j; 22 for (i = (int)(nr - 1); i >= 0; i--) { 23 for (j = 0; j < (int)nc; j++) { 24 move_south(grid, nr, nc, i, j); 25 } 26 } 27 } 28 29 static inline void move_east(char **grid, size_t nr, size_t nc, size_t r, 30 size_t c) { 31 if (grid[r][c] != 'O') 32 return; 33 if (c == nc - 1) 34 return; 35 36 if (grid[r][c + 1] == '.') { 37 grid[r][c + 1] = 'O'; 38 grid[r][c] = '.'; 39 move_east(grid, nr, nc, r, c + 1); 40 } 41 } 42 43 static inline void tilt_east(char **grid, size_t nr, size_t nc) { 44 int i, j; 45 for (j = (int)(nc - 1); j >= 0; j--) { 46 for (i = 0; i < (int)nr; i++) { 47 move_east(grid, nr, nc, i, j); 48 } 49 } 50 } 51 52 static inline void move_west(char **grid, size_t nr, size_t nc, size_t r, 53 size_t c) { 54 if (grid[r][c] != 'O') 55 return; 56 if (c == 0) 57 return; 58 59 if (grid[r][c - 1] == '.') { 60 grid[r][c - 1] = 'O'; 61 grid[r][c] = '.'; 62 move_west(grid, nr, nc, r, c - 1); 63 } 64 } 65 66 static inline void tilt_west(char **grid, size_t nr, size_t nc) { 67 int i, j; 68 for (j = 0; j < (int)nc; j++) { 69 for (i = 0; i < (int)nr; i++) { 70 move_west(grid, nr, nc, i, j); 71 } 72 } 73 } 74 75 static inline void move_north(char **grid, size_t nr, size_t nc, size_t r, 76 size_t c) { 77 if (grid[r][c] != 'O') 78 return; 79 if (r == 0) 80 return; 81 82 if (grid[r - 1][c] == '.') { 83 grid[r - 1][c] = 'O'; 84 grid[r][c] = '.'; 85 move_north(grid, nr, nc, r - 1, c); 86 } 87 } 88 89 static inline void tilt_north(char **grid, size_t nr, size_t nc) { 90 size_t i, j; 91 for (i = 0; i < nr; i++) { 92 for (j = 0; j < nc; j++) { 93 move_north(grid, nr, nc, i, j); 94 } 95 } 96 } 97 98 static inline void tilt_cycle(char **grid, size_t nr, size_t nc) { 99 tilt_north(grid, nr, nc); 100 tilt_west(grid, nr, nc); 101 tilt_south(grid, nr, nc); 102 tilt_east(grid, nr, nc); 103 } 104 105 static inline void write_pos(uint8_t *p, char **grid, size_t nr, size_t nc) { 106 size_t i, j; 107 uint8_t *pp = p; 108 109 for (i = 0; i < nr; i++) { 110 for (j = 0; j < nc; j++) { 111 if (grid[i][j] == 'O') { 112 *pp = 1; 113 pp++; 114 } else if (grid[i][j] == '.') { 115 *pp = 0; 116 pp++; 117 } 118 } 119 } 120 } 121 122 static inline size_t add_pos(uint8_t **ps, size_t nps, char **grid, size_t nr, 123 size_t nc, size_t npp) { 124 size_t i; 125 126 uint8_t n[npp]; 127 write_pos(n, grid, nr, nc); 128 129 for (i = 0; i < nps; i++) { 130 if (memcmp(ps[i], n, npp) == 0) 131 return i; 132 } 133 134 memcpy(ps[nps], n, npp); 135 136 return nps; 137 } 138 139 int main(int argc, char **argv) { 140 char **lines; 141 size_t i, j, nlines, nc, nbum; 142 uint64_t l; 143 nlines = readlines(&lines, "input"); 144 145 nc = strlen(lines[0]) - 1; 146 147 nbum = 0; 148 for (i = 0; i < nlines; i++) { 149 for (j = 0; j < nc; j++) { 150 if (lines[i][j] == 'O' || lines[i][j] == '.') { 151 nbum++; 152 } 153 } 154 } 155 uint8_t **ps = malloc(MAXNUM * sizeof(*ps)); 156 for (i = 0; i < MAXNUM; i++) { 157 ps[i] = malloc(nbum * sizeof(*ps[i])); 158 } 159 160 size_t nps = 0; 161 size_t tmp; 162 for (i = 0; i < MAXNUM; i++) { 163 tmp = add_pos(ps, nps, lines, nlines, nc, nbum); 164 if (tmp != nps) { 165 break; 166 } else { 167 nps++; 168 } 169 tilt_cycle(lines, nlines, nc); 170 } 171 assert(i < MAXNUM); 172 size_t remaining_steps = NITS - tmp; 173 size_t cycle = nps - tmp; 174 size_t rr = remaining_steps % cycle; 175 176 for (i = 0; i < rr; i++) { 177 tilt_cycle(lines, nlines, nc); 178 } 179 180 for (i = 0; i < MAXNUM; i++) { 181 free(ps[i]); 182 } 183 free(ps); 184 185 l = load(lines, nlines, nc); 186 printf("%llu\n", l); 187 }