Commits

Anonymous committed 76dd0dd

start actuallying writing the cubeutils

Comments (0)

Files changed (6)

+#include <stdio.h>
+#include "cubeutils.h"
+
+int main(int argc, char **argv)
+{
+	char buf[128];
+	int i, current, solved = 1;
+
+	while (fgets(buf, sizeof(buf), stdin)) {
+		printf("input: %s", buf);
+		set_cube(buf);
+		get_cube(buf, sizeof(buf));
+		printf("get  : %s\n\n", buf);
+
+		printf("cp: %s ", parity(cp, 8) ? "odd " : "even");
+		for (i = 0; i < 8; i++)
+			printf("%d ", cp[i]);
+		printf("\n");
+
+		printf("co: %d    ", orient(co, 8, 3));
+		for (i = 0; i < 8; i++)
+			printf("%d ", co[i]);
+		printf("\n");
+
+		printf("ep: %s ", parity(ep, 12) ? "odd " : "even");
+		for (i = 0; i < 12; i++)
+			printf("%2d ", ep[i]);
+		printf("\n");
+
+		printf("eo: %d    ", orient(eo, 12, 2));
+		for (i = 0; i < 12; i++)
+			printf("%2d ", eo[i]);
+		printf("\n\n");
+
+		printf("corner orientation is %d (%ssolved)\n", get_co_coord() , (current = get_co_coord ()) ? "not " : ""); solved &= !current;
+		printf("edge   orientation is %d (%ssolved)\n", get_eo_coord() , (current = get_eo_coord ()) ? "not " : ""); solved &= !current;
+		printf("ud1    coordinate  is %d (%ssolved)\n", get_ud1_coord(), (current = get_ud1_coord()) ? "not " : ""); solved &= !current;
+		printf("\n");
+		if (solved) {
+			printf("cube is in G1\n");
+			printf("ud2    coordinate  is %d (%ssolved)\n", get_ud2_coord(), (current = get_ud2_coord()) ? "not " : ""); solved &= !current;
+		} else {
+			printf("cube is not in G1, ud2 coordinate not checked\n");
+		}
+		printf("corner permutation is %d (%ssolved)\n", get_cp_coord()     , (current = get_cp_coord() ) ? "not " : ""); solved &= !current;
+		printf("edge   permutation is %d (%ssolved)\n", get_ep_coord()     , (current = get_ep_coord() ) ? "not " : ""); solved &= !current;
+		printf("fedge  permutation is %d (%ssolved)\n", get_ep_coord_full(), (current = get_ep_coord() ) ? "not " : ""); solved &= !current;
+
+		printf("\n");
+		printf("cube is %ssolved\n", solved ? "" : "not ");
+	}
+
+	return !solved;
+}
+#include <stdio.h>
+#include <string.h>
+
+#include "cubeutils.h"
+
+static char *names[] = { "UFU", "URU", "UBU", "ULU", "DFD", "DRD", "DBD", "DLD", "FRF", "FLF", "BRB", "BLB",
+                         "UFRUF", "URBUR", "UBLUB", "ULFUL", "DRFDR", "DFLDF", "DLBDL", "DBRDB" };
+
+static char c_cycles[6][4] = {
+	{ 0, 1, 2, 3 }, // U
+	{ 4, 5, 6, 7 }, // D
+	{ 0, 3, 5, 4 }, // F
+	{ 1, 7, 6, 2 }, // B
+	{ 0, 4, 7, 1 }, // R
+	{ 2, 6, 5, 3 }, // L
+};
+static char e_cycles[6][4] = {
+	{ 0,  1, 2,  3 }, // U
+	{ 4,  7, 6,  5 }, // D
+	{ 0,  9, 4,  8 }, // F
+	{ 2, 10, 6, 11 }, // B
+	{ 1,  8, 5, 10 }, // R
+	{ 3, 11, 7,  9 }, // L
+};
+static char c_twists[6][4] = {
+	{ 0, 0, 0, 0 }, // U
+	{ 0, 0, 0, 0 }, // D
+	{ 2, 1, 2, 1 }, // F
+	{ 1, 2, 1, 2 }, // B
+	{ 1, 2, 1, 2 }, // R
+	{ 1, 2, 1, 2 }, // L
+};
+static char e_twists[6][4] = {
+	{ 0, 0, 0, 0 }, // U
+	{ 0, 0, 0, 0 }, // D
+	{ 1, 1, 1, 1 }, // F
+	{ 1, 1, 1, 1 }, // B
+	{ 0, 0, 0, 0 }, // R
+	{ 0, 0, 0, 0 }, // L
+};
+
+
+/*
+ * perform the permutation cycle 1 - 3 times based on move
+ * perform the orientation twists on the cubies that are being cycled
+ */
+static void move_pieces(char *perm, char *orie, char *cycle, char *twist, int mod)
+{
+	char otmp, ptmp, i;
+
+	ptmp = perm[cycle[0]];
+	otmp = orie[cycle[0]];
+	for (i = 0; i < 3; i++) {
+		orie[cycle[i]] = (orie[cycle[i + 1]] + twist[i + 1]) % mod;
+		perm[cycle[i]] =  perm[cycle[i + 1]];
+	}
+	orie[cycle[3]] = (otmp + twist[0]) % mod;
+	perm[cycle[3]] =  ptmp;
+}
+
+/*
+ * perform the given move on the array cube
+ */
+void do_move(int mv)
+{
+	int face = mv / 3;
+
+	for (mv = mv % 3; mv >= 0; mv--) {
+		move_pieces(cp, co, c_cycles[face], c_twists[face], 3);
+		move_pieces(ep, eo, e_cycles[face], e_twists[face], 2);
+	}
+}
+
+/*
+ * set array cube from string
+ */
+void set_cube(char *cube)
+{
+	char *p, *t, i, j;
+
+	for (i = 0, p = strtok(cube, " \n"); p && i < 12; i++, p = strtok(NULL, " \n")) {
+		for (j = 0; (t = strstr(names[j], p)) == NULL; j++)
+			;
+		ep[i] = j + 1;
+		eo[i] = t - names[j];
+	}
+
+	for (i = 0; p && i < 8; i++, p = strtok(NULL, " \n")) {
+		for (j = 0; (t = strstr(names[j + 12], p)) == NULL; j++)
+			;
+		cp[i] = j + 1;
+		co[i] = t - names[j + 12];
+	}
+}
+
+/*
+ * get string from array cube
+ */
+char *get_cube(char *buf, int len)
+{
+	int i;
+
+	if (len < 68)
+		return NULL;
+
+	memset(buf, ' ', 68);
+
+	for (i = 0; i < 12; i++)
+		strncpy(buf + (i * 3), names[ep[i] - 1] + eo[i], 2);
+
+	for (i = 0; i < 8; i++)
+		strncpy(buf + (12 * 3) + (i * 4), names[12 + cp[i] - 1] + co[i], 3);
+
+	buf[67] = '\0';
+
+	return buf;
+}
+
+/*
+ * check even or odd parity of permutations
+ */
+int parity(char *perm, int len)
+{
+	int i, j, p = 0;
+
+	for (i = 0; i < len; i++)
+		for (j = 0; j < i; j++)
+			if (perm[j] > perm[i])
+				p = !p;
+
+	return p;
+}
+
+/*
+ * check orientations
+ */
+int orient(char *orie, int len, int mod)
+{
+	char i, o;
+
+	for (i = o = 0; i < len; i++)
+		o = (o + orie[i]) % mod;
+
+	return o;
+}
+
+// math functions
+static int fact [12] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800 };
+static int choose(int n, int k) { return fact[n]/(fact[k] * fact[n - k]); }
+
+/*
+ * ud1 coordinate
+ */
+void set_ud1_coord(int coord)
+{
+	int i, j;
+
+	memset(ep, 0, 12);
+	for (i = 11, j = 4; i >= 0 && j; i--) {
+		if (coord >= choose(i, j - 1)) {
+			coord -= choose(i, j - 1);
+		} else {
+			ep[i] = 9;
+			j--;
+		}
+	}
+}
+
+int get_ud1_coord(void)
+{
+	int i, j = 0, coord = 0;
+
+	for (i = 0; i < 12; i++) {
+		if (ep[i] > 8     ) j++;
+		if (ep[i] < 9 && j) coord += choose(i, j - 1);
+	}
+	return coord;
+}
+
+/*
+ * generic orientation coordinate
+ */
+static void set_o_coord(char *orie, int len, int coord, int mod)
+{
+	int i, s = 0;
+
+	for (i = len - 2; i >= 0; i--) {
+		orie[i] = coord % mod;
+		s = (s - orie[i] + mod) % mod;
+		coord /= mod;
+	}
+	orie[len - 1] = s;
+}
+
+static int get_o_coord(char *orie, int len, int mod)
+{
+	int i, coord = 0;
+
+	for (i = 0; i < len - 1; i++)
+		coord = coord * mod + orie[i];
+
+	return coord;
+}
+
+/*
+ * specific orientation coordinates
+ */
+void set_eo_coord(int coord) { set_o_coord(eo, 12, coord, 2); }
+void set_co_coord(int coord) { set_o_coord(co,  8, coord, 3); }
+
+int get_eo_coord(void) { return get_o_coord(eo, 12, 2); }
+int get_co_coord(void) { return get_o_coord(co,  8, 3); }
+
+/*
+ * generic permutation coordinate
+ */
+static void set_p_coord(char *perm, int len, int coord)
+{
+	int i, j;
+
+	perm[len - 1] = 1;
+
+	for (i = len - 2; i >= 0; i--) {
+		perm[i] = (coord % (len - i)) + 1;
+		coord /= len - i;
+		for (j = i + 1; j < len; j++)
+			if (perm[j] >= perm[i])
+				perm[j]++;
+	}
+}
+
+static int get_p_coord(char *perm, int len)
+{
+	int i, j, coord = 0;
+
+	for (i = 0; i < len - 1; i++) {
+		coord *= (len - i);
+		for (j = i + 1; j < len; j++)
+			if (perm[i] > perm[j])
+				coord++;
+	}
+	return coord;
+}
+
+/*
+ * specific permutation coordinates
+ */
+void set_cp_coord (int coord) { set_p_coord(cp,     8, coord); }
+void set_ep_coord (int coord) { set_p_coord(ep,     8, coord); }
+void set_ud2_coord(int coord) { set_p_coord(ep + 8, 4, coord); }
+
+int get_cp_coord (void) { return get_p_coord(cp,     8); }
+int get_ep_coord (void) { return get_p_coord(ep,     8); }
+int get_ud2_coord(void) { return get_p_coord(ep + 8, 4); }
+
+void set_ep_coord_full(int coord) {set_p_coord(ep, 12, coord); }
+int  get_ep_coord_full(void) { return get_p_coord(ep, 12); }
+#ifndef _CUBEUTILS_H_
+#define _CUBEUTILS_H_
+
+#define SOLVED_CUBE "UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR "
+
+/*
+ * index  : 0   1   2   3   4   5   6   7   8   9   10  11
+ * corners: UFR URB UBL ULF DRF DFL DLB DBR
+ * edges  : UF  UR  UB  UL  DF  DR  DB  DL  FR  FL  BR  BL
+ */
+char co[8], eo[12], cp[8], ep[12];
+
+/*
+ * moves are:
+ * U  U2 U' D  D2 D' F  F2 F' B  B2 B' R  R2 R' L  L2 L'
+ * U1 U2 U3 D1 D2 D3 F1 F2 F3 B1 B2 B3 R1 R2 R3 L1 L2 L3
+ * 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17
+ */
+enum { U1, U2, U3, D1, D2, D3, F1, F2, F3, B1, B2, B3, R1, R2, R3, L1, L2, L3 };
+
+/*
+ * perform the given move on the array cube
+ */
+void do_move(int mv);
+
+/*
+ * set array cube from string
+ */
+void set_cube(char *cube);
+
+/*
+ * get string from array cube
+ */
+char *get_cube(char *buf, int len);
+
+/*
+ * check even or odd parity of a permutation
+ */
+int parity(char *perm, int len);
+
+/*
+ * check orientations
+ */
+int orient(char *orie, int len, int mod);
+
+void set_ud1_coord(int coord);
+int get_ud1_coord(void);
+
+void set_eo_coord(int coord);
+void set_co_coord(int coord);
+
+int get_eo_coord(void);
+int get_co_coord(void);
+
+void set_cp_coord (int coord);
+void set_ep_coord (int coord);
+void set_ud2_coord(int coord);
+
+int get_cp_coord (void);
+int get_ep_coord (void);
+int get_ud2_coord(void);
+
+void set_ep_coord_full(int coord);
+int  get_ep_coord_full(void);
+
+#endif
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "cubeutils.h"
+
+char cube[] = SOLVED_CUBE, start_cube[] = SOLVED_CUBE;
+enum { undef, face, num };
+
+int main(int argc, char **argv)
+{
+	char *p, *k, buf[128], faces[] = "UDFBRL", nums[] = " +1222'-3";
+
+	int i, mv, last = undef, cur = undef;
+
+	if (argc == 1) {
+		// no argument, use a solved cube
+	} else if (argc == 2 || argc == 21) { // 1 or 20 arguments, start cube provided on commandline
+		*start_cube = '\0';
+		for (i = 1; i < argc; i++) {
+			strcat(start_cube, argv[i]);
+			strcat(start_cube, " ");
+		}
+	} else {
+		fprintf(stderr, "malformed cube, assuming solved cube\n");
+	}
+
+	set_cube(start_cube);
+
+	while (fgets(buf, sizeof(buf), stdin)) {
+		for (p = buf; *p; p++) {
+			if (strchr(" \t", *p)) continue;
+
+			if ((k = strchr(faces, *p))) {
+				if (last == face)
+					do_move(mv);
+				mv  = (k - faces) * 3;
+				cur = face;
+			} else if ((k = strchr(nums, *p))) {
+				if (last != face)
+					fprintf(stderr, "malformed move %c\n", *p);
+				mv += (k - nums) / 3;
+				cur = num;
+				do_move(mv);
+			} else if (*p == '\n') {
+				if (last == face)
+					do_move(mv);
+				get_cube(cube, sizeof(cube));
+				printf("%s\n", cube);
+				set_cube(start_cube);
+				cur = undef;
+			} else {
+				fprintf(stderr, "bad character %c\n", *p);
+				cur = undef;
+			}
+			last = cur;
+		}
+	}
+	if (cur == face)
+		do_move(mv);
+
+	if (cur != undef) {
+		get_cube(cube, sizeof(cube));
+		printf("%s\n", cube);
+	}
+
+	return 0;
+}
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/time.h>
+#include "cubeutils.h"
+
+int main(int argc, char **argv)
+{
+	int num = 1;
+	char cube[] = SOLVED_CUBE;
+
+	struct timeval tv;
+	gettimeofday(&tv, NULL);
+	srandom(tv.tv_usec);
+
+	if (argc == 1) {
+		// assume one random cube
+	} else if (argc == 2) {
+		// one argument, number of random cubes
+		num = atoi(argv[1]);
+	} else {
+		fprintf(stderr, "supply number of random cubes as argument\n");
+		exit(EXIT_FAILURE);
+	}
+
+	while (num-- > 0) {
+		set_co_coord     (random() %      2187);
+		set_eo_coord     (random() %      2048);
+		set_cp_coord     (random() %     40320);
+		set_ep_coord_full(random() % 479001600);
+
+		if (parity(cp, 8) != parity(ep, 12))
+			num++;
+		else
+			printf("%s\n", get_cube(cube, sizeof(cube)));
+	}
+	return 0;
+}
+#include <stdio.h>
+#include <string.h>
+#include "cubeutils.h"
+
+char co_prune[2187],    eo_prune[2048],    cp_prune[40320],    ep_prune[40320],    ud1_prune[495],    ud2_prune[24];
+int  co_trans[2187][6], eo_trans[2048][6], cp_trans[40320][6], ep_trans[40320][6], ud1_trans[495][6], ud2_trans[24][6];
+
+/*
+ * moves are:
+ * U U2 U' D D2 D' F F2 F' B B2 B' R  R2 R' L  L2 L'
+ * 0 1  2  3 4  5  6 7  8  9 10 11 12 13 14 15 16 17
+ */
+int sol[30];
+
+/*
+ * groups are:
+ * 0 = G0 = <U, D, F , B , R , L >
+ * 1 = G1 = <U, D, F2, B2, R2, L2>
+ */
+enum { G0, G1 };
+
+/*
+ * generic pruning table initialization
+ */
+void init_prune(int group, int coord, char prune_table[], int trans_table[][6], int mdepth, int depth, int last)
+{
+	int i, mv, old = coord;
+
+	if (depth == mdepth || prune_table[coord] <= depth)
+		return;
+
+	prune_table[coord] = depth;
+
+	for (mv = 0; mv < 18; mv += 3, coord = old) {
+		if (mv / 3 == last / 3)
+			continue;
+		for (i = 0; i < 3; i++) {
+			if (group && mv >= 6 && i) // only want double turns on F, B, R, L in G1
+				break;
+			coord = trans_table[coord][mv / 3];
+			init_prune(group, coord, prune_table, trans_table, mdepth, depth + 1, mv);
+		}
+	}
+}
+
+/*
+ * specific pruning table initializations
+ */
+void init_prune_tables(void)
+{
+	memset(eo_prune,  127, sizeof(eo_prune ));
+	memset(co_prune,  127, sizeof(co_prune ));
+	memset(ep_prune,  127, sizeof(ep_prune ));
+	memset(cp_prune,  127, sizeof(cp_prune ));
+	memset(ud1_prune, 127, sizeof(ud1_prune));
+	memset(ud2_prune, 127, sizeof(ud2_prune));
+
+	init_prune(0, 0, eo_prune,  eo_trans,  8, 0, -1);
+	init_prune(0, 0, co_prune,  co_trans,  7, 0, -1);
+	init_prune(0, 0, ud1_prune, ud1_trans, 6, 0, -1);
+
+	init_prune(1, 0, cp_prune,  cp_trans, 14, 0, -1);
+	init_prune(1, 0, ep_prune,  ep_trans,  9, 0, -1);
+	init_prune(1, 0, ud2_prune, ud2_trans, 5, 0, -1);
+}
+
+/*
+ * generic transition table initialization
+ */
+void init_trans(int group, int tran_table[][6], int len, void (*set_coord)(int), int (*get_coord)(void))
+{
+	int i, mv;
+
+	for (i = 0; i < len; i++) {
+		for (mv = 0; mv < 18; mv += 3) {
+			set_coord(i);
+			do_move(mv);
+			if (group && mv >= 6) // only want double turns on F, B, R, L in G1
+				do_move(mv);
+			tran_table[i][mv / 3] = get_coord();
+		}
+	}
+}
+
+/*
+ * specific transition table initializations
+ */
+void init_trans_tables(void)
+{
+	init_trans(0, eo_trans,  2048,  set_eo_coord,  get_eo_coord );
+	init_trans(0, co_trans,  2187,  set_co_coord,  get_co_coord );
+	init_trans(0, ud1_trans, 495,   set_ud1_coord, get_ud1_coord);
+
+	init_trans(1, cp_trans,  40320, set_cp_coord,  get_cp_coord );
+	init_trans(1, ep_trans,  40320, set_ep_coord,  get_ep_coord );
+	init_trans(1, ud2_trans, 24,    set_ud2_coord, get_ud2_coord);
+}
+
+/*
+ * generic phase solver
+ */
+int solve(int group, int e_coord, int c_coord, int ud_coord, int depth, int last)
+{
+	int mv, i, e_tmp, c_tmp, ud_tmp, face;
+
+	if (e_coord == 0 && c_coord == 0 && ud_coord == 0) return 1; // success!
+	if (!group && (depth == 0 || eo_prune[e_coord] > depth || co_prune[c_coord] > depth || ud1_prune[ud_coord] > depth)) return 0;
+	if ( group && (depth == 0 || ep_prune[e_coord] > depth || cp_prune[c_coord] > depth || ud2_prune[ud_coord] > depth)) return 0;
+
+	for (mv = face = 0; mv < 18; mv += 3, face = mv / 3) {
+		// no two moves in a row on same face, no move on same axis after U, F, R
+		if (face == last || ((last & 1) == 0 && face == last + 1))
+			continue;
+
+		e_tmp  = e_coord;
+		c_tmp  = c_coord;
+		ud_tmp = ud_coord;
+
+		for (i = 0; i < 3; i++) {
+			e_tmp  = group ? ep_trans [e_tmp ][face] : eo_trans [e_tmp ][face];
+			c_tmp  = group ? cp_trans [c_tmp ][face] : co_trans [c_tmp ][face];
+			ud_tmp = group ? ud2_trans[ud_tmp][face] : ud1_trans[ud_tmp][face];
+
+			if (solve(group, e_tmp, c_tmp, ud_tmp, depth - 1, face)) {
+				sol[(group ? 30 : 12) - depth] = mv + ((group && mv >= 6) ? 1 : i);
+				return 1;
+			}
+			if (group && mv >= 6)
+				break;
+		}
+	}
+	return 0;
+}
+
+void print_move(int mv)
+{
+	char *faces = "UDFBRL", *num = " 2'";
+
+	printf("%c%c ", faces[mv / 3], num[mv % 3]);
+}
+
+int main(int argc, char **argv)
+{
+	char buf[128], i;
+
+	init_trans_tables();
+	init_prune_tables();
+
+	while (fgets(buf, sizeof(buf), stdin)) {
+		memset(sol, -1, sizeof(sol));
+		set_cube(buf);
+
+		for (i = 0; solve(G0, get_eo_coord(), get_co_coord(), get_ud1_coord(), i, -1) == 0; i++)
+			;
+
+		for (i = 12 - i; i < 12; i++)
+			do_move(sol[i]);
+
+		for (i = 0; solve(G1, get_ep_coord(), get_cp_coord(), get_ud2_coord(), i, -1) == 0; i++)
+			;
+
+		// if the last move from phase 1 and first move from phase 2 are on the same face
+		// it will always be a quarter turn then half turn on FBLR
+		if (sol[11] > -1 && sol[30 - i] > -1 && sol[30 - i] / 3 == sol[11] / 3) {
+			sol[30 - i] = -1;
+			sol[11] += (sol[11] % 3) ? -2 : 2;
+		}
+
+		for (i = 0; i < 30; i++)
+			if (sol[i] > -1)
+				print_move(sol[i]);
+
+		printf("\n");
+	}
+	return 0;
+}
+
+/* vim: set ts=4 sw=4 noexpandtab : */