solutions.h (6922B)
1 STATIC void solution_moves_reset(solution_moves_t [static 1]); 2 STATIC void solution_moves_transform(solution_moves_t [static 1], uint8_t); 3 STATIC void solution_moves_reorient(solution_moves_t [static 1], uint8_t); 4 STATIC bool solution_list_init( 5 solution_list_t [static 1], size_t n, char [n]); 6 STATIC bool solution_moves_equal( 7 const solution_moves_t [static 1], const solution_moves_t [static 1]); 8 STATIC bool solution_moves_is_duplicate(size_t n, const solution_moves_t[n+1]); 9 STATIC bool appendchar(solution_list_t [static 1], char); 10 STATIC bool appendnormal( 11 const solution_moves_t [static 1], solution_list_t [static 1]); 12 STATIC bool appendinverse( 13 const solution_moves_t [static 1], solution_list_t [static 1]); 14 STATIC int64_t appendsolution(const solution_moves_t [static 1], 15 const solution_settings_t [static 1], solution_list_t [static 1], bool, 16 const char *); 17 STATIC bool solutions_done(const solution_list_t [static 1], 18 const solution_settings_t [static 1], int8_t depth); 19 20 STATIC void 21 solution_moves_reset(solution_moves_t sol[static 1]) 22 { 23 sol->nmoves = 0; 24 sol->npremoves = 0; 25 } 26 27 STATIC void 28 solution_moves_transform(solution_moves_t moves[static 1], uint8_t t) 29 { 30 uint8_t i; 31 32 for (i = 0; i < moves->nmoves; i++) 33 moves->moves[i] = transform_move(moves->moves[i], t); 34 35 for (i = 0; i < moves->npremoves; i++) 36 moves->premoves[i] = transform_move(moves->premoves[i], t); 37 } 38 39 STATIC void 40 solution_moves_reorient(solution_moves_t moves[static 1], uint8_t or) 41 { 42 uint8_t i; 43 44 for (i = 0; i < moves->nmoves; i++) 45 moves->moves[i] = 46 inverse_reorient_move(moves->moves[i], or); 47 48 for (i = 0; i < moves->npremoves; i++) 49 moves->premoves[i] = 50 inverse_reorient_move(moves->premoves[i], or); 51 } 52 53 STATIC bool 54 solution_list_init(solution_list_t sols[static 1], size_t n, char buf[n]) 55 { 56 if (n == 0) { 57 LOG("Error: cannot use solution buffer with size 0\n"); 58 return false; 59 } 60 61 sols->nsols = 0; 62 sols->shortest_sol = MAXLEN + 1; 63 sols->size = n; 64 sols->used = 0; 65 sols->buf = buf; 66 sols->buf[0] = '\0'; 67 68 return true; 69 } 70 71 STATIC bool 72 solution_moves_equal( 73 const solution_moves_t a[static 1], 74 const solution_moves_t b[static 1] 75 ) 76 { 77 uint8_t i; 78 79 if (a->nmoves != b->nmoves || a->npremoves != b->npremoves) 80 return false; 81 82 for (i = 0; i < a->nmoves; i++) 83 if (a->moves[i] != b->moves[i]) 84 return false; 85 86 for (i = 0; i < a->npremoves; i++) 87 if (a->premoves[i] != b->premoves[i]) 88 return false; 89 90 return true; 91 } 92 93 STATIC bool 94 solution_moves_is_duplicate(size_t n, const solution_moves_t s[n+1]) 95 { 96 size_t i; 97 98 for (i = 0; i < n; i++) 99 if (solution_moves_equal(&s[i], &s[n])) 100 return true; 101 102 return false; 103 } 104 105 STATIC bool 106 appendchar(solution_list_t solutions[static 1], char c) 107 { 108 if (solutions->size <= solutions->used) 109 return false; 110 111 solutions->buf[solutions->used++] = c; 112 113 return true; 114 } 115 116 STATIC bool 117 appendnormal( 118 const solution_moves_t moves[static 1], 119 solution_list_t list[static 1] 120 ) 121 { 122 int64_t strl; 123 124 if (moves->nmoves == 0) 125 return true; 126 127 if ((strl = writemoves(moves->nmoves, moves->moves, 128 list->size - list->used, list->buf + list->used)) < 0) 129 return false; 130 list->used += strl; 131 132 return true; 133 } 134 135 STATIC bool 136 appendinverse( 137 const solution_moves_t moves[static 1], 138 solution_list_t list[static 1] 139 ) 140 { 141 int64_t strl; 142 143 if (moves->npremoves == 0) 144 return true; 145 146 if (!appendchar(list, '(')) 147 return false; 148 149 if ((strl = writemoves(moves->npremoves, moves->premoves, 150 list->size - list->used, list->buf + list->used)) < 0) 151 return false; 152 list->used += strl; 153 154 return appendchar(list, ')'); 155 } 156 157 STATIC int64_t 158 appendsolution( 159 const solution_moves_t moves[static 1], 160 const solution_settings_t settings[static 1], 161 solution_list_t list[static 1], 162 bool log, 163 const char *solver_name 164 ) 165 { 166 int64_t r; 167 int i; 168 uint8_t t; 169 solution_moves_t tsol[NTRANS]; 170 char *last_start; 171 172 if (moves->nmoves + moves->npremoves > MAXLEN) 173 goto appendsolution_error_solution_length; 174 175 for ( 176 t = 0, r = 0; 177 t < NTRANS && list->nsols < settings->maxsolutions; 178 t++ 179 ) { 180 if (!(settings->tmask & TM_SINGLE(t))) 181 continue; 182 183 tsol[r] = *moves; 184 if (settings->unniss) { 185 tsol[r].nmoves += moves->npremoves; 186 tsol[r].npremoves = 0; 187 for (i = moves->npremoves-1; i >= 0; i--) 188 tsol[r].moves[tsol[r].nmoves - i - 1] = 189 inverse_move(moves->premoves[i]); 190 191 /* 192 This is a bit ugly: we have to sort now and then again 193 later, because the allowedmoves check would fail with 194 improperly sorted parallel moves, but then transforming 195 could swap the pairs the wrong way around. 196 TODO: maybe fix this 197 */ 198 sortparallel_moves(tsol[r].nmoves, tsol[r].moves); 199 200 /* Check if unnissed premoves cancel with normal. */ 201 if (!allowedmoves(tsol[r].nmoves, tsol[r].moves)) 202 continue; 203 } 204 solution_moves_transform(&tsol[r], t); 205 solution_moves_reorient(&tsol[r], settings->orientation); 206 sortparallel_moves(tsol[r].nmoves, tsol[r].moves); 207 sortparallel_moves(tsol[r].npremoves, tsol[r].premoves); 208 209 /* Skip duplicates that may appear after transforming */ 210 if (solution_moves_is_duplicate(r, tsol)) 211 continue; 212 213 last_start = list->buf + list->used; 214 215 /* Append first the moves on the side that has more */ 216 /* E.g. write (U L F) B instead of B (U L F) */ 217 if (tsol[r].nmoves >= tsol[r].npremoves) { 218 if (!appendnormal(&tsol[r], list)) 219 goto appendsolution_error_buffer; 220 221 if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0) 222 if (!appendchar(list, ' ')) 223 return false; 224 225 if (!appendinverse(&tsol[r], list)) 226 goto appendsolution_error_buffer; 227 } else { 228 if (!appendinverse(&tsol[r], list)) 229 goto appendsolution_error_buffer; 230 231 if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0) 232 if (!appendchar(list, ' ')) 233 return false; 234 235 if (!appendnormal(&tsol[r], list)) 236 goto appendsolution_error_buffer; 237 } 238 239 if (!appendchar(list, '\n')) 240 goto appendsolution_error_buffer; 241 242 ++list->nsols; 243 list->shortest_sol = MIN( 244 list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves); 245 r++; 246 247 if (log) { 248 list->buf[list->used-1] = '\0'; 249 LOG("[%s solve] Found solution #%" PRIu64 ": %s\n", 250 solver_name, list->nsols, last_start); 251 list->buf[list->used-1] = '\n'; 252 } 253 } 254 255 list->buf[list->used] = '\0'; 256 return r; 257 258 appendsolution_error_buffer: 259 LOG("[%s solve] Error: buffer too small\n", solver_name); 260 list->buf[0] = '\0'; 261 return NISSY_ERROR_BUFFER_SIZE; 262 263 appendsolution_error_solution_length: 264 LOG("[%s solve] Error: solution is too long (%" PRIu8 ").\n" 265 "This is a bug, please report it.\n", 266 solver_name, moves->nmoves + moves->npremoves); 267 list->buf[0] = '\0'; 268 return NISSY_ERROR_UNKNOWN; 269 } 270 271 STATIC bool 272 solutions_done( 273 const solution_list_t list[static 1], 274 const solution_settings_t settings[static 1], 275 int8_t depth 276 ) 277 { 278 279 return depth > settings->maxmoves || 280 depth > list->shortest_sol + settings->optimal || 281 list->nsols >= settings->maxsolutions; 282 }