aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano.tronto@gmail.com>2020-06-21 23:01:57 +0200
committerSebastiano Tronto <sebastiano.tronto@gmail.com>2020-06-21 23:01:57 +0200
commit0e8d73bb3edcc8bdff6e3ded442b66f68265059a (patch)
tree4f92deb9ace97e79332c0e7ce390b76b81aeaae9 /src
parent4e359b44ce111b04cc4d2b28033fba4ab4e6e989 (diff)
downloadnissy-0e8d73bb3edcc8bdff6e3ded442b66f68265059a.tar.gz
nissy-0e8d73bb3edcc8bdff6e3ded442b66f68265059a.zip
First push
Diffstat (limited to '')
-rwxr-xr-xsrc/compile.sh1
-rw-r--r--src/coordinates.c288
-rw-r--r--src/coordinates.h92
-rw-r--r--src/io.c232
-rw-r--r--src/io.h21
-rw-r--r--src/main.c801
-rw-r--r--src/moves.c526
-rw-r--r--src/moves.h83
-rw-r--r--src/pruning_tables.c483
-rw-r--r--src/pruning_tables.h66
-rw-r--r--src/solver.c893
-rw-r--r--src/solver.h13
-rw-r--r--src/utils.c115
-rw-r--r--src/utils.h54
14 files changed, 3668 insertions, 0 deletions
diff --git a/src/compile.sh b/src/compile.sh
new file mode 100755
index 0000000..49d655e
--- /dev/null
+++ b/src/compile.sh
@@ -0,0 +1 @@
gcc -Wall -Wextra -O3 -std=c99 -o ../nissy -g *.c
diff --git a/src/coordinates.c b/src/coordinates.c
new file mode 100644
index 0000000..284aaaa
--- /dev/null
+++ b/src/coordinates.c
@@ -0,0 +1,288 @@
1/* blabla */
2
3#include <stdio.h>
4
5#include "utils.h"
6#include "coordinates.h"
7
8/* Names of pieces and moves. */
9char edge_string_list[12][5] = {
10 "UF", "UL", "UB", "UR", "DF", "DL", "DB", "DR", "FR", "FL", "BL", "BR"
11};
12
13char corner_string_list[8][5] = {
14 "UFR", "UFL", "UBL", "UBR", "DFR", "DFL", "DBL", "DBR"
15};
16
17char move_string_list[19][5] = {
18 "-",
19 "U", "U2", "U\'", "D", "D2", "D\'", "R", "R2", "R\'",
20 "L", "L2", "L\'", "F", "F2", "F\'", "B", "B2", "B\'"
21};
22
23int inverse_move[19] = {
24 -1, U3, U2, U, D3, D2, D, R3, R2, R, L3, L2, L, F3, F2, F, B3, B2, B
25};
26
27/* Convert piece representation from integer to array.
28 * Come convertions are not "perfect": for example, and epud type of piece
29 * is represented by a permutation index in 8! elements, but it as an array
30 * it is converted to the first 8 elements of a 12 elements ep array (with
31 * meaningless values for the other 4 elements). */
32
33void ep_int_to_array(int ep, int a[12]) {
34 index_to_perm(ep, 12, a);
35}
36
37void epud_int_to_array(int epud, int a[12]) {
38 index_to_perm(epud, 8, a); /* Last 4 elements are left untouched. */
39}
40
41void epfb_int_to_array(int epfb, int a[12]) {
42 int edges[] = {UF, UB, DF, DB, FR, FL, BL, BR};
43 int b[8];
44 index_to_perm(epfb, 8, b);
45 for (int i = 0; i < 8; i++)
46 a[edges[i]] = edges[b[i]];
47}
48
49void eprl_int_to_array(int eprl, int a[12]) {
50 int edges[] = {UL, UR, DL, DR, FR, FL, BL, BR};
51 int b[8];
52 index_to_perm(eprl, 8, b);
53 for (int i = 0; i < 8; i++)
54 a[edges[i]] = edges[b[i]];
55}
56
57void epose_int_to_array(int epos, int a[12]) {
58 int edges[] = {FR, FL, BL, BR};
59 index_to_subset(epos, 12, 4, a);
60 for (int i = 0, j = 0; i < 12; i++)
61 a[i] = (a[i] == 1) ? edges[j++] : -1;
62}
63
64void eposs_int_to_array(int epos, int a[12]) {
65 int edges[] = {UL, UR, DL, DR};
66 index_to_subset(epos, 12, 4, a);
67 for (int i = 0, j = 0; i < 12; i++)
68 a[i] = (a[i] == 1) ? edges[j++] : -1;
69 /* Swap with last 4, so 0 is alway solved state */
70 for (int i = 0; i < 4; i++)
71 swap(&a[edges[i]], &a[i+8]);
72}
73
74void eposm_int_to_array(int epos, int a[12]) {
75 int edges[] = {UF, UB, DF, DB};
76 index_to_subset(epos, 12, 4, a);
77 for (int i = 0, j = 0; i < 12; i++)
78 a[i] = (a[i] == 1) ? edges[j++] : -1;
79 /* Swap with last 4, so 0 is alway solved state */
80 for (int i = 0; i < 4; i++)
81 swap(&a[edges[i]], &a[i+8]);
82}
83
84void epe_int_to_array(int epe, int a[12]) {
85 index_to_perm(epe, 4, a+8);
86 for (int i = 0; i < 4; i++)
87 a[i+8] += 8;
88}
89
90void eps_int_to_array(int eps, int a[12]) {
91 int edges[] = {UL, UR, DL, DR};
92 int b[4];
93 index_to_perm(eps, 4, b);
94 for (int i = 0; i < 4; i++)
95 a[edges[i]] = edges[b[i]];
96}
97
98void epm_int_to_array(int epm, int a[12]) {
99 int edges[] = {UF, UB, DF, DB};
100 int b[4];
101 index_to_perm(epm, 4, b);
102 for (int i = 0; i < 4; i++)
103 a[edges[i]] = edges[b[i]];
104}
105
106void emslices_int_to_array(int emslices, int a[12]) {
107 int b[] = {0,0,0,0,0,0,0,0};
108 int eslice[] = {FR, FL, BL, BR};
109 int mslice[] = {UF, UB, DF, DB};
110
111 index_to_subset(emslices % binom12on4, 12, 4, a);
112 index_to_subset(emslices / binom12on4, 8, 4, b);
113
114 if (emslices % binom12on4 == 0) {
115 swap(&b[UF], &b[DL]);
116 swap(&b[UB], &b[DR]);
117 /*for (int i = 0; i < 4; i++)
118 swap(&b[mslice[i]], &b[i+4]);*/
119 }
120
121 for (int i = 0, j = 0; j < 8; i++, j++) {
122 while (a[i])
123 i++;
124 a[i] = b[j] ? 2 : -1;
125 }
126 for (int i = 0, j1 = 0, j2 = 0; i < 12; i++) {
127 if (a[i] == 1)
128 a[i] = eslice[j1++];
129 if (a[i] == 2)
130 a[i] = mslice[j2++];
131 }
132}
133
134void cp_int_to_array(int cp, int a[8]) {
135 index_to_perm(cp, 8, a);
136}
137
138void eo_11bits_to_array(int eo, int a[12]) {
139 int_to_sum_zero_array(eo, 2, 12, a);
140}
141
142void co_7trits_to_array(int co, int a[8]) {
143 int_to_sum_zero_array(co, 3, 8, a);
144}
145
146
147
148
149
150int ep_array_to_int(int ep[12]) {
151 return perm_to_index(ep, 12);
152}
153
154int epud_array_to_int(int ep[12]) {
155 return perm_to_index(ep, 8); /* Last 4 elements are ignored */
156}
157
158int epfb_array_to_int(int ep[12]) {
159 int index[] = {0, -1, 1, -1, 2, -1, 3, -1, 4, 5, 6, 7};
160 int b[8];
161 for (int i = 0; i < 12; i++)
162 if (index[i] != -1)
163 b[index[i]] = index[ep[i]];
164 return perm_to_index(b, 8);
165}
166
167int eprl_array_to_int(int ep[12]) {
168 int index[] = {-1, 0, -1, 1, -1, 2, -1, 3, 4, 5, 6, 7};
169 int b[8];
170 for (int i = 0; i < 12; i++)
171 if (index[i] != -1)
172 b[index[i]] = index[ep[i]];
173 return perm_to_index(b, 8);
174}
175
176int epose_array_to_int(int ep[12]) {
177 int a[12];
178 for (int i = 0; i < 12; i++)
179 a[i] = (ep[i] >= FR);
180 return subset_to_index(a, 12, 4);
181}
182
183int eposs_array_to_int(int ep[12]) {
184 int a[12];
185 int edges[] = {UL, UR, DL, DR};
186 for (int i = 0; i < 12; i++)
187 a[i] = (ep[i] == UL || ep[i] == UR || ep[i] == DL || ep[i] == DR);
188 /* Swap with last 4, so 0 is alway solved state */
189 for (int i = 0; i < 4; i++)
190 swap(&a[edges[i]], &a[i+8]);
191 return subset_to_index(a, 12, 4);
192}
193
194int eposm_array_to_int(int ep[12]) {
195 int a[12];
196 int edges[] = {UF, UB, DF, DB};
197 for (int i = 0; i < 12; i++)
198 a[i] = (ep[i] == UF || ep[i] == UB || ep[i] == DF || ep[i] == DB);
199 /* Swap with last 4, so 0 is alway solved state */
200 for (int i = 0; i < 4; i++)
201 swap(&a[edges[i]], &a[i+8]);
202 return subset_to_index(a, 12, 4);
203}
204
205int epe_array_to_int(int ep[12]) {
206 int b[4];
207 for (int i = 0; i < 4; i++)
208 b[i] = ep[i+8] - 8;
209 return perm_to_index(b, 4);
210}
211
212int eps_array_to_int(int ep[12]) {
213 int index[] = {-1, 0, -1, 1, -1, 2, -1, 3, -1, -1, -1, -1};
214 int b[4];
215 for (int i = 0; i < 12; i++)
216 if (index[i] != -1)
217 b[index[i]] = index[ep[i]];
218 return perm_to_index(b, 4);
219}
220
221int epm_array_to_int(int ep[12]) {
222 int index[] = {0, -1, 1, -1, 2, -1, 3, -1, -1, -1, -1, -1};
223 int b[4];
224 for (int i = 0; i < 12; i++)
225 if (index[i] != -1)
226 b[index[i]] = index[ep[i]];
227 return perm_to_index(b, 4);
228}
229
230int emslices_array_to_int(int ep[12]) {
231 int a[12], b[12], c[8] = {0, 0, 0, 0, 0, 0, 0, 0};
232 /*int edges[] = {UF, UB, DF, DB};*/
233 for (int i = 0; i < 12; i++) {
234 a[i] = (ep[i] >= FR) ? 1 : 0;
235 b[i] = (ep[i] == UF || ep[i] == UB || ep[i] == DF || ep[i] == DB) ? 1 : 0;
236 }
237
238 /*for ( int i = 0; i < 12; i++)
239 printf("%d ", ep[i]);
240 printf("\n");*/
241
242 for (int i = 0, j = 0; i < 12; i++, j++) {
243 if (a[i])
244 j--;
245 if (b[i])
246 c[j] = 1;
247 }
248
249 int epose = subset_to_index(a, 12, 4);
250
251 /*if (epose == 0) {
252 printf("Before: ");
253 for (int i = 0; i < 8; i++)
254 printf("%d ", c[i]);
255 printf("\n");
256 for (int i = 0; i < 4; i++)
257 swap(&c[edges[i]], &c[i+4]);
258 printf("After: ");
259 for (int i = 0; i < 8; i++)
260 printf("%d ", c[i]);
261 printf("\n");
262 }*/
263 if (epose == 0) {
264 swap(&c[UF], &c[DL]);
265 swap(&c[UB], &c[DR]);
266 }
267
268 /*for ( int i = 0; i < 8; i++)
269 printf("%d ", c[i]);
270 printf("\n");*/
271 int eposm = subset_to_index(c, 8, 4);
272
273 return epose + 495*eposm;
274}
275
276
277int cp_array_to_int(int cp[8]) {
278 return perm_to_index(cp, 8);
279}
280
281int eo_array_to_11bits(int a[12]) {
282 return digit_array_to_int(a, 11, 2);
283}
284
285int co_array_to_7trits(int a[8]) {
286 return digit_array_to_int(a, 7, 3);
287}
288
diff --git a/src/coordinates.h b/src/coordinates.h
new file mode 100644
index 0000000..10f7d18
--- /dev/null
+++ b/src/coordinates.h
@@ -0,0 +1,92 @@
1/* General rule for piece numbering (visually nicer):
2 *
3 * 0 1 2 3 4 5 6 7 8 9 10 11
4 * UF UL UB UR DF DL DB DR FR FL BL BR
5 * UFR UFL UBL UBR DFR DFL DBL DBR
6 *
7 * The order of moves is
8 * 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
9 * - U U2 U' D D2 D' R R2 R' L L2 L' F F2 F' B B2 B'
10 * (0 is reserved for no move) */
11
12#define UF 0
13#define UL 1
14#define UB 2
15#define UR 3
16#define DF 4
17#define DL 5
18#define DB 6
19#define DR 7
20#define FR 8
21#define FL 9
22#define BL 10
23#define BR 11
24
25#define UFR 0
26#define UFL 1
27#define UBL 2
28#define UBR 3
29#define DFR 4
30#define DFL 5
31#define DBL 6
32#define DBR 7
33
34#define U 1
35#define U2 2
36#define U3 3
37#define D 4
38#define D2 5
39#define D3 6
40#define R 7
41#define R2 8
42#define R3 9
43#define L 10
44#define L2 11
45#define L3 12
46#define F 13
47#define F2 14
48#define F3 15
49#define B 16
50#define B2 17
51#define B3 18
52
53extern char edge_string_list[12][5];
54extern char corner_string_list[8][5];
55extern char move_string_list[19][5];
56extern int inverse_move[19];
57
58/* Convert piece representation from integer to array.
59 * Come convertions are not "perfect": for example, and epud type of piece
60 * is represented by a permutation index in 8! elements, but it as an array
61 * it is converted to the first 8 elements of a 12 elements ep array (with
62 * meaningless values for the other 4 elements). */
63
64void ep_int_to_array(int ep, int a[12]);
65void epud_int_to_array(int epud, int a[12]);
66void epfb_int_to_array(int epfb, int a[12]);
67void eprl_int_to_array(int eprl, int a[12]);
68void epose_int_to_array(int epos, int a[12]);
69void eposs_int_to_array(int epos, int a[12]);
70void eposm_int_to_array(int epos, int a[12]);
71void epe_int_to_array(int epe, int a[12]);
72void epm_int_to_array(int epe, int a[12]);
73void eps_int_to_array(int epe, int a[12]);
74void emslices_int_to_array(int emslices, int a[12]);
75void cp_int_to_array(int cp, int a[8]);
76void eo_11bits_to_array(int eo, int a[12]);
77void co_7trits_to_array(int co, int a[8]);
78
79int ep_array_to_int(int ep[12]);
80int epud_array_to_int(int ep[12]);
81int epfb_array_to_int(int ep[12]);
82int eprl_array_to_int(int ep[12]);
83int epose_array_to_int(int ep[12]);
84int eposs_array_to_int(int ep[12]);
85int eposm_array_to_int(int ep[12]);
86int epe_array_to_int(int epe[12]);
87int epm_array_to_int(int epe[12]);
88int eps_array_to_int(int epe[12]);
89int emslices_array_to_int(int ep[12]);
90int cp_array_to_int(int cp[8]);
91int eo_array_to_11bits(int a[12]);
92int co_array_to_7trits(int a[8]);
diff --git a/src/io.c b/src/io.c
new file mode 100644
index 0000000..ab0f658
--- /dev/null
+++ b/src/io.c
@@ -0,0 +1,232 @@
1#include <stdio.h>
2#include <stdint.h>
3#include <string.h>
4
5#include "coordinates.h"
6#include "moves.h"
7#include "utils.h"
8
9/* Functions for nice output */
10char *edge_string(int i) {
11 return (i > -1 && i < 12) ? edge_string_list[i] : "-";
12}
13
14char *corner_string(int i) {
15 return (i > -1 && i < 8) ? corner_string_list[i] : "-";
16}
17
18char *move_string(int i) {
19 return (i > -1 && i < 19) ? move_string_list[i] : "err";
20}
21
22void print_ep_array(int ep[12]) {
23 for (int i = 0; i < 12; i++)
24 printf(" %s ", edge_string(ep[i]));
25}
26
27void print_ep_int(int ep) {
28 int aux[12];
29 ep_int_to_array(ep, aux);
30 print_ep_array(aux);
31}
32
33void print_cp_array(int cp[8]) {
34 for (int i = 0; i < 8; i++)
35 printf(" %s ", corner_string(cp[i]));
36}
37
38void print_cp_int(int cp) {
39 int aux[8];
40 cp_int_to_array(cp, aux);
41 print_cp_array(aux);
42}
43
44void print_eo_array(int eo[12]) {
45 for (int i = 0; i < 12; i++) {
46 if (eo[i])
47 printf(" x ");
48 else
49 printf(" ");
50 }
51}
52
53void print_eo_int(int eo) {
54 int aux[12];
55 eo_11bits_to_array(eo, aux);
56 print_eo_array(aux);
57}
58
59void print_co_array(int co[8]) {
60 for (int i = 0; i < 8; i++) {
61 if (co[i] == 0)
62 printf(" ");
63 if (co[i] == 1)
64 printf(" cw ");
65 if (co[i] == 2)
66 printf(" ccw ");
67 }
68}
69
70void print_co_int(int co) {
71 int aux[8];
72 co_7trits_to_array(co, aux);
73 print_co_array(aux);
74}
75
76void print_cube_scram(int *scram) {
77 int ep = 0, cp = 0, eofb = 0, coud = 0;
78 for (int i = 0; scram[i]; i++) {
79 ep = apply_move_ep_int(scram[i], ep);
80 cp = cp_transition_table[cp][scram[i]];
81 eofb = eofb_transition_table[eofb][scram[i]];
82 coud = coud_transition_table[coud][scram[i]];
83 }
84 printf("\t\t"); print_ep_int(0); printf("\n");
85 printf("EP:\t\t"); print_ep_int(ep); printf("\n");
86 printf("EO(F/B):\t"); print_eo_int(eofb); printf("\n");
87 printf("\n");
88 printf("\t\t"); print_cp_int(0); printf("\n");
89 printf("CP:\t\t"); print_cp_int(cp); printf("\n");
90 printf("CO(U/D):\t"); print_co_int(coud); printf("\n");
91}
92
93
94void copy_moves(int *src, int *dst) {
95 for (int i = 0; (dst[i] = src[i]); i++);
96}
97
98void append_moves(int *src, int *dst) {
99 int n = 0;
100 for (; dst[n]; n++);
101 copy_moves(src, dst+n);
102}
103
104/* Parse a string and saves the move in a. Supports NISS notation.
105 * Returns the number of moves, or -1 in case of error. */
106int read_moves(char *str, int *a) {
107 int count = 0;
108 int niss = 0;
109 for (int i = 0; str[i] && str[i] != '\n'; i++) {
110 while (str[i] == ' ' || str[i] == '\t') i++;
111 switch (str[i]) {
112 case 'U':
113 a[count++] = niss ? -U : U;
114 break;
115 case 'D':
116 a[count++] = niss ? -D : D;
117 break;
118 case 'R':
119 a[count++] = niss ? -R : R;
120 break;
121 case 'L':
122 a[count++] = niss ? -L : L;
123 break;
124 case 'F':
125 a[count++] = niss ? -F : F;
126 break;
127 case 'B':
128 a[count++] = niss ? -B : B;
129 break;
130 case '(':
131 if (niss)
132 return -1;
133 else
134 niss = 1;
135 break;
136 case ')':
137 if (!niss)
138 return -1;
139 else
140 niss = 0;
141 break;
142 default:
143 return -1;
144 }
145 switch (str[++i]) {
146 case '2':
147 a[count-1] += niss ? -1 : 1;
148 break;
149 case '\'':
150 case '3':
151 a[count-1] += niss ? -2 : 2;
152 break;
153 case '1':
154 default:
155 --i;
156 }
157 }
158 a[count] = 0;
159 return count;
160}
161
162/* Read moves from standard input, after a prompt. */
163int read_moves_from_prompt(int *a) {
164 char str[1000];
165 printf("Enter moves: ");
166 if (fgets(str, 1000, stdin) == NULL)
167 return -1;
168 return read_moves(str, a);
169}
170
171/* Read moves from a list of token, each containing one or more moves. */
172int read_moves_from_tok(int n, char tok[][100], int *a) {
173 char str[1000] = "";
174 for (int i = 0; i < n; i++)
175 strcat(str, tok[i]);
176 return read_moves(str, a);
177}
178
179/* Checks if a sequence of moves uses NISS */
180int uses_niss(int *str) {
181 for (int i = 0; str[i]; i++)
182 if (str[i] < 0)
183 return 1;
184 return 0;
185}
186
187/* A (B) -> B' A */
188int unniss(int *src, int *dst) {
189 int n = 0;
190 for (int i = 0; src[i]; i++)
191 if (src[i] < 0)
192 n++;
193
194 int norm_count = n, inv_count = n-1;
195 for (int i = 0; src[i]; i++)
196 if (src[i] > 0)
197 dst[norm_count++] = src[i];
198 else
199 dst[inv_count--] = inverse_move[-src[i]];
200
201 dst[norm_count] = 0;
202
203 return n;
204}
205
206int invert(int *src, int *dst) {
207 int aux[255];
208 for (int i = 0; (aux[i] = -src[i]); i++);
209 return unniss(aux, dst);
210}
211
212int len(int *scram) {
213 int m;
214 for (m = 0; scram[m]; m++);
215 return m;
216}
217
218void print_moves(int moves_list[]) {
219 int niss = 0;
220 for (int i = 0; moves_list[i]; i++) {
221 if (!niss && moves_list[i] < 0) {
222 printf("(");
223 niss = 1;
224 }
225 printf("%s", move_string_list[abs(moves_list[i])]);
226 if (niss && moves_list[i+1] >= 0) {
227 niss = 0;
228 printf(")");
229 }
230 printf(" ");
231 }
232}
diff --git a/src/io.h b/src/io.h
new file mode 100644
index 0000000..f1b585d
--- /dev/null
+++ b/src/io.h
@@ -0,0 +1,21 @@
1#include <stdint.h>
2
3char *edge_string(int edge);
4char *corner_string(int edge);
5char *move_string(int move);
6
7void print_cube_scram(int *scram);
8
9void copy_moves(int *src, int *dst);
10void append_moves(int *src, int *dst);
11
12int read_moves(char *str, int *a);
13int read_moves_from_prompt(int *a);
14int read_moves_from_tok(int n, char tok[][100], int *a);
15
16int uses_niss(int *str);
17int unniss(int *src, int *dst);
18int invert(int *src, int *dst);
19int len(int *scram);
20
21void print_moves(int move_list[]);
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..30fe517
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,801 @@
1/* blabla */
2#include <stdio.h>
3#include <stdlib.h>
4#include "utils.h"
5#include "coordinates.h"
6#include "io.h"
7#include "moves.h"
8#include "solver.h"
9#include "string.h"
10
11char *commands[][10] = {
12 {"help", "[COMMAND]",
13 "Print this help, or a help page for COMMAND."},
14 {"save", "[MOVES|@ID|$ID]",
15 "Save or copy a scramble."},
16 {"change", "$ID1 [MOVES|$ID2|@ID2]",
17 "Change a memorized scramble."},
18 {"print", "[$ID|@ID]",
19 "Print memorized sequences."},
20 {"add", "[MOVES|$ID1|@ID1] $ID2",
21 "Add moves at the end of a memorized scramble."},
22 {"invert", "[MOVES|$ID|@ID]",
23 "Inverts the given sequence of moves."},
24 {"unniss", "[MOVES|$ID|@ID]}",
25 "Removes NISS: A (B) -> B\' A."},
26 {"pic", "[MOVES|$ID|@ID]",
27 "Show a text description of the scrambled cube."},
28 {"solve", "[MOVES|$ID|@ID]",
29 "Solves a scramble."},
30 {"replace", "[MOVES|$ID|@ID]",
31 "Find non-optimal subsequences."},
32 {"eo", "[MOVES|$ID|@ID]",
33 "Solves EO."},
34 {"dr", "[MOVES|$ID|@ID]",
35 "Solves DR, either directly or from eo."},
36 {"htr", "[MOVES|$ID|@ID]",
37 "Solves HTR from DR."},
38 {"drfinish", "[MOVES|$ID|@ID]",
39 "Solves the cube after DR."},
40 {"htrfinish", "[MOVES|$ID|@ID]",
41 "Solves the cube using only half turns."},
42 {"drcorners", "[MOVES|$ID|@ID]",
43 "Solves corners after DR."},
44 {"exit", "",
45 "Exit nissy."},
46 {"quit", "",
47 "Exit nissy."},
48 {"", "", ""}
49};
50
51/* Saved sequences of moves */
52int scr_count=1, tmp_count=1, max_tmp=999;
53int scrambles[255][255], tmp[1000][255];
54
55int read_moves_from_variable(char *id, int *dst) {
56 char c = id[0];
57 if (c != '$' && c != '@')
58 return -1;
59 int n = atoi(id+1);
60 if (n <= 0 || n >= (c == '$' ? scr_count : tmp_count))
61 return -1;
62 copy_moves(c == '$' ? scrambles[n] : tmp[n], dst);
63 return n;
64}
65
66int read_moves_from_argument(int n, char tok[][100], int *dst) {
67 int r = read_moves_from_variable(tok[0], dst);
68 return (r != -1) ? r : read_moves_from_tok(n, tok, dst);
69}
70
71void print_results(int n, int res[][21]) {
72 if (n == -1)
73 printf("Pre-conditions not satisfied (or other error).\n");
74
75 if (n == 0)
76 printf("No result found (try different bounds).\n");
77
78 if (n > 1)
79 printf("Found %d results.\n", n);
80 tmp_count = 1; /* Reset temporary count */
81 for (int i = 0; i < n; i++) {
82 if (i < max_tmp) {
83 copy_moves(res[i], tmp[tmp_count]);
84 printf("@%d:\t", tmp_count++);
85 } else {
86 printf(" \t");
87 }
88 print_moves(res[i]);
89 printf("(%d)\n", len(res[i]));
90 }
91}
92
93/* Removes extra white spaces from the input string */
94int parsecmd(char *cmd, char cmdtok[][100]) {
95 char *i = cmd, *j = cmd;
96 while (*j != '\n' && *j != EOF) {
97 *i = *j;
98 if (*i == ' ' || *i == '\t')
99 *i = ' ';
100 ++j;
101 if (*i == ' ' || *i == '\t')
102 while (*j == ' ' || *j == '\t')
103 ++j;
104 ++i;
105 }
106 if (*(i-1) == ' ')
107 *(i-1) = 0;
108 else
109 *i = 0;
110
111 int n = 0;
112 char *s = strtok(cmd, " ");
113 while (s != NULL) {
114 strcpy(cmdtok[n++], s);
115 s = strtok(NULL, " ");
116 }
117 return n;
118}
119
120void help_cmd(int n, char cmdtok[][100]) {
121 if (n == 1) {
122 printf("\n");
123 for (int i = 0; commands[i][0][0]; i++)
124 printf("%-10s%-20s%s\n", commands[i][0], commands[i][1], commands[i][2]);
125 printf("\n");
126 printf("Type \'help\' followed by a command for a detailed help page.\n");
127 printf("Type \'help nissy\' for a general user guide.\n");
128 } else if (n == 2) {
129 char fname[255], line[255] = "";
130 FILE *file;
131 sprintf(fname, "docs/%s.txt", cmdtok[1]);
132 file = fopen(fname, "r");
133 if (file == NULL) {
134 printf("No help file for %s.\n", cmdtok[1]);
135 return;
136 }
137 while (fgets(line, 255, file) != NULL)
138 printf("%s", line);
139 } else {
140 printf("help: wrong syntax.\n");
141 }
142}
143
144void save_cmd(int n, char cmdtok[][100]) {
145 int scram[255];
146 if (n == 1) {
147 if (read_moves_from_prompt(scram) == -1) {
148 printf("save: error reading moves. Not saved.\n");
149 return;
150 }
151 } else if (read_moves_from_argument(n-1, cmdtok+1, scram) == -1) {
152 printf("save: error reading moves or ID. Not saved.\n");
153 return;
154 }
155
156 copy_moves(scram, scrambles[scr_count]);
157
158 printf("$%d:\t", scr_count);
159 print_moves(scrambles[scr_count]);
160 printf("\n");
161 scr_count++;
162}
163
164void change_cmd(int n, char cmdtok[][100]) {
165 int id, scram[255];
166 if (n == 1) {
167 printf("change: you must specify an $ID.\n");
168 return;
169 } else if (cmdtok[1][0] != '$') {
170 printf("change: invalid $ID.\n");
171 return;
172 } else {
173 id = atoi(cmdtok[1]+1);
174 if (id <= 0 || id >= scr_count) {
175 printf("change: invalid $ID.\n");
176 return;
177 }
178 if (n == 2) {
179 if (read_moves_from_prompt(scram) == -1) {
180 printf("change: error reading moves.\n");
181 return;
182 }
183 } else if (read_moves_from_argument(n-2, cmdtok+2, scram) == -1 ) {
184 printf("change: error reading moves or ID.\n");
185 return;
186 }
187 }
188
189 copy_moves(scram, scrambles[id]);
190
191 printf("$%d:\t", id);
192 print_moves(scrambles[id]);
193 printf("\n");
194}
195
196void print_cmd(int n, char cmdtok[][100]) {
197 if (n == 1) {
198 for (int i = 1; i < scr_count; i++) {
199 printf("$%d:\t", i);
200 print_moves(scrambles[i]);
201 printf("\n");
202 }
203 } else if (n == 2) {
204 int i = atoi(cmdtok[1]+1);
205 char sign = cmdtok[1][0];
206 if (sign != '$' && sign != '@') {
207 printf("print: invalid ID (must start with $ or @).\n");
208 return;
209 }
210 if (i > 0 && i < (sign == '$' ? scr_count : tmp_count)) {
211 printf("%c%d:\t", sign, i);
212 print_moves(sign == '$' ? scrambles[i] : tmp[i]);
213 printf("\n");
214 } else {
215 printf("print: invalid ID.\n");
216 return;
217 }
218 } else {
219 printf("print: wrong syntax.\n");
220 }
221}
222
223void add_cmd(int n, char cmdtok[][100]) {
224 int id, scram[255];
225 if (n == 1) {
226 printf("add: you must specify a destination $ID.\n");
227 return;
228 } else if (cmdtok[n-1][0] != '$') {
229 printf("add: invalid destination $ID.\n");
230 return;
231 } else {
232 id = atoi(cmdtok[n-1]+1);
233 if (id <= 0 || id >= scr_count) {
234 printf("add: invalid destination $ID.\n");
235 return;
236 }
237 if (n == 2) {
238 if (read_moves_from_prompt(scram) == -1) {
239 printf("add: error reading moves.\n");
240 return;
241 }
242 } else {
243 if (read_moves_from_argument(n-2, cmdtok+1, scram) == -1) {
244 printf("add: error reading moves or ID.\n");
245 return;
246 }
247 }
248 }
249
250 append_moves(scram, scrambles[id]);
251
252 printf("$%d:\t", id);
253 print_moves(scrambles[id]);
254 printf("\n");
255}
256
257void invert_cmd(int n, char cmdtok[][100]) {
258 int scram[255];
259 if (n == 1) {
260 if (read_moves_from_prompt(scram) == -1) {
261 printf("invert: error reading moves.\n");
262 return;
263 }
264 } else if (read_moves_from_argument(n-1, cmdtok+1, scram) == -1) {
265 printf("invert: error reading moves or ID.\n");
266 return;
267 }
268
269 if (uses_niss(scram)) {
270 printf("invert: cannot invert NISS.\n");
271 return;
272 }
273
274 invert(scram, tmp[1]);
275 tmp_count = 2;
276
277 printf("@1:\t");
278 print_moves(tmp[1]);
279 printf("\n");
280}
281
282void unniss_cmd(int n, char cmdtok[][100]) {
283 int scram[255];
284 if (n == 1) {
285 if (read_moves_from_prompt(scram) == -1) {
286 printf("unniss: error reading moves.\n");
287 return;
288 }
289 } else if (read_moves_from_argument(n-1, cmdtok+1, scram) == -1) {
290 printf("unniss: error reading moves or ID.\n");
291 return;
292 }
293
294 unniss(scram, tmp[1]);
295 tmp_count = 2;
296
297 printf("@1:\t");
298 print_moves(tmp[1]);
299 printf("\n");
300}
301
302void pic_cmd(int n, char cmdtok[][100]) {
303 int scram[255];
304 if (n == 1) {
305 if (read_moves_from_prompt(scram) == -1) {
306 printf("pic: error reading moves.\n");
307 return;
308 }
309 } else if (read_moves_from_argument(n-1, cmdtok+1, scram) == -1) {
310 printf("pic: error reading moves or ID.\n");
311 return;
312 }
313 print_cube_scram(scram);
314}
315
316void solve_cmd(int n, char cmdtok[][100]) {
317 int m = 1, b = 20, optimal = 0;
318 int scram[255] = {[0] = 0};
319 int scram_unnissed[255];
320
321 /* Parse options */
322 for (int i = 1; i < n && scram[0] == 0; i++) {
323 if (!strncmp(cmdtok[i], "b=", 2)) {
324 b = atoi(cmdtok[i]+2);
325 if (b <= 0) {
326 printf("solve: bad option b.\n");
327 return;
328 }
329 } else if (!strncmp(cmdtok[i], "n=", 2)) {
330 m = atoi(cmdtok[i]+2);
331 if (m <= 0) {
332 printf("solve: bad option n.\n");
333 return;
334 }
335 } else if (!strcmp(cmdtok[i], "o")) {
336 optimal = 1;
337 } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
338 printf("solve: error reading moves or ID.\n");
339 return;
340 }
341 }
342
343 if (scram[0] == 0) {
344 if (read_moves_from_prompt(scram) == -1) {
345 printf("solve: error reading moves.\n");
346 return;
347 }
348 }
349
350 /* Call solver and print results */
351 unniss(scram, scram_unnissed);
352 int sol[m+2][21];
353 int s = solve_scram(scram_unnissed, sol, m, b, optimal);
354 print_results(s, sol);
355}
356
357void replace_cmd(int n, char cmdtok[][100]) {
358 int m = 10; /* max length */
359 int scram[255] = {[0] = 0};
360 int scram_unnissed[255];
361
362 /* Parse options */
363 for (int i = 1; i < n && scram[0] == 0; i++) {
364 if (!strncmp(cmdtok[i], "b=", 2)) {
365 m = atoi(cmdtok[i]+2);
366 if (m <= 0) {
367 printf("replace: bad option n.\n");
368 return;
369 }
370 } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
371 printf("replace: error reading moves or ID.\n");
372 return;
373 }
374 }
375
376 if (scram[0] == 0) {
377 if (read_moves_from_prompt(scram) == -1) {
378 printf("replace: error reading moves.\n");
379 return;
380 }
381 }
382
383 unniss(scram, scram_unnissed);
384 int l = len(scram_unnissed);
385 int aux1[255], aux2[15][21], aux3[21];
386 for (int i = 0; i < l; i++) {
387 for (int j = 2; j <= m && i + j <= l; j++) {
388 copy_moves(scram_unnissed+i, aux1);
389 aux1[j] = 0;
390 int s = solve_scram(aux1, aux2, 10, j-1, 1);
391 for (int k = 0; k < s; k++) {
392 invert(aux2[k], aux3);
393 /* TODO: the following part should also chek for the case when
394 * the last moves are R L or similar. */
395 if (aux3[0] != aux1[0] && aux3[len(aux3)-1] != aux1[len(aux1)-1]) {
396 printf("Replace [ ");
397 print_moves(aux1);
398 printf("] (moves %d-%d) with: [ ", i+1, i+j);
399 print_moves(aux3);
400 printf("] (-%d+%d)\n", j, len(aux3));
401 }
402 }
403 }
404 }
405}
406
407void eo_cmd(int n, char cmdtok[][100]) {
408
409 /* Default values */
410 int m = 1, b = 20;
411 int niss = 0, hide = 1;
412 int fb = 1, rl = 1, ud = 1;
413 int scram[255] = {[0] = 0};
414 int scram_unnissed[255];
415
416 /* Parse options */
417 for (int i = 1; i < n && scram[0] == 0; i++) {
418 if (!strcmp(cmdtok[i], "h")) {
419 hide = 0;
420 } else if (!strcmp(cmdtok[i], "niss")) {
421 niss = 1;
422 } else if (!strncmp(cmdtok[i], "axis=", 5)) {
423 fb = rl = ud = 0;
424 if (strstr(cmdtok[i], "fb") != NULL)
425 fb = 1;
426 if (strstr(cmdtok[i], "rl") != NULL)
427 rl = 1;
428 if (strstr(cmdtok[i], "ud") != NULL)
429 ud = 1;
430 if (fb + rl + ud == 0) {
431 printf("eo: bad axis option.\n");
432 return;
433 }
434 } else if (!strncmp(cmdtok[i], "n=", 2)) {
435 m = atoi(cmdtok[i]+2);
436 if (m <= 0) {
437 printf("eo: bad option n.\n");
438 return;
439 }
440 } else if (!strncmp(cmdtok[i], "b=", 2)) {
441 b = atoi(cmdtok[i]+2);
442 if (b <= 0) {
443 printf("eo: bad option b.\n");
444 return;
445 }
446 } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
447 printf("eo: error reading moves or ID.\n");
448 return;
449 }
450 }
451
452 if (scram[0] == 0) {
453 if (read_moves_from_prompt(scram) == -1) {
454 printf("eo: error reading moves.\n");
455 return;
456 }
457 }
458
459 unniss(scram, scram_unnissed);
460
461 /* Call solver and print results */
462 int eo_list[m+5][21];
463 int neo = eo_scram_spam(scram_unnissed, eo_list, fb, rl, ud, m, b, niss,
464 hide);
465 print_results(neo, eo_list);
466}
467
468void dr_cmd(int n, char cmdtok[][100]) {
469
470 /* Default values */
471 int m = 1, b = 20;
472 int niss = 0, hide = 1;
473 int from = 0; /* 0: direct dr; {1,2,3}: from {eofb,eorl,eoud} */
474 int fb = 1, rl = 1, ud = 1;
475 int scram[255] = {[0] = 0};
476 int scram_unnissed[255];
477
478 /* Parse options */
479 for (int i = 1; i < n && scram[0] == 0; i++) {
480 if (!strcmp(cmdtok[i], "h")) {
481 hide = 0;
482 } else if (!strcmp(cmdtok[i], "niss")) {
483 niss = 1;
484 } else if (!strncmp(cmdtok[i], "axis=", 5)) {
485 fb = rl = ud = 0;
486 if (strstr(cmdtok[i], "fb") != NULL)
487 fb = 1;
488 if (strstr(cmdtok[i], "rl") != NULL)
489 rl = 1;
490 if (strstr(cmdtok[i], "ud") != NULL)
491 ud = 1;
492 if (fb + rl + ud == 0) {
493 printf("dr: bad axis option.\n");
494 return;
495 }
496 } else if (!strncmp(cmdtok[i], "n=", 2)) {
497 m = atoi(cmdtok[i]+2);
498 if (m <= 0) {
499 printf("dr: bad option n.\n");
500 return;
501 }
502 } else if (!strncmp(cmdtok[i], "b=", 2)) {
503 b = atoi(cmdtok[i]+2);
504 if (b <= 0) {
505 printf("dr: bad option b.\n");
506 return;
507 }
508 } else if (!strcmp(cmdtok[i], "from")) {
509 i++;
510 char x[3][3] = {"fb", "rl", "ud"};
511 for (int j = 0; j < 3; j++)
512 if (!strcmp(cmdtok[i], x[j]))
513 from = j+1;
514 if (!from) {
515 printf("dr: bad from option.\n");
516 return;
517 }
518 } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
519 printf("dr: error reading moves or ID.\n");
520 return;
521 }
522 }
523
524 if (scram[0] == 0) {
525 if (read_moves_from_prompt(scram) == -1) {
526 printf("dr: error reading moves.\n");
527 return;
528 }
529 }
530
531 unniss(scram, scram_unnissed);
532
533 /* Call solver */
534 int dr_list[m+5][21], ndr;
535 if (from) {
536 ndr = drfrom_scram_spam(scram_unnissed, dr_list, from, fb, rl, ud,
537 m, b, niss, hide);
538 if (ndr == -1) {
539 printf("dr: from given, but EO not found (possibly other error).\n");
540 return;
541 }
542 } else {
543 if (niss)
544 printf("Warning: not using NISS for direct DR.\n");
545 ndr = dr_scram_spam(scram_unnissed, dr_list, fb, rl, ud, m, b, hide);
546 }
547 print_results(ndr, dr_list);
548}
549
550void htr_cmd(int n, char cmdtok[][100]) {
551
552 /* Default values */
553 int m = 1, b = 20;
554 int niss = 0, hide = 1;
555 int from = 0; /* 0: unspecified; {1,2,3}: from {ud,fb,rl} */
556 int scram[255] = {[0] = 0};
557 int scram_unnissed[255];
558
559 /* Parse options */
560 for (int i = 1; i < n && scram[0] == 0; i++) {
561 if (!strcmp(cmdtok[i], "h")) {
562 hide = 0;
563 } else if (!strcmp(cmdtok[i], "niss")) {
564 niss = 1;
565 } else if (!strncmp(cmdtok[i], "n=", 2)) {
566 m = atoi(cmdtok[i]+2);
567 if (m <= 0) {
568 printf("htr: bad option n.\n");
569 return;
570 }
571 } else if (!strncmp(cmdtok[i], "b=", 2)) {
572 b = atoi(cmdtok[i]+2);
573 if (b <= 0) {
574 printf("htr: bad option b.\n");
575 return;
576 }
577 } else if (!strcmp(cmdtok[i], "from")) {
578 i++;
579 char x[3][3] = {"ud", "fb", "rl"};
580 for (int j = 0; j < 3; j++)
581 if (!strcmp(cmdtok[i], x[j]))
582 from = j+1;
583 if (!from) {
584 printf("htr: bad from option.\n");
585 return;
586 }
587 } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
588 printf("htr: error reading moves or ID.\n");
589 return;
590 }
591 }
592
593 if (scram[0] == 0) {
594 if (read_moves_from_prompt(scram) == -1) {
595 printf("htr: error reading moves.\n");
596 return;
597 }
598 }
599
600 unniss(scram, scram_unnissed);
601
602 /* Call solver */
603 int htr_list[m+5][21], nhtr;
604 nhtr = htr_scram_spam(scram_unnissed, htr_list, from, m, b, niss, hide);
605 print_results(nhtr, htr_list);
606}
607
608void drfinish_cmd(int n, char cmdtok[][100]) {
609 /* Default values */
610 int m = 1, b = 20;
611 int from = 0; /* 0: unspecified; {1,2,3}: from {ud,fb,rl} */
612 int scram[255] = {[0] = 0};
613 int scram_unnissed[255];
614
615 /* Parse options */
616 for (int i = 1; i < n && scram[0] == 0; i++) {
617 if (!strncmp(cmdtok[i], "n=", 2)) {
618 m = atoi(cmdtok[i]+2);
619 if (m <= 0) {
620 printf("drfinish: bad option n.\n");
621 return;
622 }
623 } else if (!strncmp(cmdtok[i], "b=", 2)) {
624 b = atoi(cmdtok[i]+2);
625 if (b <= 0) {
626 printf("drfinish: bad option b.\n");
627 return;
628 }
629 } else if (!strcmp(cmdtok[i], "from")) {
630 i++;
631 char x[3][3] = {"ud", "fb", "rl"};
632 for (int j = 0; j < 3; j++)
633 if (!strcmp(cmdtok[i], x[j]))
634 from = j+1;
635 if (!from) {
636 printf("drfinish: bad from option.\n");
637 return;
638 }
639 } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
640 printf("drfinish: error reading moves or ID.\n");
641 return;
642 }
643 }
644
645 if (scram[0] == 0) {
646 if (read_moves_from_prompt(scram) == -1) {
647 printf("drfinish: error reading moves.\n");
648 return;
649 }
650 }
651
652 unniss(scram, scram_unnissed);
653
654 /* Call solver */
655 int c_list[m+5][21], nc;
656 nc = dr_finish_scram_spam(scram_unnissed, c_list, from, m, b);
657 print_results(nc, c_list);
658}
659
660void htrfinish_cmd(int n, char cmdtok[][100]) {
661 /* Default values */
662 int m = 1, b = 20;
663 int scram[255] = {[0] = 0};
664 int scram_unnissed[255];
665
666 /* Parse options */
667 for (int i = 1; i < n && scram[0] == 0; i++) {
668 if (!strncmp(cmdtok[i], "n=", 2)) {
669 m = atoi(cmdtok[i]+2);
670 if (m <= 0) {
671 printf("htrfinish: bad option n.\n");
672 return;
673 }
674 } else if (!strncmp(cmdtok[i], "b=", 2)) {
675 b = atoi(cmdtok[i]+2);
676 if (b <= 0) {
677 printf("htrfinish: bad option b.\n");
678 return;
679 }
680 } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
681 printf("htrfinish: error reading moves or ID.\n");
682 return;
683 }
684 }
685
686 if (scram[0] == 0) {
687 if (read_moves_from_prompt(scram) == -1) {
688 printf("htrfinish: error reading moves.\n");
689 return;
690 }
691 }
692
693 unniss(scram, scram_unnissed);
694
695 /* Call solver */
696 int c_list[m+5][21], nc;
697 nc = htr_finish_scram_spam(scram_unnissed, c_list, m, b);
698 print_results(nc, c_list);
699}
700
701void drcorners_cmd(int n, char cmdtok[][100]) {
702 /* Default values */
703 int m = 1, b = 20, ignore=0;
704 int from = 0; /* 0: unspecified; {1,2,3}: from {ud,fb,rl} */
705 int scram[255] = {[0] = 0};
706 int scram_unnissed[255];
707
708 /* Parse options */
709 for (int i = 1; i < n && scram[0] == 0; i++) {
710 if (!strncmp(cmdtok[i], "n=", 2)) {
711 m = atoi(cmdtok[i]+2);
712 if (m <= 0) {
713 printf("drcorners: bad option n.\n");
714 return;
715 }
716 } else if (!strncmp(cmdtok[i], "b=", 2)) {
717 b = atoi(cmdtok[i]+2);
718 if (b <= 0) {
719 printf("drcorners: bad option b.\n");
720 return;
721 }
722 } else if (!strcmp(cmdtok[i], "i")) {
723 ignore = 1;
724 } else if (!strcmp(cmdtok[i], "from")) {
725 i++;
726 char x[3][3] = {"ud", "fb", "rl"};
727 for (int j = 0; j < 3; j++)
728 if (!strcmp(cmdtok[i], x[j]))
729 from = j+1;
730 if (!from) {
731 printf("drcorners: bad from option.\n");
732 return;
733 }
734 } else if (read_moves_from_argument(n-i, cmdtok+i, scram) == -1) {
735 printf("drcorners: error reading moves or ID.\n");
736 return;
737 }
738 }
739
740 if (scram[0] == 0) {
741 if (read_moves_from_prompt(scram) == -1) {
742 printf("drcorners: error reading moves.\n");
743 return;
744 }
745 }
746
747 unniss(scram, scram_unnissed);
748
749 /* Call solver */
750 int c_list[m+5][21], nc;
751 nc = dr_corners_scram_spam(scram_unnissed, c_list, from, m, b, ignore);
752 print_results(nc, c_list);
753}
754
755
756void exit_quit_cmd(int n, char cmdtok[][100]) {
757 if (n == 1)
758 exit(0);
759 else
760 printf("%s: wrong synstax.\n", cmdtok[0]);
761}
762
763void (*cmd_list[])(int n, char cmdtok[][100]) = {
764 help_cmd, save_cmd, change_cmd, print_cmd,
765 add_cmd, invert_cmd, unniss_cmd, pic_cmd,
766 solve_cmd, replace_cmd,
767 eo_cmd, dr_cmd, htr_cmd,
768 drfinish_cmd, htrfinish_cmd, drcorners_cmd,
769 exit_quit_cmd, exit_quit_cmd, NULL
770};
771
772void execcmd(int n, char cmdtok[][100]) {
773 int i = 0;
774 while (strcmp(commands[i][0], cmdtok[0]) && strcmp(commands[i][0], ""))
775 i++;
776 if (strcmp(commands[i][0], ""))
777 (*cmd_list[i])(n, cmdtok);
778 else
779 printf("%s: not a command.\n", cmdtok[0]);
780}
781
782int main() {
783 init_transition_table();
784 init_possible_next();
785
786 printf("Type help for a list of commands.\n");
787
788 char cmd[1000] = "";
789 while (1) {
790 printf("nissy-# ");
791 if (fgets(cmd, 1000, stdin) == NULL)
792 break;
793 char cmdtok[100][100];
794 int n = parsecmd(cmd, cmdtok);
795 if (n == 0)
796 continue;
797 execcmd(n, cmdtok);
798 }
799
800 return 0;
801}
diff --git a/src/moves.c b/src/moves.c
new file mode 100644
index 0000000..15d5dad
--- /dev/null
+++ b/src/moves.c
@@ -0,0 +1,526 @@
1/* This is a simple program to solve the Rubik's Cube.
2 * No idea how many features I am going to implement.
3 * Open source license and whatnot.
4 * I am trying to follow the C99 standard. */
5
6/* This file contains the definitions of the basic moves of the cube.
7 * There is no object or type representing the cube.
8 * Data about the cube can be represented by arrays (describing the position
9 * of pieces of certain types), integers (representing for example a bitmask
10 * for the orientation of pieces of certain type, or the permutation index of
11 * an array representing the permutation of pieces).
12 * Each of the moves functions operates on one such piece of data.
13 *
14 * For example, a way of representing the cube can be:
15 * - An integer eo, which is a bitmask for the orientation of the edges.
16 * - An integer co, same for corners.
17 * - An array ep[12], where a[i]=j means that the edge j is in place i.
18 * - An integer cp representing the permutation index of a permutation array
19 * which is the analogue of that described for edges.
20 *
21 * Different representations will be used for different use-cases. */
22
23#include "coordinates.h"
24#include "moves.h"
25
26/* possible_next[i][j] is a bitmask representing the possible
27 * next moves we can apply. For example, if the last moves a 0 R then it does
28 * not make sense to apply R, R2 or R'. If they are U D2 it does not make
29 * sense to apply any U* or D*. */
30int possible_next[19][19];
31
32int parallel(int m1, int m2) {
33 if (m1 == 0 || m2 == 0) return 0;
34 return ((m1-1)/6 == (m2-1)/6);
35}
36
37int compute_possible_next(int last1, int last2) {
38 if (last1 == 0) return move_mask_all;
39
40 /* Removes the 2 or ' (e.g. turns U2 to U, R' to R). */
41 last2 = (last2 == 0) ? last2 : 3*((last2-1)/3) + 1;
42 last1 = 3*((last1-1)/3) + 1;
43
44 int mask = move_mask_all ^ (7 << last1);
45
46 if (parallel(last1, last2))
47 mask ^= 7 << last2;
48 else if (last1 % 6 == 4) /*Always U before D, R before L, F before B*/
49 mask ^= 7 << (last1-3);
50
51 return mask;
52}
53
54void init_possible_next() {
55 for (int i = 0; i < 19; i++)
56 for (int j = 0; j < 19; j++)
57 possible_next[i][j] = compute_possible_next(i, j);
58}
59
60/* Piece cycles depending on the move. For example edge_cycle[U2][UF]
61 * gives the piece in position UF after applying U2 to a solved cube */
62
63int edge_cycle[19][12] = {
64 {UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR}, /* - */
65 {UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR}, /* U */
66 {UB, UR, UF, UL, DF, DL, DB, DR, FR, FL, BL, BR}, /* U2 */
67 {UL, UB, UR, UF, DF, DL, DB, DR, FR, FL, BL, BR}, /* U' */
68 {UF, UL, UB, UR, DL, DB, DR, DF, FR, FL, BL, BR}, /* D */
69 {UF, UL, UB, UR, DB, DR, DF, DL, FR, FL, BL, BR}, /* D2 */
70 {UF, UL, UB, UR, DR, DF, DL, DB, FR, FL, BL, BR}, /* D' */
71 {UF, UL, UB, FR, DF, DL, DB, BR, DR, FL, BL, UR}, /* R */
72 {UF, UL, UB, DR, DF, DL, DB, UR, BR, FL, BL, FR}, /* R2 */
73 {UF, UL, UB, BR, DF, DL, DB, FR, UR, FL, BL, DR}, /* R' */
74 {UF, BL, UB, UR, DF, FL, DB, DR, FR, UL, DL, BR}, /* L */
75 {UF, DL, UB, UR, DF, UL, DB, DR, FR, BL, FL, BR}, /* L2 */
76 {UF, FL, UB, UR, DF, BL, DB, DR, FR, DL, UL, BR}, /* L' */
77 {FL, UL, UB, UR, FR, DL, DB, DR, UF, DF, BL, BR}, /* F */
78 {DF, UL, UB, UR, UF, DL, DB, DR, FL, FR, BL, BR}, /* F2 */
79 {FR, UL, UB, UR, FL, DL, DB, DR, DF, UF, BL, BR}, /* F' */
80 {UF, UL, BR, UR, DF, DL, BL, DR, FR, FL, UB, DB}, /* B */
81 {UF, UL, DB, UR, DF, DL, UB, DR, FR, FL, BR, BL}, /* B2 */
82 {UF, UL, BL, UR, DF, DL, BR, DR, FR, FL, DB, UB} /* B' */
83};
84
85int corner_cycle[19][8] = {
86 {UFR, UFL, UBL, UBR, DFR, DFL, DBL, DBR}, /* - */
87 {UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR}, /* U */
88 {UBL, UBR, UFR, UFL, DFR, DFL, DBL, DBR}, /* U2 */
89 {UFL, UBL, UBR, UFR, DFR, DFL, DBL, DBR}, /* U' */
90 {UFR, UFL, UBL, UBR, DFL, DBL, DBR, DFR}, /* D */
91 {UFR, UFL, UBL, UBR, DBL, DBR, DFR, DFL}, /* D2 */
92 {UFR, UFL, UBL, UBR, DBR, DFR, DFL, DBL}, /* D' */
93 {DFR, UFL, UBL, UFR, DBR, DFL, DBL, UBR}, /* R */
94 {DBR, UFL, UBL, DFR, UBR, DFL, DBL, UFR}, /* R2 */
95 {UBR, UFL, UBL, DBR, UFR, DFL, DBL, DFR}, /* R' */
96 {UFR, UBL, DBL, UBR, DFR, UFL, DFL, DBR}, /* L */
97 {UFR, DBL, DFL, UBR, DFR, UBL, UFL, DBR}, /* L2 */
98 {UFR, DFL, UFL, UBR, DFR, DBL, UBL, DBR}, /* L' */
99 {UFL, DFL, UBL, UBR, UFR, DFR, DBL, DBR}, /* F */
100 {DFL, DFR, UBL, UBR, UFL, UFR, DBL, DBR}, /* F2 */
101 {DFR, UFR, UBL, UBR, DFL, UFL, DBL, DBR}, /* F' */
102 {UFR, UFL, UBR, DBR, DFR, DFL, UBL, DBL}, /* B */
103 {UFR, UFL, DBR, DBL, DFR, DFL, UBR, UBL}, /* B2 */
104 {UFR, UFL, DBL, UBL, DFR, DFL, DBR, UBR}, /* U' */
105};
106
107/* Transition tables */
108
109int eofb_transition_table[pow2to11][19];
110int eorl_transition_table[pow2to11][19];
111int eoud_transition_table[pow2to11][19];
112int coud_transition_table[pow3to7][19];
113int cofb_transition_table[pow3to7][19];
114int corl_transition_table[pow3to7][19];
115int epud_transition_table[factorial8][19];
116int eprl_transition_table[factorial8][19];
117int epfb_transition_table[factorial8][19];
118int epose_transition_table[binom12on4][19];
119int eposs_transition_table[binom12on4][19];
120int eposm_transition_table[binom12on4][19];
121int epe_transition_table[factorial4][19];
122int eps_transition_table[factorial4][19];
123int epm_transition_table[factorial4][19];
124int emslices_transition_table[binom12on4*binom8on4][19];
125int cp_transition_table[factorial8][19];
126
127/***/
128/* Functions for permuting pieces (given in array format) */
129/***/
130
131void apply_move_ep_array(int move, int ep[12]) {
132 int aux[12];
133 for (int i = 0; i < 12; i++)
134 aux[i] = ep[i];
135 for (int i = 0; i < 12; i++)
136 ep[i] = aux[edge_cycle[move][i]];
137}
138
139void apply_move_cp_array(int move, int cp[8]) {
140 int aux[8];
141 for (int i = 0; i < 8; i++)
142 aux[i] = cp[i];
143 for (int i = 0; i < 8; i++)
144 cp[i] = aux[corner_cycle[move][i]];
145}
146
147/***/
148/* Functions for permuting pieces (given in integer format) */
149/***/
150
151int apply_move_ep_int(int move, int ep) {
152 int a[12];
153 ep_int_to_array(ep, a);
154 apply_move_ep_array(move, a);
155 return ep_array_to_int(a);
156}
157
158int apply_move_epud_int(int move, int ep) {
159 int a[12];
160 epud_int_to_array(ep, a);
161 apply_move_ep_array(move, a);
162 return epud_array_to_int(a);
163}
164
165int apply_move_eprl_int(int move, int ep) {
166 int a[12];
167 eprl_int_to_array(ep, a);
168 apply_move_ep_array(move, a);
169 return eprl_array_to_int(a);
170}
171
172int apply_move_epfb_int(int move, int ep) {
173 int a[12];
174 epfb_int_to_array(ep, a);
175 apply_move_ep_array(move, a);
176 return epfb_array_to_int(a);
177}
178
179int apply_move_epose_int(int move, int ep) {
180 int a[12];
181 epose_int_to_array(ep, a);
182 apply_move_ep_array(move, a);
183 return epose_array_to_int(a);
184}
185
186int apply_move_eposs_int(int move, int ep) {
187 int a[12];
188 eposs_int_to_array(ep, a);
189 apply_move_ep_array(move, a);
190 return eposs_array_to_int(a);
191}
192
193int apply_move_eposm_int(int move, int ep) {
194 int a[12];
195 eposm_int_to_array(ep, a);
196 apply_move_ep_array(move, a);
197 return eposm_array_to_int(a);
198}
199
200int apply_move_epe_int(int move, int ep) {
201 int a[12];
202 epe_int_to_array(ep, a);
203 apply_move_ep_array(move, a);
204 return epe_array_to_int(a);
205}
206
207int apply_move_eps_int(int move, int ep) {
208 int a[12];
209 eps_int_to_array(ep, a);
210 apply_move_ep_array(move, a);
211 return eps_array_to_int(a);
212}
213
214int apply_move_epm_int(int move, int ep) {
215 int a[12];
216 epm_int_to_array(ep, a);
217 apply_move_ep_array(move, a);
218 return epm_array_to_int(a);
219}
220
221int apply_move_emslices_int(int move, int e) {
222 int a[12];
223 emslices_int_to_array(e, a);
224 apply_move_ep_array(move, a);
225 return emslices_array_to_int(a);
226}
227
228int apply_move_cp_int(int move, int cp) {
229 int a[8];
230 cp_int_to_array(cp, a);
231 apply_move_cp_array(move, a);
232 return cp_array_to_int(a);
233}
234
235int apply_move_eofb_int(int move, int eo) {
236 int a[12];
237 eo_11bits_to_array(eo, a);
238 apply_move_ep_array(move, a);
239 /* Change edge orientation */
240 if (move == F || move == F3) {
241 a[UF] = 1 - a[UF];
242 a[DF] = 1 - a[DF];
243 a[FR] = 1 - a[FR];
244 a[FL] = 1 - a[FL];
245 }
246 if (move == B || move == B3) {
247 a[UB] = 1 - a[UB];
248 a[DB] = 1 - a[DB];
249 a[BL] = 1 - a[BL];
250 a[BR] = 1 - a[BR];
251 }
252 return eo_array_to_11bits(a);
253}
254
255int apply_move_eorl_int(int move, int eo) {
256 int a[12];
257 eo_11bits_to_array(eo, a);
258 apply_move_ep_array(move, a);
259 /* Change edge orientation */
260 if (move == R || move == R3) {
261 a[UR] = 1 - a[UR];
262 a[DR] = 1 - a[DR];
263 a[FR] = 1 - a[FR];
264 a[BR] = 1 - a[BR];
265 }
266 if (move == L || move == L3) {
267 a[UL] = 1 - a[UL];
268 a[DL] = 1 - a[DL];
269 a[FL] = 1 - a[FL];
270 a[BL] = 1 - a[BL];
271 }
272 return eo_array_to_11bits(a);
273}
274
275int apply_move_eoud_int(int move, int eo) {
276 int a[12];
277 eo_11bits_to_array(eo, a);
278 apply_move_ep_array(move, a);
279 /* Change edge orientation */
280 if (move == U || move == U3) {
281 a[UF] = 1 - a[UF];
282 a[UL] = 1 - a[UL];
283 a[UB] = 1 - a[UB];
284 a[UR] = 1 - a[UR];
285 }
286 if (move == D || move == D3) {
287 a[DF] = 1 - a[DF];
288 a[DL] = 1 - a[DL];
289 a[DB] = 1 - a[DB];
290 a[DR] = 1 - a[DR];
291 }
292 return eo_array_to_11bits(a);
293}
294
295int apply_move_coud_int(int move, int co) {
296 int a[8];
297 co_7trits_to_array(co, a);
298 apply_move_cp_array(move, a);
299 /* Change corner orientation */
300 if (move == R || move == R3) {
301 a[UFR] = (a[UFR] + 2) % 3;
302 a[UBR] = (a[UBR] + 1) % 3;
303 a[DBR] = (a[DBR] + 2) % 3;
304 a[DFR] = (a[DFR] + 1) % 3;
305 }
306 if (move == L || move == L3) {
307 a[UBL] = (a[UBL] + 2) % 3;
308 a[UFL] = (a[UFL] + 1) % 3;
309 a[DFL] = (a[DFL] + 2) % 3;
310 a[DBL] = (a[DBL] + 1) % 3;
311 }
312 if (move == F || move == F3) {
313 a[UFL] = (a[UFL] + 2) % 3;
314 a[UFR] = (a[UFR] + 1) % 3;
315 a[DFR] = (a[DFR] + 2) % 3;
316 a[DFL] = (a[DFL] + 1) % 3;
317 }
318 if (move == B || move == B3) {
319 a[UBR] = (a[UBR] + 2) % 3;
320 a[UBL] = (a[UBL] + 1) % 3;
321 a[DBL] = (a[DBL] + 2) % 3;
322 a[DBR] = (a[DBR] + 1) % 3;
323 }
324 return co_array_to_7trits(a);
325}
326
327int apply_move_cofb_int(int move, int co) {
328 int a[8];
329 co_7trits_to_array(co, a);
330 apply_move_cp_array(move, a);
331 /* Change corner orientation */
332 if (move == R || move == R3) {
333 a[UFR] = (a[UFR] + 1) % 3;
334 a[UBR] = (a[UBR] + 2) % 3;
335 a[DBR] = (a[DBR] + 1) % 3;
336 a[DFR] = (a[DFR] + 2) % 3;
337 }
338 if (move == L || move == L3) {
339 a[UBL] = (a[UBL] + 1) % 3;
340 a[UFL] = (a[UFL] + 2) % 3;
341 a[DFL] = (a[DFL] + 1) % 3;
342 a[DBL] = (a[DBL] + 2) % 3;
343 }
344 if (move == U || move == U3) {
345 a[UFL] = (a[UFL] + 1) % 3;
346 a[UFR] = (a[UFR] + 2) % 3;
347 a[UBL] = (a[UBL] + 2) % 3;
348 a[UBR] = (a[UBR] + 1) % 3;
349 }
350 if (move == D || move == D3) {
351 a[DFL] = (a[DFL] + 2) % 3;
352 a[DFR] = (a[DFR] + 1) % 3;
353 a[DBL] = (a[DBL] + 1) % 3;
354 a[DBR] = (a[DBR] + 2) % 3;
355 }
356 return co_array_to_7trits(a);
357}
358
359int apply_move_corl_int(int move, int co) {
360 int a[8];
361 co_7trits_to_array(co, a);
362 apply_move_cp_array(move, a);
363 /* Change corner orientation */
364 if (move == F || move == F3) {
365 a[UFR] = (a[UFR] + 2) % 3;
366 a[UFL] = (a[UFL] + 1) % 3;
367 a[DFL] = (a[DFL] + 2) % 3;
368 a[DFR] = (a[DFR] + 1) % 3;
369 }
370 if (move == B || move == B3) {
371 a[UBL] = (a[UBL] + 2) % 3;
372 a[UBR] = (a[UBR] + 1) % 3;
373 a[DBR] = (a[DBR] + 2) % 3;
374 a[DBL] = (a[DBL] + 1) % 3;
375 }
376 if (move == U || move == U3) {
377 a[UFL] = (a[UFL] + 2) % 3;
378 a[UFR] = (a[UFR] + 1) % 3;
379 a[UBL] = (a[UBL] + 1) % 3;
380 a[UBR] = (a[UBR] + 2) % 3;
381 }
382 if (move == D || move == D3) {
383 a[DFL] = (a[DFL] + 1) % 3;
384 a[DFR] = (a[DFR] + 2) % 3;
385 a[DBL] = (a[DBL] + 2) % 3;
386 a[DBR] = (a[DBR] + 1) % 3;
387 }
388 return co_array_to_7trits(a);
389}
390
391
392
393/* Initialize transition tables */
394
395void init_epud_transition_table() {
396 for (int i = 0; i < factorial8; i++)
397 for (int j = 0; j < 19; j++)
398 if (move_mask_drud & (1 << j))
399 epud_transition_table[i][j] = apply_move_epud_int(j, i);
400}
401
402void init_eprl_transition_table() {
403 for (int i = 0; i < factorial8; i++)
404 for (int j = 0; j < 19; j++)
405 if (move_mask_drrl & (1 << j))
406 eprl_transition_table[i][j] = apply_move_eprl_int(j, i);
407}
408
409void init_epfb_transition_table() {
410 for (int i = 0; i < factorial8; i++)
411 for (int j = 0; j < 19; j++)
412 if (move_mask_drfb & (1 << j))
413 epfb_transition_table[i][j] = apply_move_epfb_int(j, i);
414}
415
416void init_epose_transition_table() {
417 for (int i = 0; i < binom12on4; i++)
418 for (int j = 0; j < 19; j++)
419 epose_transition_table[i][j] = apply_move_epose_int(j, i);
420}
421
422void init_eposs_transition_table() {
423 for (int i = 0; i < binom12on4; i++)
424 for (int j = 0; j < 19; j++)
425 eposs_transition_table[i][j] = apply_move_eposs_int(j, i);
426}
427
428void init_eposm_transition_table() {
429 for (int i = 0; i < binom12on4; i++)
430 for (int j = 0; j < 19; j++)
431 eposm_transition_table[i][j] = apply_move_eposm_int(j, i);
432}
433
434void init_epe_transition_table() {
435 for (int i = 0; i < factorial4; i++) {
436 for (int j = 0; j < 19; j++)
437 if (move_mask_drud & (1 << j))
438 epe_transition_table[i][j] = apply_move_epe_int(j, i);
439 }
440}
441
442void init_eps_transition_table() {
443 for (int i = 0; i < factorial4; i++) {
444 for (int j = 0; j < 19; j++)
445 if (move_mask_drfb & (1 << j))
446 eps_transition_table[i][j] = apply_move_eps_int(j, i);
447 }
448}
449
450void init_epm_transition_table() {
451 for (int i = 0; i < factorial4; i++) {
452 for (int j = 0; j < 19; j++)
453 if (move_mask_drrl & (1 << j))
454 epm_transition_table[i][j] = apply_move_epm_int(j, i);
455 }
456}
457
458void init_emslices_transition_table() {
459 for (int i = 0; i < binom12on4*binom8on4; i++) {
460 for (int j = 0; j < 19; j++)
461 emslices_transition_table[i][j] = apply_move_emslices_int(j, i);
462 }
463}
464
465void init_cp_transition_table() {
466 for (int i = 0; i < factorial8; i++)
467 for (int j = 0; j < 19; j++)
468 cp_transition_table[i][j] = apply_move_cp_int(j, i);
469}
470
471void init_eofb_transition_table() {
472 for (int i = 0; i < pow2to11; i++)
473 for (int j = 0; j < 19; j++)
474 eofb_transition_table[i][j] = apply_move_eofb_int(j, i);
475}
476
477void init_eorl_transition_table() {
478 for (int i = 0; i < pow2to11; i++)
479 for (int j = 0; j < 19; j++)
480 eorl_transition_table[i][j] = apply_move_eorl_int(j, i);
481}
482
483void init_eoud_transition_table() {
484 for (int i = 0; i < pow2to11; i++)
485 for (int j = 0; j < 19; j++)
486 eoud_transition_table[i][j] = apply_move_eoud_int(j, i);
487}
488
489void init_coud_transition_table() {
490 for (int i = 0; i < pow3to7; i++)
491 for (int j = 0; j < 19; j++ )
492 coud_transition_table[i][j] = apply_move_coud_int(j, i);
493}
494
495void init_cofb_transition_table() {
496 for (int i = 0; i < pow3to7; i++)
497 for (int j = 0; j < 19; j++ )
498 cofb_transition_table[i][j] = apply_move_cofb_int(j, i);
499}
500
501void init_corl_transition_table() {
502 for (int i = 0; i < pow3to7; i++)
503 for (int j = 0; j < 19; j++ )
504 corl_transition_table[i][j] = apply_move_corl_int(j, i);
505}
506
507void init_transition_table() {
508 init_epud_transition_table();
509 init_eprl_transition_table();
510 init_epfb_transition_table();
511 init_epose_transition_table();
512 init_eposs_transition_table();
513 init_eposm_transition_table();
514 init_epe_transition_table();
515 init_eps_transition_table();
516 init_epm_transition_table();
517 init_emslices_transition_table();
518 init_cp_transition_table();
519 init_eofb_transition_table();
520 init_eorl_transition_table();
521 init_eoud_transition_table();
522 init_coud_transition_table();
523 init_cofb_transition_table();
524 init_corl_transition_table();
525}
526
diff --git a/src/moves.h b/src/moves.h
new file mode 100644
index 0000000..99d0ec3
--- /dev/null
+++ b/src/moves.h
@@ -0,0 +1,83 @@
1#include "utils.h"
2
3/* Bitmask that define certain movesets. */
4#define move_mask_all 524287 /* Reverse 1111111111111111111 */
5#define move_mask_eofb 155647 /* Reverse 1111111111111010010 */
6#define move_mask_eorl 518527 /* Reverse 1111111010101111111 */
7#define move_mask_eoud 524197 /* Reverse 1010010111111111111 */
8#define move_mask_drud 149887 /* Reverse 1111111010010010010 */
9#define move_mask_drfb 518437 /* Reverse 1010010010010111111 */
10#define move_mask_drrl 155557 /* Reverse 1010010111111010010 */
11#define move_mask_htr 149797 /* Reverse 1010010010010010010 */
12
13extern int possible_next[19][19];
14
15int parallel(int m1, int m2);
16void init_possible_next();
17
18/* Transition tables */
19extern int eofb_transition_table[pow2to11][19];
20extern int eorl_transition_table[pow2to11][19];
21extern int eoud_transition_table[pow2to11][19];
22extern int coud_transition_table[pow3to7][19];
23extern int cofb_transition_table[pow3to7][19];
24extern int corl_transition_table[pow3to7][19];
25extern int epud_transition_table[factorial8][19];
26extern int epfb_transition_table[factorial8][19];
27extern int eprl_transition_table[factorial8][19];
28extern int epose_transition_table[binom12on4][19];
29extern int eposs_transition_table[binom12on4][19];
30extern int eposm_transition_table[binom12on4][19];
31extern int epe_transition_table[factorial4][19];
32extern int eps_transition_table[factorial4][19];
33extern int epm_transition_table[factorial4][19];
34extern int emslices_transition_table[binom12on4*binom8on4][19];
35extern int cp_transition_table[factorial8][19];
36
37
38/* Functions for permuting pieces (given in array format) */
39
40void apply_move_ep_array(int move, int ep[12]);
41void apply_move_cp_array(int move, int cp[8]);
42
43/* Functions for permuting pieces (given in integer format) */
44
45int apply_move_ep_int(int move, int ep);
46int apply_move_epud_int(int move, int ep);
47int apply_move_epfb_int(int move, int ep);
48int apply_move_eprl_int(int move, int ep);
49int apply_move_epose_int(int move, int ep);
50int apply_move_eposs_int(int move, int ep);
51int apply_move_eposm_int(int move, int ep);
52int apply_move_epe_int(int move, int ep);
53int apply_move_eps_int(int move, int ep);
54int apply_move_epm_int(int move, int ep);
55int apply_move_cp_int(int move, int cp);
56int apply_move_eofb_int(int move, int eo);
57int apply_move_eorl_int(int move, int eo);
58int apply_move_eoud_int(int move, int eo);
59int apply_move_coud_int(int move, int co);
60int apply_move_cofb_int(int move, int co);
61int apply_move_corl_int(int move, int co);
62
63/* Initialize transition tables */
64
65void init_epud_transition_table();
66void init_epfb_transition_table();
67void init_eprl_transition_table();
68void init_epose_transition_table();
69void init_eposs_transition_table();
70void init_eposm_transition_table();
71void init_epe_transition_table();
72void init_eps_transition_table();
73void init_epm_transition_table();
74void init_cp_transition_table();
75void init_eofb_transition_table();
76void init_eorl_transition_table();
77void init_eoud_transition_table();
78void init_coud_transition_table();
79void init_cofb_transition_table();
80void init_corl_transition_table();
81
82void init_transition_table();
83
diff --git a/src/pruning_tables.c b/src/pruning_tables.c
new file mode 100644
index 0000000..8936b99
--- /dev/null
+++ b/src/pruning_tables.c
@@ -0,0 +1,483 @@
1#include <stdint.h>
2#include "pruning_tables.h"
3#include "moves.h"
4
5/* The data contained in e.g. eofb pruning table is the same that is contained
6 * in eolr pruning table and so on. For small tables the memory wasted is not
7 * too much and it makes things easier. I may change this when I implement
8 * bigger tables. */
9int eofb_pruning_table[pow2to11];
10int eorl_pruning_table[pow2to11];
11int eoud_pruning_table[pow2to11];
12int coud_pruning_table[pow3to7];
13int cofb_pruning_table[pow3to7];
14int corl_pruning_table[pow3to7];
15int cp_pruning_table[factorial8];
16
17int eorl_from_eofb_pruning_table[pow2to11];
18int eoud_from_eofb_pruning_table[pow2to11];
19int eoud_from_eorl_pruning_table[pow2to11];
20int eofb_from_eorl_pruning_table[pow2to11];
21int eofb_from_eoud_pruning_table[pow2to11];
22int eorl_from_eoud_pruning_table[pow2to11];
23
24int coud_from_eofb_pruning_table[pow3to7];
25int coud_from_eorl_pruning_table[pow3to7];
26int cofb_from_eorl_pruning_table[pow3to7];
27int cofb_from_eoud_pruning_table[pow3to7];
28int corl_from_eoud_pruning_table[pow3to7];
29int corl_from_eofb_pruning_table[pow3to7];
30
31int cp_drud_pruning_table[factorial8];
32int cp_drfb_pruning_table[factorial8];
33int cp_drrl_pruning_table[factorial8];
34int epud_pruning_table[factorial8];
35int epfb_pruning_table[factorial8];
36int eprl_pruning_table[factorial8];
37
38int cp_htr_pruning_table[factorial8];
39
40int cpud_to_htr_pruning_table[factorial8];
41int cpfb_to_htr_pruning_table[factorial8];
42int cprl_to_htr_pruning_table[factorial8];
43
44
45/* About 1Mb each */
46int8_t eofb_epose_pruning_table[pow2to11][binom12on4];
47int8_t eorl_eposs_pruning_table[pow2to11][binom12on4];
48int8_t eoud_eposm_pruning_table[pow2to11][binom12on4];
49
50/* About 4.5Mb each */
51int8_t eofb_coud_pruning_table[pow2to11][pow3to7];
52int8_t eofb_corl_pruning_table[pow2to11][pow3to7];
53int8_t eorl_coud_pruning_table[pow2to11][pow3to7];
54int8_t eorl_cofb_pruning_table[pow2to11][pow3to7];
55int8_t eoud_cofb_pruning_table[pow2to11][pow3to7];
56int8_t eoud_corl_pruning_table[pow2to11][pow3to7];
57
58/* About 1Mb each */
59int8_t coud_epose_from_eofb_pruning_table[pow3to7][binom12on4];
60int8_t cofb_eposs_from_eorl_pruning_table[pow3to7][binom12on4];
61int8_t corl_eposm_from_eoud_pruning_table[pow3to7][binom12on4];
62int8_t coud_epose_from_eorl_pruning_table[pow3to7][binom12on4];
63int8_t cofb_eposs_from_eoud_pruning_table[pow3to7][binom12on4];
64int8_t corl_eposm_from_eofb_pruning_table[pow3to7][binom12on4];
65
66
67/* Firs one is 88Mb, second one is 71Mb */
68int8_t cp_co_pruning_table[factorial8][pow3to7];
69int8_t triple_eo_pruning_table[pow2to11][binom12on4*binom8on4];
70
71int initialized_small = 0;
72int initialized_directdr = 0;
73int initialized_drfromeo = 0;
74int initialized_huge = 0;
75
76void init_single_table(int n, int t_tab[][19], int p_tab[n], int mask) {
77 int state[n];
78 state[0] = 0; /* 0 should always be the solved state. */
79 p_tab[0] = 0;
80 int state_count = 1;
81 for (int i = 0; i < state_count; i++) {
82 for (int m = 1; m < 19; m++) {
83 int next = t_tab[state[i]][m];
84 if (mask & (1<<m) && !p_tab[next] && next) {
85 p_tab[next] = p_tab[state[i]] + 1;
86 state[state_count++] = next;
87 }
88 }
89 }
90}
91
92/* Similar to single table, but specific to "cp to htr".
93 * The idea is that we are considering the distance not necessarily to the
94 * solved state, but to any state that is either solved or reachable from
95 * cp_pruning_table. */
96void init_cptohtr_table(int n, int t_tab[][19], int p_tab[n], int mask) {
97
98 for (int i = 0; i < n; i++)
99 p_tab[i] = 21;
100
101 /* List of htr states */
102 int good[n]; good[0] = 0;
103 int good_count = 1;
104 for (int i = 0; i < n; i++)
105 if (cp_htr_pruning_table[i])
106 good[good_count++] = i;
107
108 /* Init pruning table starting from each possible state */
109 int state[n];
110 for (int j = 0; j < good_count; j++) {
111 state[0] = good[j];
112 p_tab[state[0]] = 0;
113 int state_count = 1;
114 for (int i = 0; i < state_count; i++) {
115 for (int m = 1; m < 19; m++) {
116 int next = t_tab[state[i]][m];
117 if (mask & (1<<m) && (p_tab[next] > p_tab[state[i]] + 1) && next) {
118 p_tab[next] = p_tab[state[i]] + 1;
119 state[state_count++] = next;
120 }
121 }
122 }
123 }
124}
125
126void init_double_table(int n1, int n2,
127 int t_table1[n1][19], int t_table2[n2][19],
128 int8_t p_table[n1][n2], int mask) {
129 static int state1[factorial8*pow3to7], state2[factorial8*pow3to7];
130 state1[0] = 0;
131 state2[0] = 0;
132 p_table[0][0] = 0;
133 int state_count = 1;
134 for (int i = 0; i < state_count; i++) {
135 for (int m = 1; m < 19; m++) {
136 int next1 = t_table1[state1[i]][m];
137 int next2 = t_table2[state2[i]][m];
138 if (mask & (1<<m) && !p_table[next1][next2] && (next1 || next2)) {
139 p_table[next1][next2] = p_table[state1[i]][state2[i]] + 1;
140 state1[state_count] = next1;
141 state2[state_count] = next2;
142 state_count++;
143 }
144 }
145 }
146}
147
148void init_eofb_pruning_table() {
149 init_single_table(pow2to11, eofb_transition_table, eofb_pruning_table,
150 move_mask_all);
151}
152
153void init_eorl_pruning_table() {
154 init_single_table(pow2to11, eorl_transition_table, eorl_pruning_table,
155 move_mask_all);
156}
157
158void init_eoud_pruning_table() {
159 init_single_table(pow2to11, eoud_transition_table, eoud_pruning_table,
160 move_mask_all);
161}
162
163void init_coud_pruning_table() {
164 init_single_table(pow3to7, coud_transition_table, coud_pruning_table,
165 move_mask_all);
166}
167
168void init_cofb_pruning_table() {
169 init_single_table(pow3to7, cofb_transition_table, cofb_pruning_table,
170 move_mask_all);
171}
172
173void init_corl_pruning_table() {
174 init_single_table(pow3to7, corl_transition_table, corl_pruning_table,
175 move_mask_all);
176}
177
178void init_cp_pruning_table() {
179 init_single_table(factorial8, cp_transition_table, cp_pruning_table,
180 move_mask_all);
181}
182
183/* The following tables use the eo moveset */
184void init_eorl_from_eofb_pruning_table() {
185 init_single_table(pow2to11, eorl_transition_table,
186 eorl_from_eofb_pruning_table, move_mask_eofb);
187}
188
189void init_eoud_from_eofb_pruning_table() {
190 init_single_table(pow2to11, eoud_transition_table,
191 eoud_from_eofb_pruning_table, move_mask_eofb);
192}
193
194void init_eoud_from_eorl_pruning_table() {
195 init_single_table(pow2to11, eoud_transition_table,
196 eoud_from_eorl_pruning_table, move_mask_eorl);
197}
198
199void init_eofb_from_eorl_pruning_table() {
200 init_single_table(pow2to11, eofb_transition_table,
201 eofb_from_eorl_pruning_table, move_mask_eorl);
202}
203
204void init_eofb_from_eoud_pruning_table() {
205 init_single_table(pow2to11, eofb_transition_table,
206 eofb_from_eoud_pruning_table, move_mask_eoud);
207}
208
209void init_eorl_from_eoud_pruning_table() {
210 init_single_table(pow2to11, eorl_transition_table,
211 eorl_from_eoud_pruning_table, move_mask_eoud);
212}
213
214void init_coud_from_eofb_pruning_table() {
215 init_single_table(pow3to7, coud_transition_table,
216 coud_from_eofb_pruning_table, move_mask_eofb);
217}
218
219void init_corl_from_eofb_pruning_table() {
220 init_single_table(pow3to7, corl_transition_table,
221 corl_from_eofb_pruning_table, move_mask_eofb);
222}
223
224void init_coud_from_eorl_pruning_table() {
225 init_single_table(pow3to7, coud_transition_table,
226 coud_from_eorl_pruning_table, move_mask_eorl);
227}
228
229void init_cofb_from_eorl_pruning_table() {
230 init_single_table(pow3to7, cofb_transition_table,
231 cofb_from_eorl_pruning_table, move_mask_eorl);
232}
233
234void init_corl_from_eoud_pruning_table() {
235 init_single_table(pow3to7, corl_transition_table,
236 corl_from_eoud_pruning_table, move_mask_eoud);
237}
238
239void init_cofb_from_eoud_pruning_table() {
240 init_single_table(pow3to7, cofb_transition_table,
241 cofb_from_eoud_pruning_table, move_mask_eoud);
242}
243
244/* The following tables always use DR moveset */
245void init_epud_pruning_table() {
246 init_single_table(factorial8, epud_transition_table, epud_pruning_table,
247 move_mask_drud);
248}
249
250void init_epfb_pruning_table() {
251 init_single_table(factorial8, epfb_transition_table, epfb_pruning_table,
252 move_mask_drfb);
253}
254
255void init_eprl_pruning_table() {
256 init_single_table(factorial8, eprl_transition_table, eprl_pruning_table,
257 move_mask_drrl);
258}
259
260void init_cp_drud_pruning_table() {
261 init_single_table(factorial8, cp_transition_table, cp_drud_pruning_table,
262 move_mask_drud);
263}
264
265void init_cp_drfb_pruning_table() {
266 init_single_table(factorial8, cp_transition_table, cp_drfb_pruning_table,
267 move_mask_drfb);
268}
269
270void init_cp_drrl_pruning_table() {
271 init_single_table(factorial8, cp_transition_table, cp_drrl_pruning_table,
272 move_mask_drrl);
273}
274
275void init_cp_htr_table() {
276 init_single_table(factorial8, cp_transition_table, cp_htr_pruning_table,
277 move_mask_htr);
278}
279
280void init_cpud_to_htr_table() {
281 init_cptohtr_table(factorial8, cp_transition_table,
282 cpud_to_htr_pruning_table, move_mask_drud);
283}
284
285void init_cpfb_to_htr_table() {
286 init_cptohtr_table(factorial8, cp_transition_table,
287 cpfb_to_htr_pruning_table, move_mask_drfb);
288}
289
290void init_cprl_to_htr_table() {
291 init_cptohtr_table(factorial8, cp_transition_table,
292 cprl_to_htr_pruning_table, move_mask_drrl);
293}
294
295
296void init_eofb_epose_pruning_table() {
297 init_double_table(pow2to11, binom12on4,
298 eofb_transition_table, epose_transition_table,
299 eofb_epose_pruning_table, move_mask_all);
300}
301
302void init_eorl_eposs_pruning_table() {
303 init_double_table(pow2to11, binom12on4,
304 eorl_transition_table, eposs_transition_table,
305 eorl_eposs_pruning_table, move_mask_all);
306}
307
308void init_eoud_eposm_pruning_table() {
309 init_double_table(pow2to11, binom12on4,
310 eoud_transition_table, eposm_transition_table,
311 eoud_eposm_pruning_table, move_mask_all);
312}
313
314
315
316void init_eofb_coud_pruning_table() {
317 init_double_table(pow2to11, pow3to7,
318 eofb_transition_table, coud_transition_table,
319 eofb_coud_pruning_table, move_mask_all);
320}
321
322void init_eofb_corl_pruning_table() {
323 init_double_table(pow2to11, pow3to7,
324 eofb_transition_table, corl_transition_table,
325 eofb_corl_pruning_table, move_mask_all);
326}
327
328void init_eorl_coud_pruning_table() {
329 init_double_table(pow2to11, pow3to7,
330 eorl_transition_table, coud_transition_table,
331 eorl_coud_pruning_table, move_mask_all);
332}
333
334void init_eorl_cofb_pruning_table() {
335 init_double_table(pow2to11, pow3to7,
336 eorl_transition_table, cofb_transition_table,
337 eorl_cofb_pruning_table, move_mask_all);
338}
339
340void init_eoud_corl_pruning_table() {
341 init_double_table(pow2to11, pow3to7,
342 eoud_transition_table, corl_transition_table,
343 eoud_corl_pruning_table, move_mask_all);
344}
345
346void init_eoud_cofb_pruning_table() {
347 init_double_table(pow2to11, pow3to7,
348 eoud_transition_table, cofb_transition_table,
349 eoud_cofb_pruning_table, move_mask_all);
350}
351
352void init_coud_epose_from_eofb_pruning_table() {
353 init_double_table(pow3to7, binom12on4,
354 coud_transition_table, epose_transition_table,
355 coud_epose_from_eofb_pruning_table, move_mask_eofb);
356}
357
358void init_cofb_eposs_from_eorl_pruning_table() {
359 init_double_table(pow3to7, binom12on4,
360 cofb_transition_table, eposs_transition_table,
361 cofb_eposs_from_eorl_pruning_table, move_mask_eorl);
362}
363
364void init_corl_eposm_from_eoud_pruning_table() {
365 init_double_table(pow3to7, binom12on4,
366 corl_transition_table, eposm_transition_table,
367 corl_eposm_from_eoud_pruning_table, move_mask_eoud);
368}
369
370void init_coud_epose_from_eorl_pruning_table() {
371 init_double_table(pow3to7, binom12on4,
372 coud_transition_table, epose_transition_table,
373 coud_epose_from_eorl_pruning_table, move_mask_eorl);
374}
375
376void init_cofb_eposs_from_eoud_pruning_table() {
377 init_double_table(pow3to7, binom12on4,
378 cofb_transition_table, eposs_transition_table,
379 cofb_eposs_from_eoud_pruning_table, move_mask_eoud);
380}
381
382void init_corl_eposm_from_eofb_pruning_table() {
383 init_double_table(pow3to7, binom12on4,
384 corl_transition_table, eposm_transition_table,
385 corl_eposm_from_eofb_pruning_table, move_mask_eofb);
386}
387
388void init_cp_co_pruning_table() {
389 init_double_table(factorial8, pow3to7,
390 cp_transition_table, coud_transition_table,
391 cp_co_pruning_table, move_mask_all);
392}
393
394void init_triple_eo_pruning_table() {
395 init_double_table(pow2to11, binom12on4*binom8on4,
396 eofb_transition_table, emslices_transition_table,
397 triple_eo_pruning_table, move_mask_all);
398}
399
400
401void init_small_pruning_tables() {
402 if (initialized_small)
403 return;
404
405 init_eofb_pruning_table();
406 init_eorl_pruning_table();
407 init_eoud_pruning_table();
408 init_coud_pruning_table();
409 init_cofb_pruning_table();
410 init_corl_pruning_table();
411 init_cp_pruning_table();
412
413 init_eorl_from_eofb_pruning_table();
414 init_eoud_from_eofb_pruning_table();
415 init_eoud_from_eorl_pruning_table();
416 init_eofb_from_eorl_pruning_table();
417 init_eofb_from_eoud_pruning_table();
418 init_eorl_from_eoud_pruning_table();
419
420 init_coud_from_eofb_pruning_table();
421 init_corl_from_eofb_pruning_table();
422 init_coud_from_eorl_pruning_table();
423 init_cofb_from_eorl_pruning_table();
424 init_cofb_from_eoud_pruning_table();
425 init_corl_from_eoud_pruning_table();
426
427 init_epud_pruning_table();
428 init_epfb_pruning_table();
429 init_eprl_pruning_table();
430 init_cp_drud_pruning_table();
431 init_cp_drfb_pruning_table();
432 init_cp_drrl_pruning_table();
433
434 init_cp_htr_table();
435 init_cpud_to_htr_table();
436 init_cpfb_to_htr_table();
437 init_cprl_to_htr_table();
438
439 initialized_small = 1;
440}
441
442void init_directdr_pruning_tables() {
443 if (initialized_directdr)
444 return;
445
446 init_eofb_epose_pruning_table();
447 init_eorl_eposs_pruning_table();
448 init_eoud_eposm_pruning_table();
449
450 init_eofb_coud_pruning_table();
451 init_eofb_corl_pruning_table();
452 init_eorl_coud_pruning_table();
453 init_eorl_cofb_pruning_table();
454 init_eoud_cofb_pruning_table();
455 init_eoud_corl_pruning_table();
456
457 initialized_directdr = 1;
458}
459
460void init_drfromeo_pruning_tables() {
461 if (initialized_drfromeo)
462 return;
463
464 init_coud_epose_from_eofb_pruning_table();
465 init_cofb_eposs_from_eorl_pruning_table();
466 init_corl_eposm_from_eoud_pruning_table();
467 init_coud_epose_from_eorl_pruning_table();
468 init_cofb_eposs_from_eoud_pruning_table();
469 init_corl_eposm_from_eofb_pruning_table();
470
471 initialized_drfromeo = 1;
472}
473
474void init_huge_pruning_tables() {
475 if (initialized_huge)
476 return;
477
478 init_cp_co_pruning_table();
479 init_triple_eo_pruning_table();
480
481 initialized_huge = 1;
482}
483
diff --git a/src/pruning_tables.h b/src/pruning_tables.h
new file mode 100644
index 0000000..7921e97
--- /dev/null
+++ b/src/pruning_tables.h
@@ -0,0 +1,66 @@
1#include <stdint.h>
2#include "utils.h"
3
4extern int eofb_pruning_table[pow2to11];
5extern int eorl_pruning_table[pow2to11];
6extern int eoud_pruning_table[pow2to11];
7extern int coud_pruning_table[pow3to7];
8extern int cofb_pruning_table[pow3to7];
9extern int corl_pruning_table[pow3to7];
10extern int cp_pruning_table[factorial8];
11
12extern int eorl_from_eofb_pruning_table[pow2to11];
13extern int eoud_from_eofb_pruning_table[pow2to11];
14extern int eoud_from_eorl_pruning_table[pow2to11];
15extern int eofb_from_eorl_pruning_table[pow2to11];
16extern int eofb_from_eoud_pruning_table[pow2to11];
17extern int eorl_from_eoud_pruning_table[pow2to11];
18
19extern int coud_from_eofb_pruning_table[pow3to7];
20extern int coud_from_eorl_pruning_table[pow3to7];
21extern int cofb_from_eorl_pruning_table[pow3to7];
22extern int cofb_from_eoud_pruning_table[pow3to7];
23extern int corl_from_eoud_pruning_table[pow3to7];
24extern int corl_from_eofb_pruning_table[pow3to7];
25
26extern int cp_drud_pruning_table[factorial8];
27extern int cp_drfb_pruning_table[factorial8];
28extern int cp_drrl_pruning_table[factorial8];
29extern int epud_pruning_table[factorial8];
30extern int epfb_pruning_table[factorial8];
31extern int eprl_pruning_table[factorial8];
32
33extern int cp_htr_pruning_table[factorial8];
34extern int cpud_to_htr_pruning_table[factorial8];
35extern int cpfb_to_htr_pruning_table[factorial8];
36extern int cprl_to_htr_pruning_table[factorial8];
37
38/* About 1Mb each */
39extern int8_t eofb_epose_pruning_table[pow2to11][binom12on4];
40extern int8_t eorl_eposs_pruning_table[pow2to11][binom12on4];
41extern int8_t eoud_eposm_pruning_table[pow2to11][binom12on4];
42
43/* About 4.5Mb each */
44extern int8_t eofb_coud_pruning_table[pow2to11][pow3to7];
45extern int8_t eofb_corl_pruning_table[pow2to11][pow3to7];
46extern int8_t eorl_coud_pruning_table[pow2to11][pow3to7];
47extern int8_t eorl_cofb_pruning_table[pow2to11][pow3to7];
48extern int8_t eoud_cofb_pruning_table[pow2to11][pow3to7];
49extern int8_t eoud_corl_pruning_table[pow2to11][pow3to7];
50
51/* About 1Mb each */
52extern int8_t coud_epose_from_eofb_pruning_table[pow3to7][binom12on4];
53extern int8_t cofb_eposs_from_eorl_pruning_table[pow3to7][binom12on4];
54extern int8_t corl_eposm_from_eoud_pruning_table[pow3to7][binom12on4];
55extern int8_t coud_epose_from_eorl_pruning_table[pow3to7][binom12on4];
56extern int8_t cofb_eposs_from_eoud_pruning_table[pow3to7][binom12on4];
57extern int8_t corl_eposm_from_eofb_pruning_table[pow3to7][binom12on4];
58
59/* First one 88Mb, second one 21Mb */
60extern int8_t cp_co_pruning_table[factorial8][pow3to7];
61extern int8_t triple_eo_pruning_table[pow2to11][binom12on4*binom8on4];
62
63void init_small_pruning_tables();
64void init_directdr_pruning_tables();
65void init_drfromeo_pruning_tables();
66void init_huge_pruning_tables();
diff --git a/src/solver.c b/src/solver.c
new file mode 100644
index 0000000..c2b3ff5
--- /dev/null
+++ b/src/solver.c
@@ -0,0 +1,893 @@
1#include <stdint.h>
2#include <stdio.h>
3
4#include "utils.h"
5#include "coordinates.h"
6#include "moves.h"
7#include "io.h"
8#include "pruning_tables.h"
9
10/* Applies inverse of moves, inverse of prev_moves and then inverse of scramble
11 * and returns a coordinate determined by t_table. */
12int premoves_inverse(int moves[21], int scramble[], int prev_moves[21],
13 int t_table[][19]) {
14 int nprevmoves, nmoves, nscramble, coord = 0;
15
16 for (nmoves = 0; moves[nmoves]; nmoves++);
17 for (nprevmoves = 0; prev_moves[nprevmoves]; nprevmoves++);
18 for (nscramble = 0; scramble[nscramble]; nscramble++);
19
20 for (int i = nmoves - 1; i >= 0; i--)
21 coord = t_table[coord][inverse_move[moves[i]]];
22 for (int i = nprevmoves - 1; i >= 0; i--)
23 coord = t_table[coord][inverse_move[prev_moves[i]]];
24 for (int i = nscramble - 1; i >= 0; i--)
25 coord = t_table[coord][inverse_move[scramble[i]]];
26
27 return coord;
28}
29
30
31/******/
32/* EO */
33/******/
34void niss_eo_dfs(int eo, int scramble[], int eo_list[][21], int *eo_count,
35 int t_table[pow2to11][19], int p_table[pow2to11],
36 int last1, int last2, int moves, int m, int d, int niss,
37 int can_use_niss, int hide) {
38
39 if (*eo_count >= m || moves > d ||
40 ((!can_use_niss || niss) && moves + p_table[eo] > d))
41 return;
42
43 eo_list[*eo_count][moves] = 0;
44
45 if (eo == 0) {
46 /* If an early EO is found, or if "case F2 B", or if hide is on. */
47 if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
48 (hide && moves > 0 &&
49 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
50 return;
51 /* Copy moves for the next solution */
52 if (*eo_count < m - 1)
53 copy_moves(eo_list[*eo_count], eo_list[(*eo_count)+1]);
54 (*eo_count)++;
55 return;
56 }
57
58 if (moves + p_table[eo] <= d) {
59 for (int i = 1; i < 19; i++) {
60 if (possible_next[last1][last2] & (1 << i)) {
61 eo_list[*eo_count][moves] = niss ? -i : i;
62 niss_eo_dfs(t_table[eo][i], scramble, eo_list, eo_count, t_table,
63 p_table, i, last1, moves+1, m, d, niss,
64 can_use_niss, hide);
65 }
66 }
67 }
68
69 eo_list[*eo_count][moves] = 0;
70
71 /* If not nissing already and we either have not done any move yet or
72 * the last move was F/F' etc, and if I am allowed to niss, try niss! */
73 if (!niss && (last1 == 0 || t_table[0][last1] != 0) && can_use_niss &&
74 !(hide && moves > 0 &&
75 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0)))) {
76 int aux[] = {0,0};
77 niss_eo_dfs(premoves_inverse(eo_list[*eo_count], scramble, aux, t_table),
78 scramble, eo_list, eo_count, t_table, p_table,
79 0, 0, moves, m, d, 1, can_use_niss, hide);
80 }
81}
82
83int eo_scram_spam(int scram[], int eo_list[][21], int fb, int rl, int ud,
84 int m, int b, int niss, int h) {
85
86 init_small_pruning_tables();
87
88 int n = 0, eofb = 0, eorl = 0, eoud = 0;
89 for (int i = 0; scram[i]; i++) {
90 eofb = eofb_transition_table[eofb][scram[i]];
91 eorl = eorl_transition_table[eorl][scram[i]];
92 eoud = eoud_transition_table[eoud][scram[i]];
93 }
94 for (int i = 0; i <= b; i++) {
95 if (fb)
96 niss_eo_dfs(eofb, scram, eo_list, &n, eofb_transition_table,
97 eofb_pruning_table, 0, 0, 0, m, i, 0, niss, h);
98 if (rl)
99 niss_eo_dfs(eorl, scram, eo_list, &n, eorl_transition_table,
100 eorl_pruning_table, 0, 0, 0, m, i, 0, niss, h);
101 if (ud)
102 niss_eo_dfs(eoud, scram, eo_list, &n, eoud_transition_table,
103 eoud_pruning_table, 0, 0, 0, m, i, 0, niss, h);
104 }
105 return n;
106}
107
108
109/**************/
110/* DR from EO */
111/**************/
112
113
114/* Scramble includes premoves for previous EO */
115void niss_dr_from_eo_dfs(int co, int epos, int scramble[], int eo_moves[21],
116 int dr_list[][21], int *dr_count,
117 int co_t_table[pow3to7][19],
118 int epos_t_table[binom12on4][19],
119 int8_t p_table[pow3to7][binom12on4], int mask,
120 int last1, int last2, int last1_inv, int last2_inv,
121 int moves, int m, int d, int niss,
122 int can_use_niss, int hide) {
123
124 if (*dr_count >= m || moves > d ||
125 ((!can_use_niss || niss) && moves + p_table[co][epos] > d))
126 return;
127
128 dr_list[*dr_count][moves] = 0;
129
130 if (co == 0 && epos == 0) {
131 if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
132 (hide && moves > 0 &&
133 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
134 return;
135 /* Copy moves for the next solution */
136 if (*dr_count < m - 1)
137 copy_moves(dr_list[*dr_count], dr_list[(*dr_count)+1]);
138 (*dr_count)++;
139 return;
140 }
141
142 if (moves + p_table[co][epos] <= d) {
143 for (int i = 1; i < 19; i++) {
144 if (possible_next[last1][last2] & (1 << i) & mask) {
145 dr_list[*dr_count][moves] = niss ? -i : i;
146 niss_dr_from_eo_dfs(co_t_table[co][i], epos_t_table[epos][i],
147 scramble, eo_moves, dr_list, dr_count,
148 co_t_table, epos_t_table, p_table, mask,
149 i, last1, last1_inv, last2_inv,
150 moves+1, m, d, niss, can_use_niss, hide);
151 }
152 }
153 }
154
155 dr_list[*dr_count][moves] = 0;
156
157 /* If not nissing already and we either have not done any move yet or
158 * the last move was F/F' etc and I am allowed to niss, try niss! */
159 if (!niss && (last1 == 0 || co_t_table[0][last1] != 0) && can_use_niss &&
160 !(hide && moves > 0 &&
161 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
162 niss_dr_from_eo_dfs(premoves_inverse(dr_list[*dr_count], scramble,
163 eo_moves, co_t_table),
164 premoves_inverse(dr_list[*dr_count], scramble,
165 eo_moves, epos_t_table),
166 scramble, eo_moves, dr_list, dr_count,
167 co_t_table, epos_t_table, p_table,
168 mask, last1_inv, last2_inv, 0, 0,
169 moves, m, d, 1, can_use_niss, hide);
170}
171
172int drfrom_scram_spam(int scram[], int dr_list[][21], int from, int fb,
173 int rl, int ud, int m, int b, int niss, int hide) {
174
175 init_drfromeo_pruning_tables();
176
177 int n = 0;
178 int eofb = 0, eorl = 0, eoud = 0;
179 int epose = 0, eposm = 0, eposs = 0;
180 int coud = 0, corl = 0, cofb = 0;
181
182 for (int i = 0; scram[i]; i++) {
183 eofb = eofb_transition_table[eofb][scram[i]];
184 eorl = eorl_transition_table[eorl][scram[i]];
185 eoud = eoud_transition_table[eoud][scram[i]];
186
187 cofb = cofb_transition_table[cofb][scram[i]];
188 corl = corl_transition_table[corl][scram[i]];
189 coud = coud_transition_table[coud][scram[i]];
190
191 epose = epose_transition_table[epose][scram[i]];
192 eposm = eposm_transition_table[eposm][scram[i]];
193 eposs = eposs_transition_table[eposs][scram[i]];
194 }
195
196 int fake_eom[2] = {0, 0}; /* Fake EO moves */
197
198 if (from == 1) {
199 if (eofb)
200 return -1;
201 for (int i = 0; i <= b; i++) {
202 if (ud)
203 niss_dr_from_eo_dfs(coud, epose, scram, fake_eom, dr_list, &n,
204 coud_transition_table, epose_transition_table,
205 coud_epose_from_eofb_pruning_table, move_mask_eofb,
206 0, 0, 0, 0, 0, m, i, 0, niss, hide);
207 if (rl)
208 niss_dr_from_eo_dfs(corl, eposm, scram, fake_eom, dr_list, &n,
209 corl_transition_table, eposm_transition_table,
210 corl_eposm_from_eofb_pruning_table, move_mask_eofb,
211 0, 0, 0, 0, 0, m, i, 0, niss, hide);
212 }
213 } else if (from == 2) {
214 if (eorl)
215 return -1;
216 for (int i = 0; i <= b; i++) {
217 if (fb)
218 niss_dr_from_eo_dfs(cofb, eposs, scram, fake_eom, dr_list, &n,
219 cofb_transition_table, eposs_transition_table,
220 cofb_eposs_from_eorl_pruning_table, move_mask_eorl,
221 0, 0, 0, 0, 0, m, i, 0, niss, hide);
222 if (ud)
223 niss_dr_from_eo_dfs(coud, epose, scram, fake_eom, dr_list, &n,
224 coud_transition_table, epose_transition_table,
225 coud_epose_from_eorl_pruning_table, move_mask_eorl,
226 0, 0, 0, 0, 0, m, i, 0, niss, hide);
227 }
228 } else if (from == 3) {
229 if (eoud)
230 return -1;
231 for (int i = 0; i <= b; i++) {
232 if (rl)
233 niss_dr_from_eo_dfs(corl, eposm, scram, fake_eom, dr_list, &n,
234 corl_transition_table, eposm_transition_table,
235 corl_eposm_from_eoud_pruning_table, move_mask_eoud,
236 0, 0, 0, 0, 0, m, i, 0, niss, hide);
237 if (fb)
238 niss_dr_from_eo_dfs(cofb, eposs, scram, fake_eom, dr_list, &n,
239 cofb_transition_table, eposs_transition_table,
240 cofb_eposs_from_eoud_pruning_table, move_mask_eoud,
241 0, 0, 0, 0, 0, m, i, 0, niss, hide);
242 }
243 } else {
244 return -1;
245 }
246 return n;
247}
248
249
250/***************/
251/* HTR from DR */
252/***************/
253
254/* Scramble includes premoves for previous DR */
255void niss_htr_from_dr_dfs(int cp, int eo3, int scramble[], int eodr_moves[21],
256 int htr_list[][21], int *htr_count,
257 int eo3_t_table[pow2to11][19],
258 int cp_to_htr_pruning_table[factorial8],
259 int cp_htr_pruning_table[factorial8],
260 int cp_finish_pruning_table[factorial8],
261 int mask, int last1, int last2,
262 int last1_inv, int last2_inv, int moves,
263 int m, int d, int niss,
264 int can_use_niss, int hide) {
265
266 if (*htr_count >= m || moves > d ||
267 ((!can_use_niss || niss) && moves + cp_to_htr_pruning_table[cp] > d) ||
268 moves + cp_finish_pruning_table[cp] - 4 > d)
269 return;
270
271 htr_list[*htr_count][moves] = 0;
272
273 if ((cp == 0 || cp_htr_pruning_table[cp]) && eo3 == 0) {
274 if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
275 (hide && moves > 0 &&
276 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
277 return;
278 /* Copy moves for the next solution */
279 if (*htr_count < m - 1)
280 copy_moves(htr_list[*htr_count], htr_list[(*htr_count)+1]);
281 (*htr_count)++;
282 return;
283 }
284
285 if (moves + cp_htr_pruning_table[cp] <= d) {
286 for (int i = 1; i < 19; i++) {
287 if (possible_next[last1][last2] & (1 << i) & mask) {
288 htr_list[*htr_count][moves] = niss ? -i : i;
289 niss_htr_from_dr_dfs(cp_transition_table[cp][i], eo3_t_table[eo3][i],
290 scramble, eodr_moves, htr_list, htr_count,
291 eo3_t_table, cp_to_htr_pruning_table,
292 cp_htr_pruning_table, cp_finish_pruning_table,
293 mask, i, last1, last1_inv, last2_inv,
294 moves+1, m, d, niss, can_use_niss, hide);
295 }
296 }
297 }
298
299 htr_list[*htr_count][moves] = 0;
300
301 /* If not nissing already and we either have not done any move yet or
302 * the last move was a quarter turn and I am allowed to niss, try niss! */
303 if (!niss && last1 % 3 != 2 && can_use_niss &&
304 !(hide && moves > 0 &&
305 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
306 niss_htr_from_dr_dfs(premoves_inverse(htr_list[*htr_count], scramble,
307 eodr_moves, cp_transition_table),
308 premoves_inverse(htr_list[*htr_count], scramble,
309 eodr_moves, eo3_t_table),
310 scramble, eodr_moves, htr_list, htr_count,
311 eo3_t_table, cp_to_htr_pruning_table,
312 cp_htr_pruning_table, cp_finish_pruning_table,
313 mask, last1_inv, last2_inv,
314 0, 0, moves, m, d, 1, can_use_niss, hide);
315}
316
317int htr_scram_spam(int scram[], int htr_list[][21], int from,
318 int m, int b, int niss, int hide) {
319
320 init_small_pruning_tables();
321
322 int n = 0;
323 int eofb = 0, eorl = 0, eoud = 0;
324 int coud = 0, corl = 0, cofb = 0;
325 int cp = 0;
326
327 for (int i = 0; scram[i]; i++) {
328 eofb = eofb_transition_table[eofb][scram[i]];
329 eorl = eorl_transition_table[eorl][scram[i]];
330 eoud = eoud_transition_table[eoud][scram[i]];
331
332 cofb = cofb_transition_table[cofb][scram[i]];
333 corl = corl_transition_table[corl][scram[i]];
334 coud = coud_transition_table[coud][scram[i]];
335
336 cp = cp_transition_table[cp][scram[i]];
337 }
338
339 int fake_drm[2] = {0, 0}; /* Fake DR moves */
340
341 if ((from == 1 || from == 0) && (!eofb && !eorl && !coud)) {
342 for (int i = 0; i <= b; i++) {
343 niss_htr_from_dr_dfs(cp, eoud, scram, fake_drm, htr_list, &n,
344 eoud_transition_table, cpud_to_htr_pruning_table,
345 cp_htr_pruning_table, cp_drud_pruning_table,
346 move_mask_drud, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
347 }
348 } else if ((from == 2 || from == 0) && (!eorl && !eoud && !cofb)) {
349 for (int i = 0; i <= b; i++) {
350 niss_htr_from_dr_dfs(cp, eofb, scram, fake_drm, htr_list, &n,
351 eofb_transition_table, cpfb_to_htr_pruning_table,
352 cp_htr_pruning_table, cp_drfb_pruning_table,
353 move_mask_drfb, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
354 }
355 } else if ((from == 3 || from == 0) && (!eoud && !eofb && !corl)) {
356 for (int i = 0; i <= b; i++) {
357 niss_htr_from_dr_dfs(cp, eorl, scram, fake_drm, htr_list, &n,
358 eorl_transition_table, cprl_to_htr_pruning_table,
359 cp_htr_pruning_table, cp_drrl_pruning_table,
360 move_mask_drrl, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
361 }
362 } else {
363 return -1;
364 }
365 return n;
366}
367
368
369/***********************/
370/* Direct DR (no NISS) */
371/***********************/
372void dr_dfs(int eo, int eo2, int eslice, int co,
373 int dr_list[][21], int *dr_count,
374 int eo_t_table[pow2to11][19], int eo2_t_table[pow2to11][19],
375 int eslice_t_table[binom12on4][19], int co_t_table[pow3to7][19],
376 int8_t eo_eslice_p_table[pow2to11][binom12on4],
377 int8_t eo_co_p_table[pow2to11][pow3to7],
378 int8_t eo2_co_p_table[pow2to11][pow3to7],
379 int last1, int last2, int moves, int max_sol,
380 int depth, int hide) {
381 if (*dr_count >= max_sol || moves + eo_eslice_p_table[eo][eslice] > depth ||
382 moves + eo_co_p_table[eo][co] > depth ||
383 moves + eo2_co_p_table[eo2][co] > depth)
384 return;
385
386 dr_list[*dr_count][moves] = 0;
387
388 if (eo == 0 && eslice == 0 && co == 0) {
389 /* If an early DR is found, or if "case R2 L". */
390 if (moves != depth || (parallel(last1, last2) && last2 % 3 == 2) ||
391 (hide && moves > 0 &&
392 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
393 return;
394 /* Copy moves for the next solution */
395 if (*dr_count < max_sol - 1)
396 copy_moves(dr_list[*dr_count], dr_list[(*dr_count)+1]);
397 (*dr_count)++;
398 return;
399 }
400
401 for (int i = 1; i < 19; i++) {
402 if (possible_next[last1][last2] & (1 << i)) {
403 dr_list[*dr_count][moves] = i;
404 dr_dfs(eo_t_table[eo][i], eo2_t_table[eo2][i],
405 eslice_t_table[eslice][i], co_t_table[co][i],
406 dr_list, dr_count,
407 eo_t_table, eo2_t_table, eslice_t_table, co_t_table,
408 eo_eslice_p_table, eo_co_p_table, eo2_co_p_table,
409 i, last1, moves+1, max_sol, depth, hide);
410 }
411 }
412}
413
414int dr_scram_spam(int scram[], int dr_list[][21], int fb, int rl, int ud,
415 int m, int b, int h) {
416
417 init_directdr_pruning_tables();
418
419 int n = 0;
420 int eofb = 0, eorl = 0, eoud = 0;
421 int epose = 0, eposm = 0, eposs = 0;
422 int coud = 0, corl = 0, cofb = 0;
423
424 for (int i = 0; scram[i]; i++) {
425 eofb = eofb_transition_table[eofb][scram[i]];
426 eorl = eorl_transition_table[eorl][scram[i]];
427 eoud = eoud_transition_table[eoud][scram[i]];
428
429 cofb = cofb_transition_table[cofb][scram[i]];
430 corl = corl_transition_table[corl][scram[i]];
431 coud = coud_transition_table[coud][scram[i]];
432
433 epose = epose_transition_table[epose][scram[i]];
434 eposm = eposm_transition_table[eposm][scram[i]];
435 eposs = eposs_transition_table[eposs][scram[i]];
436 }
437
438 for (int i = 0; i <= b; i++) {
439 if (ud)
440 dr_dfs(eofb, eorl, epose, coud, dr_list, &n,
441 eofb_transition_table, eorl_transition_table,
442 epose_transition_table, coud_transition_table,
443 eofb_epose_pruning_table, eofb_coud_pruning_table,
444 eorl_coud_pruning_table, 0, 0, 0, m, i, h);
445 if (fb)
446 dr_dfs(eorl, eoud, eposs, cofb, dr_list, &n,
447 eorl_transition_table, eoud_transition_table,
448 eposs_transition_table, cofb_transition_table,
449 eorl_eposs_pruning_table, eorl_cofb_pruning_table,
450 eoud_cofb_pruning_table, 0, 0, 0, m, i, h);
451 if (rl)
452 dr_dfs(eoud, eofb, eposm, corl, dr_list, &n,
453 eoud_transition_table, eofb_transition_table,
454 eposm_transition_table, corl_transition_table,
455 eoud_eposm_pruning_table, eoud_corl_pruning_table,
456 eofb_corl_pruning_table, 0, 0, 0, m, i, h);
457 }
458 return n;
459}
460
461
462/*************/
463/* DR finish */
464/*************/
465void dr_finish_dfs(int cp, int ep8, int ep4, int sol[][21], int *sol_count,
466 int ep8_t_table[factorial8][19],
467 int ep4_t_table[factorial4][19],
468 int cp_p_table[factorial8],
469 int ep8_p_table[factorial8],
470 int mask, int last1, int last2, int moves, int m, int d) {
471
472
473 if (*sol_count >= m || moves + cp_p_table[cp] > d ||
474 moves + ep8_p_table[ep8] > d)
475 return;
476
477 sol[*sol_count][moves] = 0;
478
479 if (cp == 0 && ep8 == 0 && ep4 == 0) {
480 if (moves != d)
481 return;
482 /* Copy moves for the next solution */
483 if (*sol_count < m - 1)
484 copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
485 (*sol_count)++;
486 return;
487 }
488
489 for (int i = 1; i < 19; i++) {
490 if (possible_next[last1][last2] & (1 << i) & mask) {
491 sol[*sol_count][moves] = i;
492 dr_finish_dfs(cp_transition_table[cp][i], ep8_t_table[ep8][i],
493 ep4_t_table[ep4][i], sol, sol_count,
494 ep8_t_table, ep4_t_table,
495 cp_p_table, ep8_p_table,
496 mask, i, last1, moves+1, m, d);
497 }
498 }
499
500 return;
501}
502
503int dr_finish_scram_spam(int scram[], int sol[][21], int from, int m, int b) {
504
505 init_small_pruning_tables();
506
507 int n = 0;
508 int eofb = 0, eorl = 0, eoud = 0;
509 int coud = 0, corl = 0, cofb = 0;
510 int cp = 0;
511 int ep[12];
512 ep_int_to_array(0, ep);
513
514 for (int i = 0; scram[i]; i++) {
515 eofb = eofb_transition_table[eofb][scram[i]];
516 eorl = eorl_transition_table[eorl][scram[i]];
517 eoud = eoud_transition_table[eoud][scram[i]];
518
519 cofb = cofb_transition_table[cofb][scram[i]];
520 corl = corl_transition_table[corl][scram[i]];
521 coud = coud_transition_table[coud][scram[i]];
522
523 cp = cp_transition_table[cp][scram[i]];
524 apply_move_ep_array(scram[i], ep);
525 }
526
527 if ((from == 1 && (eofb || eorl || coud)) ||
528 (from == 2 && (eorl || eoud || cofb)) ||
529 (from == 3 && (eoud || eofb || corl)) ||
530 ((eofb || eorl || coud) && (eorl || eoud ||cofb) && (eoud ||eofb || corl)))
531 return -1;
532
533 for (int i = 0; i <= b; i++) {
534 if ((from == 1 || from == 0) && (!eofb && !eorl && !coud))
535 dr_finish_dfs(cp, epud_array_to_int(ep), epe_array_to_int(ep),
536 sol, &n, epud_transition_table, epe_transition_table,
537 cp_drud_pruning_table, epud_pruning_table,
538 move_mask_drud, 0, 0, 0, m, i);
539 if ((from == 2 || from == 0) && (!eorl && !eoud && !cofb))
540 dr_finish_dfs(cp, epfb_array_to_int(ep), eps_array_to_int(ep),
541 sol, &n, epfb_transition_table, eps_transition_table,
542 cp_drfb_pruning_table, epfb_pruning_table,
543 move_mask_drfb, 0, 0, 0, m, i);
544 if ((from == 3 || from == 0) && (!eoud && !eofb && !corl))
545 dr_finish_dfs(cp, eprl_array_to_int(ep), epm_array_to_int(ep),
546 sol, &n, eprl_transition_table, epm_transition_table,
547 cp_drrl_pruning_table, eprl_pruning_table,
548 move_mask_drrl, 0, 0, 0, m, i);
549 }
550
551 return n;
552}
553
554int htr_finish_scram_spam(int scram[], int sol[][21], int m, int b) {
555
556 init_small_pruning_tables();
557
558 int n = 0;
559 int eofb = 0, eorl = 0, eoud = 0;
560 int coud = 0, cp = 0;
561 int ep[12];
562 ep_int_to_array(0, ep);
563
564 for (int i = 0; scram[i]; i++) {
565 eofb = eofb_transition_table[eofb][scram[i]];
566 eorl = eorl_transition_table[eorl][scram[i]];
567 eoud = eoud_transition_table[eoud][scram[i]];
568
569 coud = coud_transition_table[coud][scram[i]];
570
571 cp = cp_transition_table[cp][scram[i]];
572 apply_move_ep_array(scram[i], ep);
573 }
574
575 if (eofb || eorl || eoud || coud || cpud_to_htr_pruning_table[cp] != 0)
576 return -1;
577
578 for (int i = 0; i <= b; i++)
579 dr_finish_dfs(cp, epud_array_to_int(ep), epe_array_to_int(ep),
580 sol, &n, epud_transition_table, epe_transition_table,
581 cp_drud_pruning_table, epud_pruning_table,
582 move_mask_htr, 0, 0, 0, m, i);
583
584 return n;
585}
586
587
588/**************/
589/* DR corners */
590/**************/
591void dr_corners_dfs(int cp, int sol[][21], int *sol_count,
592 int cp_p_table[factorial8], int mask, int last1, int last2,
593 int moves, int m, int d, int ignore) {
594
595 if (*sol_count >= m || (!ignore && moves + cp_p_table[cp] > d) ||
596 (ignore && moves + cp_p_table[cp] - 2 > d))
597 return;
598
599
600 sol[*sol_count][moves] = 0;
601
602 if (cp == 0 || (ignore &&
603 (cp_transition_table[cp_transition_table[cp][U]][D3] == 0 ||
604 cp_transition_table[cp_transition_table[cp][U2]][D2] == 0 ||
605 cp_transition_table[cp_transition_table[cp][U3]][D] == 0 ))) {
606 if (moves != d)
607 return;
608 /* Copy moves for the next solution */
609 if (*sol_count < m - 1)
610 copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
611 (*sol_count)++;
612 return;
613 }
614
615 for (int i = 1; i < 19; i++) {
616 if (possible_next[last1][last2] & (1 << i) & mask) {
617 sol[*sol_count][moves] = i;
618 dr_corners_dfs(cp_transition_table[cp][i], sol, sol_count,
619 cp_p_table, mask, i, last1, moves+1, m, d, ignore);
620 }
621 }
622}
623
624int dr_corners_scram_spam(int scram[], int sol[][21], int from, int m, int b,
625 int ignore) {
626
627 init_small_pruning_tables();
628
629 int n = 0;
630 int eofb = 0, eorl = 0, eoud = 0;
631 int coud = 0, corl = 0, cofb = 0;
632 int cp = 0;
633
634 for (int i = 0; scram[i]; i++) {
635 eofb = eofb_transition_table[eofb][scram[i]];
636 eorl = eorl_transition_table[eorl][scram[i]];
637 eoud = eoud_transition_table[eoud][scram[i]];
638
639 cofb = cofb_transition_table[cofb][scram[i]];
640 corl = corl_transition_table[corl][scram[i]];
641 coud = coud_transition_table[coud][scram[i]];
642
643 cp = cp_transition_table[cp][scram[i]];
644 }
645
646 if ((from == 1 && coud) || (from == 2 && cofb) || (from == 3 && corl) ||
647 (coud && cofb && corl))
648 return -1;
649
650 for (int i = 0; i <= b; i++) {
651 if ((from == 1 || from == 0) && !coud)
652 dr_corners_dfs(cp, sol, &n, cp_drud_pruning_table, move_mask_drud,
653 0, 0, 0, m, i, ignore);
654 if ((from == 2 || from == 0) && !cofb)
655 dr_corners_dfs(cp, sol, &n, cp_drfb_pruning_table, move_mask_drfb,
656 0, 0, 0, m, i, ignore);
657 if ((from == 3 || from == 0) && !corl)
658 dr_corners_dfs(cp, sol, &n, cp_drrl_pruning_table, move_mask_drrl,
659 0, 0, 0, m, i, ignore);
660 }
661
662 return n;
663}
664
665/***************/
666/* Full solver */
667/***************/
668
669int is_ep_solved(int ep, int moves[21]) {
670 int ep_arr[12];
671 ep_int_to_array(ep, ep_arr);
672 for (int i = 0; moves[i]; i++)
673 apply_move_ep_array(moves[i], ep_arr);
674 return !ep_array_to_int(ep_arr);
675}
676
677/* Solves directly using only small tables. Suitable for short solutions. */
678void small_optimal_dfs(int eofb, int eorl, int eoud, int ep,
679 int coud, int cofb, int corl, int cp,
680 int sol[][21], int *sol_count, int last1, int last2,
681 int moves, int m, int d) {
682 if (moves + eofb_pruning_table[eofb] > d ||
683 moves + eorl_pruning_table[eorl] > d ||
684 moves + eoud_pruning_table[eoud] > d ||
685 moves + coud_pruning_table[coud] > d ||
686 moves + cofb_pruning_table[cofb] > d ||
687 moves + corl_pruning_table[corl] > d ||
688 moves + cp_pruning_table[cp] > d ||
689 *sol_count >= m)
690 return;
691
692 sol[*sol_count][moves] = 0;
693
694 if (eofb == 0 && coud == 0 && cp == 0) {
695 if (is_ep_solved(ep, sol[*sol_count])) {
696 if (moves != d)
697 return;
698 if (*sol_count < m - 1)
699 copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
700 (*sol_count)++;
701 return;
702 }
703 }
704
705 for (int i = 1; i < 19; i++) {
706 if (possible_next[last1][last2] & (1 << i)) {
707 sol[*sol_count][moves] = i;
708 small_optimal_dfs(eofb_transition_table[eofb][i],
709 eorl_transition_table[eorl][i],
710 eoud_transition_table[eoud][i], ep,
711 coud_transition_table[coud][i],
712 cofb_transition_table[cofb][i],
713 corl_transition_table[corl][i],
714 cp_transition_table[cp][i],
715 sol, sol_count, i, last1, moves+1, m, d);
716 }
717 }
718}
719
720/* Solves directly using only medium tables. Suitable for short solutions. */
721void medium_optimal_dfs(int eofb, int eorl, int eoud,
722 int epose, int eposs, int eposm, int ep,
723 int coud, int cofb, int corl, int cp,
724 int sol[][21], int *sol_count, int last1, int last2,
725 int moves, int m, int d) {
726 if (moves + eofb_epose_pruning_table[eofb][epose] > d ||
727 moves + eorl_eposs_pruning_table[eorl][eposs] > d ||
728 moves + eoud_eposm_pruning_table[eoud][eposm] > d ||
729 moves + eofb_coud_pruning_table[eofb][coud] > d ||
730 moves + eofb_corl_pruning_table[eofb][corl] > d ||
731 moves + eorl_coud_pruning_table[eorl][coud] > d ||
732 moves + eorl_cofb_pruning_table[eorl][cofb] > d ||
733 moves + eoud_cofb_pruning_table[eoud][cofb] > d ||
734 moves + eoud_corl_pruning_table[eoud][corl] > d ||
735 moves + cp_pruning_table[cp] > d ||
736 *sol_count >= m)
737 return;
738
739 sol[*sol_count][moves] = 0;
740
741 if (eofb == 0 && coud == 0 && cp == 0) {
742 if (is_ep_solved(ep, sol[*sol_count])) {
743 if (moves != d)
744 return;
745 if (*sol_count < m - 1)
746 copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
747 (*sol_count)++;
748 return;
749 }
750 }
751
752 for (int i = 1; i < 19; i++) {
753 if (possible_next[last1][last2] & (1 << i)) {
754 sol[*sol_count][moves] = i;
755 medium_optimal_dfs(eofb_transition_table[eofb][i],
756 eorl_transition_table[eorl][i],
757 eoud_transition_table[eoud][i],
758 epose_transition_table[epose][i],
759 eposs_transition_table[eposs][i],
760 eposm_transition_table[eposm][i], ep,
761 coud_transition_table[coud][i],
762 cofb_transition_table[cofb][i],
763 corl_transition_table[corl][i],
764 cp_transition_table[cp][i],
765 sol, sol_count, i, last1, moves+1, m, d);
766 }
767 }
768}
769
770/* Uses huge tables */
771int optimal_dfs(int ep, int cp, int eo, int co, int emslices,
772 int sol[][21], int last1, int last2, int moves, int d) {
773 if (moves + cp_co_pruning_table[cp][co] > d ||
774 moves + triple_eo_pruning_table[eo][emslices] > d)
775 return 0;
776
777 sol[0][moves] = 0;
778
779 /* If solved, no need to check the depth */
780 if (cp == 0 && co == 0 && eo == 0 && emslices == 0)
781 if (is_ep_solved(ep, sol[0]))
782 return 1;
783
784 for (int i = 1; i < 19; i++) {
785 if (possible_next[last1][last2] & (1 << i)) {
786 sol[0][moves] = i;
787 if (optimal_dfs(ep, cp_transition_table[cp][i],
788 eofb_transition_table[eo][i],
789 coud_transition_table[co][i],
790 emslices_transition_table[emslices][i],
791 sol, i, last1, moves+1, d))
792 return 1;
793 }
794 }
795 return 0;
796}
797
798int solve_scram(int scram[], int sol[][21], int m, int b, int optimal) {
799
800 /* Initialize pieces. */
801 int eofb = 0, eorl = 0, eoud = 0, ep = 0;
802 int epose = 0, eposs = 0, eposm = 0;
803 int coud = 0, cofb = 0, corl = 0, cp = 0;
804 int emslices = 0;
805 for (int i = 0; scram[i]; i++) {
806 eofb = eofb_transition_table[eofb][scram[i]];
807 eorl = eorl_transition_table[eorl][scram[i]];
808 eoud = eoud_transition_table[eoud][scram[i]];
809
810 epose = epose_transition_table[epose][scram[i]];
811 eposs = eposs_transition_table[eposs][scram[i]];
812 eposm = eposm_transition_table[eposm][scram[i]];
813
814 ep = apply_move_ep_int(scram[i], ep);
815
816 coud = coud_transition_table[coud][scram[i]];
817 cofb = cofb_transition_table[cofb][scram[i]];
818 corl = corl_transition_table[corl][scram[i]];
819 cp = cp_transition_table[cp][scram[i]];
820
821 emslices = emslices_transition_table[emslices][scram[i]];
822 }
823
824 /* First we check if there are solutions of up to max_small moves. */
825 int max_small = 10;
826 int n = 0;
827 init_small_pruning_tables();
828 for (int i = 0; i <= min(b, max_small); i++) {
829 small_optimal_dfs(eofb, eorl, eoud, ep, coud, cofb, corl, cp,
830 sol, &n, 0, 0, 0, m, i);
831 if (n > 0 && optimal)
832 b = min(b, len(sol[0]));
833 }
834
835
836 if (n >= m || b <= 10)
837 return n;
838
839 /* Then we try a slightly larger optimal solver */
840 /*
841 int max_medium = 11;
842 init_directdr_pruning_tables();
843 for (int i = 0; i <= min(b, max_medium); i++)
844 medium_optimal_dfs(eofb, eorl, eoud, epose, eposs, eposm, ep,
845 coud, cofb, corl, cp, sol, &n, 0, 0, 0, m, i);
846 */
847
848 /* If we found at least a solution, we return */
849 if (n > 0)
850 return n;
851
852 /* Then we try a 2-step solver */
853 int max_step1 = 5000;
854 int db = 14;
855 int step1[max_step1+10][21];
856 int ss[300], step2[2][21];
857 int best = b+1;
858
859 /* TODO maybe: for now, multiple solutions can be found only using the
860 * short solver. */
861
862 int n_step1 = dr_scram_spam(scram, step1, 1, 1, 1, max_step1, min(b, db), 0);
863 for (int i = 0; i < n_step1; i++) {
864 copy_moves(scram, ss);
865 append_moves(step1[i], ss);
866 if (dr_finish_scram_spam(ss, step2, 0, 1, min(best-1,b) - len(step1[i]))) {
867 copy_moves(step1[i], sol[0]);
868 append_moves(step2[0], sol[0]);
869 best = len(sol[0]);
870 }
871 }
872
873 /* If optimal solving was not required, or we have already found an optimal
874 * solution, we return. */
875 if (best <= len(step1[n_step1-1]) || !optimal)
876 return best > b ? 0 : 1;
877
878 /* Otherwise, we go on with the optimal solver. */
879 int searched = len(step1[n_step1-1])-1;
880
881 printf("Searched up to %d moves, no solution found.\n", searched);
882 printf("Using huge pruning tables, if not loaded it might take a while.\n");
883 init_huge_pruning_tables();
884
885 for (int i = searched+1; i <= min(b, best-1); i++) {
886 if (i >= 10)
887 printf("Searching at depth %d.\n", i);
888 if (optimal_dfs(ep, cp, eofb, coud, emslices, sol, 0, 0, 0, i)) {
889 return 1;
890 }
891 }
892 return best > b ? 0 : 1;
893}
diff --git a/src/solver.h b/src/solver.h
new file mode 100644
index 0000000..7724e52
--- /dev/null
+++ b/src/solver.h
@@ -0,0 +1,13 @@
1int eo_scram_spam(int scram[], int eo_list[][21], int fb, int rl, int ud,
2 int m, int b, int niss, int h);
3int dr_scram_spam(int scram[], int dr_list[][21], int fb, int rl, int ud,
4 int m, int b, int h);
5int drfrom_scram_spam(int scram[], int dr_list[][21], int from, int fb,
6 int rl, int ud, int m, int b, int niss, int hide);
7int htr_scram_spam(int scram[], int htr_list[][21], int from,
8 int m, int b, int niss, int hide);
9int dr_corners_scram_spam(int scram[], int sol[][21], int from, int m, int b,
10 int ignore);
11int dr_finish_scram_spam(int scram[], int sol[][21], int from, int m, int b);
12int htr_finish_scram_spam(int scram[], int sol[][21], int m, int b);
13int solve_scram(int scram[], int sol[][21], int m, int b, int optimal);
diff --git a/src/utils.c b/src/utils.c
new file mode 100644
index 0000000..c672453
--- /dev/null
+++ b/src/utils.c
@@ -0,0 +1,115 @@
1#include "utils.h"
2
3/* Hardcoded factorial of small numbers (n<=12). */
4int factorial[13] = {
5 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600
6};
7
8/* swaps two integers */
9void swap(int *a, int *b) {
10 int aux = *a;
11 *a = *b;
12 *b = aux;
13}
14
15/* Converts the integer a to its representation in base b (first n digits
16 * only) and saves the result in r. */
17void int_to_digit_array(int a, int b, int n, int *r) {
18 for (int i = 0; i < n; i++) {
19 r[i] = a % b;
20 a /= b;
21 }
22}
23
24/* Converts the array of n digits a to a integer using base b. */
25int digit_array_to_int(int *a, int n, int b) {
26 int ret = 0, p = 1;
27 for (int i = 0; i < n; i++) {
28 ret += a[i] * p;
29 p *= b;
30 }
31 return ret;
32}
33
34/* Converts a permutation on [0..(n-1)] into the integer i which is the index
35 * of the permutation in the sorted list of all n! such permutations.
36 * Only works for n<=12. */
37int perm_to_index(int *a, int n) {
38 int ret = 0;
39 for (int i = 0; i < n; i++) {
40 int c = 0;
41 for (int j = i+1; j < n; j++)
42 if (a[i] > a[j])
43 c++;
44 ret += factorial[n-i-1] * c;
45 }
46 return ret;
47}
48
49/* Converts a permutation index to the actual permutation as an array
50 * (see perm_to_index) and saves the result to r. */
51void index_to_perm(int p, int n, int *r) {
52 int a[n];
53 for (int j = 0; j < n; j++)
54 a[j] = 0; /* picked elements */
55 for (int i = 0; i < n; i++) {
56 int c = 0, j = 0;
57 while (c <= p / factorial[n-i-1]) {
58 if (!a[j])
59 c++;
60 j++;
61 }
62 r[i] = j-1;
63 a[j-1] = 1;
64 p %= factorial[n-i-1];
65 }
66}
67
68/* Converts a k-element subset of a set with an element from an array of n
69 * elements, of which k are 1 (or just non-zero) and n-k are 0, to its index
70 * in the sorted list of all such subsets.
71 * Works only for n <= 12. */
72int subset_to_index(int *a, int n, int k) {
73 int ret = 0;
74 for (int i = 0; i < n; i++) {
75 if (k == n-i)
76 return ret;
77 if (a[i]) {
78 ret += factorial[n-i-1] / (factorial[k] * factorial[n-i-1-k]);
79 k--;
80 }
81 }
82 return ret;
83}
84
85/* Inverse of the above */
86void index_to_subset(int s, int n, int k, int *r) {
87 for (int i = 0; i < n; i++) {
88 if (k == n-i) {
89 for (int j = i; j < n; j++)
90 r[j] = 1;
91 return;
92 }
93 int v = factorial[n-i-1] / (factorial[k] * factorial[n-i-1-k]);
94 if (s >= v) {
95 r[i] = 1;
96 k--;
97 s -= v;
98 } else {
99 r[i] = 0;
100 }
101 }
102}
103
104/* Converts the first n-1 digits of a number to an array a of digits in base b;
105 * then adds one element to the array, so that the sum of the elements of a is
106 * zero modulo b.
107 * This is used for determing the edge orientation from an 11-bits integer or
108 * the corner orientation from a 7-trits integer. */
109void int_to_sum_zero_array(int x, int b, int n, int *a) {
110 int_to_digit_array(x, b, n-1, a);
111 int s = 0;
112 for (int i = 0; i < n - 1; i++) s = (s + a[i]) % b;
113 a[n-1] = (b - s) % b;
114}
115
diff --git a/src/utils.h b/src/utils.h
new file mode 100644
index 0000000..b24ccb2
--- /dev/null
+++ b/src/utils.h
@@ -0,0 +1,54 @@
1#define min(a,b) (((a) < (b)) ? (a) : (b))
2#define max(a,b) (((a) > (b)) ? (a) : (b))
3#define abs(a) (((a) > 0) ? (a) : (-(a)))
4
5/* Some useful constants */
6#define pow2to11 2048
7#define pow2to12 4096
8#define pow3to7 2187
9#define pow3to8 6561
10#define pow12to4 20736
11#define factorial4 24
12#define factorial6 720
13#define factorial8 40320
14#define factorial12 479001600
15#define binom12on4 495
16#define binom8on4 70
17
18void swap(int *a, int *b);
19
20/* Hardcoded factorial of small numbers (n<=12). */
21extern int factorial[13];
22
23/* Converts the integer a to its representation in base b (first n digits
24 * only) and saves the result in r. */
25void int_to_digit_array(int a, int b, int n, int *r);
26
27/* Converts the array of n digits a to a integer using base b. */
28int digit_array_to_int(int *a, int n, int b);
29
30/* Converts a permutation on [0..(n-1)] into the integer i which is the index
31 * of the permutation in the sorted list of all n! such permutations.
32 * Only works for n<=12. */
33int perm_to_index(int *a, int n);
34
35/* Converts a permutation index to the actual permutation as an array
36 * (see perm_to_index) and saves the result to r. */
37void index_to_perm(int p, int n, int *r);
38
39/* Converts a k-element subset of a set with an element from an array of n
40 * elements, of which k are 1 and n-k are 0, to its index in the sorted list
41 * of all such subsets.
42 * Works only for n <= 12. */
43int subset_to_index(int *a, int n, int k);
44
45/* Inverse of the above */
46void index_to_subset(int s, int n, int k, int *r);
47
48/* Converts the first n-1 digits of a number to an array a of digits in base b;
49 * then adds one element to the array, so that the sum of the elements of a is
50 * zero modulo b.
51 * This is used for determing the edge orientation from an 11-bits integer or
52 * the corner orientation from a 7-trits integer. */
53void int_to_sum_zero_array(int x, int b, int n, int *a);
54

Generated with cgit - Back to sebastiano.tronto.net