Subversion Repositories wimsdev

Rev

Rev 8185 | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. /*    Copyright (C) 1998-2003 XIAO, Gang of Universite de Nice - Sophia Antipolis
  2.  *
  3.  *  This program is free software; you can redistribute it and/or modify
  4.  *  it under the terms of the GNU General Public License as published by
  5.  *  the Free Software Foundation; either version 2 of the License, or
  6.  *  (at your option) any later version.
  7.  *
  8.  *  This program is distributed in the hope that it will be useful,
  9.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.  *  GNU General Public License for more details.
  12.  *
  13.  *  You should have received a copy of the GNU General Public License
  14.  *  along with this program; if not, write to the Free Software
  15.  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16.  */
  17.  
  18.  /* Solves cryptarithms, to be interfaced by wims. */
  19.  
  20. #define MAX_LINES 64
  21. #define MAX_CHARS 32
  22.  
  23. #include "../includes.h"
  24.  
  25. char basetab[MAX_LINES][MAX_CHARS];
  26. int carry[MAX_LINES][MAX_CHARS+8];
  27. char corresp[32],bcorresp[16];
  28. int linecnt,charcnt[MAX_LINES],activelen,maxlen;
  29. int active[MAX_LINES];
  30. int style[MAX_LINES];
  31. int total=0;
  32.  
  33. char *input;
  34.  
  35. /* Print the result */
  36. void printresult(char curr[])
  37. {
  38.   int i,j;
  39.   char ch;
  40.   for(i=0;i<linecnt;i++) {
  41.     for(j=0;j<charcnt[i];j++) {
  42.       ch=basetab[i][j];
  43.       if(ch==0) ch=' ';
  44.       else if(ch>='A' && ch<='Z') ch=curr[ch-'A'];
  45.       printf(" %d",ch);
  46.     }
  47.     printf("\n");
  48.   }
  49.   printf("\n");
  50. }
  51.  
  52. /* returns 1 if OK, 0 if bad. */
  53. int putvalue(char ch, char k, char curr[], char currb[])
  54. {
  55.   int i=ch-'A';
  56.   if(ch==0) {
  57.     if(k>0) return 0; else return 1;
  58.   }
  59.   if((curr[i]!=-1 && curr[i]!=k) || (currb[k]!=0 && currb[k]!=ch))
  60.     return 0;
  61.   curr[i]=k;currb[k]=ch; return 1;
  62. }
  63.  
  64. /* check that leading number is not 0. Returns 0 if bad. */
  65. int checklead(char curr[])
  66. {
  67.   int i;
  68.   char ch;
  69.   for(i=0;i<linecnt;i++) {
  70.     ch=basetab[i][charcnt[i]-1];
  71.     if(curr[ch-'A']<=0) return 0;
  72.   }
  73.   return 1;
  74. }
  75.  
  76. /* returns 0 if fail, 1 if OK. */
  77. int colcompute(int c,char curr[],char currb[])
  78. {
  79.   int i,j,k,sum;
  80.   char ch;
  81.  
  82.   switch(style[1]) {
  83.     case '-':
  84.     case '+':
  85.     case '.': {
  86.       for(j=sum=0;j<linecnt;j++) {
  87.         if(!active[j]) continue;
  88.         ch=basetab[j][c];
  89.         if(ch!=0) {
  90.           if(style[j]!='-') sum+=curr[ch-'A'];
  91.           else sum-=curr[ch-'A'];
  92.         }
  93.       }
  94.       lastline:
  95.       sum+=carry[linecnt-1][c];
  96.       carry[linecnt-1][c+1]=(sum+10000)/10-1000; k=(sum+10000)%10;
  97.       return putvalue(basetab[linecnt-1][c],k,curr,currb);
  98.     }
  99.  
  100.     case '*': {
  101.       char c1,c2;
  102.       c2=basetab[0][c];
  103.       if(c2!=0) c2=curr[c2-'A'];
  104.       for(i=0;i<c && i<linecnt-3;i++) {
  105.         c1=basetab[1][i];
  106.         if(c2*c1!=0) sum=c2*curr[c1-'A']+carry[2+i][c];
  107.         else sum=carry[2+i][c];
  108.         carry[2+i][c+1]=sum/10;
  109.         if(!putvalue(basetab[2+i][c],sum%10,curr,currb))
  110.           return 0;
  111.       }
  112.       c2=basetab[1][c];
  113.       if(c2!=0) {
  114.         c2=curr[c2-'A'];
  115.         for(i=0;i<=c;i++) {
  116.           c1=basetab[0][i];
  117.           if(c1==0) break;
  118.           sum=c2*curr[c1-'A']+carry[2+c][i];
  119.           carry[2+c][i+1]=sum/10;
  120.           if(!putvalue(basetab[2+c][i],sum%10,curr,currb))
  121.             return 0;
  122.         }
  123.       }
  124.       for(i=sum=0;i<=c && i<linecnt-3;i++) {
  125.           ch=basetab[2+i][c-i];
  126.           if(ch!=0) sum+=curr[ch-'A'];
  127.       }
  128.       goto lastline;
  129.     }
  130.  
  131. /* short multiplication */
  132.     case '$': {
  133.       char c1,c2;
  134.       for(j=sum=0;j<=c;j++) {
  135.         c1=basetab[0][j]; c2=basetab[1][c-j];
  136.         if(c1==0) break;
  137.         if(c2==0) continue;
  138.         sum+=curr[c1-'A']*curr[c2-'A'];
  139.       }
  140.       goto lastline;
  141.     }
  142.  
  143.     default: return 0;
  144.   }
  145. }
  146.  
  147. void column(int c, char prev[], char prevb[])
  148. {
  149.   char curr[32], currb[16];
  150.   int lreg[MAX_LINES],lfix[MAX_LINES];
  151.   int i,j,icarry;
  152.   char ch;
  153.  
  154.   memset(lreg,0,sizeof(lreg));
  155.   memset(lfix,0,sizeof(lfix));
  156.  
  157.   for(i=0;i<linecnt;i++) {
  158.     if(!active[i]) continue;
  159.     ch=basetab[i][c];
  160.     if(ch==0 || prev[ch-'A']!=-1) lfix[i]=1;
  161.   }
  162.   for(icarry=0;;icarry=1) {
  163.     memmove(curr,prev,sizeof(curr));
  164.     memmove(currb,prevb,sizeof(currb));
  165.     for(i=0;i<linecnt;i++) {
  166.       if(!active[i] || lfix[i]) continue;
  167.       for(j=lreg[i]+icarry;j<10 && prevb[j]!=0;j++);
  168.       if(j>=10) {
  169.         for(j=0;j<10 && prevb[j]!=0;j++);
  170.         if(j>=10) return;
  171.         icarry=1;
  172.       }
  173.       else icarry=0;
  174.       lreg[i]=j;
  175.     }
  176.     if(icarry) break;
  177.     for(i=0;i<linecnt;i++) {
  178.       if(!active[i] || lfix[i]) continue;
  179.       if(!putvalue(basetab[i][c],lreg[i],curr,currb)) goto loopend;
  180.     }
  181.     if(!colcompute(c,curr,currb)) continue;
  182.     if(c<activelen-1) column(c+1,curr,currb);
  183.     else {
  184.       for(i=activelen;i<maxlen;i++) {
  185.         if(!colcompute(i,curr,currb)) goto loopend;
  186.       }
  187.       for(i=0;i<linecnt;i++) {
  188.         if(active[i]) continue;
  189.         if(carry[i][maxlen]) goto loopend;
  190.       }
  191.       if(!checklead(curr)) goto loopend;
  192.       total++;
  193.       printresult(curr);
  194.     }
  195.     loopend:
  196.   }
  197. }
  198.  
  199. int main(int argc, char *argv[])
  200. {
  201.   char *p,*p2,*p3;
  202.   int i;
  203.   input=getenv("wims_exec_parm");
  204. /* nothing to do if no problem */
  205.   if(input==NULL || *input==0) return 0;
  206.  
  207.   memset(basetab,0,sizeof(basetab));
  208.   memset(corresp,-1,sizeof(corresp));
  209.   memset(bcorresp,0,sizeof(bcorresp));
  210.   memset(carry,0,sizeof(carry));
  211.   memset(active,0,sizeof(active));
  212.  
  213.   for(p=input+strlen(input);p>input && isspace(*(p-1));p--);
  214.   *p=0;
  215.   activelen=maxlen=0;
  216.   active[0]=active[1]=1;
  217.   for(linecnt=0,p=input;*p!=0 && linecnt<MAX_LINES;p=p3) {
  218.     p2=strchr(p,'\n');
  219.     if(p2==NULL) {
  220.       p2=p+strlen(p);p3=p2;
  221.     }
  222.     else p3=p2+1;
  223.     while(isspace(*p)) p++;
  224.     if(strchr("+-*/=.",*p)!=NULL) {
  225.       style[linecnt]=*p;p++;
  226.       while(isspace(*p)) p++;
  227.     }
  228.     else style[linecnt]='+';
  229.     if(*p3==0) style[linecnt]='=';
  230.     if(linecnt>1) {
  231.      switch(style[1]) {
  232.        case '+':
  233.        case '-': {
  234.         if(*p3!=0) active[linecnt]=1;
  235.         break;
  236.        }
  237.  
  238.        case '*':
  239.        case '/':
  240.        case '=':
  241.        break;
  242.     }
  243.   }
  244.   while(p2>p && isspace(*(p2-1))) p2--;
  245.   if(p2>p+MAX_CHARS) p2=p+MAX_CHARS;
  246.   *p2=0;
  247.   if(p2<=p) continue;
  248.   for(i=0;i<p2-p;i++) {
  249.     char ch;
  250.     ch=toupper(*(p2-i-1));
  251. /* bad char */
  252.     if(ch<'A' || ch>'Z') return 1;
  253.       basetab[linecnt][i]=ch;
  254.     }
  255.     charcnt[linecnt]=p2-p;
  256.     if(active[linecnt] && p2-p>activelen) activelen=p2-p;
  257.     if(p2-p>maxlen) maxlen=p2-p;
  258.     linecnt++;
  259.   }
  260. /* multiplication */
  261.   if(style[1]=='*') {
  262.     if(linecnt==3) style[1]='$';
  263.     else {
  264.       if(linecnt!=charcnt[1]+3) return 1;
  265.     for(i=3;i<linecnt-1;i++)
  266.       if(charcnt[i]+i-2>maxlen) maxlen=charcnt[i]+i-2;
  267.     }
  268.   }
  269.  
  270.   column(0,corresp,bcorresp);
  271.   printf("\n!total %d solution(s).\n\n",total);
  272.   return 0;
  273. }
  274.