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