aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/cube.sync-conflict-20230524-181836-JOKKFPA.c614
-rw-r--r--src/cube.sync-conflict-20230524-181836-JOKKFPA.h27
-rw-r--r--src/cube.sync-conflict-20230524-182143-JOKKFPA.c614
-rw-r--r--src/cube.sync-conflict-20230524-182143-JOKKFPA.h27
-rw-r--r--src/cube.sync-conflict-20230524-182146-JOKKFPA.c614
-rw-r--r--src/cube.sync-conflict-20230524-182146-JOKKFPA.h27
6 files changed, 0 insertions, 1923 deletions
diff --git a/src/cube.sync-conflict-20230524-181836-JOKKFPA.c b/src/cube.sync-conflict-20230524-181836-JOKKFPA.c
deleted file mode 100644
index e64acca..0000000
--- a/src/cube.sync-conflict-20230524-181836-JOKKFPA.c
+++ /dev/null
@@ -1,614 +0,0 @@
1/*
2# Cube representation, moves, transformations and indexing
3
4## String description
5
6The functions readcube() and writecube() use the following format.
7Each edge is represented by two letters denoting the sides it belongs to
8and one number denoting its orientation (0 oriented, 1 mis-oriented).
9Similarly, each corner is represented by three letters and a number
10(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
11Edge orientation is relative to the F / B axis, corner orientation is
12relative to the U / D axis.
13
14The correct order of the pieces is the same as that defined in the
15section "Internal cube representation", except that pieces are read
16left-to-right. Pieces are divided by slices, so the ordering is not the
17most intuitive, but it is more convenient for the internal representation.
18
19Whitespaces between pieces are ignored when reading the cube, and a
20single whitespace character is added between pieces when writing.
21
22For example, the solved cube looks like this:
23
24UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
25
26The cube after the moves R'U'F looks like this:
27
28FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0 UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
29
30More formats might be supported in the future.
31
32## Internal cube representation
33
34The cube_t data structure implemented in this file is designed to
35efficiently perform common operations on a 3x3x3 Rubik's cube when
36solving it with an iterative-deepening DFS search. It is not the most
37general, complete, easy to read or compact one. Since the cube can
38be trivially reoriented before the search, we only encode permutations
39of the cube that keep the center pieces in a fixed position (that is,
40we do not encode the position of the centers).
41
42The cube state is encoded in two 64-bit integers, one for edges and one
43for centers. We explain how edges are encoded first, and the highlight
44the few differences with corners afterwards.
45
46For encoding edges, only the 60 least-significant bits are used. Each
47edge described by 5 bits. The position of a 5-bit block in the 64-bit
48integer determine the position of the edge piece in the cube, according
49to the following table (least-significant bits on the right):
50
5155-59 50-54 45-49 40-44 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
52 BR BL FL FR DR DL UL UR DF DB UB UF
53ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee
54
55For each edge, the 4 least-significant bits ('ssee' in the table)
56determine the piece. The two bits marked with 'ss' determine the internal
57slice the piece belongs to, i.e. they are either '00' for M, '01' for
58S or '10' for E. The other two bits (marked with 'ee') determine the
59actual edge piece among the 4 in the same slice, and they are assigned
60somewhat arbitarily. Using this representation and the ordering defined
61in the table above, the edges are correctly permuted when these 4 bits
62for each represent the numbers 0 to 11 in the correct order.
63
64The last bit determines the orientation. The orientation of an edge
65depends on its position, and it is defined being 0 if the edge can be
66moved to its place in the solved orientation by permutations in the
67subgroup <U, D, R, L, F2, B2>.
68
69Corners are encoded in the 48 least-significant bits, and are described
70by 6 bits each, their position being defined by the following table:
71
72 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
73 DBL DFL UBR UFL DBR DFL UBL UFR
74oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc
75
76The bit marked with an 'x' describes the axis the corner belongs to.
77The 0 axis consists of the corners UFR, UBL, DFL and DBR, and the other
78four corners form the axis marked with 1. Then two bits are needed to
79identify the corner among the four of the same axis. The last three bits
80determine the orientation, where one corner is defined to be oriented
81(marked with '000') if its top or bottom sticker faces the top or bottom
82side. A corner a clockwise turn away from being oriented, thus requiring
83a counter-clockwise turn to be oriented correctly, is marked with '001',
84and a corner a counter-clockwise turn away is marked with '010'. The most
85significant bit is not used to determine the corner orientation, but it
86must always be set to '0' to simplify the moving operations (see below).
87
88## Basic moves
89
90The 18 basic moves of the cube could be performed by applying a suitable
91general permutation (see below), but they have instead been manually
92implemented with a few simple operations each, to improve performance.
93
94For each move we first permute the pieces. This amounts to shifting
95around 4 blocks of bits for edges and 4 for corners. Since in some cases
96adjacent pieces on the cube are also adjacent in the bit representation we
97use, we can save some operations by shifting multiple blocks together.
98For example, for the move U for edges we shift a block of 15 bits 5
99positions to the left and a block of 5 bits 15 positions to the right.
100
101There are some moves that change the orientation of the pieces. Namely,
102the moves F, F', B and B' change the orientation of the edges and those
103moves as well as R, R', L and L' change the orientation of the corners.
104Edge orientation is easy to address: we simply xor the edge representation
105by a bit mask with zeroes everywhere except for the 4 edges that need
106to be flipped (i.e. the ones on the twisted face).
107
108Corner orientation is harder to reproduce efficiently working only with
109bitwise operations, as it involves performing operations modulo 3.
110However, with the help of the extra bit we reserved, we are able to
111do this using only two additions and 3 bitwise operations, without
112any multiplication, division or modulo operation. The trick is
113to use the following formula to sum two numbers x, y in {0,1,2}:
114
115 ((x+y) + (x+y+1)/4) % 4
116
117The thrid bit is needed because x+y and x+y+1 can exceed 3.
118See below (in the code) for the details.
119
120## Inverting the cube
121
122TODO
123
124## Transformations (conjugations by full-cube rotations)
125
126TODO
127
128## Indexing
129
130TODO - subgroup description etc
131
132Ideas for pruning (for another file?):
133- Use corner separation + CO as main coordinate (~150k states)
134 - for huge tables, htr corners can be used (6 times larger)
135- Symmetry table, one entry or each main coordinate value with the
136 following info:
137 - index of the corresponding main symcoord (13 bits)
138 - transtorep (6 bits)
139 - base value for pruning table (5 bits, probably 4)
140 - pruning value for only main coord, i.e. fallback (4 bits)
141- To get a full coord for the cube:
142 - get first coord c, get the transtorep
143 - transform edges with transtorep
144 - get second coordinate e
145 - return c * MAXE + e
146 - This is still too big, so divide by a power of 2 to get the hashed index
147 - second coordinate: ep always, + varible number of eo bit (0 to 11)
148- Generate table:
149 - first probe for base value:
150 - solve coord using fallback table for pruning for 10k random states or so
151 - loop over all possible values (even if going for smaller table)
152 - with inverse-index strategy or what?
153 - use 1 bit per entry (more than base value or not)
154*/
155
156#include <stdbool.h>
157#include <stdint.h>
158#include <string.h>
159
160#ifdef DEBUG
161#include <stdio.h>
162#endif
163
164#include "cube.h"
165
166#define _error 0xFFFFFFFF
167
168#define _esize 5ULL
169#define _eoblock 0x10ULL /* 10000 */
170#define _epblock 0x0FULL /* 01111 */
171#define _eblock 0x1FULL /* 11111 */
172
173#define _csize 6ULL
174#define _coblock 0x18ULL /* 011000 */
175#define _cpblock 0x07ULL /* 000111 */
176#define _cblock 0x3FULL /* 111111 */
177
178#define _edge_uf 0ULL /* 00 00 */
179#define _edge_ub 1ULL /* 00 01 */
180#define _edge_db 2ULL /* 00 10 */
181#define _edge_df 3ULL /* 00 11 */
182#define _edge_ur 4ULL /* 01 00 */
183#define _edge_ul 5ULL /* 01 01 */
184#define _edge_dl 6ULL /* 01 10 */
185#define _edge_dr 7ULL /* 01 11 */
186#define _edge_fr 8ULL /* 10 00 */
187#define _edge_fl 9ULL /* 10 01 */
188#define _edge_bl 10ULL /* 10 10 */
189#define _edge_br 11ULL /* 10 11 */
190
191#define _corner_ufr 0ULL /* 0 00 */
192#define _corner_ubl 1ULL /* 0 01 */
193#define _corner_dfl 2ULL /* 0 10 */
194#define _corner_dbr 3ULL /* 0 11 */
195#define _corner_ufl 4ULL /* 1 00 */
196#define _corner_ubr 5ULL /* 1 01 */
197#define _corner_dfr 6ULL /* 1 10 */
198#define _corner_dbl 7ULL /* 1 11 */
199
200#define ESHIFT(i) ((i) * _esize)
201#define EOSHIFT(i) (4ULL + (i) * _esize)
202#define EMASK(i) (_eblock << ESHIFT(i))
203#define EOMASK(i) (_eoblock << ESHIFT(i))
204#define EPMASK(i) (_epblock << ESHIFT(i))
205#define ESOLVED(ee) (_edge_##ee << (_edge_##ee * _esize))
206#define EDGEAT(e, i) (((e) & EMASK(i)) >> ESHIFT(i))
207#define EOAT(e, i) (((e) & EOMASK(i)) >> EOSHIFT(i))
208#define EPAT(e, i) (((e) & EPMASK(i)) >> ESHIFT(i))
209
210#define CSHIFT(i) ((i) * _csize)
211#define COSHIFT(i) (3ULL + (i) * _csize)
212#define CMASK(i) (_cblock << CSHIFT(i))
213#define COMASK(i) (_coblock << CSHIFT(i))
214#define CPMASK(i) (_cpblock << CSHIFT(i))
215#define CSOLVED(ccc) (_corner_##ccc << (_corner_##ccc * _csize))
216#define CORNERAT(c, i) (((c) & CMASK(i)) >> CSHIFT(i))
217#define COAT(c, i) (((c) & COMASK(i)) >> COSHIFT(i))
218#define CPAT(c, i) (((c) & CPMASK(i)) >> CSHIFT(i))
219
220#define _emask_u (EMASK(uf) | EMASK(ul) | EMASK(ub) | EMASK(ur))
221#define _emask_d (EMASK(df) | EMASK(dl) | EMASK(db) | EMASK(dr))
222#define _emask_r (EMASK(ur) | EMASK(dr) | EMASK(fr) | EMASK(br))
223#define _emask_l (EMASK(ul) | EMASK(dl) | EMASK(fl) | EMASK(bl))
224#define _emask_f (EMASK(uf) | EMASK(df) | EMASK(fr) | EMASK(fl))
225#define _emask_b (EMASK(ub) | EMASK(db) | EMASK(br) | EMASK(bl))
226
227#define _cmask_u (CMASK(ufr) | CMASK(ufl) | CMASK(ubl) | CMASK(ubr))
228#define _cmask_d (CMASK(dfr) | CMASK(dfl) | CMASK(dbl) | CMASK(dbr))
229#define _cmask_r (CMASK(ufr) | CMASK(dfr) | CMASK(ubr) | CMASK(dbr))
230#define _cmask_l (CMASK(ufl) | CMASK(dfl) | CMASK(ubl) | CMASK(dbl))
231#define _cmask_f (CMASK(ufr) | CMASK(ufl) | CMASK(dfr) | CMASK(dfl))
232#define _cmask_b (CMASK(ubr) | CMASK(ubl) | CMASK(dbr) | CMASK(dbl))
233
234#define _eomask (EOMASK(uf) | EOMASK(ul) | EOMASK(ub) | EOMASK(ur) \
235 EOMASK(df) | EOMASK(dl) | EOMASK(db) | EOMASK(dr) \
236 EOMASK(fr) | EOMASK(fl) | EOMASK(bl) | EOMASK(br))
237#define _comask (COMASK(ufr) | COMASK(ufl) | COMASK(ubl) | COMASK(ubr) \
238 COMASK(dfr) | COMASK(dfl) | COMASK(dbl) | COMASK(dbr))
239
240static uint64_t permsign(uint64_t *, int);
241static uint64_t readep(char *);
242static uint64_t readeo(char *);
243static uint64_t readcp(char *);
244static uint64_t readco(char *);
245static uint64_t readmove(char);
246static uint64_t readmodifier(char);
247
248static char *edgestr[] = {
249 [_edge_uf] = "UF",
250 [_edge_ub] = "UB",
251 [_edge_db] = "DB",
252 [_edge_df] = "DF",
253 [_edge_ur] = "UR",
254 [_edge_ul] = "UL",
255 [_edge_dl] = "DL",
256 [_edge_dr] = "DR",
257 [_edge_fr] = "FR",
258 [_edge_fl] = "FL",
259 [_edge_bl] = "BL",
260 [_edge_br] = "BR"
261};
262static char *cornerstr[] = {
263 [_corner_ufr] = "UFR",
264 [_corner_ubl] = "UBL",
265 [_corner_dfl] = "DFL",
266 [_corner_dbr] = "DBR",
267 [_corner_ufl] = "UFL",
268 [_corner_ubr] = "UBR",
269 [_corner_dfr] = "DFR",
270 [_corner_dbl] = "DBL"
271};
272static char *movestr[] = {
273 [U] = "U", [U2] = "U2", [U3] = "U'",
274 [D] = "D", [D2] = "D2", [D3] = "D'",
275 [R] = "R", [R2] = "R2", [R3] = "R'",
276 [L] = "L", [L2] = "L2", [L3] = "L'",
277 [F] = "F", [F2] = "F2", [F3] = "F'",
278 [B] = "B", [B2] = "B2", [B3] = "B'",
279};
280
281cube_t solvedcube = {
282 .e = ESOLVED(uf) | ESOLVED(ul) | ESOLVED(ub) | ESOLVED(ur) |
283 ESOLVED(df) | ESOLVED(dl) | ESOLVED(db) | ESOLVED(dr) |
284 ESOLVED(fr) | ESOLVED(fl) | ESOLVED(bl) | ESOLVED(br),
285 .c = CSOLVED(ufr) | CSOLVED(ufl) | CSOLVED(ubl) | CSOLVED(ubr) |
286 CSOLVED(dfr) | CSOLVED(dfl) | CSOLVED(dbl) | CSOLVED(dbr),
287};
288cube_t errorcube = { .e = _error, .c = _error };
289
290
291static uint64_t
292permsign(uint64_t *a, int n)
293{
294 int i, j;
295 uint64_t ret;
296
297 ret = 0;
298
299 for (i = 0; i < n; i++)
300 for (j = i+1; j < n; j++)
301 ret += a[i] > a[j] ? 1 : 0;
302
303 return ret % 2;
304}
305
306bool
307isconsistent(cube_t cube)
308{
309 uint64_t p[12], sum;
310 bool found[12];
311 int i;
312
313 sum = 0;
314
315 /* Check for EP consistency */
316 for (i = 0; i < 12; i++)
317 found[i] = false;
318 for (i = 0; i < 12; i++) {
319 p[i] = EPAT(cube.e, i);
320 found[p[i]] = true;
321 }
322 for (i = 0; i < 12; i++)
323 if (!found[i])
324 return false;
325 sum = permsign(p, 12);
326
327 /* Check for CP consistency */
328 for (i = 0; i < 8; i++)
329 found[i] = false;
330 for (i = 0; i < 8; i++) {
331 p[i] = CPAT(cube.c, i);
332 found[p[i]] = true;
333 }
334 for (i = 0; i < 8; i++)
335 if (!found[i])
336 return false;
337 sum += permsign(p, 8);
338
339 /* Check permutation parity */
340 if (sum % 2 != 0)
341 return false;
342
343 /* Check for EO parity */
344 for (i = 0, sum = 0; i < 12; i++)
345 sum += EOAT(cube.e, i);
346 if (sum % 2 != 0)
347 return false;
348
349 /* Check for CO parity */
350 for (i = 0, sum = 0; i < 8; i++)
351 sum += COAT(cube.c, i);
352 if (sum % 3 != 0)
353 return false;
354
355 /* Check that CO extra bit is zero */
356 for (i = 0; i < 8; i++)
357 if (cube.c & (1ULL << (5 + i * _csize)))
358 return false;
359
360 return true;
361}
362
363bool
364issolved(cube_t cube)
365{
366 return cube.c == solvedcube.c && cube.e == solvedcube.e;
367}
368
369
370static uint64_t
371readep(char *str)
372{
373 if (!strncmp(str, "UF", 2))
374 return _edge_uf;
375 if (!strncmp(str, "UL", 2))
376 return _edge_ul;
377 if (!strncmp(str, "UB", 2))
378 return _edge_ub;
379 if (!strncmp(str, "UR", 2))
380 return _edge_ur;
381 if (!strncmp(str, "DF", 2))
382 return _edge_df;
383 if (!strncmp(str, "DL", 2))
384 return _edge_dl;
385 if (!strncmp(str, "DB", 2))
386 return _edge_db;
387 if (!strncmp(str, "DR", 2))
388 return _edge_dr;
389 if (!strncmp(str, "FR", 2))
390 return _edge_fr;
391 if (!strncmp(str, "FL", 2))
392 return _edge_fl;
393 if (!strncmp(str, "BL", 2))
394 return _edge_bl;
395 if (!strncmp(str, "BR", 2))
396 return _edge_br;
397
398 return _error;
399}
400
401static uint64_t
402readeo(char *str)
403{
404 if (*str == '0')
405 return 0ULL;
406 if (*str == '1')
407 return 1ULL;
408
409 return _error;
410}
411
412static uint64_t
413readcp(char *str)
414{
415 if (!strncmp(str, "UFR", 3) || !strncmp(str, "URF", 3))
416 return _corner_ufr;
417 if (!strncmp(str, "UFL", 3) || !strncmp(str, "ULF", 3))
418 return _corner_ufl;
419 if (!strncmp(str, "UBL", 3) || !strncmp(str, "ULB", 3))
420 return _corner_ubl;
421 if (!strncmp(str, "UBR", 3) || !strncmp(str, "URB", 3))
422 return _corner_ubr;
423 if (!strncmp(str, "DFR", 3) || !strncmp(str, "DRF", 3))
424 return _corner_dfr;
425 if (!strncmp(str, "DFL", 3) || !strncmp(str, "DLF", 3))
426 return _corner_dfl;
427 if (!strncmp(str, "DBL", 3) || !strncmp(str, "DLB", 3))
428 return _corner_dbl;
429 if (!strncmp(str, "DBR", 3) || !strncmp(str, "DRB", 3))
430 return _corner_dbr;
431
432 return _error;
433}
434
435static uint64_t
436readco(char *str)
437{
438 if (*str == '0')
439 return 0ULL;
440 if (*str == '1')
441 return 1ULL;
442 if (*str == '2')
443 return 2ULL;
444
445 return _error;
446}
447
448cube_t
449readcube(char *buf)
450{
451 int i;
452 uint64_t piece, orient;
453 cube_t ret = {0};
454 char *b = buf;
455
456 for (i = 0; i < 12; i++) {
457 while (*b == ' ' || *b == '\t' || *b == '\n')
458 b++;
459 if ((piece = readep(b)) == _error)
460 goto readcube_error;
461 b += 2;
462 if ((orient = readeo(b)) == _error)
463 goto readcube_error;
464 b++;
465 ret.e |= (piece << ESHIFT(i)) | (orient << EOSHIFT(i));
466 }
467 for (i = 0; i < 8; i++) {
468 while (*b == ' ' || *b == '\t' || *b == '\n')
469 b++;
470 if ((piece = readcp(b)) == _error)
471 goto readcube_error;
472 b += 3;
473 if ((orient = readco(b)) == _error)
474 goto readcube_error;
475 b++;
476 ret.c |= (piece << CSHIFT(i)) | (orient << COSHIFT(i));
477 }
478
479 return ret;
480
481readcube_error:
482 return errorcube;
483}
484
485void
486writecube(cube_t cube, char *buf)
487{
488 char *errormsg;
489 uint64_t piece;
490 size_t len;
491 int i;
492
493 if (!isconsistent(cube)) {
494 errormsg = "ERROR: cannot write inconsistent cube";
495 goto writecube_error;
496 }
497
498 for (i = 0; i < 12; i++) {
499 piece = EPAT(cube.e, i);
500 buf[4*i ] = edgestr[piece][0];
501 buf[4*i + 1] = edgestr[piece][1];
502 buf[4*i + 2] = EOAT(cube.e, i) + '0';
503 buf[4*i + 3] = ' ';
504 }
505 for (i = 0; i < 8; i++) {
506 piece = CPAT(cube.c, i);
507 buf[48 + 5*i ] = cornerstr[piece][0];
508 buf[48 + 5*i + 1] = cornerstr[piece][1];
509 buf[48 + 5*i + 2] = cornerstr[piece][2];
510 buf[48 + 5*i + 3] = COAT(cube.c, i) + '0';
511 buf[48 + 5*i + 4] = ' ';
512 }
513
514 buf[48+39] = '\0';
515
516 return;
517
518writecube_error:
519 len = strlen(errormsg);
520 strcpy(buf, errormsg);
521 buf[len] = '\n';
522 buf[len+1] = '\0';
523}
524
525
526static uint64_t
527readmove(char c)
528{
529 switch (c) {
530 case 'U':
531 return U;
532 case 'D':
533 return D;
534 case 'R':
535 return R;
536 case 'L':
537 return L;
538 case 'F':
539 return F;
540 case 'B':
541 return B;
542 default:
543 return _error;
544 }
545}
546
547static uint64_t
548readmodifier(char c)
549{
550 switch (c) {
551 case '1': /* Fallthrough */
552 case '2': /* Fallthrough */
553 case '3':
554 return c - '0' - 1;
555 case '\'':
556 return 2;
557 default:
558 return 0;
559 }
560}
561
562int
563readmoves(char *buf, move_t *m)
564{
565 int n;
566 uint64_t r;
567 char *b;
568
569 for (b = buf, n = 0; *b != '\0'; b++) {
570 while (*b == ' ' || *b == '\t' || *b == '\n')
571 b++;
572 if ((r = readmove(*b)) == _error)
573 return -1;
574 m[n] = (move_t)r;
575 if ((r = readmodifier(*(b+1))) != 0) {
576 b++;
577 m[n] += r;
578 }
579 n++;
580 }
581
582 return n;
583}
584
585void
586writemoves(move_t *m, int n, char *buf)
587{
588 int i;
589 char *b, *s;
590
591 for (i = 0, b = buf; i < n; i++, b++) {
592 s = movestr[m[i]];
593 strcpy(b, s);
594 b += strlen(s);
595 *b = ' ';
596 }
597 *b = '\0';
598}
599
600
601cube_t
602move(move_t m, cube_t c)
603{
604 /* TODO - not implemented yet */
605
606 cube_t ret = {0};
607
608 switch (m) {
609 case U:
610 return ret;
611 default:
612 return ret;
613 }
614}
diff --git a/src/cube.sync-conflict-20230524-181836-JOKKFPA.h b/src/cube.sync-conflict-20230524-181836-JOKKFPA.h
deleted file mode 100644
index 2763d16..0000000
--- a/src/cube.sync-conflict-20230524-181836-JOKKFPA.h
+++ /dev/null
@@ -1,27 +0,0 @@
1typedef enum {
2 U, U2, U3, D, D2, D3,
3 R, R2, R3, L, L2, L3,
4 F, F2, F3, B, B2, B3
5} move_t;
6typedef struct {
7 uint64_t e;
8 uint64_t c;
9} cube_t;
10
11extern cube_t solvedcube;
12extern cube_t errorcube;
13
14bool isconsistent(cube_t);
15bool issolved(cube_t);
16
17cube_t readcube(char *);
18void writecube(cube_t, char *);
19
20int readmoves(char *, move_t *);
21void writemoves(move_t *, int, char *);
22
23/*
24cube_t move(move_t, cube_t);
25cube_t inverse(cube_t);
26
27*/
diff --git a/src/cube.sync-conflict-20230524-182143-JOKKFPA.c b/src/cube.sync-conflict-20230524-182143-JOKKFPA.c
deleted file mode 100644
index e64acca..0000000
--- a/src/cube.sync-conflict-20230524-182143-JOKKFPA.c
+++ /dev/null
@@ -1,614 +0,0 @@
1/*
2# Cube representation, moves, transformations and indexing
3
4## String description
5
6The functions readcube() and writecube() use the following format.
7Each edge is represented by two letters denoting the sides it belongs to
8and one number denoting its orientation (0 oriented, 1 mis-oriented).
9Similarly, each corner is represented by three letters and a number
10(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
11Edge orientation is relative to the F / B axis, corner orientation is
12relative to the U / D axis.
13
14The correct order of the pieces is the same as that defined in the
15section "Internal cube representation", except that pieces are read
16left-to-right. Pieces are divided by slices, so the ordering is not the
17most intuitive, but it is more convenient for the internal representation.
18
19Whitespaces between pieces are ignored when reading the cube, and a
20single whitespace character is added between pieces when writing.
21
22For example, the solved cube looks like this:
23
24UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
25
26The cube after the moves R'U'F looks like this:
27
28FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0 UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
29
30More formats might be supported in the future.
31
32## Internal cube representation
33
34The cube_t data structure implemented in this file is designed to
35efficiently perform common operations on a 3x3x3 Rubik's cube when
36solving it with an iterative-deepening DFS search. It is not the most
37general, complete, easy to read or compact one. Since the cube can
38be trivially reoriented before the search, we only encode permutations
39of the cube that keep the center pieces in a fixed position (that is,
40we do not encode the position of the centers).
41
42The cube state is encoded in two 64-bit integers, one for edges and one
43for centers. We explain how edges are encoded first, and the highlight
44the few differences with corners afterwards.
45
46For encoding edges, only the 60 least-significant bits are used. Each
47edge described by 5 bits. The position of a 5-bit block in the 64-bit
48integer determine the position of the edge piece in the cube, according
49to the following table (least-significant bits on the right):
50
5155-59 50-54 45-49 40-44 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
52 BR BL FL FR DR DL UL UR DF DB UB UF
53ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee
54
55For each edge, the 4 least-significant bits ('ssee' in the table)
56determine the piece. The two bits marked with 'ss' determine the internal
57slice the piece belongs to, i.e. they are either '00' for M, '01' for
58S or '10' for E. The other two bits (marked with 'ee') determine the
59actual edge piece among the 4 in the same slice, and they are assigned
60somewhat arbitarily. Using this representation and the ordering defined
61in the table above, the edges are correctly permuted when these 4 bits
62for each represent the numbers 0 to 11 in the correct order.
63
64The last bit determines the orientation. The orientation of an edge
65depends on its position, and it is defined being 0 if the edge can be
66moved to its place in the solved orientation by permutations in the
67subgroup <U, D, R, L, F2, B2>.
68
69Corners are encoded in the 48 least-significant bits, and are described
70by 6 bits each, their position being defined by the following table:
71
72 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
73 DBL DFL UBR UFL DBR DFL UBL UFR
74oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc
75
76The bit marked with an 'x' describes the axis the corner belongs to.
77The 0 axis consists of the corners UFR, UBL, DFL and DBR, and the other
78four corners form the axis marked with 1. Then two bits are needed to
79identify the corner among the four of the same axis. The last three bits
80determine the orientation, where one corner is defined to be oriented
81(marked with '000') if its top or bottom sticker faces the top or bottom
82side. A corner a clockwise turn away from being oriented, thus requiring
83a counter-clockwise turn to be oriented correctly, is marked with '001',
84and a corner a counter-clockwise turn away is marked with '010'. The most
85significant bit is not used to determine the corner orientation, but it
86must always be set to '0' to simplify the moving operations (see below).
87
88## Basic moves
89
90The 18 basic moves of the cube could be performed by applying a suitable
91general permutation (see below), but they have instead been manually
92implemented with a few simple operations each, to improve performance.
93
94For each move we first permute the pieces. This amounts to shifting
95around 4 blocks of bits for edges and 4 for corners. Since in some cases
96adjacent pieces on the cube are also adjacent in the bit representation we
97use, we can save some operations by shifting multiple blocks together.
98For example, for the move U for edges we shift a block of 15 bits 5
99positions to the left and a block of 5 bits 15 positions to the right.
100
101There are some moves that change the orientation of the pieces. Namely,
102the moves F, F', B and B' change the orientation of the edges and those
103moves as well as R, R', L and L' change the orientation of the corners.
104Edge orientation is easy to address: we simply xor the edge representation
105by a bit mask with zeroes everywhere except for the 4 edges that need
106to be flipped (i.e. the ones on the twisted face).
107
108Corner orientation is harder to reproduce efficiently working only with
109bitwise operations, as it involves performing operations modulo 3.
110However, with the help of the extra bit we reserved, we are able to
111do this using only two additions and 3 bitwise operations, without
112any multiplication, division or modulo operation. The trick is
113to use the following formula to sum two numbers x, y in {0,1,2}:
114
115 ((x+y) + (x+y+1)/4) % 4
116
117The thrid bit is needed because x+y and x+y+1 can exceed 3.
118See below (in the code) for the details.
119
120## Inverting the cube
121
122TODO
123
124## Transformations (conjugations by full-cube rotations)
125
126TODO
127
128## Indexing
129
130TODO - subgroup description etc
131
132Ideas for pruning (for another file?):
133- Use corner separation + CO as main coordinate (~150k states)
134 - for huge tables, htr corners can be used (6 times larger)
135- Symmetry table, one entry or each main coordinate value with the
136 following info:
137 - index of the corresponding main symcoord (13 bits)
138 - transtorep (6 bits)
139 - base value for pruning table (5 bits, probably 4)
140 - pruning value for only main coord, i.e. fallback (4 bits)
141- To get a full coord for the cube:
142 - get first coord c, get the transtorep
143 - transform edges with transtorep
144 - get second coordinate e
145 - return c * MAXE + e
146 - This is still too big, so divide by a power of 2 to get the hashed index
147 - second coordinate: ep always, + varible number of eo bit (0 to 11)
148- Generate table:
149 - first probe for base value:
150 - solve coord using fallback table for pruning for 10k random states or so
151 - loop over all possible values (even if going for smaller table)
152 - with inverse-index strategy or what?
153 - use 1 bit per entry (more than base value or not)
154*/
155
156#include <stdbool.h>
157#include <stdint.h>
158#include <string.h>
159
160#ifdef DEBUG
161#include <stdio.h>
162#endif
163
164#include "cube.h"
165
166#define _error 0xFFFFFFFF
167
168#define _esize 5ULL
169#define _eoblock 0x10ULL /* 10000 */
170#define _epblock 0x0FULL /* 01111 */
171#define _eblock 0x1FULL /* 11111 */
172
173#define _csize 6ULL
174#define _coblock 0x18ULL /* 011000 */
175#define _cpblock 0x07ULL /* 000111 */
176#define _cblock 0x3FULL /* 111111 */
177
178#define _edge_uf 0ULL /* 00 00 */
179#define _edge_ub 1ULL /* 00 01 */
180#define _edge_db 2ULL /* 00 10 */
181#define _edge_df 3ULL /* 00 11 */
182#define _edge_ur 4ULL /* 01 00 */
183#define _edge_ul 5ULL /* 01 01 */
184#define _edge_dl 6ULL /* 01 10 */
185#define _edge_dr 7ULL /* 01 11 */
186#define _edge_fr 8ULL /* 10 00 */
187#define _edge_fl 9ULL /* 10 01 */
188#define _edge_bl 10ULL /* 10 10 */
189#define _edge_br 11ULL /* 10 11 */
190
191#define _corner_ufr 0ULL /* 0 00 */
192#define _corner_ubl 1ULL /* 0 01 */
193#define _corner_dfl 2ULL /* 0 10 */
194#define _corner_dbr 3ULL /* 0 11 */
195#define _corner_ufl 4ULL /* 1 00 */
196#define _corner_ubr 5ULL /* 1 01 */
197#define _corner_dfr 6ULL /* 1 10 */
198#define _corner_dbl 7ULL /* 1 11 */
199
200#define ESHIFT(i) ((i) * _esize)
201#define EOSHIFT(i) (4ULL + (i) * _esize)
202#define EMASK(i) (_eblock << ESHIFT(i))
203#define EOMASK(i) (_eoblock << ESHIFT(i))
204#define EPMASK(i) (_epblock << ESHIFT(i))
205#define ESOLVED(ee) (_edge_##ee << (_edge_##ee * _esize))
206#define EDGEAT(e, i) (((e) & EMASK(i)) >> ESHIFT(i))
207#define EOAT(e, i) (((e) & EOMASK(i)) >> EOSHIFT(i))
208#define EPAT(e, i) (((e) & EPMASK(i)) >> ESHIFT(i))
209
210#define CSHIFT(i) ((i) * _csize)
211#define COSHIFT(i) (3ULL + (i) * _csize)
212#define CMASK(i) (_cblock << CSHIFT(i))
213#define COMASK(i) (_coblock << CSHIFT(i))
214#define CPMASK(i) (_cpblock << CSHIFT(i))
215#define CSOLVED(ccc) (_corner_##ccc << (_corner_##ccc * _csize))
216#define CORNERAT(c, i) (((c) & CMASK(i)) >> CSHIFT(i))
217#define COAT(c, i) (((c) & COMASK(i)) >> COSHIFT(i))
218#define CPAT(c, i) (((c) & CPMASK(i)) >> CSHIFT(i))
219
220#define _emask_u (EMASK(uf) | EMASK(ul) | EMASK(ub) | EMASK(ur))
221#define _emask_d (EMASK(df) | EMASK(dl) | EMASK(db) | EMASK(dr))
222#define _emask_r (EMASK(ur) | EMASK(dr) | EMASK(fr) | EMASK(br))
223#define _emask_l (EMASK(ul) | EMASK(dl) | EMASK(fl) | EMASK(bl))
224#define _emask_f (EMASK(uf) | EMASK(df) | EMASK(fr) | EMASK(fl))
225#define _emask_b (EMASK(ub) | EMASK(db) | EMASK(br) | EMASK(bl))
226
227#define _cmask_u (CMASK(ufr) | CMASK(ufl) | CMASK(ubl) | CMASK(ubr))
228#define _cmask_d (CMASK(dfr) | CMASK(dfl) | CMASK(dbl) | CMASK(dbr))
229#define _cmask_r (CMASK(ufr) | CMASK(dfr) | CMASK(ubr) | CMASK(dbr))
230#define _cmask_l (CMASK(ufl) | CMASK(dfl) | CMASK(ubl) | CMASK(dbl))
231#define _cmask_f (CMASK(ufr) | CMASK(ufl) | CMASK(dfr) | CMASK(dfl))
232#define _cmask_b (CMASK(ubr) | CMASK(ubl) | CMASK(dbr) | CMASK(dbl))
233
234#define _eomask (EOMASK(uf) | EOMASK(ul) | EOMASK(ub) | EOMASK(ur) \
235 EOMASK(df) | EOMASK(dl) | EOMASK(db) | EOMASK(dr) \
236 EOMASK(fr) | EOMASK(fl) | EOMASK(bl) | EOMASK(br))
237#define _comask (COMASK(ufr) | COMASK(ufl) | COMASK(ubl) | COMASK(ubr) \
238 COMASK(dfr) | COMASK(dfl) | COMASK(dbl) | COMASK(dbr))
239
240static uint64_t permsign(uint64_t *, int);
241static uint64_t readep(char *);
242static uint64_t readeo(char *);
243static uint64_t readcp(char *);
244static uint64_t readco(char *);
245static uint64_t readmove(char);
246static uint64_t readmodifier(char);
247
248static char *edgestr[] = {
249 [_edge_uf] = "UF",
250 [_edge_ub] = "UB",
251 [_edge_db] = "DB",
252 [_edge_df] = "DF",
253 [_edge_ur] = "UR",
254 [_edge_ul] = "UL",
255 [_edge_dl] = "DL",
256 [_edge_dr] = "DR",
257 [_edge_fr] = "FR",
258 [_edge_fl] = "FL",
259 [_edge_bl] = "BL",
260 [_edge_br] = "BR"
261};
262static char *cornerstr[] = {
263 [_corner_ufr] = "UFR",
264 [_corner_ubl] = "UBL",
265 [_corner_dfl] = "DFL",
266 [_corner_dbr] = "DBR",
267 [_corner_ufl] = "UFL",
268 [_corner_ubr] = "UBR",
269 [_corner_dfr] = "DFR",
270 [_corner_dbl] = "DBL"
271};
272static char *movestr[] = {
273 [U] = "U", [U2] = "U2", [U3] = "U'",
274 [D] = "D", [D2] = "D2", [D3] = "D'",
275 [R] = "R", [R2] = "R2", [R3] = "R'",
276 [L] = "L", [L2] = "L2", [L3] = "L'",
277 [F] = "F", [F2] = "F2", [F3] = "F'",
278 [B] = "B", [B2] = "B2", [B3] = "B'",
279};
280
281cube_t solvedcube = {
282 .e = ESOLVED(uf) | ESOLVED(ul) | ESOLVED(ub) | ESOLVED(ur) |
283 ESOLVED(df) | ESOLVED(dl) | ESOLVED(db) | ESOLVED(dr) |
284 ESOLVED(fr) | ESOLVED(fl) | ESOLVED(bl) | ESOLVED(br),
285 .c = CSOLVED(ufr) | CSOLVED(ufl) | CSOLVED(ubl) | CSOLVED(ubr) |
286 CSOLVED(dfr) | CSOLVED(dfl) | CSOLVED(dbl) | CSOLVED(dbr),
287};
288cube_t errorcube = { .e = _error, .c = _error };
289
290
291static uint64_t
292permsign(uint64_t *a, int n)
293{
294 int i, j;
295 uint64_t ret;
296
297 ret = 0;
298
299 for (i = 0; i < n; i++)
300 for (j = i+1; j < n; j++)
301 ret += a[i] > a[j] ? 1 : 0;
302
303 return ret % 2;
304}
305
306bool
307isconsistent(cube_t cube)
308{
309 uint64_t p[12], sum;
310 bool found[12];
311 int i;
312
313 sum = 0;
314
315 /* Check for EP consistency */
316 for (i = 0; i < 12; i++)
317 found[i] = false;
318 for (i = 0; i < 12; i++) {
319 p[i] = EPAT(cube.e, i);
320 found[p[i]] = true;
321 }
322 for (i = 0; i < 12; i++)
323 if (!found[i])
324 return false;
325 sum = permsign(p, 12);
326
327 /* Check for CP consistency */
328 for (i = 0; i < 8; i++)
329 found[i] = false;
330 for (i = 0; i < 8; i++) {
331 p[i] = CPAT(cube.c, i);
332 found[p[i]] = true;
333 }
334 for (i = 0; i < 8; i++)
335 if (!found[i])
336 return false;
337 sum += permsign(p, 8);
338
339 /* Check permutation parity */
340 if (sum % 2 != 0)
341 return false;
342
343 /* Check for EO parity */
344 for (i = 0, sum = 0; i < 12; i++)
345 sum += EOAT(cube.e, i);
346 if (sum % 2 != 0)
347 return false;
348
349 /* Check for CO parity */
350 for (i = 0, sum = 0; i < 8; i++)
351 sum += COAT(cube.c, i);
352 if (sum % 3 != 0)
353 return false;
354
355 /* Check that CO extra bit is zero */
356 for (i = 0; i < 8; i++)
357 if (cube.c & (1ULL << (5 + i * _csize)))
358 return false;
359
360 return true;
361}
362
363bool
364issolved(cube_t cube)
365{
366 return cube.c == solvedcube.c && cube.e == solvedcube.e;
367}
368
369
370static uint64_t
371readep(char *str)
372{
373 if (!strncmp(str, "UF", 2))
374 return _edge_uf;
375 if (!strncmp(str, "UL", 2))
376 return _edge_ul;
377 if (!strncmp(str, "UB", 2))
378 return _edge_ub;
379 if (!strncmp(str, "UR", 2))
380 return _edge_ur;
381 if (!strncmp(str, "DF", 2))
382 return _edge_df;
383 if (!strncmp(str, "DL", 2))
384 return _edge_dl;
385 if (!strncmp(str, "DB", 2))
386 return _edge_db;
387 if (!strncmp(str, "DR", 2))
388 return _edge_dr;
389 if (!strncmp(str, "FR", 2))
390 return _edge_fr;
391 if (!strncmp(str, "FL", 2))
392 return _edge_fl;
393 if (!strncmp(str, "BL", 2))
394 return _edge_bl;
395 if (!strncmp(str, "BR", 2))
396 return _edge_br;
397
398 return _error;
399}
400
401static uint64_t
402readeo(char *str)
403{
404 if (*str == '0')
405 return 0ULL;
406 if (*str == '1')
407 return 1ULL;
408
409 return _error;
410}
411
412static uint64_t
413readcp(char *str)
414{
415 if (!strncmp(str, "UFR", 3) || !strncmp(str, "URF", 3))
416 return _corner_ufr;
417 if (!strncmp(str, "UFL", 3) || !strncmp(str, "ULF", 3))
418 return _corner_ufl;
419 if (!strncmp(str, "UBL", 3) || !strncmp(str, "ULB", 3))
420 return _corner_ubl;
421 if (!strncmp(str, "UBR", 3) || !strncmp(str, "URB", 3))
422 return _corner_ubr;
423 if (!strncmp(str, "DFR", 3) || !strncmp(str, "DRF", 3))
424 return _corner_dfr;
425 if (!strncmp(str, "DFL", 3) || !strncmp(str, "DLF", 3))
426 return _corner_dfl;
427 if (!strncmp(str, "DBL", 3) || !strncmp(str, "DLB", 3))
428 return _corner_dbl;
429 if (!strncmp(str, "DBR", 3) || !strncmp(str, "DRB", 3))
430 return _corner_dbr;
431
432 return _error;
433}
434
435static uint64_t
436readco(char *str)
437{
438 if (*str == '0')
439 return 0ULL;
440 if (*str == '1')
441 return 1ULL;
442 if (*str == '2')
443 return 2ULL;
444
445 return _error;
446}
447
448cube_t
449readcube(char *buf)
450{
451 int i;
452 uint64_t piece, orient;
453 cube_t ret = {0};
454 char *b = buf;
455
456 for (i = 0; i < 12; i++) {
457 while (*b == ' ' || *b == '\t' || *b == '\n')
458 b++;
459 if ((piece = readep(b)) == _error)
460 goto readcube_error;
461 b += 2;
462 if ((orient = readeo(b)) == _error)
463 goto readcube_error;
464 b++;
465 ret.e |= (piece << ESHIFT(i)) | (orient << EOSHIFT(i));
466 }
467 for (i = 0; i < 8; i++) {
468 while (*b == ' ' || *b == '\t' || *b == '\n')
469 b++;
470 if ((piece = readcp(b)) == _error)
471 goto readcube_error;
472 b += 3;
473 if ((orient = readco(b)) == _error)
474 goto readcube_error;
475 b++;
476 ret.c |= (piece << CSHIFT(i)) | (orient << COSHIFT(i));
477 }
478
479 return ret;
480
481readcube_error:
482 return errorcube;
483}
484
485void
486writecube(cube_t cube, char *buf)
487{
488 char *errormsg;
489 uint64_t piece;
490 size_t len;
491 int i;
492
493 if (!isconsistent(cube)) {
494 errormsg = "ERROR: cannot write inconsistent cube";
495 goto writecube_error;
496 }
497
498 for (i = 0; i < 12; i++) {
499 piece = EPAT(cube.e, i);
500 buf[4*i ] = edgestr[piece][0];
501 buf[4*i + 1] = edgestr[piece][1];
502 buf[4*i + 2] = EOAT(cube.e, i) + '0';
503 buf[4*i + 3] = ' ';
504 }
505 for (i = 0; i < 8; i++) {
506 piece = CPAT(cube.c, i);
507 buf[48 + 5*i ] = cornerstr[piece][0];
508 buf[48 + 5*i + 1] = cornerstr[piece][1];
509 buf[48 + 5*i + 2] = cornerstr[piece][2];
510 buf[48 + 5*i + 3] = COAT(cube.c, i) + '0';
511 buf[48 + 5*i + 4] = ' ';
512 }
513
514 buf[48+39] = '\0';
515
516 return;
517
518writecube_error:
519 len = strlen(errormsg);
520 strcpy(buf, errormsg);
521 buf[len] = '\n';
522 buf[len+1] = '\0';
523}
524
525
526static uint64_t
527readmove(char c)
528{
529 switch (c) {
530 case 'U':
531 return U;
532 case 'D':
533 return D;
534 case 'R':
535 return R;
536 case 'L':
537 return L;
538 case 'F':
539 return F;
540 case 'B':
541 return B;
542 default:
543 return _error;
544 }
545}
546
547static uint64_t
548readmodifier(char c)
549{
550 switch (c) {
551 case '1': /* Fallthrough */
552 case '2': /* Fallthrough */
553 case '3':
554 return c - '0' - 1;
555 case '\'':
556 return 2;
557 default:
558 return 0;
559 }
560}
561
562int
563readmoves(char *buf, move_t *m)
564{
565 int n;
566 uint64_t r;
567 char *b;
568
569 for (b = buf, n = 0; *b != '\0'; b++) {
570 while (*b == ' ' || *b == '\t' || *b == '\n')
571 b++;
572 if ((r = readmove(*b)) == _error)
573 return -1;
574 m[n] = (move_t)r;
575 if ((r = readmodifier(*(b+1))) != 0) {
576 b++;
577 m[n] += r;
578 }
579 n++;
580 }
581
582 return n;
583}
584
585void
586writemoves(move_t *m, int n, char *buf)
587{
588 int i;
589 char *b, *s;
590
591 for (i = 0, b = buf; i < n; i++, b++) {
592 s = movestr[m[i]];
593 strcpy(b, s);
594 b += strlen(s);
595 *b = ' ';
596 }
597 *b = '\0';
598}
599
600
601cube_t
602move(move_t m, cube_t c)
603{
604 /* TODO - not implemented yet */
605
606 cube_t ret = {0};
607
608 switch (m) {
609 case U:
610 return ret;
611 default:
612 return ret;
613 }
614}
diff --git a/src/cube.sync-conflict-20230524-182143-JOKKFPA.h b/src/cube.sync-conflict-20230524-182143-JOKKFPA.h
deleted file mode 100644
index 2763d16..0000000
--- a/src/cube.sync-conflict-20230524-182143-JOKKFPA.h
+++ /dev/null
@@ -1,27 +0,0 @@
1typedef enum {
2 U, U2, U3, D, D2, D3,
3 R, R2, R3, L, L2, L3,
4 F, F2, F3, B, B2, B3
5} move_t;
6typedef struct {
7 uint64_t e;
8 uint64_t c;
9} cube_t;
10
11extern cube_t solvedcube;
12extern cube_t errorcube;
13
14bool isconsistent(cube_t);
15bool issolved(cube_t);
16
17cube_t readcube(char *);
18void writecube(cube_t, char *);
19
20int readmoves(char *, move_t *);
21void writemoves(move_t *, int, char *);
22
23/*
24cube_t move(move_t, cube_t);
25cube_t inverse(cube_t);
26
27*/
diff --git a/src/cube.sync-conflict-20230524-182146-JOKKFPA.c b/src/cube.sync-conflict-20230524-182146-JOKKFPA.c
deleted file mode 100644
index e64acca..0000000
--- a/src/cube.sync-conflict-20230524-182146-JOKKFPA.c
+++ /dev/null
@@ -1,614 +0,0 @@
1/*
2# Cube representation, moves, transformations and indexing
3
4## String description
5
6The functions readcube() and writecube() use the following format.
7Each edge is represented by two letters denoting the sides it belongs to
8and one number denoting its orientation (0 oriented, 1 mis-oriented).
9Similarly, each corner is represented by three letters and a number
10(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
11Edge orientation is relative to the F / B axis, corner orientation is
12relative to the U / D axis.
13
14The correct order of the pieces is the same as that defined in the
15section "Internal cube representation", except that pieces are read
16left-to-right. Pieces are divided by slices, so the ordering is not the
17most intuitive, but it is more convenient for the internal representation.
18
19Whitespaces between pieces are ignored when reading the cube, and a
20single whitespace character is added between pieces when writing.
21
22For example, the solved cube looks like this:
23
24UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
25
26The cube after the moves R'U'F looks like this:
27
28FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0 UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
29
30More formats might be supported in the future.
31
32## Internal cube representation
33
34The cube_t data structure implemented in this file is designed to
35efficiently perform common operations on a 3x3x3 Rubik's cube when
36solving it with an iterative-deepening DFS search. It is not the most
37general, complete, easy to read or compact one. Since the cube can
38be trivially reoriented before the search, we only encode permutations
39of the cube that keep the center pieces in a fixed position (that is,
40we do not encode the position of the centers).
41
42The cube state is encoded in two 64-bit integers, one for edges and one
43for centers. We explain how edges are encoded first, and the highlight
44the few differences with corners afterwards.
45
46For encoding edges, only the 60 least-significant bits are used. Each
47edge described by 5 bits. The position of a 5-bit block in the 64-bit
48integer determine the position of the edge piece in the cube, according
49to the following table (least-significant bits on the right):
50
5155-59 50-54 45-49 40-44 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
52 BR BL FL FR DR DL UL UR DF DB UB UF
53ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee
54
55For each edge, the 4 least-significant bits ('ssee' in the table)
56determine the piece. The two bits marked with 'ss' determine the internal
57slice the piece belongs to, i.e. they are either '00' for M, '01' for
58S or '10' for E. The other two bits (marked with 'ee') determine the
59actual edge piece among the 4 in the same slice, and they are assigned
60somewhat arbitarily. Using this representation and the ordering defined
61in the table above, the edges are correctly permuted when these 4 bits
62for each represent the numbers 0 to 11 in the correct order.
63
64The last bit determines the orientation. The orientation of an edge
65depends on its position, and it is defined being 0 if the edge can be
66moved to its place in the solved orientation by permutations in the
67subgroup <U, D, R, L, F2, B2>.
68
69Corners are encoded in the 48 least-significant bits, and are described
70by 6 bits each, their position being defined by the following table:
71
72 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
73 DBL DFL UBR UFL DBR DFL UBL UFR
74oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc
75
76The bit marked with an 'x' describes the axis the corner belongs to.
77The 0 axis consists of the corners UFR, UBL, DFL and DBR, and the other
78four corners form the axis marked with 1. Then two bits are needed to
79identify the corner among the four of the same axis. The last three bits
80determine the orientation, where one corner is defined to be oriented
81(marked with '000') if its top or bottom sticker faces the top or bottom
82side. A corner a clockwise turn away from being oriented, thus requiring
83a counter-clockwise turn to be oriented correctly, is marked with '001',
84and a corner a counter-clockwise turn away is marked with '010'. The most
85significant bit is not used to determine the corner orientation, but it
86must always be set to '0' to simplify the moving operations (see below).
87
88## Basic moves
89
90The 18 basic moves of the cube could be performed by applying a suitable
91general permutation (see below), but they have instead been manually
92implemented with a few simple operations each, to improve performance.
93
94For each move we first permute the pieces. This amounts to shifting
95around 4 blocks of bits for edges and 4 for corners. Since in some cases
96adjacent pieces on the cube are also adjacent in the bit representation we
97use, we can save some operations by shifting multiple blocks together.
98For example, for the move U for edges we shift a block of 15 bits 5
99positions to the left and a block of 5 bits 15 positions to the right.
100
101There are some moves that change the orientation of the pieces. Namely,
102the moves F, F', B and B' change the orientation of the edges and those
103moves as well as R, R', L and L' change the orientation of the corners.
104Edge orientation is easy to address: we simply xor the edge representation
105by a bit mask with zeroes everywhere except for the 4 edges that need
106to be flipped (i.e. the ones on the twisted face).
107
108Corner orientation is harder to reproduce efficiently working only with
109bitwise operations, as it involves performing operations modulo 3.
110However, with the help of the extra bit we reserved, we are able to
111do this using only two additions and 3 bitwise operations, without
112any multiplication, division or modulo operation. The trick is
113to use the following formula to sum two numbers x, y in {0,1,2}:
114
115 ((x+y) + (x+y+1)/4) % 4
116
117The thrid bit is needed because x+y and x+y+1 can exceed 3.
118See below (in the code) for the details.
119
120## Inverting the cube
121
122TODO
123
124## Transformations (conjugations by full-cube rotations)
125
126TODO
127
128## Indexing
129
130TODO - subgroup description etc
131
132Ideas for pruning (for another file?):
133- Use corner separation + CO as main coordinate (~150k states)
134 - for huge tables, htr corners can be used (6 times larger)
135- Symmetry table, one entry or each main coordinate value with the
136 following info:
137 - index of the corresponding main symcoord (13 bits)
138 - transtorep (6 bits)
139 - base value for pruning table (5 bits, probably 4)
140 - pruning value for only main coord, i.e. fallback (4 bits)
141- To get a full coord for the cube:
142 - get first coord c, get the transtorep
143 - transform edges with transtorep
144 - get second coordinate e
145 - return c * MAXE + e
146 - This is still too big, so divide by a power of 2 to get the hashed index
147 - second coordinate: ep always, + varible number of eo bit (0 to 11)
148- Generate table:
149 - first probe for base value:
150 - solve coord using fallback table for pruning for 10k random states or so
151 - loop over all possible values (even if going for smaller table)
152 - with inverse-index strategy or what?
153 - use 1 bit per entry (more than base value or not)
154*/
155
156#include <stdbool.h>
157#include <stdint.h>
158#include <string.h>
159
160#ifdef DEBUG
161#include <stdio.h>
162#endif
163
164#include "cube.h"
165
166#define _error 0xFFFFFFFF
167
168#define _esize 5ULL
169#define _eoblock 0x10ULL /* 10000 */
170#define _epblock 0x0FULL /* 01111 */
171#define _eblock 0x1FULL /* 11111 */
172
173#define _csize 6ULL
174#define _coblock 0x18ULL /* 011000 */
175#define _cpblock 0x07ULL /* 000111 */
176#define _cblock 0x3FULL /* 111111 */
177
178#define _edge_uf 0ULL /* 00 00 */
179#define _edge_ub 1ULL /* 00 01 */
180#define _edge_db 2ULL /* 00 10 */
181#define _edge_df 3ULL /* 00 11 */
182#define _edge_ur 4ULL /* 01 00 */
183#define _edge_ul 5ULL /* 01 01 */
184#define _edge_dl 6ULL /* 01 10 */
185#define _edge_dr 7ULL /* 01 11 */
186#define _edge_fr 8ULL /* 10 00 */
187#define _edge_fl 9ULL /* 10 01 */
188#define _edge_bl 10ULL /* 10 10 */
189#define _edge_br 11ULL /* 10 11 */
190
191#define _corner_ufr 0ULL /* 0 00 */
192#define _corner_ubl 1ULL /* 0 01 */
193#define _corner_dfl 2ULL /* 0 10 */
194#define _corner_dbr 3ULL /* 0 11 */
195#define _corner_ufl 4ULL /* 1 00 */
196#define _corner_ubr 5ULL /* 1 01 */
197#define _corner_dfr 6ULL /* 1 10 */
198#define _corner_dbl 7ULL /* 1 11 */
199
200#define ESHIFT(i) ((i) * _esize)
201#define EOSHIFT(i) (4ULL + (i) * _esize)
202#define EMASK(i) (_eblock << ESHIFT(i))
203#define EOMASK(i) (_eoblock << ESHIFT(i))
204#define EPMASK(i) (_epblock << ESHIFT(i))
205#define ESOLVED(ee) (_edge_##ee << (_edge_##ee * _esize))
206#define EDGEAT(e, i) (((e) & EMASK(i)) >> ESHIFT(i))
207#define EOAT(e, i) (((e) & EOMASK(i)) >> EOSHIFT(i))
208#define EPAT(e, i) (((e) & EPMASK(i)) >> ESHIFT(i))
209
210#define CSHIFT(i) ((i) * _csize)
211#define COSHIFT(i) (3ULL + (i) * _csize)
212#define CMASK(i) (_cblock << CSHIFT(i))
213#define COMASK(i) (_coblock << CSHIFT(i))
214#define CPMASK(i) (_cpblock << CSHIFT(i))
215#define CSOLVED(ccc) (_corner_##ccc << (_corner_##ccc * _csize))
216#define CORNERAT(c, i) (((c) & CMASK(i)) >> CSHIFT(i))
217#define COAT(c, i) (((c) & COMASK(i)) >> COSHIFT(i))
218#define CPAT(c, i) (((c) & CPMASK(i)) >> CSHIFT(i))
219
220#define _emask_u (EMASK(uf) | EMASK(ul) | EMASK(ub) | EMASK(ur))
221#define _emask_d (EMASK(df) | EMASK(dl) | EMASK(db) | EMASK(dr))
222#define _emask_r (EMASK(ur) | EMASK(dr) | EMASK(fr) | EMASK(br))
223#define _emask_l (EMASK(ul) | EMASK(dl) | EMASK(fl) | EMASK(bl))
224#define _emask_f (EMASK(uf) | EMASK(df) | EMASK(fr) | EMASK(fl))
225#define _emask_b (EMASK(ub) | EMASK(db) | EMASK(br) | EMASK(bl))
226
227#define _cmask_u (CMASK(ufr) | CMASK(ufl) | CMASK(ubl) | CMASK(ubr))
228#define _cmask_d (CMASK(dfr) | CMASK(dfl) | CMASK(dbl) | CMASK(dbr))
229#define _cmask_r (CMASK(ufr) | CMASK(dfr) | CMASK(ubr) | CMASK(dbr))
230#define _cmask_l (CMASK(ufl) | CMASK(dfl) | CMASK(ubl) | CMASK(dbl))
231#define _cmask_f (CMASK(ufr) | CMASK(ufl) | CMASK(dfr) | CMASK(dfl))
232#define _cmask_b (CMASK(ubr) | CMASK(ubl) | CMASK(dbr) | CMASK(dbl))
233
234#define _eomask (EOMASK(uf) | EOMASK(ul) | EOMASK(ub) | EOMASK(ur) \
235 EOMASK(df) | EOMASK(dl) | EOMASK(db) | EOMASK(dr) \
236 EOMASK(fr) | EOMASK(fl) | EOMASK(bl) | EOMASK(br))
237#define _comask (COMASK(ufr) | COMASK(ufl) | COMASK(ubl) | COMASK(ubr) \
238 COMASK(dfr) | COMASK(dfl) | COMASK(dbl) | COMASK(dbr))
239
240static uint64_t permsign(uint64_t *, int);
241static uint64_t readep(char *);
242static uint64_t readeo(char *);
243static uint64_t readcp(char *);
244static uint64_t readco(char *);
245static uint64_t readmove(char);
246static uint64_t readmodifier(char);
247
248static char *edgestr[] = {
249 [_edge_uf] = "UF",
250 [_edge_ub] = "UB",
251 [_edge_db] = "DB",
252 [_edge_df] = "DF",
253 [_edge_ur] = "UR",
254 [_edge_ul] = "UL",
255 [_edge_dl] = "DL",
256 [_edge_dr] = "DR",
257 [_edge_fr] = "FR",
258 [_edge_fl] = "FL",
259 [_edge_bl] = "BL",
260 [_edge_br] = "BR"
261};
262static char *cornerstr[] = {
263 [_corner_ufr] = "UFR",
264 [_corner_ubl] = "UBL",
265 [_corner_dfl] = "DFL",
266 [_corner_dbr] = "DBR",
267 [_corner_ufl] = "UFL",
268 [_corner_ubr] = "UBR",
269 [_corner_dfr] = "DFR",
270 [_corner_dbl] = "DBL"
271};
272static char *movestr[] = {
273 [U] = "U", [U2] = "U2", [U3] = "U'",
274 [D] = "D", [D2] = "D2", [D3] = "D'",
275 [R] = "R", [R2] = "R2", [R3] = "R'",
276 [L] = "L", [L2] = "L2", [L3] = "L'",
277 [F] = "F", [F2] = "F2", [F3] = "F'",
278 [B] = "B", [B2] = "B2", [B3] = "B'",
279};
280
281cube_t solvedcube = {
282 .e = ESOLVED(uf) | ESOLVED(ul) | ESOLVED(ub) | ESOLVED(ur) |
283 ESOLVED(df) | ESOLVED(dl) | ESOLVED(db) | ESOLVED(dr) |
284 ESOLVED(fr) | ESOLVED(fl) | ESOLVED(bl) | ESOLVED(br),
285 .c = CSOLVED(ufr) | CSOLVED(ufl) | CSOLVED(ubl) | CSOLVED(ubr) |
286 CSOLVED(dfr) | CSOLVED(dfl) | CSOLVED(dbl) | CSOLVED(dbr),
287};
288cube_t errorcube = { .e = _error, .c = _error };
289
290
291static uint64_t
292permsign(uint64_t *a, int n)
293{
294 int i, j;
295 uint64_t ret;
296
297 ret = 0;
298
299 for (i = 0; i < n; i++)
300 for (j = i+1; j < n; j++)
301 ret += a[i] > a[j] ? 1 : 0;
302
303 return ret % 2;
304}
305
306bool
307isconsistent(cube_t cube)
308{
309 uint64_t p[12], sum;
310 bool found[12];
311 int i;
312
313 sum = 0;
314
315 /* Check for EP consistency */
316 for (i = 0; i < 12; i++)
317 found[i] = false;
318 for (i = 0; i < 12; i++) {
319 p[i] = EPAT(cube.e, i);
320 found[p[i]] = true;
321 }
322 for (i = 0; i < 12; i++)
323 if (!found[i])
324 return false;
325 sum = permsign(p, 12);
326
327 /* Check for CP consistency */
328 for (i = 0; i < 8; i++)
329 found[i] = false;
330 for (i = 0; i < 8; i++) {
331 p[i] = CPAT(cube.c, i);
332 found[p[i]] = true;
333 }
334 for (i = 0; i < 8; i++)
335 if (!found[i])
336 return false;
337 sum += permsign(p, 8);
338
339 /* Check permutation parity */
340 if (sum % 2 != 0)
341 return false;
342
343 /* Check for EO parity */
344 for (i = 0, sum = 0; i < 12; i++)
345 sum += EOAT(cube.e, i);
346 if (sum % 2 != 0)
347 return false;
348
349 /* Check for CO parity */
350 for (i = 0, sum = 0; i < 8; i++)
351 sum += COAT(cube.c, i);
352 if (sum % 3 != 0)
353 return false;
354
355 /* Check that CO extra bit is zero */
356 for (i = 0; i < 8; i++)
357 if (cube.c & (1ULL << (5 + i * _csize)))
358 return false;
359
360 return true;
361}
362
363bool
364issolved(cube_t cube)
365{
366 return cube.c == solvedcube.c && cube.e == solvedcube.e;
367}
368
369
370static uint64_t
371readep(char *str)
372{
373 if (!strncmp(str, "UF", 2))
374 return _edge_uf;
375 if (!strncmp(str, "UL", 2))
376 return _edge_ul;
377 if (!strncmp(str, "UB", 2))
378 return _edge_ub;
379 if (!strncmp(str, "UR", 2))
380 return _edge_ur;
381 if (!strncmp(str, "DF", 2))
382 return _edge_df;
383 if (!strncmp(str, "DL", 2))
384 return _edge_dl;
385 if (!strncmp(str, "DB", 2))
386 return _edge_db;
387 if (!strncmp(str, "DR", 2))
388 return _edge_dr;
389 if (!strncmp(str, "FR", 2))
390 return _edge_fr;
391 if (!strncmp(str, "FL", 2))
392 return _edge_fl;
393 if (!strncmp(str, "BL", 2))
394 return _edge_bl;
395 if (!strncmp(str, "BR", 2))
396 return _edge_br;
397
398 return _error;
399}
400
401static uint64_t
402readeo(char *str)
403{
404 if (*str == '0')
405 return 0ULL;
406 if (*str == '1')
407 return 1ULL;
408
409 return _error;
410}
411
412static uint64_t
413readcp(char *str)
414{
415 if (!strncmp(str, "UFR", 3) || !strncmp(str, "URF", 3))
416 return _corner_ufr;
417 if (!strncmp(str, "UFL", 3) || !strncmp(str, "ULF", 3))
418 return _corner_ufl;
419 if (!strncmp(str, "UBL", 3) || !strncmp(str, "ULB", 3))
420 return _corner_ubl;
421 if (!strncmp(str, "UBR", 3) || !strncmp(str, "URB", 3))
422 return _corner_ubr;
423 if (!strncmp(str, "DFR", 3) || !strncmp(str, "DRF", 3))
424 return _corner_dfr;
425 if (!strncmp(str, "DFL", 3) || !strncmp(str, "DLF", 3))
426 return _corner_dfl;
427 if (!strncmp(str, "DBL", 3) || !strncmp(str, "DLB", 3))
428 return _corner_dbl;
429 if (!strncmp(str, "DBR", 3) || !strncmp(str, "DRB", 3))
430 return _corner_dbr;
431
432 return _error;
433}
434
435static uint64_t
436readco(char *str)
437{
438 if (*str == '0')
439 return 0ULL;
440 if (*str == '1')
441 return 1ULL;
442 if (*str == '2')
443 return 2ULL;
444
445 return _error;
446}
447
448cube_t
449readcube(char *buf)
450{
451 int i;
452 uint64_t piece, orient;
453 cube_t ret = {0};
454 char *b = buf;
455
456 for (i = 0; i < 12; i++) {
457 while (*b == ' ' || *b == '\t' || *b == '\n')
458 b++;
459 if ((piece = readep(b)) == _error)
460 goto readcube_error;
461 b += 2;
462 if ((orient = readeo(b)) == _error)
463 goto readcube_error;
464 b++;
465 ret.e |= (piece << ESHIFT(i)) | (orient << EOSHIFT(i));
466 }
467 for (i = 0; i < 8; i++) {
468 while (*b == ' ' || *b == '\t' || *b == '\n')
469 b++;
470 if ((piece = readcp(b)) == _error)
471 goto readcube_error;
472 b += 3;
473 if ((orient = readco(b)) == _error)
474 goto readcube_error;
475 b++;
476 ret.c |= (piece << CSHIFT(i)) | (orient << COSHIFT(i));
477 }
478
479 return ret;
480
481readcube_error:
482 return errorcube;
483}
484
485void
486writecube(cube_t cube, char *buf)
487{
488 char *errormsg;
489 uint64_t piece;
490 size_t len;
491 int i;
492
493 if (!isconsistent(cube)) {
494 errormsg = "ERROR: cannot write inconsistent cube";
495 goto writecube_error;
496 }
497
498 for (i = 0; i < 12; i++) {
499 piece = EPAT(cube.e, i);
500 buf[4*i ] = edgestr[piece][0];
501 buf[4*i + 1] = edgestr[piece][1];
502 buf[4*i + 2] = EOAT(cube.e, i) + '0';
503 buf[4*i + 3] = ' ';
504 }
505 for (i = 0; i < 8; i++) {
506 piece = CPAT(cube.c, i);
507 buf[48 + 5*i ] = cornerstr[piece][0];
508 buf[48 + 5*i + 1] = cornerstr[piece][1];
509 buf[48 + 5*i + 2] = cornerstr[piece][2];
510 buf[48 + 5*i + 3] = COAT(cube.c, i) + '0';
511 buf[48 + 5*i + 4] = ' ';
512 }
513
514 buf[48+39] = '\0';
515
516 return;
517
518writecube_error:
519 len = strlen(errormsg);
520 strcpy(buf, errormsg);
521 buf[len] = '\n';
522 buf[len+1] = '\0';
523}
524
525
526static uint64_t
527readmove(char c)
528{
529 switch (c) {
530 case 'U':
531 return U;
532 case 'D':
533 return D;
534 case 'R':
535 return R;
536 case 'L':
537 return L;
538 case 'F':
539 return F;
540 case 'B':
541 return B;
542 default:
543 return _error;
544 }
545}
546
547static uint64_t
548readmodifier(char c)
549{
550 switch (c) {
551 case '1': /* Fallthrough */
552 case '2': /* Fallthrough */
553 case '3':
554 return c - '0' - 1;
555 case '\'':
556 return 2;
557 default:
558 return 0;
559 }
560}
561
562int
563readmoves(char *buf, move_t *m)
564{
565 int n;
566 uint64_t r;
567 char *b;
568
569 for (b = buf, n = 0; *b != '\0'; b++) {
570 while (*b == ' ' || *b == '\t' || *b == '\n')
571 b++;
572 if ((r = readmove(*b)) == _error)
573 return -1;
574 m[n] = (move_t)r;
575 if ((r = readmodifier(*(b+1))) != 0) {
576 b++;
577 m[n] += r;
578 }
579 n++;
580 }
581
582 return n;
583}
584
585void
586writemoves(move_t *m, int n, char *buf)
587{
588 int i;
589 char *b, *s;
590
591 for (i = 0, b = buf; i < n; i++, b++) {
592 s = movestr[m[i]];
593 strcpy(b, s);
594 b += strlen(s);
595 *b = ' ';
596 }
597 *b = '\0';
598}
599
600
601cube_t
602move(move_t m, cube_t c)
603{
604 /* TODO - not implemented yet */
605
606 cube_t ret = {0};
607
608 switch (m) {
609 case U:
610 return ret;
611 default:
612 return ret;
613 }
614}
diff --git a/src/cube.sync-conflict-20230524-182146-JOKKFPA.h b/src/cube.sync-conflict-20230524-182146-JOKKFPA.h
deleted file mode 100644
index 2763d16..0000000
--- a/src/cube.sync-conflict-20230524-182146-JOKKFPA.h
+++ /dev/null
@@ -1,27 +0,0 @@
1typedef enum {
2 U, U2, U3, D, D2, D3,
3 R, R2, R3, L, L2, L3,
4 F, F2, F3, B, B2, B3
5} move_t;
6typedef struct {
7 uint64_t e;
8 uint64_t c;
9} cube_t;
10
11extern cube_t solvedcube;
12extern cube_t errorcube;
13
14bool isconsistent(cube_t);
15bool issolved(cube_t);
16
17cube_t readcube(char *);
18void writecube(cube_t, char *);
19
20int readmoves(char *, move_t *);
21void writemoves(move_t *, int, char *);
22
23/*
24cube_t move(move_t, cube_t);
25cube_t inverse(cube_t);
26
27*/

Generated with cgit - Back to sebastiano.tronto.net