commit 5fb58d73581256c64d47250c5544d1cbf22f79c3 parent 518d98ad5f9eec0cf4124375bdbb84d1296b3f3f Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri, 5 Jul 2024 19:23:58 +0200 Added more math utilities Diffstat:
42 files changed, 345 insertions(+), 1 deletion(-)
diff --git a/TODO.txt b/TODO.txt @@ -3,6 +3,8 @@ Check stats for all tables using H48stats solver x implement stuff in utils.h x implement functions x unit tests for permtoindex and indextoperm + x implement digit array to sumzero and inverse + x unit tests for digit arra to sumzero x move cubefromarray from cube_io to where needed (cube_generic) - implement in cube_generic x getcube_fix @@ -60,6 +62,9 @@ Improvements small things - maybe move part of the logic for coord_h48 (and its inverse) to utils.h (subsettoindex-like) + - rename TYPE build switch to something more intuitive like ARCH + remove one of TYPE and CUBE_TYPE (why do I have two?) + - merge constants and utils? ## H48 optimal solver (some has already been implemented) diff --git a/src/utils.h b/src/utils.h @@ -3,6 +3,8 @@ _static bool isperm(uint8_t *, int64_t); _static int64_t permtoindex(uint8_t *, int64_t); _static void indextoperm(int64_t, int64_t, uint8_t *); _static int permsign(uint8_t *, int64_t); +_static int64_t digitstosumzero(uint8_t *, uint8_t, uint8_t); +_static void sumzerotodigits(int64_t, uint8_t, uint8_t, uint8_t *); _static int64_t factorial(int64_t n) @@ -39,7 +41,7 @@ isperm(uint8_t *a, int64_t n) memset(aux, false, n); for (i = 0; i < n; i++) { - if (a[i] < 0 || a[i] >= n) + if (a[i] >= n) return false; else aux[a[i]] = true; @@ -123,3 +125,57 @@ permsign(uint8_t *a, int64_t n) return ret % 2; } + +_static int64_t +digitstosumzero(uint8_t *a, uint8_t n, uint8_t b) +{ + int64_t ret, p; + uint8_t i, sum; + + if (!((n == 8 && b == 3 ) || (n == 12 && b == 2))) { + LOG("Won't compute 'sumzero' for n=%" PRIu8 "and b=%" PRIu8 + " (use n=8 b=3 or n=12 b=2)\n", n, b); + return -1; + } + + for (i = 1, ret = 0, p = 1; i < n; i++, p *= (int64_t)b) { + if (a[i] >= b) { + LOG("Error: digit %" PRIu8 " larger than maximum" + " (b=%" PRIu8 "\n", a[i], b); + return -1; + } + sum += a[i]; + ret += p * (int64_t)a[i]; + } + + if ((sum + a[0]) % b != 0) { + LOG("Error: digits do not have sum zero modulo b\n"); + return -1; + } + + return ret; +} + +_static void +sumzerotodigits(int64_t d, uint8_t n, uint8_t b, uint8_t *a) +{ + uint8_t sum; + int64_t i; + + if (!((n == 8 && b == 3 ) || (n == 12 && b == 2))) { + LOG("Won't compute 'digits' for n=%" PRIu8 "and b=%" PRIu8 + " (use n=8 b=3 or n=12 b=2)\n"); + goto digitstosumzero_error; + } + + for (i = 1; i < n; i++, d /= (int64_t)b) { + a[i] = (uint8_t)(d % (int64_t)b); + sum += a[i]; + } + a[0] = (b - (sum % b)) % b; + + return; + +digitstosumzero_error: + memset(a, _error, n); +} diff --git a/test/013_math_digitstosumzero/00_bad_n.in b/test/013_math_digitstosumzero/00_bad_n.in @@ -0,0 +1,5 @@ +3 +4 +0 +1 +0 diff --git a/test/013_math_digitstosumzero/00_bad_n.out b/test/013_math_digitstosumzero/00_bad_n.out @@ -0,0 +1 @@ +-1 diff --git a/test/013_math_digitstosumzero/01_bad_b12.in b/test/013_math_digitstosumzero/01_bad_b12.in @@ -0,0 +1,14 @@ +12 +3 +0 +1 +2 +0 +1 +2 +2 +1 +0 +0 +0 +1 diff --git a/test/013_math_digitstosumzero/01_bad_b12.out b/test/013_math_digitstosumzero/01_bad_b12.out @@ -0,0 +1 @@ +-1 diff --git a/test/013_math_digitstosumzero/02_bad_b8.in b/test/013_math_digitstosumzero/02_bad_b8.in @@ -0,0 +1,10 @@ +8 +2 +0 +0 +0 +0 +0 +0 +0 +1 diff --git a/test/013_math_digitstosumzero/02_bad_b8.out b/test/013_math_digitstosumzero/02_bad_b8.out @@ -0,0 +1 @@ +-1 diff --git a/test/013_math_digitstosumzero/03_zero12.in b/test/013_math_digitstosumzero/03_zero12.in @@ -0,0 +1,14 @@ +12 +2 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 diff --git a/test/013_math_digitstosumzero/03_zero12.out b/test/013_math_digitstosumzero/03_zero12.out @@ -0,0 +1 @@ +0 diff --git a/test/013_math_digitstosumzero/04_zero8.in b/test/013_math_digitstosumzero/04_zero8.in @@ -0,0 +1,10 @@ +8 +3 +0 +0 +0 +0 +0 +0 +0 +0 diff --git a/test/013_math_digitstosumzero/04_zero8.out b/test/013_math_digitstosumzero/04_zero8.out @@ -0,0 +1 @@ +0 diff --git a/test/013_math_digitstosumzero/05_max12.in b/test/013_math_digitstosumzero/05_max12.in @@ -0,0 +1,14 @@ +12 +2 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 diff --git a/test/013_math_digitstosumzero/05_max12.out b/test/013_math_digitstosumzero/05_max12.out @@ -0,0 +1 @@ +2047 diff --git a/test/013_math_digitstosumzero/06_max8.in b/test/013_math_digitstosumzero/06_max8.in @@ -0,0 +1,10 @@ +8 +3 +1 +2 +2 +2 +2 +2 +2 +2 diff --git a/test/013_math_digitstosumzero/06_max8.out b/test/013_math_digitstosumzero/06_max8.out @@ -0,0 +1 @@ +2186 diff --git a/test/013_math_digitstosumzero/07_random12.in b/test/013_math_digitstosumzero/07_random12.in @@ -0,0 +1,14 @@ +12 +2 +0 +1 +0 +1 +0 +1 +1 +1 +0 +1 +0 +0 diff --git a/test/013_math_digitstosumzero/07_random12.out b/test/013_math_digitstosumzero/07_random12.out @@ -0,0 +1 @@ +373 diff --git a/test/013_math_digitstosumzero/08_random8.in b/test/013_math_digitstosumzero/08_random8.in @@ -0,0 +1,10 @@ +8 +3 +1 +1 +0 +2 +0 +0 +0 +2 diff --git a/test/013_math_digitstosumzero/08_random8.out b/test/013_math_digitstosumzero/08_random8.out @@ -0,0 +1 @@ +1477 diff --git a/test/013_math_digitstosumzero/09_sumnonzero.in b/test/013_math_digitstosumzero/09_sumnonzero.in @@ -0,0 +1,10 @@ +8 +3 +1 +2 +1 +1 +1 +1 +2 +2 diff --git a/test/013_math_digitstosumzero/09_sumnonzero.out b/test/013_math_digitstosumzero/09_sumnonzero.out @@ -0,0 +1 @@ +-1 diff --git a/test/013_math_digitstosumzero/digitstosumzero_tests.c b/test/013_math_digitstosumzero/digitstosumzero_tests.c @@ -0,0 +1,21 @@ +#include "../test.h" + +int64_t digitstosumzero(uint8_t *, uint8_t, uint8_t); + +void run(void) { + char str[STRLENMAX]; + uint8_t i, n, b, a[100]; + int64_t p; + + fgets(str, STRLENMAX, stdin); + n = atoi(str); + fgets(str, STRLENMAX, stdin); + b = atoi(str); + for (i = 0; i < n; i++) { + fgets(str, STRLENMAX, stdin); + a[i] = atoi(str); + } + + p = digitstosumzero(a, n, b); + printf("%" PRId64 "\n", p); +} diff --git a/test/014_math_sumzerotodigits/00_bad_n.in b/test/014_math_sumzerotodigits/00_bad_n.in @@ -0,0 +1,3 @@ +13 +4 +2 diff --git a/test/014_math_sumzerotodigits/00_bad_n.out b/test/014_math_sumzerotodigits/00_bad_n.out @@ -0,0 +1,13 @@ +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 diff --git a/test/014_math_sumzerotodigits/01_bad_b12.in b/test/014_math_sumzerotodigits/01_bad_b12.in @@ -0,0 +1,3 @@ +12 +3 +2 diff --git a/test/014_math_sumzerotodigits/01_bad_b12.out b/test/014_math_sumzerotodigits/01_bad_b12.out @@ -0,0 +1,12 @@ +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 +255 diff --git a/test/014_math_sumzerotodigits/02_bad_b8.in b/test/014_math_sumzerotodigits/02_bad_b8.in @@ -0,0 +1,3 @@ +8 +7 +0 diff --git a/test/014_math_sumzerotodigits/02_bad_b8.out b/test/014_math_sumzerotodigits/02_bad_b8.out @@ -0,0 +1,8 @@ +255 +255 +255 +255 +255 +255 +255 +255 diff --git a/test/014_math_sumzerotodigits/03_zero12.in b/test/014_math_sumzerotodigits/03_zero12.in @@ -0,0 +1,3 @@ +12 +2 +0 diff --git a/test/014_math_sumzerotodigits/03_zero12.out b/test/014_math_sumzerotodigits/03_zero12.out @@ -0,0 +1,12 @@ +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 diff --git a/test/014_math_sumzerotodigits/04_zero8.in b/test/014_math_sumzerotodigits/04_zero8.in @@ -0,0 +1,3 @@ +8 +3 +0 diff --git a/test/014_math_sumzerotodigits/04_zero8.out b/test/014_math_sumzerotodigits/04_zero8.out @@ -0,0 +1,8 @@ +0 +0 +0 +0 +0 +0 +0 +0 diff --git a/test/014_math_sumzerotodigits/05_max12.in b/test/014_math_sumzerotodigits/05_max12.in @@ -0,0 +1,3 @@ +12 +2 +2047 diff --git a/test/014_math_sumzerotodigits/05_max12.out b/test/014_math_sumzerotodigits/05_max12.out @@ -0,0 +1,12 @@ +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 diff --git a/test/014_math_sumzerotodigits/06_max8.in b/test/014_math_sumzerotodigits/06_max8.in @@ -0,0 +1,3 @@ +8 +3 +2186 diff --git a/test/014_math_sumzerotodigits/06_max8.out b/test/014_math_sumzerotodigits/06_max8.out @@ -0,0 +1,8 @@ +1 +2 +2 +2 +2 +2 +2 +2 diff --git a/test/014_math_sumzerotodigits/07_random12.in b/test/014_math_sumzerotodigits/07_random12.in @@ -0,0 +1,3 @@ +12 +2 +373 diff --git a/test/014_math_sumzerotodigits/07_random12.out b/test/014_math_sumzerotodigits/07_random12.out @@ -0,0 +1,12 @@ +0 +1 +0 +1 +0 +1 +1 +1 +0 +1 +0 +0 diff --git a/test/014_math_sumzerotodigits/08_random8.in b/test/014_math_sumzerotodigits/08_random8.in @@ -0,0 +1,3 @@ +8 +3 +1477 diff --git a/test/014_math_sumzerotodigits/08_random8.out b/test/014_math_sumzerotodigits/08_random8.out @@ -0,0 +1,8 @@ +1 +1 +0 +2 +0 +0 +0 +2 diff --git a/test/014_math_sumzerotodigits/sumzerotodigits.c b/test/014_math_sumzerotodigits/sumzerotodigits.c @@ -0,0 +1,21 @@ +#include "../test.h" + +void sumzerotodigits(int64_t, uint8_t, uint8_t, uint8_t *); + +void run(void) { + char str[STRLENMAX]; + uint8_t i, n, b, a[100]; + int64_t d; + + fgets(str, STRLENMAX, stdin); + n = atoi(str); + fgets(str, STRLENMAX, stdin); + b = atoi(str); + fgets(str, STRLENMAX, stdin); + d = atoll(str); + + sumzerotodigits(d, n, b, a); + + for (i = 0; i < n; i++) + printf("%" PRIu8 "\n", a[i]); +}