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

expected_distributions.h (4185B)


      1 uint64_t expected_cocsep[21] = {
      2 	[0] = 1,
      3 	[1] = 6,
      4 	[2] = 63,
      5 	[3] = 468,
      6 	[4] = 3068,
      7 	[5] = 15438,
      8 	[6] = 53814,
      9 	[7] = 71352,
     10 	[8] = 8784,
     11 	[9] = 96
     12 };
     13 
     14 uint64_t expected_h48[12][9][21] = {
     15 	[0] = {
     16 		[2] = {
     17 			[0] = 5473562,
     18 			[1] = 34776317,
     19 			[2] = 68566704,
     20 			[3] = 8750867,
     21 		},
     22 		[4] = {
     23 			[0] = 1,
     24 			[1] = 1,
     25 			[2] = 4,
     26 			[3] = 34,
     27 			[4] = 331,
     28 			[5] = 3612,
     29 			[6] = 41605,
     30 			[7] = 474128,
     31 			[8] = 4953846,
     32 			[9] = 34776317,
     33 			[10] = 68566704,
     34 			[11] = 8749194,
     35 			[12] = 1673,
     36 		},
     37 	},
     38 	[1] = {
     39 		[2] = {
     40 			[0] = 6012079,
     41 			[1] = 45822302,
     42 			[2] = 142018732,
     43 			[3] = 41281787,
     44 		},
     45 	},
     46 	[2] = {
     47 		[2] = {
     48 			[0] = 6391286,
     49 			[1] = 55494785,
     50 			[2] = 252389935,
     51 			[3] = 155993794,
     52 		},
     53 	},
     54 	[3] = {
     55 		[2] = {
     56 			[0] = 6686828,
     57 			[1] = 63867852,
     58 			[2] = 392789689,
     59 			[3] = 477195231,
     60 		},
     61 	},
     62 	[4] = {
     63 		[2] = {
     64 			[0] = 77147213,
     65 			[1] = 543379415,
     66 			[2] = 1139570251,
     67 			[3] = 120982321,
     68 		},
     69 	},
     70 	[5] = {
     71 		[2] = {
     72 			[0] = 82471284,
     73 			[1] = 687850732,
     74 			[2] = 2345840746,
     75 			[3] = 645995638,
     76 		},
     77 	},
     78 	[6] = {
     79 		[2] = {
     80 			[0] = 85941099,
     81 			[1] = 804752968,
     82 			[2] = 4077248182,
     83 			[3] = 2556374551,
     84 		},
     85 	},
     86 	[7] = {
     87 		[2] = {
     88 			[0] = 88529761,
     89 			[1] = 897323475,
     90 			[2] = 6126260791,
     91 			[3] = 7936519573,
     92 		},
     93 	},
     94 	[8] = {
     95 		[2] = {
     96 			[0] = 1051579940,
     97 			[1] = 8136021316,
     98 			[2] = 19024479822,
     99 			[3] = 18851861220,
    100 		},
    101 	},
    102 	[9] = {
    103 		[2] = {
    104 			[0] = 1102038189,
    105 			[1] = 9888265242,
    106 			[2] = 38299375805,
    107 			[3] = 10904855164,
    108 		},
    109 	},
    110 	[10] = {
    111 		[2] = {
    112 			[0] = 1133240039,
    113 			[1] = 11196285614,
    114 			[2] = 64164702961,
    115 			[3] = 43894840186,
    116 		},
    117 	},
    118 	[11] = {
    119 		[2] = {
    120 			[0] = 1150763161,
    121 			[1] = 12045845660,
    122 			[2] = 91163433330,
    123 			[3] = 136418095449,
    124 		},
    125 	},
    126 };
    127 
    128 uint64_t expected_eo[21] = {
    129 	[0] = 1,
    130 	[1] = 2,
    131 	[2] = 25,
    132 	[3] = 202,
    133 	[4] = 620,
    134 	[5] = 900,
    135 	[6] = 285,
    136 	[7] = 13,
    137 };
    138 
    139 uint64_t expected_dr[21] = {
    140 	[0] = 1,
    141 	[1] = 1,
    142 	[2] = 5,
    143 	[3] = 44,
    144 	[4] = 487,
    145 	[5] = 5841,
    146 	[6] = 68364,
    147 	[7] = 776568,
    148 	[8] = 7950748,
    149 	[9] = 52098876,
    150 	[10] = 76236234,
    151 	[11] = 3771112,
    152 	[12] = 129,
    153 };
    154 
    155 static bool
    156 distribution_equal(const uint64_t *expected, const uint64_t *actual, int n)
    157 {
    158 	bool equal;
    159 	int i;
    160 
    161 	for (i = 0, equal = true; i <= n; i++) {
    162 		if (expected[i] != actual[i]) {
    163 			equal = false;
    164 			printf("Wrong value for %d: expected %" PRIu64
    165 			    ", actual %" PRIu64 "\n",
    166 			    i, expected[i], actual[i]);
    167 		}
    168 	}
    169 
    170 	return equal;
    171 }
    172 
    173 STATIC bool
    174 check_table(uint64_t *exp, tableinfo_t *info)
    175 {
    176 	if (!distribution_equal(exp, info->distribution, info->maxvalue)) {
    177 		printf("ERROR! Distribution is incorrect\n");
    178 		return false;
    179 	}
    180 
    181 	printf("Distribution is correct\n");
    182 	return true;
    183 }
    184 
    185 static bool
    186 check_cocsep(size_t data_size, const void *data)
    187 {
    188 	tableinfo_t info;
    189 
    190 	readtableinfo(data_size, data, &info);
    191 	return distribution_equal(
    192 	    expected_cocsep, info.distribution, info.maxvalue);
    193 }
    194 
    195 static bool
    196 unknown_h48(uint8_t h, uint8_t k)
    197 {
    198 	if (k != 2 && k != 4)
    199 		return true;
    200 
    201 	if (k == 4 && h != 0)
    202 		return true;
    203 
    204 	return k == 2 && h > 7;
    205 }
    206 
    207 STATIC bool
    208 check_distribution(const char *solver, size_t data_size, const void *data)
    209 {
    210 	const char *str;
    211 	tableinfo_t info = {0};
    212 
    213 	if (!strncmp(solver, "h48", 3)) {
    214 		readtableinfo(data_size, data, &info);
    215 		if (!distribution_equal(
    216 		    expected_cocsep, info.distribution, info.maxvalue)) {
    217 			printf("ERROR! cocsep distribution is incorrect\n");
    218 			return false;
    219 		}
    220 		printf("cocsep distribution is correct\n");
    221 
    222 		readtableinfo_n(data_size, data, 2, &info);
    223 		if (unknown_h48(info.h48h, info.bits))
    224 			goto check_distribution_unknown;
    225 
    226 		return check_table(expected_h48[info.h48h][info.bits], &info);
    227 	}
    228 
    229 	if (!strncmp(solver, "coord_", 6)) {
    230 		readtableinfo(data_size, data, &info);
    231 		if (!strncmp(info.solver, "coord helper table for ", 23))
    232 			readtableinfo_n(data_size, data, 2, &info);
    233 
    234 		str = info.solver + 22; /* "coordinate solver for COORD" */
    235 		if (!strcmp(str, "EO")) {
    236 			return check_table(expected_eo, &info);
    237 		} else if (!strcmp(str, "DR")) {
    238 			return check_table(expected_dr, &info);
    239 		} else {
    240 			goto check_distribution_unknown;
    241 		}
    242 	}
    243 
    244 check_distribution_unknown:
    245 	printf("Distribution unknown, not checked\n");
    246 	return true;
    247 }