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

math.h (3711B)

      1 #define SWAP(x, y) do { x ^= y; y ^= x; x ^= y; } while (0)
      2 #define MIN(x, y) ((x) < (y) ? (x) : (y))
      3 #define MAX(x, y) ((x) > (y) ? (x) : (y))
      4 #define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
      5 
      6 STATIC int64_t factorial(int64_t);
      7 STATIC bool isperm(uint8_t *, int64_t);
      8 STATIC int64_t permtoindex(uint8_t *, int64_t);
      9 STATIC void indextoperm(int64_t, int64_t, uint8_t *);
     10 STATIC int permsign(uint8_t *, int64_t);
     11 STATIC int64_t digitstosumzero(uint8_t *, uint8_t, uint8_t);
     12 STATIC void sumzerotodigits(int64_t, uint8_t, uint8_t, uint8_t *);
     13 
     14 STATIC int64_t
     15 factorial(int64_t n)
     16 {
     17 	int64_t i, ret;
     18 
     19 	if (n > FACTORIAL_MAX) {
     20 		LOG("Error: won't compute factorial for n=%" PRId64 " because"
     21 		    " it is larger than %" PRId64 "\n", n, FACTORIAL_MAX);
     22 		return -1;
     23 	}
     24 
     25 	if (n < 0)
     26 		return 0;
     27 
     28 	for (i = 1, ret = 1; i <= n; i++)
     29 		ret *= i;
     30 
     31 	return ret;
     32 }
     33 
     34 STATIC bool
     35 isperm(uint8_t *a, int64_t n)
     36 {
     37 	int64_t i;
     38 	bool aux[FACTORIAL_MAX+1];
     39 
     40 	if (n > FACTORIAL_MAX) {
     41 		LOG("Error: won't compute 'isperm()' for n=%" PRId64 " because"
     42 		    " it is larger than %" PRId64 "\n", n, FACTORIAL_MAX);
     43 		return false;
     44 	}
     45 
     46 	memset(aux, false, n);
     47 	
     48 	for (i = 0; i < n; i++) {
     49 		if (a[i] >= n)
     50 			return false;
     51 		else
     52 			aux[a[i]] = true;
     53 	}
     54 
     55 	for (i = 0; i < n; i++)
     56 		if (!aux[i])
     57 			return false;
     58 
     59 	return true;
     60 }
     61 
     62 STATIC int64_t
     63 permtoindex(uint8_t *a, int64_t n)
     64 {
     65 	int64_t i, j, c, ret;
     66 
     67 	if (n > FACTORIAL_MAX) {
     68 		LOG("Error: won't compute 'permtoindex()' for n=%" PRId64
     69 		    " because it is larger than %" PRId64 "\n",
     70 		    n, FACTORIAL_MAX);
     71 		return -1;
     72 	}
     73 
     74 	if (!isperm(a, n))
     75 		return -1;
     76 
     77 	for (i = 0, ret = 0; i < n; i++) {
     78 		for (j = i+1, c = 0; j < n; j++)
     79 			c += (a[i] > a[j]) ? 1 : 0;
     80 		ret += factorial(n-i-1) * c;
     81 	}
     82 
     83 	return ret;
     84 }
     85 
     86 STATIC void
     87 indextoperm(int64_t p, int64_t n, uint8_t *r)
     88 {
     89 	int64_t i, j, c;
     90 	uint8_t a[FACTORIAL_MAX+1];
     91 
     92 	if (n > FACTORIAL_MAX) {
     93 		LOG("Error: won't compute 'permtoindex()' for n=%" PRId64
     94 		    " because it is larger than %" PRId64 "\n",
     95 		    n, FACTORIAL_MAX);
     96 		goto indextoperm_error;
     97 	}
     98 
     99 	memset(a, 0, n);
    100 
    101 	if (p < 0 || p >= factorial(n))
    102 		goto indextoperm_error;
    103 
    104 	for (i = 0; i < n; i++) {
    105 		for (j = 0, c = 0; c <= p / factorial(n-i-1); j++)
    106 			c += a[j] ? 0 : 1;
    107 		r[i] = j-1;
    108 		a[j-1] = 1;
    109 		p %= factorial(n-i-1);
    110 	}
    111 
    112 	if (!isperm(r, n))
    113 		goto indextoperm_error;
    114 
    115 	return;
    116 
    117 indextoperm_error:
    118 	memset(r, UINT8_ERROR, n);
    119 }
    120 
    121 STATIC int
    122 permsign(uint8_t *a, int64_t n)
    123 {
    124 	int i, j;
    125 	uint8_t ret;
    126 
    127 	for (i = 0, ret = 0; i < n; i++)
    128 		for (j = i+1; j < n; j++)
    129 			ret += a[i] > a[j] ? 1 : 0;
    130 
    131 	return ret % 2;
    132 }
    133 
    134 STATIC int64_t
    135 digitstosumzero(uint8_t *a, uint8_t n, uint8_t b)
    136 {
    137 	int64_t ret, p;
    138 	uint8_t i, sum;
    139 
    140 	if (!((n == 8 && b == 3 ) || (n == 12 && b == 2))) {
    141 		LOG("Won't compute 'sumzero' for n=%" PRIu8 "and b=%" PRIu8
    142 		    " (use n=8 b=3 or n=12 b=2)\n", n, b);
    143 		return -1;
    144 	}
    145 
    146 	for (i = 1, ret = 0, p = 1, sum = 0; i < n; i++, p *= (int64_t)b) {
    147 		if (a[i] >= b) {
    148 			LOG("Error: digit %" PRIu8 " larger than maximum"
    149 			    " (b=%" PRIu8 "\n", a[i], b);
    150 			return -1;
    151 		}
    152 		sum += a[i];
    153 		ret += p * (int64_t)a[i];
    154 	}
    155 
    156 	if ((sum + a[0]) % b != 0) {
    157 		LOG("Error: digits do not have sum zero modulo b\n");
    158 		return -1;
    159 	}
    160 
    161 	return ret;
    162 }
    163 
    164 STATIC void
    165 sumzerotodigits(int64_t d, uint8_t n, uint8_t b, uint8_t *a)
    166 {
    167 	uint8_t sum;
    168 	int64_t i;
    169 
    170 	if (!((n == 8 && b == 3 ) || (n == 12 && b == 2))) {
    171 		LOG("Won't compute 'digits' for n=%" PRIu8 "and b=%" PRIu8
    172 		    " (use n=8 b=3 or n=12 b=2)\n");
    173 		goto digitstosumzero_error;
    174 	}
    175 
    176 	for (i = 1, sum = 0; i < n; i++, d /= (int64_t)b) {
    177 		a[i] = (uint8_t)(d % (int64_t)b);
    178 		sum += a[i];
    179 	}
    180 	a[0] = (b - (sum % b)) % b;
    181 
    182 	return;
    183 
    184 digitstosumzero_error:
    185 	memset(a, UINT8_ERROR, n);
    186 }