From 5fb58d73581256c64d47250c5544d1cbf22f79c3 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 5 Jul 2024 19:23:58 +0200 Subject: Added more math utilities --- TODO.txt | 5 ++ src/utils.h | 58 +++++++++++++++++++++- test/013_math_digitstosumzero/00_bad_n.in | 5 ++ test/013_math_digitstosumzero/00_bad_n.out | 1 + test/013_math_digitstosumzero/01_bad_b12.in | 14 ++++++ test/013_math_digitstosumzero/01_bad_b12.out | 1 + test/013_math_digitstosumzero/02_bad_b8.in | 10 ++++ test/013_math_digitstosumzero/02_bad_b8.out | 1 + test/013_math_digitstosumzero/03_zero12.in | 14 ++++++ test/013_math_digitstosumzero/03_zero12.out | 1 + test/013_math_digitstosumzero/04_zero8.in | 10 ++++ test/013_math_digitstosumzero/04_zero8.out | 1 + test/013_math_digitstosumzero/05_max12.in | 14 ++++++ test/013_math_digitstosumzero/05_max12.out | 1 + test/013_math_digitstosumzero/06_max8.in | 10 ++++ test/013_math_digitstosumzero/06_max8.out | 1 + test/013_math_digitstosumzero/07_random12.in | 14 ++++++ test/013_math_digitstosumzero/07_random12.out | 1 + test/013_math_digitstosumzero/08_random8.in | 10 ++++ test/013_math_digitstosumzero/08_random8.out | 1 + test/013_math_digitstosumzero/09_sumnonzero.in | 10 ++++ test/013_math_digitstosumzero/09_sumnonzero.out | 1 + .../digitstosumzero_tests.c | 21 ++++++++ test/014_math_sumzerotodigits/00_bad_n.in | 3 ++ test/014_math_sumzerotodigits/00_bad_n.out | 13 +++++ test/014_math_sumzerotodigits/01_bad_b12.in | 3 ++ test/014_math_sumzerotodigits/01_bad_b12.out | 12 +++++ test/014_math_sumzerotodigits/02_bad_b8.in | 3 ++ test/014_math_sumzerotodigits/02_bad_b8.out | 8 +++ test/014_math_sumzerotodigits/03_zero12.in | 3 ++ test/014_math_sumzerotodigits/03_zero12.out | 12 +++++ test/014_math_sumzerotodigits/04_zero8.in | 3 ++ test/014_math_sumzerotodigits/04_zero8.out | 8 +++ test/014_math_sumzerotodigits/05_max12.in | 3 ++ test/014_math_sumzerotodigits/05_max12.out | 12 +++++ test/014_math_sumzerotodigits/06_max8.in | 3 ++ test/014_math_sumzerotodigits/06_max8.out | 8 +++ test/014_math_sumzerotodigits/07_random12.in | 3 ++ test/014_math_sumzerotodigits/07_random12.out | 12 +++++ test/014_math_sumzerotodigits/08_random8.in | 3 ++ test/014_math_sumzerotodigits/08_random8.out | 8 +++ test/014_math_sumzerotodigits/sumzerotodigits.c | 21 ++++++++ 42 files changed, 345 insertions(+), 1 deletion(-) create mode 100644 test/013_math_digitstosumzero/00_bad_n.in create mode 100644 test/013_math_digitstosumzero/00_bad_n.out create mode 100644 test/013_math_digitstosumzero/01_bad_b12.in create mode 100644 test/013_math_digitstosumzero/01_bad_b12.out create mode 100644 test/013_math_digitstosumzero/02_bad_b8.in create mode 100644 test/013_math_digitstosumzero/02_bad_b8.out create mode 100644 test/013_math_digitstosumzero/03_zero12.in create mode 100644 test/013_math_digitstosumzero/03_zero12.out create mode 100644 test/013_math_digitstosumzero/04_zero8.in create mode 100644 test/013_math_digitstosumzero/04_zero8.out create mode 100644 test/013_math_digitstosumzero/05_max12.in create mode 100644 test/013_math_digitstosumzero/05_max12.out create mode 100644 test/013_math_digitstosumzero/06_max8.in create mode 100644 test/013_math_digitstosumzero/06_max8.out create mode 100644 test/013_math_digitstosumzero/07_random12.in create mode 100644 test/013_math_digitstosumzero/07_random12.out create mode 100644 test/013_math_digitstosumzero/08_random8.in create mode 100644 test/013_math_digitstosumzero/08_random8.out create mode 100644 test/013_math_digitstosumzero/09_sumnonzero.in create mode 100644 test/013_math_digitstosumzero/09_sumnonzero.out create mode 100644 test/013_math_digitstosumzero/digitstosumzero_tests.c create mode 100644 test/014_math_sumzerotodigits/00_bad_n.in create mode 100644 test/014_math_sumzerotodigits/00_bad_n.out create mode 100644 test/014_math_sumzerotodigits/01_bad_b12.in create mode 100644 test/014_math_sumzerotodigits/01_bad_b12.out create mode 100644 test/014_math_sumzerotodigits/02_bad_b8.in create mode 100644 test/014_math_sumzerotodigits/02_bad_b8.out create mode 100644 test/014_math_sumzerotodigits/03_zero12.in create mode 100644 test/014_math_sumzerotodigits/03_zero12.out create mode 100644 test/014_math_sumzerotodigits/04_zero8.in create mode 100644 test/014_math_sumzerotodigits/04_zero8.out create mode 100644 test/014_math_sumzerotodigits/05_max12.in create mode 100644 test/014_math_sumzerotodigits/05_max12.out create mode 100644 test/014_math_sumzerotodigits/06_max8.in create mode 100644 test/014_math_sumzerotodigits/06_max8.out create mode 100644 test/014_math_sumzerotodigits/07_random12.in create mode 100644 test/014_math_sumzerotodigits/07_random12.out create mode 100644 test/014_math_sumzerotodigits/08_random8.in create mode 100644 test/014_math_sumzerotodigits/08_random8.out create mode 100644 test/014_math_sumzerotodigits/sumzerotodigits.c diff --git a/TODO.txt b/TODO.txt index b625e12..abcefc8 100644 --- 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 index 0c0b4d1..3d35437 100644 --- 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 new file mode 100644 index 0000000..edcdc1b --- /dev/null +++ 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 new file mode 100644 index 0000000..3a2e3f4 --- /dev/null +++ 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 new file mode 100644 index 0000000..26bb819 --- /dev/null +++ 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 new file mode 100644 index 0000000..3a2e3f4 --- /dev/null +++ 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 new file mode 100644 index 0000000..146d291 --- /dev/null +++ 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 new file mode 100644 index 0000000..3a2e3f4 --- /dev/null +++ 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 new file mode 100644 index 0000000..8afbb56 --- /dev/null +++ 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 new file mode 100644 index 0000000..573541a --- /dev/null +++ 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 new file mode 100644 index 0000000..a49222d --- /dev/null +++ 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 new file mode 100644 index 0000000..573541a --- /dev/null +++ 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 new file mode 100644 index 0000000..5daa5b0 --- /dev/null +++ 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 new file mode 100644 index 0000000..b6ac305 --- /dev/null +++ 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 new file mode 100644 index 0000000..d2a9333 --- /dev/null +++ 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 new file mode 100644 index 0000000..fdc6491 --- /dev/null +++ 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 new file mode 100644 index 0000000..44bb31d --- /dev/null +++ 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 new file mode 100644 index 0000000..a5c3fde --- /dev/null +++ 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 new file mode 100644 index 0000000..1d97656 --- /dev/null +++ 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 new file mode 100644 index 0000000..3ffc420 --- /dev/null +++ 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 new file mode 100644 index 0000000..9466f9a --- /dev/null +++ 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 new file mode 100644 index 0000000..3a2e3f4 --- /dev/null +++ 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 new file mode 100644 index 0000000..f28c02a --- /dev/null +++ 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 new file mode 100644 index 0000000..5e34db5 --- /dev/null +++ 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 new file mode 100644 index 0000000..f9c0ae0 --- /dev/null +++ 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 new file mode 100644 index 0000000..8a6d31c --- /dev/null +++ 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 new file mode 100644 index 0000000..32b57e3 --- /dev/null +++ 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 new file mode 100644 index 0000000..b70bee9 --- /dev/null +++ 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 new file mode 100644 index 0000000..22d5f76 --- /dev/null +++ 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 new file mode 100644 index 0000000..e1d53ea --- /dev/null +++ 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 new file mode 100644 index 0000000..66f4ca4 --- /dev/null +++ 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 new file mode 100644 index 0000000..db46735 --- /dev/null +++ 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 new file mode 100644 index 0000000..405d334 --- /dev/null +++ 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 new file mode 100644 index 0000000..c688648 --- /dev/null +++ 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 new file mode 100644 index 0000000..4dff9ef --- /dev/null +++ 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 new file mode 100644 index 0000000..4d1df80 --- /dev/null +++ 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 new file mode 100644 index 0000000..a3ad9a2 --- /dev/null +++ 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 new file mode 100644 index 0000000..99af582 --- /dev/null +++ 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 new file mode 100644 index 0000000..2230573 --- /dev/null +++ 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 new file mode 100644 index 0000000..b392c81 --- /dev/null +++ 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 new file mode 100644 index 0000000..cb68c56 --- /dev/null +++ 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 new file mode 100644 index 0000000..5bea7ca --- /dev/null +++ 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]); +} -- cgit v1.3