h48

A prototype for an optimal Rubik's cube solver, work in progress.
git clone https://git.tronto.net/h48
Download | Log | Files | Refs | README | LICENSE

moves.h (6350B)


      1 #define MOVE(M, c) compose(c, MOVE_CUBE_ ## M)
      2 #define PREMOVE(M, c) compose(MOVE_CUBE_ ## M, c)
      3 
      4 STATIC uint8_t readmove(char);
      5 STATIC int64_t readmoves(const char *, size_t n, uint8_t [n]);
      6 STATIC int64_t countmoves(const char *);
      7 STATIC uint8_t readmodifier(char);
      8 STATIC int64_t writemoves(size_t n, const uint8_t [n], size_t m, char [m]);
      9 
     10 STATIC_INLINE bool allowednextmove(uint8_t, uint8_t);
     11 STATIC bool allowedmoves(size_t n, const uint8_t [n]);
     12 
     13 STATIC_INLINE uint8_t movebase(uint8_t);
     14 STATIC_INLINE uint8_t moveaxis(uint8_t);
     15 STATIC_INLINE bool isbase(uint8_t);
     16 STATIC_INLINE bool parallel(uint8_t, uint8_t);
     17 
     18 STATIC cube_t move(cube_t, uint8_t);
     19 STATIC cube_t premove(cube_t, uint8_t);
     20 STATIC uint8_t inverse_move(uint8_t);
     21 STATIC void sortparallel_moves(size_t n, uint8_t [n]);
     22 STATIC bool are_lastmoves_singlecw(size_t n, const uint8_t [n]);
     23 
     24 STATIC cube_t applymoves(cube_t, const char *);
     25 
     26 #define FOREACH_READMOVE(ARG_BUF, ARG_MOVE, ARG_C, ARG_MAX, \
     27 	RET_ERROR, ARG_ACTION) \
     28 	const char *VAR_B; \
     29 	uint8_t VAR_MOVE_NOMOD, VAR_MOD; \
     30 	for (VAR_B = ARG_BUF, ARG_C = 0; *VAR_B != '\0'; VAR_B++, ARG_C++) { \
     31 		while (*VAR_B == ' ' || *VAR_B == '\t' || *VAR_B == '\n') \
     32 			VAR_B++; \
     33 		if (*VAR_B == '\0' || ARG_C == ARG_MAX) \
     34 			break; \
     35 		if ((VAR_MOVE_NOMOD = readmove(*VAR_B)) == UINT8_ERROR) { \
     36 			LOG("Unknown move: %c\n", *VAR_B); \
     37 			return RET_ERROR; \
     38 		} \
     39 		if ((VAR_MOD = readmodifier(*(VAR_B+1))) != 0) \
     40 			VAR_B++; \
     41 		ARG_MOVE = VAR_MOVE_NOMOD + VAR_MOD; \
     42 		ARG_ACTION \
     43 	}
     44 
     45 STATIC uint8_t
     46 readmove(char c)
     47 {
     48 	switch (c) {
     49 	case 'U':
     50 		return MOVE_U;
     51 	case 'D':
     52 		return MOVE_D;
     53 	case 'R':
     54 		return MOVE_R;
     55 	case 'L':
     56 		return MOVE_L;
     57 	case 'F':
     58 		return MOVE_F;
     59 	case 'B':
     60 		return MOVE_B;
     61 	default:
     62 		return UINT8_ERROR;
     63 	}
     64 }
     65 
     66 STATIC uint8_t
     67 readmodifier(char c)
     68 {
     69 	switch (c) {
     70 	case '1': /* Fallthrough */
     71 	case '2': /* Fallthrough */
     72 	case '3':
     73 		return c - '0' - 1;
     74 	case '\'':
     75 		return 2;
     76 	default:
     77 		return 0;
     78 	}
     79 }
     80 
     81 STATIC int64_t
     82 readmoves(const char *buf, size_t n, uint8_t ret[n])
     83 {
     84 	uint8_t m;
     85 	uint64_t c;
     86 
     87 	FOREACH_READMOVE(buf, m, c, n, NISSY_ERROR_INVALID_MOVES,
     88 		ret[c] = m;
     89 	)
     90 
     91 	return (int64_t)c;
     92 }
     93 
     94 STATIC int64_t
     95 countmoves(const char *buf)
     96 {
     97 	uint8_t m;
     98 	uint64_t c;
     99 
    100 	FOREACH_READMOVE(buf, m, c, INT_MAX, NISSY_ERROR_INVALID_MOVES,
    101 		{}
    102 	)
    103 
    104 	(void)m; /* Ignore "variable set but not used" warning */
    105 
    106 	return (int64_t)c;
    107 }
    108 
    109 STATIC int64_t
    110 writemoves(
    111 	size_t nmoves,
    112 	const uint8_t m[nmoves],
    113 	size_t buf_size,
    114 	char buf[buf_size]
    115 )
    116 {
    117 	size_t i, len, w;
    118 	const char *s;
    119 
    120 	if (buf_size == 0) {
    121 		LOG("Error: cannot write moves to buffer of size 0.\n");
    122 		return NISSY_ERROR_BUFFER_SIZE;
    123 	}
    124 
    125 	for (i = 0, w = 0; i < nmoves; i++, w++) {
    126 		s = movestr[m[i]];
    127 		len = strlen(s);
    128 		if (len + w >= buf_size) {
    129 			LOG("Error: the given buffer is too small for "
    130 			     "writing the given moves.\n");
    131 			goto writemoves_error;
    132 		}
    133 		memcpy(buf+w, s, len);
    134 		w += len;
    135 		buf[w] = ' ';
    136 	}
    137 
    138 	if (w > 0) w--; /* Remove last space */
    139 	buf[w] = '\0';
    140 
    141 	return (int64_t)w;
    142 
    143 writemoves_error:
    144 	*buf = '\0';
    145 	return NISSY_ERROR_BUFFER_SIZE;
    146 }
    147 
    148 STATIC_INLINE bool
    149 allowednextmove(uint8_t m1, uint8_t m2)
    150 {
    151 	return allowedmask[movebase(m1)] & (UINT32_C(1) << m2);
    152 }
    153 
    154 STATIC bool
    155 allowedmoves(size_t n, const uint8_t m[n])
    156 {
    157 	uint8_t j;
    158 
    159 	for (j = 1; j < n; j++)
    160 		if (!allowednextmove(m[j-1], m[j]))
    161 			return false;
    162 
    163 	return true;
    164 }
    165 
    166 STATIC_INLINE uint8_t
    167 movebase(uint8_t move)
    168 {
    169 	return move / 3;
    170 }
    171 
    172 STATIC_INLINE uint8_t
    173 moveaxis(uint8_t move)
    174 {
    175 	return move / 6;
    176 }
    177 
    178 STATIC_INLINE bool
    179 isbase(uint8_t move)
    180 {
    181 	return move == 3 * movebase(move);
    182 }
    183 
    184 STATIC_INLINE bool
    185 parallel(uint8_t m1, uint8_t m2)
    186 {
    187 	return moveaxis(m1) == moveaxis(m2);
    188 }
    189 
    190 STATIC_INLINE uint8_t
    191 moveopposite(uint8_t move)
    192 {
    193 	return movebase(move) == 2 * moveaxis(move) ? move + 3 : move - 3;
    194 }
    195 
    196 STATIC cube_t
    197 move(cube_t c, uint8_t m)
    198 {
    199 	switch (m) {
    200 	case MOVE_U:
    201 		return MOVE(U, c);
    202 	case MOVE_U2:
    203 		return MOVE(U2, c);
    204 	case MOVE_U3:
    205 		return MOVE(U3, c);
    206 	case MOVE_D:
    207 		return MOVE(D, c);
    208 	case MOVE_D2:
    209 		return MOVE(D2, c);
    210 	case MOVE_D3:
    211 		return MOVE(D3, c);
    212 	case MOVE_R:
    213 		return MOVE(R, c);
    214 	case MOVE_R2:
    215 		return MOVE(R2, c);
    216 	case MOVE_R3:
    217 		return MOVE(R3, c);
    218 	case MOVE_L:
    219 		return MOVE(L, c);
    220 	case MOVE_L2:
    221 		return MOVE(L2, c);
    222 	case MOVE_L3:
    223 		return MOVE(L3, c);
    224 	case MOVE_F:
    225 		return MOVE(F, c);
    226 	case MOVE_F2:
    227 		return MOVE(F2, c);
    228 	case MOVE_F3:
    229 		return MOVE(F3, c);
    230 	case MOVE_B:
    231 		return MOVE(B, c);
    232 	case MOVE_B2:
    233 		return MOVE(B2, c);
    234 	case MOVE_B3:
    235 		return MOVE(B3, c);
    236 	default:
    237 		LOG("move error: unknown move %" PRIu8 "\n", m);
    238 		return ZERO_CUBE;
    239 	}
    240 }
    241 
    242 /* Applies the INVERSE of m BEFORE the scramble corresponding to c */
    243 STATIC cube_t
    244 premove(cube_t c, uint8_t m)
    245 {
    246 	switch (m) {
    247 	case MOVE_U:
    248 		return PREMOVE(U3, c);
    249 	case MOVE_U2:
    250 		return PREMOVE(U2, c);
    251 	case MOVE_U3:
    252 		return PREMOVE(U, c);
    253 	case MOVE_D:
    254 		return PREMOVE(D3, c);
    255 	case MOVE_D2:
    256 		return PREMOVE(D2, c);
    257 	case MOVE_D3:
    258 		return PREMOVE(D, c);
    259 	case MOVE_R:
    260 		return PREMOVE(R3, c);
    261 	case MOVE_R2:
    262 		return PREMOVE(R2, c);
    263 	case MOVE_R3:
    264 		return PREMOVE(R, c);
    265 	case MOVE_L:
    266 		return PREMOVE(L3, c);
    267 	case MOVE_L2:
    268 		return PREMOVE(L2, c);
    269 	case MOVE_L3:
    270 		return PREMOVE(L, c);
    271 	case MOVE_F:
    272 		return PREMOVE(F3, c);
    273 	case MOVE_F2:
    274 		return PREMOVE(F2, c);
    275 	case MOVE_F3:
    276 		return PREMOVE(F, c);
    277 	case MOVE_B:
    278 		return PREMOVE(B3, c);
    279 	case MOVE_B2:
    280 		return PREMOVE(B2, c);
    281 	case MOVE_B3:
    282 		return PREMOVE(B, c);
    283 	default:
    284 		LOG("premove error: unknown move %" PRIu8 "\n", m);
    285 		return ZERO_CUBE;
    286 	}
    287 }
    288 
    289 STATIC uint8_t
    290 inverse_move(uint8_t m)
    291 {
    292 	return m - 2 * (m % 3) + 2;	
    293 }
    294 
    295 STATIC void
    296 sortparallel_moves(size_t n, uint8_t moves[n])
    297 {
    298 	uint8_t i;
    299 
    300 	if (n < 2)
    301 		return;
    302 
    303 	for (i = 0; i < n-1; i++)
    304 		if (moveaxis(moves[i]) == moveaxis(moves[i+1]) &&
    305 		    movebase(moves[i]) == movebase(moves[i+1]) + 1)
    306 			SWAP(moves[i], moves[i+1]);
    307 }
    308 
    309 STATIC bool
    310 are_lastmoves_singlecw(size_t n, const uint8_t moves[n])
    311 {
    312 	bool two;
    313 
    314 	if (n == 0)
    315 		return true;
    316 
    317 	two = n > 1 && parallel(moves[n-1], moves[n-2]);
    318 
    319 	return isbase(moves[n-1]) && (!two || isbase(moves[n-2]));
    320 }
    321 
    322 STATIC cube_t
    323 applymoves(cube_t cube, const char *buf)
    324 {
    325 	int c;
    326 	uint8_t m;
    327 
    328 	DBG_ASSERT(isconsistent(cube), ZERO_CUBE,
    329 	    "move error: inconsistent cube\n");
    330 
    331 	FOREACH_READMOVE(buf, m, c, -1, ZERO_CUBE,
    332 		cube = move(cube, m);
    333 	)
    334 
    335 	return cube;
    336 }