diff options
| -rw-r--r-- | euler315.c | 128 | ||||
| -rw-r--r-- | euler90.c | 69 |
2 files changed, 197 insertions, 0 deletions
diff --git a/euler315.c b/euler315.c new file mode 100644 index 0000000..2d06cf4 --- /dev/null +++ b/euler315.c @@ -0,0 +1,128 @@ +#include <stdio.h> + +/* The digital root (also repeated digital sum) of a non-negative + * integer is the (single digit) value obtained by an iterative process + * of summing digits, on each iteration using the result from the previous + * iteration to compute a digit sum. The process continues until a + * single-digit number is reached. + */ + +/* bit 0-2: top, mid, bottom + * bit 3-6: top-left, top-right, bottom-left, bottom-right + */ + +enum { + TOP = 1, + MID = 2, + BOTTOM = 4, + TL = 8, + TR = 16, + BL = 32, + BR = 64 +}; + +unsigned char lines[10] = { + TOP | BOTTOM | TL | TR | BL | BR, + TR | BR, + TOP | MID | BOTTOM | TR | BL, + TOP | MID | BOTTOM | TR | BR, + MID | TL | TR | BR, + TOP | MID | BOTTOM | TL | BR, + TOP | MID | BOTTOM | TL | BL | BR, + TOP | TL | TR | BR, + TOP | MID | BOTTOM | TL | TR | BL | BR, + TOP | MID | BOTTOM | TL | TR | BR +}; + +int popcount(unsigned char x) +{ + int count = 0; + while (x) { + count += (x&1); + x >>= 1; + } + return count; +} + +void get_digits(int x, int a[]) +{ + int i = 0; + do { + a[i] = x % 10; + x /= 10; + i++; + } while (x); + a[i] = -1; +} + +int clock_sam(int x) +{ + int digits[10]; + int l = 0; + while (x >= 10) { + get_digits(x, digits); + x = 0; + for (int i = 0; digits[i] != -1; i++) { + l += popcount(lines[digits[i]]) * 2; + x += digits[i]; + } + } + l += popcount(lines[x]) * 2; + return l; +} + +int clock_max(int x) +{ + int digits[10],next_digits[10], nx; + int l = 0; + get_digits(x, digits); + nx = 0; + for (int i = 0; digits[i] != -1; i++) { + l += popcount(lines[digits[i]]); + nx += digits[i]; + } + while (x >= 10) { + get_digits(nx, next_digits); + int i; + /* calculate the diff */ + for (i = 0; next_digits[i] != -1; i++) { + l += popcount(lines[digits[i]]^lines[next_digits[i]]); + } + while (digits[i] != -1) { + l += popcount(lines[digits[i]]); + i++; + } + /* get the next */ + x = nx; + nx = 0; + for (i = 0; next_digits[i] != -1; i++) { + digits[i] = next_digits[i]; + nx += next_digits[i]; + } + digits[i] = -1; + } + l += popcount(lines[x]); + return l; +} + +int isoddprime(int x) +{ + for (int i = 3; i*i <= x; i += 2) { + if (x % i == 0) + return 0; + } + return 1; +} + +int main() +{ + int sum = 0; + const int A = 10*1000*1000; + const int B = 20*1000*1000; + for (int i = A+1; i < B; i += 2) { + if (isoddprime(i)) { + sum += clock_sam(i) - clock_max(i); + } + } + printf("%d\n", sum); +} diff --git a/euler90.c b/euler90.c new file mode 100644 index 0000000..b514269 --- /dev/null +++ b/euler90.c @@ -0,0 +1,69 @@ +#include <stdio.h> +#include <string.h> +#include <assert.h> + +char dices[210][6]; + +#define FOR(i) for (a[i] = a[i-1]+1; a[i] < 10; a[i]++) + +void init() +{ + char a[6]; + int k = 0; + for (a[0] = 0; a[0] < 10; a[0]++) { + FOR(1) { + FOR(2) { + FOR(3) { + FOR(4) { + FOR(5) { + memcpy(dices[k], a, sizeof(a)); + k++; + } + } + } + } + } + } + assert(k == 210); +} + +int matches(char c, char dic[]) +{ + for (int i = 0; i < 6; i++) { + if (c == dic[i] || + ((c == 6 || c== 9) && (dic[i] == 6 || dic[i] == 9))) + return 1; + } + return 0; +} + +int ok(int x, int y) +{ + const char sqrs[9][2] = { + {0, 1}, {0, 4}, {0, 9}, {1, 6}, {2, 5}, {3, 6}, {4, 9}, + {6, 4}, {8, 1} + }; + for (int i = 0; i < 9; i++) { + if (matches(sqrs[i][0], dices[x]) + && matches(sqrs[i][1], dices[y])) + continue; + if (matches(sqrs[i][0], dices[y]) + && matches(sqrs[i][1], dices[x])) + continue; + return 0; + } + return 1; +} + +int main() +{ + int count = 0; + init(); + for (int i = 0; i < 210; i++) { + for (int j = i+1; j < 210; j++) { + if (ok(i, j)) + count++; + } + } + printf("%d\n", count); +} |