math.c

   1 /*
   2 Simple Numeric Operations
   3 (c) 1995 Martin Mares, MJSoft System Software
   4 */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8
   9 #define MAXSTEPS 9
  10 #define MAXNUM 5001
  11
  12 #define FIRSTUNARY 10
  13 #define NUMOPS 15
  14
  15 int able[MAXSTEPS+1][MAXNUM];
  16 int func[MAXSTEPS+1][MAXNUM];
  17 int op1[MAXSTEPS+1][MAXNUM];
  18 int op2[MAXSTEPS+1][MAXNUM];
  19 int op1l[MAXSTEPS+1][MAXNUM];
  20 int op2l[MAXSTEPS+1][MAXNUM];
  21 int max[MAXSTEPS+1];
  22 int penalty[MAXSTEPS+1][MAXNUM];
  23
  24 int maxdisp,digit,maxsteps,maxnum;
  25
  26 /*            0 1 2 3 4 5 6  7  8  9 10 1112  13  */
  27 #if 0
  28 int pen[] = { 1,1,2,2,6,3,60,30,60,6,4,20,3,150,150 };
  29 #else
  30 int pen[] = { 1,1,2,2,5,3,8 ,6 ,8 ,5,4,6 ,3,13 ,13  };
  31 #endif
  32 /*            + - * / % ^ @  C  $  \ ! S  R r   t   */
  33 int pri[] = { 2,2,3,3,4,5,3, 7, 3, 3,9,7, 7,7,  7   };
  34
  35 /* PRI == 7 <=> left-associative function with no priority */
  36
  37 int op(int code,int a,int b,int src1,int src2)
  38 {
  39 int i,j,k,l;
  40    switch(code)
  41            {
  42                 case 0: return a+b;
  43                 case 1: return a-b;
  44                 case 2: return a*b;
  45                 case 3: if (b && !(a%b)) return a/b; else return -1; /* DIV */
  46                 case 4: if (b) return a%b; else return -1;                        /* MODULO */
  47                 case 5: i=1;                                                                                                      /* POWER */
  48                                   while (b--)
  49                                      {
  50                                           i *= a;
  51                                           if (i >= maxnum) return -1;
  52                                           }
  53                                   return i;
  54                 case 6: if (!b || a%b || able[src2][b] != 2) return -1; /* A/.(B) */
  55                                   i=0;
  56                                   a/=b;
  57                                   while (b)
  58                                      {
  59                                           i=i*10+9;
  60                                           b/=10;
  61                                           }
  62                                   return a*i;
  63                 case 7: if (a < b) return -1;                                                                   /* COMBINATION */
  64                                   i=1; j=a; k=2; l=b;
  65                                   while (l || k<=b)
  66                                      {
  67                                           while (k<=b && !(i%k))
  68                                              {
  69                                                   i/=k;
  70                                                   k++;
  71                                                   }
  72                                           if (l)
  73                                              {
  74                                                   i*=j;
  75                                                   l--;
  76                                                   j--;
  77                                                   }
  78                                           if (i>100000) return -1;
  79                                           }
  80                                   return i;
  81                 case 8: if (!b || a%b || able[src2][b] != 2) return -1; /* A/.B */
  82                                   i=1;
  83                                   a/=b;
  84                                   while (b)
  85                                      {
  86                                           i=i*10;
  87                                           b/=10;
  88                                           }
  89                                   return a*i;
  90                 case 9: if (b) return a/b; else return -1;                              /* DIV */
  91                 case FIRSTUNARY: i=1;                                                                                   /* FACT */
  92                                   while (a)
  93                                      {
  94                                           i*=a;
  95                                           if (i >= maxnum) return -1;
  96                                           a--;
  97                                           }
  98                                   return i;
  99                 case FIRSTUNARY+1: if (a) return 1; else return 0;                      /* SIGNUM */
 100                 case FIRSTUNARY+2: for(i=0;i<maxnum;i++)                                                /* ROOT */
 101                            {
 102                                           j=i*i;
 103                                           if (j == a) return i;
 104                                           if (j > a) return -1;
 105                                           }
 106                                         return -1;
 107                 case FIRSTUNARY+3: for(i=0;i<maxnum;i++)                                                /* UPPER ROOT */
 108                            {
 109                                           j=i*i;
 110                                           if (j >= a) return i;
 111                                           }
 112                                   return -1;
 113                 case FIRSTUNARY+4: for(i=0;i<maxnum;i++)                                                /* LOWER ROOT */
 114                            {
 115                                           j=i*i;
 116                                           if (j == a) return i;
 117                                           if (j > a) return i-1;
 118                                           }
 119                                   return -1;
 120                 }
 121         return -1;
 122 }
 123
 124 int doop(int dest,int k,int i,int j,int src1,int src2,int p)
 125 {
 126 int l = op(k,i,j,src1,src2);
 127         if (l>=0 && l<maxnum)
 128            if (!able[dest][l] || penalty[dest][l] > p+pen[k])
 129            {
 130                 able[dest][l] = 1;
 131            func[dest][l] = k;
 132                 op1[dest][l] = i;
 133                 op1l[dest][l] = src1;
 134                 op2[dest][l] = j;
 135                 op2l[dest][l] = src2;
 136                 penalty[dest][l] = p+pen[k];
 137                 if (l > max[dest]) max[dest] = l;
 138                 return 1;
 139                 }
 140         return 0;
 141 }
 142
 143 void try(int dest,int src1,int src2)
 144 {
 145 int i,j,k,l;
 146         fprintf(stderr,"Trying %d %d -> %d\n",src1+1,src2+1,dest+1);
 147         l=0;
 148    for(i=0;i<=max[src1];i++)
 149            if (able[src1][i])
 150                         {
 151                         if (i-l>=10 || i<15) { fprintf(stderr,"%d\r",i); l=i; }
 152                    for(j=0;j<=max[src2];j++)
 153                            if (able[src2][j])
 154                                    for(k=0;k<FIRSTUNARY;k++)
 155                                                 doop(dest,k,i,j,src1,src2,penalty[src1][i]+penalty[src2][j]);
 156                         }
 157 }
 158
 159 void tryuna(int dest)
 160 {
 161 int i,j,k;
 162         fprintf(stderr,"Trying unary ops for level %d\n",dest+1);
 163         do
 164            {
 165         j=0;
 166            for(i=0;i<=max[dest];i++)
 167                    if (able[dest][i])
 168                                 for(k=FIRSTUNARY;k<NUMOPS;k++)
 169                                    if (doop(dest,k,i,0,dest,0,penalty[dest][i]))
 170                                            j=1;
 171                 }
 172         while (j);
 173 }
 174
 175 #ifdef SIMPLE_DUMP
 176
 177 void dump(int level,int i)
 178 {
 179    if (able[level][i] == 2) printf("%d",i);
 180         else if (func[level][i] < FIRSTUNARY)
 181            {
 182                 putchar('(');
 183                 dump(op1l[level][i],op1[level][i]);
 184                 putchar("+-*/%^@C$\\"[func[level][i]]);
 185                 dump(op2l[level][i],op2[level][i]);
 186                 putchar(')');
 187                 }
 188         else
 189            {
 190                 putchar("!SRrt"[func[level][i]-FIRSTUNARY]);
 191                 putchar('(');
 192                 dump(op1l[level][i],op1[level][i]);
 193                 putchar(')');
 194                 }
 195 }
 196
 197 #else
 198
 199 union par {
 200         int value;
 201         struct node *p;
 202         };
 203
 204 struct node {
 205         unsigned char op;
 206         union par a[2];
 207         };
 208
 209 #define OP_CONST 0xff
 210
 211 char *unam[] = {"sgn","sqr","ceil sqr","int sqr"};
 212
 213 struct node *firstfree;
 214
 215 struct node *obtain_node(void)
 216 {
 217 struct node *p;
 218         if (firstfree)
 219                 {
 220                 p=firstfree;
 221                 firstfree=p->a[0].p;
 222                 }
 223         else p=malloc(sizeof(struct node));
 224         return p;
 225 }
 226
 227 void free_node(struct node *p)
 228 {
 229         p->a[0].p = firstfree;
 230         firstfree=p;
 231 }
 232
 233 void free_tree(struct node *p)
 234 {
 235         if (p->op != OP_CONST)
 236                 {
 237                 free_tree(p->a[0].p);
 238                 if (p->op < FIRSTUNARY) free_tree(p->a[1].p);
 239                 }
 240         free_node(p);
 241 }
 242
 243 struct node *build_tree(int level,int i)
 244 {
 245 struct node *p = obtain_node();
 246         if (able[level][i] == 2)
 247                 {
 248                 p->op = OP_CONST;
 249                 p->a[0].value = i;
 250                 }
 251         else
 252                 {
 253                 p->op = func[level][i];
 254                 p->a[0].p = build_tree(op1l[level][i],op1[level][i]);
 255                 if (p->op < FIRSTUNARY)
 256                         p->a[1].p = build_tree(op2l[level][i],op2[level][i]);
 257                 }
 258         return p;
 259 }
 260
 261 void print_tree(struct node *n,int p,int orop)
 262 {
 263 int g,r;
 264         if (n->op == OP_CONST) printf("%d",n->a[0].value);
 265         else
 266                 {
 267                 g = (pri[n->op] < p
 268                     || (pri[n->op] == p &&
 269                                   (orop == 1 || orop == 3 || orop == 4 || orop == 6
 270                                              || orop == 8))
 271                         );
 272                 if (g) putchar('(');
 273                 r=pri[n->op];
 274                 if (r==7) r=0;
 275                 if (n->op <= 5)         /* standard binary */
 276                         {
 277                         print_tree(n->a[0].p,r,n->op);
 278                         putchar("+-*/%^"[n->op]);
 279                         print_tree(n->a[1].p,r,n->op);
 280                         }
 281                 else if (n->op == 6)            /* /.() */
 282                         {
 283                         print_tree(n->a[0].p,r,n->op);
 284                         printf("/.(");
 285                         print_tree(n->a[1].p,r,n->op);
 286                         putchar(')');
 287                         }
 288                 else if (n->op == 7)            /* COMB */
 289                         {
 290                         printf("C(");
 291                         print_tree(n->a[0].p,r,n->op);
 292                         putchar(',');
 293                         print_tree(n->a[1].p,r,n->op);
 294                         putchar(')');
 295                         }
 296                 else if (n->op == 8)            /* /. */
 297                         {
 298                         print_tree(n->a[0].p,r,n->op);
 299                         printf("/.");
 300                         print_tree(n->a[1].p,r,n->op);
 301                         }
 302                 else if (n->op == 9)            /* DIV */
 303                         {
 304                         print_tree(n->a[0].p,r,n->op);
 305                         putchar('\\');
 306                         print_tree(n->a[1].p,r,n->op);
 307                         }
 308                 else if (n->op == FIRSTUNARY)           /* FACT */
 309                         {
 310                         print_tree(n->a[0].p,r,n->op);
 311                         putchar('!');
 312                         }
 313                 else                                                                            /* classical prefix unary */
 314                         {
 315                         printf(unam[n->op-FIRSTUNARY-1]);
 316                         print_tree(n->a[0].p,255,255);
 317                         }
 318                 if (g) putchar(')');
 319                 }
 320 }
 321
 322 void dump(int level,int i)
 323 {
 324 struct node *root;
 325         root = build_tree(level,i);
 326         print_tree(root,0,-1);
 327         free_tree(root);
 328 }
 329
 330 #endif
 331
 332 void fillin(void)
 333 {
 334 int i,j;
 335         i=0;
 336         for(j=0;j<=maxsteps;j++)
 337                 {
 338                 i=i*10+digit;
 339                 if (i>=maxnum) return;
 340                 able[j][i]=2;
 341                 max[j]=i;
 342                 }
 343 }
 344
 345 void findall(void)
 346 {
 347 int steps,i;
 348         tryuna(0);
 349         for(steps=1;steps<=maxsteps;steps++)
 350            {
 351                 for(i=0;i<steps;i++)
 352                    try(steps,i,steps-i-1);
 353                 tryuna(steps);
 354                 }
 355 }
 356
 357 void prtall(void)
 358 {
 359 int steps,totb,i;
 360         putchar('\n');
 361         steps=0; totb=0;
 362         for(i=0;i<maxdisp;i++)
 363            if (able[maxsteps][i])
 364                    {
 365                         printf("%d = ",i);
 366                    dump(maxsteps,i);
 367                         printf("  {%d}\n",penalty[maxsteps][i]);
 368                         totb += penalty[maxsteps][i];
 369                         steps++;
 370                         }
 371                 else printf("%d : MISSING\n",i);
 372         printf("%d of %d. {%d}\n",steps,maxdisp,totb);
 373 }
 374
 375 void err(char *e)
 376 {
 377         fprintf(stderr,e);
 378         exit(1);
 379 }
 380
 381 int main(int argc,char **argv)
 382 {
 383         if (argc != 5)
 384                 {
 385                 printf("Usage: math <digit> <count> <limit> <calclimit>\n");
 386                 return 0;
 387                 }
 388         digit = atol(argv[1]);
 389         if (digit<0 || digit>9) err("Invalid digit!");
 390         maxsteps = atol(argv[2])-1;
 391         if (maxsteps<0 || maxsteps>MAXSTEPS) err("Invalid digit count!");
 392         maxdisp = atol(argv[3])+1;
 393         maxnum = atol(argv[4])+1;
 394         if (maxnum<1 || maxnum>MAXNUM) err("Invalid internal maximum!");
 395         if (maxdisp<1 || maxdisp>maxnum) err("Invalid limit!");
 396         fillin();
 397         findall();
 398         prtall();
 399         return 0;
 400 }