nissy-core

The "engine" of nissy, including the H48 optimal solver.
git clone https://git.tronto.net/nissy-core
Download | Log | Files | Refs | README | LICENSE

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 }