h48

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

dr.h (4652B)


      1 #define DREOESEP_CLASSES   UINT64_C(64430)
      2 #define DREOESEP_MAX       (POW_2_11 * COMB_12_4)
      3 
      4 #define DR_CLASS_TABLESIZE (sizeof(uint32_t) * (size_t)DREOESEP_MAX)
      5 #define DR_REP_TABLESIZE   (sizeof(uint32_t) * (size_t)DREOESEP_CLASSES)
      6 #define DR_COORD_DATASIZE  (INFOSIZE + DR_CLASS_TABLESIZE + DR_REP_TABLESIZE)
      7 
      8 #define DR_CLASS_SHIFT     UINT32_C(16)
      9 #define DR_CLASS_MASK      (UINT32_C(0xFFFF) << DR_CLASS_SHIFT)
     10 #define DR_CLASS(d)        (((d) & DR_CLASS_MASK) >> DR_CLASS_SHIFT)
     11 
     12 #define DR_TTREP_SHIFT     UINT32_C(0)
     13 #define DR_TTREP_MASK      (UINT32_C(0xFF) << DR_TTREP_SHIFT)
     14 #define DR_TTREP(d)        (((d) & DR_TTREP_MASK) >> DR_TTREP_SHIFT)
     15 
     16 #define DR_ISNASTY_SHIFT   UINT32_C(8)
     17 #define DR_ISNASTY_MASK    (UINT32_C(0xFF) << DR_ISNASTY_SHIFT)
     18 #define DR_ISNASTY(d)      (((d) & DR_ISNASTY_MASK) >> DR_ISNASTY_SHIFT)
     19 
     20 STATIC uint64_t coord_dreoesep_nosym(cube_t);
     21 STATIC cube_t invcoord_dreoesep_nosym(uint64_t);
     22 
     23 STATIC uint64_t coordinate_dr_coord(cube_t, const void *);
     24 STATIC cube_t coordinate_dr_cube(uint64_t, const void *);
     25 STATIC bool coordinate_dr_isnasty(uint64_t, const void *);
     26 STATIC size_t coordinate_dr_gendata(void *);
     27 
     28 STATIC coord_t coordinate_dr = {
     29 	.name = "DR",
     30 	.coord = &coordinate_dr_coord,
     31 	.cube = &coordinate_dr_cube,
     32 	.isnasty = &coordinate_dr_isnasty,
     33 	.gendata = coordinate_dr_gendata,
     34 	.max = DREOESEP_CLASSES * POW_3_7,
     35 	.trans_mask = TM_UDFIX,
     36 	.moves_mask = MM_ALLMOVES,
     37 	.axistrans = {
     38 		[AXIS_UD] = TRANS_UFr,
     39 		[AXIS_RL] = TRANS_RFr,
     40 		[AXIS_FB] = TRANS_FDr,
     41 	},
     42 	.is_admissible = &solution_lastqt_cw,
     43 };
     44 
     45 STATIC uint64_t
     46 coord_dreoesep_nosym(cube_t cube)
     47 {
     48 	uint64_t eo, esep;
     49 
     50 	esep = coord_esep(cube) / COMB_8_4;
     51 	eo = coord_eo(cube);
     52 
     53 	return esep * POW_2_11 + eo;
     54 }
     55 
     56 STATIC cube_t
     57 invcoord_dreoesep_nosym(uint64_t coord)
     58 {
     59 	uint64_t eo, esep;
     60 	cube_t cube;
     61 
     62 	eo = coord % POW_2_11;
     63 	esep = (coord / POW_2_11) * COMB_8_4; 
     64 	cube = invcoord_esep(esep);
     65 	set_eo(&cube, eo);
     66 
     67 	return cube;
     68 }
     69 
     70 STATIC uint64_t
     71 coordinate_dr_coord(cube_t cube, const void *data)
     72 {
     73 	const char *datanoinfo;
     74 	const uint32_t *data32;
     75 	uint32_t d;
     76 	cube_t transformed;
     77 
     78 	datanoinfo = (const char *)data + INFOSIZE;
     79 	data32 = (const uint32_t *)datanoinfo;
     80 	d = data32[coord_dreoesep_nosym(cube)];
     81 	transformed = transform(cube, DR_TTREP(d));
     82 	
     83 	return DR_CLASS(d) * POW_3_7 + coord_co(transformed);
     84 }
     85 
     86 STATIC cube_t
     87 coordinate_dr_cube(uint64_t coord, const void *data)
     88 {
     89 	const char *datanoinfo;
     90 	const uint32_t *rep32;
     91 	cube_t cube;
     92 
     93 	datanoinfo = (const char *)data + INFOSIZE;
     94 	rep32 = (const uint32_t *)(datanoinfo + DR_CLASS_TABLESIZE);
     95 	cube = invcoord_dreoesep_nosym(rep32[coord / POW_3_7]);
     96 	copy_corners(&cube, invcoord_co(coord % POW_3_7));
     97 
     98 	return cube;
     99 }
    100 
    101 STATIC bool
    102 coordinate_dr_isnasty(uint64_t coord, const void *data)
    103 {
    104 	const char *datanoinfo;
    105 	const uint32_t *classttrep, *rep32;
    106 	uint32_t r;
    107 
    108 	datanoinfo = (const char *)data + INFOSIZE;
    109 	classttrep = (const uint32_t *)datanoinfo;
    110 	rep32 = (const uint32_t *)(datanoinfo + DR_CLASS_TABLESIZE);
    111 	r = rep32[coord / POW_3_7];
    112 
    113 	return DR_ISNASTY(classttrep[r]);
    114 }
    115 
    116 STATIC size_t
    117 coordinate_dr_gendata(void *data)
    118 {
    119 	uint64_t i, j, n, t, nasty;
    120 	char *datanoinfo;
    121 	uint32_t *classttrep, *rep;
    122 	cube_t c;
    123 	tableinfo_t info;
    124 
    125 	if (data == NULL)
    126 		goto coordinate_dr_gendata_returnsize;
    127 
    128 	datanoinfo = (char *)data + INFOSIZE;
    129 	classttrep = (uint32_t *)datanoinfo;
    130 	rep = classttrep + (DR_CLASS_TABLESIZE / sizeof(uint32_t));
    131 	memset(data, 0xFF, DR_COORD_DATASIZE);
    132 
    133 	info = (tableinfo_t) {
    134 		.solver = "coord data for DR",
    135 		.type = TABLETYPE_SPECIAL,
    136 		.infosize = INFOSIZE,
    137 		.fullsize = DR_COORD_DATASIZE,
    138 		.hash = 0,
    139 		.entries = DREOESEP_CLASSES + DREOESEP_MAX,
    140 		.classes = DREOESEP_CLASSES,
    141 		.bits = 32,
    142 		.base = 0,
    143 		.maxvalue = 0,
    144 		.next = 0
    145 	};
    146 
    147 	for (i = 0, n = 0; i < COMB_12_4 * POW_2_11; i++) {
    148 		if (classttrep[i] != 0xFFFFFFFF)
    149 			continue;
    150 
    151 		c = invcoord_dreoesep_nosym(i);
    152 		for (t = 1, nasty = 0; t < NTRANS && !nasty; t++) {
    153 			if (!((UINT64_C(1) << t) & coordinate_dr.trans_mask))
    154 				continue;
    155 
    156 			nasty = i == coord_dreoesep_nosym(transform(c, t));
    157 		}
    158 
    159 		for (t = 0; t < NTRANS; t++) {
    160 			if (!((UINT64_C(1) << t) & coordinate_dr.trans_mask))
    161 				continue;
    162 
    163 			j = coord_dreoesep_nosym(transform(c, t));
    164 			classttrep[j] =
    165 			    (n << DR_CLASS_SHIFT) |
    166 			    (nasty << DR_ISNASTY_SHIFT) |
    167 			    (inverse_trans(t) << DR_TTREP_SHIFT);
    168 		}
    169 		rep[n++] = i;
    170 	}
    171 
    172 	writetableinfo(&info, DR_COORD_DATASIZE, data);
    173 
    174 	DBG_ASSERT(n == DREOESEP_CLASSES, 0,
    175 	    "dr coordinate data: computed %" PRIu64 " classes, "
    176 	    "expected %" PRIu64 "\n", n, DREOESEP_CLASSES);
    177 
    178 coordinate_dr_gendata_returnsize:
    179 	return DR_COORD_DATASIZE;
    180 }