Added more math utilities

42 files changed, 345 insertions, 1 deletions

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]);
+}