solutions.h (5406B)
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 int64_t appendsolution(const solution_moves_t [static 1], 10 const solution_settings_t [static 1], solution_list_t [static 1]); 11 STATIC bool solutions_done(const solution_list_t [static 1], 12 const solution_settings_t [static 1], int8_t depth); 13 14 STATIC void 15 solution_moves_reset(solution_moves_t sol[static 1]) 16 { 17 sol->nmoves = 0; 18 sol->npremoves = 0; 19 } 20 21 STATIC void 22 solution_moves_transform(solution_moves_t moves[static 1], uint8_t t) 23 { 24 uint8_t i; 25 26 for (i = 0; i < moves->nmoves; i++) 27 moves->moves[i] = transform_move(moves->moves[i], t); 28 29 for (i = 0; i < moves->npremoves; i++) 30 moves->premoves[i] = transform_move(moves->premoves[i], t); 31 } 32 33 STATIC bool 34 solution_list_init(solution_list_t sols[static 1], size_t n, char buf[n]) 35 { 36 if (n == 0) { 37 LOG("Cannot use solution buffer with size 0\n"); 38 return false; 39 } 40 41 sols->nsols = 0; 42 sols->shortest_sol = MAXLEN + 1; 43 sols->size = n; 44 sols->used = 0; 45 sols->buf = buf; 46 47 /* Ensure string buffer is NULL-terminated */ 48 sols->buf[0] = '\0'; 49 50 return true; 51 } 52 53 STATIC bool 54 solution_moves_equal( 55 const solution_moves_t a[static 1], 56 const solution_moves_t b[static 1] 57 ) 58 { 59 uint8_t i; 60 61 if (a->nmoves != b->nmoves || a->npremoves != b->npremoves) 62 return false; 63 64 for (i = 0; i < a->nmoves; i++) 65 if (a->moves[i] != b->moves[i]) 66 return false; 67 68 for (i = 0; i < a->npremoves; i++) 69 if (a->premoves[i] != b->premoves[i]) 70 return false; 71 72 return true; 73 } 74 75 STATIC bool 76 solution_moves_is_duplicate(size_t n, const solution_moves_t s[n+1]) 77 { 78 size_t i; 79 80 for (i = 0; i < n; i++) 81 if (solution_moves_equal(&s[i], &s[n])) 82 return true; 83 84 return false; 85 } 86 87 STATIC bool 88 appendchar(solution_list_t solutions[static 1], char c) 89 { 90 if (solutions->size <= solutions->used) 91 return false; 92 93 solutions->buf[solutions->used++] = c; 94 95 return true; 96 } 97 98 STATIC int64_t 99 appendsolution( 100 const solution_moves_t moves[static 1], 101 const solution_settings_t settings[static 1], 102 solution_list_t list[static 1] 103 ) 104 { 105 int64_t r, strl; 106 int i; 107 uint8_t t; 108 solution_moves_t tsol[NTRANS]; 109 110 if (moves->nmoves + moves->npremoves > MAXLEN) 111 goto appendsolution_error_solution_length; 112 113 for ( 114 t = 0, r = 0; 115 t < NTRANS && list->nsols < settings->maxsolutions; 116 t++ 117 ) { 118 if (!(settings->tmask & TM_SINGLE(t))) 119 continue; 120 121 tsol[r] = *moves; 122 if (settings->unniss) { 123 tsol[r].nmoves += moves->npremoves; 124 tsol[r].npremoves = 0; 125 for (i = moves->npremoves-1; i >= 0; i--) 126 tsol[r].moves[tsol[r].nmoves - i - 1] = 127 inverse_move(moves->premoves[i]); 128 129 /* 130 This is a bit ugly: we have to sort now and then again 131 later, because the allowedmoves check would fail with 132 improperly sorted parallel moves, but then transforming 133 could swap the pairs the wrong way around. 134 TODO: maybe fix this 135 */ 136 sortparallel_moves(tsol[r].nmoves, tsol[r].moves); 137 138 /* Check if unnissed premoves cancel with normal. */ 139 if (!allowedmoves(tsol[r].nmoves, tsol[r].moves)) 140 continue; 141 } 142 solution_moves_transform(&tsol[r], t); 143 sortparallel_moves(tsol[r].nmoves, tsol[r].moves); 144 sortparallel_moves(tsol[r].npremoves, tsol[r].premoves); 145 146 /* Skip duplicates that may appear after transforming */ 147 if (solution_moves_is_duplicate(r, tsol)) 148 continue; 149 150 /* Write moves on normal */ 151 strl = writemoves(tsol[r].nmoves, tsol[r].moves, 152 list->size - list->used, list->buf + list->used); 153 if (strl < 0) 154 goto appendsolution_error_buffer; 155 list->used += strl; 156 157 /* Write moves on inverse with NISS notation */ 158 if (tsol[r].npremoves > 0) { 159 if (strl > 0) 160 if (!appendchar(list, ' ')) 161 goto appendsolution_error_buffer; 162 if (!appendchar(list, '(')) 163 goto appendsolution_error_buffer; 164 165 strl = writemoves(tsol[r].npremoves, tsol[r].premoves, 166 list->size - list->used, list->buf + list->used); 167 if (strl < 0) 168 goto appendsolution_error_buffer; 169 list->used += strl; 170 171 if (!appendchar(list, ')')) 172 goto appendsolution_error_buffer; 173 } 174 175 if (!appendchar(list, '\n')) 176 goto appendsolution_error_buffer; 177 178 ++list->nsols; 179 list->shortest_sol = MIN( 180 list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves); 181 r++; 182 } 183 184 list->buf[list->used] = '\0'; 185 return r; 186 187 appendsolution_error_buffer: 188 LOG("Could not append solution to buffer: size too small\n"); 189 list->buf[0] = '\0'; 190 return NISSY_ERROR_BUFFER_SIZE; 191 192 appendsolution_error_solution_length: 193 LOG("Error: solution is too long (%" PRIu8 ").\n" 194 "This is a bug, please report it.\n", 195 moves->nmoves + moves->npremoves); 196 list->buf[0] = '\0'; 197 return NISSY_ERROR_UNKNOWN; 198 } 199 200 STATIC bool 201 solutions_done( 202 const solution_list_t list[static 1], 203 const solution_settings_t settings[static 1], 204 int8_t depth 205 ) 206 { 207 if (list->nsols >= settings->maxsolutions) 208 return true; 209 210 if (depth > settings->maxmoves) 211 return true; 212 213 if (list->nsols > 0 && settings->optimal >= 0 && 214 depth > list->shortest_sol + settings->optimal) 215 return true; 216 217 return false; 218 }