Guest User

PSE Pre-alpha calculator (Variant)

a guest
Apr 6th, 2017
74
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <stdint.h>
  5. #include <ctype.h>
  6.  
  7. #include <omp.h>
  8.  
  9. #define BITS (1u << 21)
  10. #define MAX (BITS * 8)
  11.  
  12. #define LEN 14
  13.  
  14.  
  15.  
  16. static void eval_r(int64_t *val,
  17.     size_t nval, size_t i, int64_t res, uint8_t *set)
  18. {
  19.     if (i == nval) {
  20.         if (res >= 0 && res <= MAX) {
  21.             int m = res / 8;
  22.             int j = res % 8;
  23.  
  24.             set[m] |= (1u << j);
  25.         }
  26.     } else {
  27.         if (i == 0) {
  28.             eval_r(val, nval, i + 1, *val, set);
  29.         } else {            
  30.             eval_r(val, nval, i + 1, res + val[i], set);
  31.             eval_r(val, nval, i + 1, res - val[i], set);
  32.             eval_r(val, nval, i + 1, res * val[i], set);
  33.             if (res % val[i] == 0) {
  34.                 eval_r(val, nval, i + 1, res / val[i], set);
  35.             }
  36.         }
  37.     }
  38. }
  39.  
  40. static void eval(const char *str, int n, uint8_t *set)
  41. {
  42.     const char *end = str + n;
  43.     int64_t val[5];
  44.     size_t nval = 0;
  45.    
  46.     while (str < end) {
  47.         int64_t x = 0;
  48.        
  49.         while (str < end && isdigit(*str)) {
  50.             x = x * 10 + *str++ - '0';
  51.         }
  52.        
  53.         val[nval++] = x;        
  54.         str++;
  55.     }
  56.    
  57.     eval_r(val, nval, 0, 0, set);
  58. }
  59.  
  60. static void swap(char *str, int i, int j)
  61. {
  62.     char s = str[i]; str[i] = str[j]; str[j] = s;
  63. }
  64.  
  65. static void permute(char *str, int n, uint8_t *set)
  66. {
  67.     int op = (str[n - 1] == '#');
  68.     int i;
  69.     int hash = 0;
  70.    
  71.     if (!op) {
  72.         eval(str, n, set);
  73.     }
  74.  
  75.     for (i = n; i < LEN; i++) {
  76.         if (!op || isdigit(str[i])) {
  77.             if (op && str[i] == '0') continue;
  78.            
  79.             if (str[i] == '#') {
  80.                 if (hash) continue;
  81.                 hash = 1;
  82.             }
  83.  
  84.             swap(str, i, n);
  85.             permute(str, n + 1, set);
  86.             swap(str, i, n);
  87.         }
  88.     }
  89. }
  90.  
  91. int main(void)
  92. {
  93.     int mthread = omp_get_max_threads();
  94.     uint8_t *set[mthread];
  95.     int m = 0;
  96.     int i;
  97.    
  98.     fprintf(stderr, "Maximum number of threads: %d\n", mthread);
  99.    
  100.     for (i = 0; i < mthread; i++) set[i] = NULL;
  101.  
  102.     #pragma omp parallel
  103.     {
  104.         int nthread = omp_get_num_threads();
  105.         int ithread = omp_get_thread_num();
  106.         int n;
  107.  
  108.         set[ithread] = calloc(1, BITS);
  109.         set[ithread][0] = 1;
  110.  
  111.         #pragma omp for
  112.         for (n = 1; n < 90; n++) {
  113.             char pool[] = "0123456789####";
  114.  
  115.             swap(pool, 0, 1 + n / 10);
  116.             swap(pool, 1, 1 + n % 10);
  117.  
  118.             fprintf(stderr,
  119.                 "Exploring %c%c... on thread %d/%d.\n",
  120.                 pool[0], pool[1], ithread, nthread);
  121.  
  122.             permute(pool, 2, set[ithread]);
  123.         }
  124.     }
  125.    
  126.     {    
  127.         int nthread = 0;
  128.        
  129.         while (nthread < mthread && set[nthread]) nthread++;
  130.  
  131.         for (i = 0; i < BITS; i++) {
  132.             uint8_t mask = 0u;
  133.             int k;
  134.  
  135.             for (k = 0; k < nthread; k++) {
  136.                 mask |= set[k][i];
  137.             }
  138.  
  139.             for (k = 0; k < 8; k++) {
  140.                 if ((mask & (1u << k)) == 0) {
  141.                     printf("%d\n", m);
  142.                 }
  143.                 m++;
  144.             }
  145.         }
  146.  
  147.         for (i = 0; i < nthread; i++) free(set[i]);
  148.     }    
  149.    
  150.     return 0;
  151. }
RAW Paste Data