Guest User

PSE pre-aplha calculator (sequential)

a guest
Apr 6th, 2017
80
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. #define BITS (1 << 21)
  8. #define MAX (BITS * 8)
  9.  
  10. #define LEN 14
  11.  
  12. uint8_t *set;
  13.  
  14.  
  15.  
  16. static int64_t eval(const char *str, int n)
  17. {
  18.     const char *end = str + n;
  19.     int64_t res = 0;
  20.     int op= '+';
  21.    
  22.     while (str < end) {
  23.         int64_t x = 0;
  24.        
  25.         while (str < end && isdigit(*str)) {
  26.             x = x * 10 + *str++ - '0';
  27.         }
  28.        
  29.         switch (op) {
  30.             case '+':   res += x; break;
  31.             case '-':   res -= x; break;
  32.             case '*':   res *= x; break;
  33.             case '/':   if (x == 0) return -1;
  34.                         if (res % x) return -1;
  35.                         res /= x; break;
  36.         }
  37.        
  38.         if (res == 0) return -1;
  39.        
  40.         op = *str++;
  41.     }
  42.    
  43.     if (res < 0 || res >= MAX) return -1;    
  44.     return res;
  45. }
  46.  
  47. static void swap(char *str, int i, int j)
  48. {
  49.     char s = str[i]; str[i] = str[j]; str[j] = s;
  50. }
  51.  
  52. static void permute(char *str, int n)
  53. {
  54.     int op = n ? !isdigit(str[n - 1]) : 1;
  55.     int i;
  56.    
  57.     if (!op) {
  58.         int64_t e = eval(str, n);
  59.        
  60.         if (e >= 0) {
  61.             int m = e / 8;
  62.             int j = e % 8;
  63.  
  64.             if ((set[m] & (1u << j)) == 0) {
  65.                 if (0 && n < 5000000) printf("%ld == %.*s\n", e, n, str);
  66.                 set[m] |= (1u << j);
  67.             }
  68.         }
  69.     }
  70.  
  71.     for (i = n; i < LEN; i++) {
  72.         if (!op || isdigit(str[i])) {
  73.             if (op && str[i] == '0') continue;
  74.  
  75.             swap(str, i, n);
  76.             permute(str, n + 1);
  77.             swap(str, i, n);
  78.         }
  79.     }
  80. }
  81.  
  82. int main(void)
  83. {
  84.     char pool[] = "0123456789+-*/";
  85.     size_t n;
  86.  
  87.     set = calloc(1, BITS);
  88.     permute(pool, 0);
  89.    
  90.     for (n = 0; n < 5000000; n++) {
  91.         int m = n / 8;
  92.         int j = n % 8;
  93.        
  94.         if ((set[m] & (1u << j)) == 0) {
  95.             printf("%zu\n", n);
  96.         }
  97.     }
  98.    
  99.     free(set);
  100.    
  101.     return 0;
  102. }
RAW Paste Data