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

gendata.h (6593B)


      1 STATIC size_t gendata_coord(const coord_t [static 1], void *);
      2 STATIC int64_t gendata_coord_dispatch(const char *, void *);
      3 STATIC tableinfo_t genptable_coord(
      4     const coord_t [static 1], const void *, uint8_t *);
      5 STATIC bool switch_to_fromnew(uint64_t, uint64_t, uint64_t);
      6 STATIC uint64_t genptable_coord_fillneighbors(
      7     const coord_t [static 1], const void *, uint64_t, uint8_t, uint8_t *);
      8 STATIC uint64_t genptable_coord_fillfromnew(
      9     const coord_t [static 1], const void *, uint64_t, uint8_t, uint8_t *);
     10 STATIC void getdistribution_coord(
     11     const uint8_t *, const char *, uint64_t [static INFO_DISTRIBUTION_LEN]);
     12 STATIC uint8_t get_coord_pval(
     13     const coord_t [static 1], const uint8_t *, uint64_t);
     14 STATIC void set_coord_pval(
     15     const coord_t [static 1], uint8_t *, uint64_t, uint8_t);
     16 
     17 STATIC int64_t
     18 gendata_coord_dispatch(const char *coordstr, void *buf)
     19 {
     20 	coord_t *coord;
     21 
     22 	parse_coord_and_axis(strlen(coordstr), coordstr, &coord, NULL);
     23 
     24 	if (coord == NULL) {
     25 		LOG("Could not parse coordinate '%s'\n", coord);
     26 		return NISSY_ERROR_INVALID_SOLVER;
     27 	}
     28 
     29 	return (int64_t)gendata_coord(coord, buf);
     30 }
     31 
     32 STATIC size_t
     33 gendata_coord(const coord_t coord[static 1], void *buf)
     34 {
     35 	uint64_t coord_dsize, tablesize, ninfo;
     36 	void *pruningbuf, *coord_data;
     37 	uint8_t *table;
     38 	tableinfo_t coord_data_info, pruning_info;
     39 
     40 	coord_data = buf == NULL ? NULL : ((uint8_t *)buf) + INFOSIZE;
     41 	coord_dsize = coord->gendata(coord_data);
     42 	ninfo = coord_dsize == 0 ? 1 : 2;
     43 	tablesize = DIV_ROUND_UP(coord->max, 2);
     44 
     45 	if (buf == NULL)
     46 		goto gendata_coord_return_size;
     47 
     48 	if (ninfo == 2) {
     49 		coord_data_info = (tableinfo_t) {
     50 			.solver = "coord helper table for ",
     51 			.type = TABLETYPE_SPECIAL,
     52 			.infosize = INFOSIZE,
     53 			.fullsize = INFOSIZE + coord_dsize,
     54 			.hash = 0, /* TODO */
     55 			.next = INFOSIZE + coord_dsize,
     56 
     57 			/* Unknown / non-applicable values */
     58 			.entries = 0,
     59 			.classes = 0,
     60 			.bits = 0,
     61 			.base = 0,
     62 			.maxvalue = 0,
     63 		};
     64 
     65 		append_coord_name(coord, coord_data_info.solver);
     66 
     67 		writetableinfo(&coord_data_info, INFOSIZE + coord_dsize, buf);
     68 
     69 		pruningbuf = ((uint8_t *)buf) + INFOSIZE + coord_dsize;
     70 	} else {
     71 		pruningbuf = buf;
     72 	}
     73 
     74 	table = ((uint8_t *)pruningbuf) + INFOSIZE;
     75 	pruning_info = genptable_coord(coord, coord_data, table);
     76 	writetableinfo(&pruning_info, INFOSIZE + tablesize, pruningbuf);
     77 
     78 gendata_coord_return_size:
     79 	return ninfo * INFOSIZE + coord_dsize + tablesize;
     80 }
     81 
     82 STATIC tableinfo_t
     83 genptable_coord(
     84 	const coord_t coord[static 1],
     85 	const void *data,
     86 	uint8_t *table
     87 )
     88 {
     89 	uint64_t tablesize, i, d, tot, t, nm;
     90 	tableinfo_t info;
     91 
     92 	tablesize = DIV_ROUND_UP(coord->max, 2);
     93 
     94 	memset(table, 0xFF, tablesize);
     95 
     96 	info = (tableinfo_t) {
     97 		.solver = "coordinate solver for ",
     98 		.type = TABLETYPE_PRUNING,
     99 		.infosize = INFOSIZE,
    100 		.fullsize = INFOSIZE + tablesize,
    101 		.hash = 0, /* TODO */
    102 		.entries = coord->max,
    103 		.classes = 0,
    104 		.bits = 4,
    105 		.base = 0,
    106 		.maxvalue = 0,
    107 		.next = 0
    108 	};
    109 
    110 	memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
    111 	append_coord_name(coord, info.solver);
    112 
    113 	nm = popcount_u32(coord->moves_mask);
    114 	i = coord->coord(SOLVED_CUBE, data);
    115 	set_coord_pval(coord, table, i, 0);
    116 	info.distribution[0] = 1;
    117 	for (d = 1, tot = 1; tot < coord->max && d < 20; d++) {
    118 		t = 0;
    119 		if (switch_to_fromnew(tot, coord->max, nm)) {
    120 			for (i = 0; i < coord->max; i++)
    121 				if (get_coord_pval(coord, table, i) > d)
    122 					t += genptable_coord_fillfromnew(
    123 					    coord, data, i, d, table);
    124 		} else {
    125 			for (i = 0; i < coord->max; i++)
    126 				if (get_coord_pval(coord, table, i) == d-1)
    127 					t += genptable_coord_fillneighbors(
    128 					    coord, data, i, d, table);
    129 		}
    130 		tot += t;
    131 		info.distribution[d] = t;
    132 		LOG("Depth %" PRIu64 ": found %" PRIu64 " (%" PRIu64 " of %"
    133 		    PRIu64 ")\n", d, t, tot, coord->max);
    134 	}
    135 	info.maxvalue = d-1;
    136 
    137 	return info;
    138 }
    139 
    140 STATIC bool
    141 switch_to_fromnew(uint64_t done, uint64_t max, uint64_t nm)
    142 {
    143 	/*
    144 	Heuristic to determine if it is more conveniente to loop over
    145       	done coordinates and fill the new discovered, or to loop from new
    146 	coordinates and fill them if they have a done neighbor.
    147 	*/
    148 
    149 	double r = (double)done / (double)max;
    150 	return 1.0 - intpow(1.0-r, nm) > nm * (1.0-r);
    151 }
    152 
    153 STATIC uint64_t
    154 genptable_coord_fillneighbors(
    155 	const coord_t coord[static 1],
    156 	const void *data,
    157 	uint64_t i, 
    158 	uint8_t d,
    159 	uint8_t *table
    160 )
    161 {
    162 	bool isnasty;
    163 	uint8_t m;
    164 	uint64_t ii, j, t, tot;
    165 	cube_t c, moved;
    166 
    167 	c = coord->cube(i, data);
    168 	tot = 0;
    169 	for (m = 0; m < NMOVES; m++) {
    170 		moved = move(c, m);
    171 		ii = coord->coord(moved, data);
    172 		isnasty = coord->isnasty(ii, data);
    173 		for (t = 0; t < NTRANS && (t == 0 || isnasty); t++) {
    174 			if (!((UINT64_C(1) << t) & coord->trans_mask))
    175 				continue;
    176 
    177 			j = coord->coord(transform(moved, t), data);
    178 			if (get_coord_pval(coord, table, j) > d) {
    179 				set_coord_pval(coord, table, j, d);
    180 				tot++;
    181 			}
    182 		}
    183 	}
    184 
    185 	return tot;
    186 }
    187 
    188 STATIC uint64_t
    189 genptable_coord_fillfromnew(
    190 	const coord_t coord[static 1],
    191 	const void *data,
    192 	uint64_t i,
    193 	uint8_t d,
    194 	uint8_t *table
    195 )
    196 {
    197 	bool found;
    198 	uint8_t m;
    199 	uint64_t tot, t, ii, j, nsim, sim[NTRANS];
    200 	cube_t c;
    201 
    202 	tot = 0;
    203 	c = coord->cube(i, data);
    204 
    205 	for (t = 0, nsim = 0; t < NTRANS; t++) {
    206 		if (!((UINT64_C(1) << t) & coord->trans_mask))
    207 			continue;
    208 
    209 		ii = coord->coord(transform(c, t), data);
    210 		for (j = 0, found = false; j < nsim && !found; j++)
    211 			found = sim[j] == ii;
    212 		if (!found)
    213 			sim[nsim++] = ii;
    214 	}
    215 
    216 	for (j = 0, found = false; j < nsim && !found; j++) {
    217 		c = coord->cube(sim[j], data);
    218 		for (m = 0; m < NMOVES; m++) {
    219 			ii = coord->coord(move(c, m), data);
    220 			if (get_coord_pval(coord, table, ii) < d) {
    221 				found = true;
    222 				break;
    223 			}
    224 		}
    225 	}
    226 
    227 	tot = 0;
    228 	if (found) {
    229 		for (j = 0; j < nsim; j++) {
    230 			if (get_coord_pval(coord, table, sim[j]) > d) {
    231 				set_coord_pval(coord, table, sim[j], d);
    232 				tot++;
    233 			}
    234 		}
    235 	}
    236 
    237 	return tot;
    238 }
    239 
    240 STATIC void
    241 getdistribution_coord(
    242 	const uint8_t *table,
    243 	const char *coord,
    244 	uint64_t distr[static INFO_DISTRIBUTION_LEN]
    245 )
    246 {
    247 	uint8_t v;
    248 	uint64_t i;
    249 	coord_t *c;
    250 
    251 	memset(distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
    252 
    253 	if((c = parse_coord(strlen(coord), coord)) == NULL)
    254 		return;
    255 
    256 	for (i = 0; i < c->max; i++) {
    257 		v = get_coord_pval(c, table, i);
    258 		distr[v]++;
    259 	}
    260 }
    261 
    262 STATIC uint8_t
    263 get_coord_pval(
    264 	const coord_t coord[static 1],
    265 	const uint8_t *table,
    266 	uint64_t i
    267 )
    268 {
    269 	return (table[COORD_INDEX(i)] & COORD_MASK(i)) >> COORD_SHIFT(i);
    270 }
    271 
    272 STATIC void
    273 set_coord_pval(
    274 	const coord_t coord[static 1],
    275 	uint8_t *table,
    276 	uint64_t i,
    277 	uint8_t val
    278 )
    279 {
    280 	table[COORD_INDEX(i)] = (table[COORD_INDEX(i)] & (~COORD_MASK(i)))
    281 	    | (val << COORD_SHIFT(i));
    282 }