solutions.h (6314B)
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 = 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 > 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 TODO: maybe fix this 190 */ 191 sortparallel_moves(tsol[r].nmoves, tsol[r].moves); 192 193 /* Check if unnissed premoves cancel with normal. */ 194 if (!allowedmoves(tsol[r].nmoves, tsol[r].moves)) 195 continue; 196 } 197 solution_moves_transform(&tsol[r], t); 198 solution_moves_reorient(&tsol[r], settings->orientation); 199 sortparallel_moves(tsol[r].nmoves, tsol[r].moves); 200 sortparallel_moves(tsol[r].npremoves, tsol[r].premoves); 201 202 /* Skip duplicates that may appear after transforming */ 203 if (solution_moves_is_duplicate(r, tsol)) 204 continue; 205 206 /* Append first the moves on the side that has more */ 207 /* E.g. write (U L F) B instead of B (U L F) */ 208 if (tsol[r].nmoves >= tsol[r].npremoves) { 209 if (!appendnormal(&tsol[r], list)) 210 goto appendsolution_error_buffer; 211 212 if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0) 213 if (!appendchar(list, ' ')) 214 return false; 215 216 if (!appendinverse(&tsol[r], list)) 217 goto appendsolution_error_buffer; 218 } else { 219 if (!appendinverse(&tsol[r], list)) 220 goto appendsolution_error_buffer; 221 222 if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0) 223 if (!appendchar(list, ' ')) 224 return false; 225 226 if (!appendnormal(&tsol[r], list)) 227 goto appendsolution_error_buffer; 228 } 229 230 if (!appendchar(list, '\n')) 231 goto appendsolution_error_buffer; 232 233 ++list->nsols; 234 list->shortest_sol = MIN( 235 list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves); 236 r++; 237 238 } 239 240 list->buf[list->used] = '\0'; 241 return r; 242 243 appendsolution_error_buffer: 244 list->buf[0] = '\0'; 245 return NISSY_ERROR_BUFFER_SIZE; 246 247 appendsolution_error_solution_length: 248 list->buf[0] = '\0'; 249 return NISSY_ERROR_UNKNOWN; 250 } 251 252 STATIC bool 253 solutions_done( 254 const solution_list_t list[static 1], 255 const solution_settings_t settings[static 1], 256 int8_t depth 257 ) 258 { 259 260 return depth > settings->maxmoves || 261 depth > list->shortest_sol + settings->optimal || 262 list->nsols >= settings->maxsolutions; 263 }