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