fork(3) download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <limits.h>
  5.  
  6. void pis(int *is, int size) {
  7.   int i;
  8.   for (i = 0; i < size; i++) printf("%d ", is[i]);
  9.   puts("");
  10. }
  11. int fact(int n) {
  12.   int i, fact = 1;
  13.   for (i = 1; i <= n; i++) fact *= i;
  14.   return fact;
  15. }
  16. int count_permutations(int n, int r) {return fact(n) / fact(n - r);}
  17. int count_combinations(int n, int r) {return count_permutations(n, r) / fact(r);}
  18.  
  19.  
  20. struct nruis {int n, r, size, cap, *is; unsigned int *uis;};
  21. void push_int(struct nruis *p, int value) {
  22.   if (p && p->size + 1 <= p->cap) p->uis[p->size++] = value;
  23. }
  24. void comb(struct nruis *p, int need, int chosen, int at) {
  25.   if (!p || p->n < need + at) return;
  26.   if (!need) {
  27.     push_int(p, chosen);
  28.     return;
  29.   }
  30.   comb(p, need - 1, chosen | (1 << at), at + 1);
  31.   comb(p, need, chosen, at + 1);
  32. }
  33. struct nruis *create_combinations(int n, int r) {
  34.   if (sizeof (unsigned int) * CHAR_BIT < n) return 0;
  35.   if (n < r) return 0;
  36.   struct nruis *p = malloc(sizeof (struct nruis));
  37.   p->n = n;p->r = r;p->size = 0;
  38.   p->cap = count_combinations(n, r);
  39.   p->is = malloc(sizeof (int) * r);
  40.   p->uis = malloc(sizeof (unsigned int) * p->cap);
  41.   comb(p, r, 0, 0);
  42.   return p;
  43. }
  44. void delete_nruis(struct nruis *p) {
  45.   if (p) {
  46.     free(p->uis);
  47.     free(p->is);
  48.     free(p);
  49.   }
  50. }
  51. struct nruis *ui2is(struct nruis *p, unsigned int ui) {
  52.   int i = 0, j;
  53.   if (p) for (j = 0; j < p->n; j++) if (ui & (1 << j)) p->is[i++] = j;
  54.   return p;
  55. }
  56. void pnruis(struct nruis *p) {
  57.   int i;
  58.   if (p) for (i = 0; i < p->size; i++) pis(ui2is(p, p->uis[i])->is, p->r);
  59. }
  60.  
  61.  
  62. #define DIGIT_MASK 0xFull
  63. #define DIGIT_MASK_WIDTH 4
  64. struct nulls {int n, size, cap, *is; unsigned long long *ulls;};
  65. struct nulls *ull2is(struct nulls *p, unsigned long long value) {
  66.   int i;
  67.   if (p) for (i = 0; i < p->n; i++) p->is[i] = (value >> DIGIT_MASK_WIDTH * i) & DIGIT_MASK;
  68.   return p;
  69. }
  70. unsigned long long is2ull(struct nulls *p) {
  71.   int i;
  72.   unsigned long long value = 0;
  73.   if (p) for (i = 0; i < p->n; i++) value |= (unsigned long long)p->is[i] << DIGIT_MASK_WIDTH * i;
  74.   return value;
  75. }
  76. #undef DIGIT_MASK
  77. #undef DIGIT_MASK_WIDTH
  78. void push_current_buff(struct nulls *p) {
  79.   if (p && p->size + 1 <= p->cap) p->ulls[p->size++] = is2ull(p);
  80. }
  81. void permute(struct nulls *p, int l, int r) {
  82.   int i, tmp;
  83.   if (!p) return;
  84.   else if (l == r) push_current_buff(p);
  85.   else {
  86.     for (i = l; i <= r; i++) {
  87. #define SWAP(t, p, q) (t = *(p), *(p) = *(q), *(q) = t)
  88.       SWAP(tmp, p->is + l, p->is + i);
  89.       permute(p, l + 1, r);
  90.       SWAP(tmp, p->is + l, p->is + i);
  91. #undef SWAP
  92.     }
  93.   }
  94. }
  95. #define DIGIT_MAX 15
  96. struct nulls *create_permutations(int n) {
  97.   if (n < 1 || DIGIT_MAX + 1 < n) return 0;
  98.   int i;
  99.   struct nulls *p = malloc(sizeof (struct nulls));
  100.   p->n = n;p->size = 0;
  101.   p->cap = count_permutations(n, n);
  102.   p->is = malloc(sizeof (int) * n);
  103.   for (i = 0; i < n; i++) p->is[i] = i;
  104.   p->ulls = malloc(sizeof (unsigned long long) * p->cap);
  105.   permute(p, 0, n-1);
  106.   return p;
  107. }
  108. #undef DIGIT_MAX
  109. void delete_nulls(struct nulls *p) {
  110.   if (p) {
  111.     free(p->ulls);
  112.     free(p->is);
  113.     free(p);
  114.   }
  115. }
  116. void pnulls(struct nulls *p) {
  117.   int i;
  118.   if (p) for (i = 0; i < p->size; i++) pis(ull2is(p, p->ulls[i])->is, p->n);
  119. }
  120.  
  121.  
  122. struct pool {int *nums, **ps, n_ps;};
  123. struct pool *create_pool(const char *cs) {
  124.   struct pool *pool = 0;
  125.   int counts[128] = {0}, i, len = strlen(cs), n_alpha = 0, **p;
  126.   for (i = 0; i < len; i++) counts[cs[i]]++;
  127.   for (i = 0; i < 128; i++) if (counts[i] && isalpha(i)) n_alpha++;
  128.   pool = malloc(sizeof (struct pool));
  129.   pool->nums = malloc(sizeof (int) * 128);
  130.   pool->ps = malloc(sizeof (int *) * n_alpha);
  131.   pool->n_ps = n_alpha;
  132.   for (i = 0, p = pool->ps; i < 128; i++) if (counts[i] && isalpha(i)) *p++ = &pool->nums[i];
  133.   return pool;
  134. }
  135. void delete_pool(struct pool *p) {
  136.   if (p) {
  137.     free(p->ps);
  138.     free(p->nums);
  139.     free(p);
  140.   }
  141. }
  142. void p(struct pool *pool) {
  143.   int i;
  144.   for (i = 0; i < pool->n_ps; i++) printf("%d: %d\n", i, *pool->ps[i]);
  145. }
  146. int cs2i(const char *cs, struct pool *pool) {
  147.   int i, len = strlen(cs), j = 1, ret = 0;
  148.   for (i = 0; i < len; i++) {
  149.     ret += pool->nums[cs[len - 1 - i]] * j;
  150.     j *= 10;
  151.   }
  152.   return ret;
  153. }
  154. struct pool *create_pool3(const char *a, const char *b, const char *c) {
  155.   char *buff = malloc(strlen(a) + strlen(b) + strlen(c) + 1);
  156.   sprintf(buff, "%s%s%s", a, b, c);
  157.   struct pool *pool = create_pool(buff);
  158.   free(buff);
  159.   return pool;
  160. }
  161. void f440(const char *a, int (*op)(int, int), const char *b, const char *c) {
  162.   struct pool *pool = create_pool3(a, b, c);
  163.   struct nruis *combinations = create_combinations(10, pool->n_ps);
  164.   struct nulls *permutations = create_permutations(pool->n_ps);
  165.   int i, j, k;
  166.   printf("%s\t%s\t%s\n", a, b, c);
  167.   for (i = 0; i < combinations->size; i++) {
  168.     ui2is(combinations, combinations->uis[i]);
  169.     for (j = 0; j < permutations->size; j++) {
  170.       ull2is(permutations, permutations->ulls[j]);
  171.       for (k = 0; k < pool->n_ps; k++) *pool->ps[k] = combinations->is[permutations->is[k]];
  172.       if (pool->nums[*a] == 0 || pool->nums[*b] == 0 || pool->nums[*c] == 0) continue;
  173.  
  174.       if (op(cs2i(a, pool), cs2i(b, pool)) == cs2i(c, pool)) {
  175. 	printf("%d\t%d\t%d\n", cs2i(a, pool), cs2i(b, pool), cs2i(c, pool));
  176.       }
  177.     }
  178.   }
  179.   puts("");
  180.   delete_nulls(permutations);
  181.   delete_nruis(combinations);
  182.   delete_pool(pool);
  183. }
  184. int add(int a, int b) {return a + b;}
  185. int sub(int a, int b) {return a - b;}
  186. int main() {
  187.   f440("SEND", add, "MORE", "MONEY");
  188.   f440("WWWDOT", sub, "GOOGLE", "DOTCOM");
  189.   return 0;
  190. }
  191.  
Success #stdin #stdout 0.87s 2248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
SEND	MORE	MONEY
9567	1085	10652

WWWDOT	GOOGLE	DOTCOM
777589	188103	589486
777589	188106	589483
https://ideone.com/WQrzaa
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!