Back to index

wims  3.65+svn20090927
cryptarith.c
Go to the documentation of this file.
00001 /*    Copyright (C) 1998-2003 XIAO, Gang of Universite de Nice - Sophia Antipolis
00002  *
00003  *  This program is free software; you can redistribute it and/or modify
00004  *  it under the terms of the GNU General Public License as published by
00005  *  the Free Software Foundation; either version 2 of the License, or
00006  *  (at your option) any later version.
00007  *
00008  *  This program is distributed in the hope that it will be useful,
00009  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00010  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00011  *  GNU General Public License for more details.
00012  *
00013  *  You should have received a copy of the GNU General Public License
00014  *  along with this program; if not, write to the Free Software
00015  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00016  */
00017 
00018  /* Solves cryptarithms, to be interfaced by wims. */
00019 
00020 #define MAX_LINES 64
00021 #define MAX_CHARS 32
00022 
00023 #include "../wims.h"
00024 
00025 char basetab[MAX_LINES][MAX_CHARS];
00026 int carry[MAX_LINES][MAX_CHARS+8];
00027 char corresp[32],bcorresp[16];
00028 int linecnt,charcnt[MAX_LINES],activelen,maxlen;
00029 int active[MAX_LINES];
00030 int style[MAX_LINES];
00031 int total=0;
00032 
00033 char *input;
00034 
00035        /* Print the result */
00036 void printresult(char curr[])
00037 {
00038     int i,j;
00039     char ch;
00040     for(i=0;i<linecnt;i++) {
00041        for(j=0;j<charcnt[i];j++) {
00042            ch=basetab[i][j];
00043            if(ch==0) ch=' ';
00044            else if(ch>='A' && ch<='Z') ch=curr[ch-'A'];
00045            printf(" %d",ch);
00046        }
00047        printf("\n");
00048     }
00049     printf("\n");
00050 }
00051 
00052        /* returns 1 if OK, 0 if bad. */
00053 int putvalue(char ch, char k, char curr[], char currb[])
00054 {
00055     int i=ch-'A';
00056     if(ch==0) {
00057        if(k>0) return 0; else return 1;
00058     }
00059     if((curr[i]!=-1 && curr[i]!=k) || (currb[k]!=0 && currb[k]!=ch))
00060       return 0;
00061     curr[i]=k;currb[k]=ch; return 1;
00062 }
00063 
00064        /* check that leading number is not 0. Returns 0 if bad. */
00065 int checklead(char curr[])
00066 {
00067     int i;
00068     char ch;
00069     for(i=0;i<linecnt;i++) {
00070        ch=basetab[i][charcnt[i]-1];
00071        if(curr[ch-'A']<=0) return 0;
00072     }
00073     return 1;
00074 }
00075 
00076        /* returns 0 if fail, 1 if OK. */
00077 int colcompute(int c,char curr[],char currb[])
00078 {
00079     int i,j,k,sum;
00080     char ch;
00081 
00082     switch(style[1]) {
00083        case '-':
00084        case '+':
00085        case '.': {
00086            for(j=sum=0;j<linecnt;j++) {
00087               if(!active[j]) continue;
00088               ch=basetab[j][c];
00089               if(ch!=0) {
00090                   if(style[j]!='-') sum+=curr[ch-'A'];
00091                   else sum-=curr[ch-'A'];
00092               }
00093            }
00094            lastline:
00095            sum+=carry[linecnt-1][c];
00096            carry[linecnt-1][c+1]=(sum+10000)/10-1000; k=(sum+10000)%10;
00097            return putvalue(basetab[linecnt-1][c],k,curr,currb);
00098        }
00099        
00100        case '*': {
00101            char c1,c2;
00102            c2=basetab[0][c];
00103            if(c2!=0) c2=curr[c2-'A'];
00104            for(i=0;i<c && i<linecnt-3;i++) {
00105               c1=basetab[1][i];
00106               if(c2*c1!=0) sum=c2*curr[c1-'A']+carry[2+i][c];
00107               else sum=carry[2+i][c];
00108               carry[2+i][c+1]=sum/10;
00109               if(!putvalue(basetab[2+i][c],sum%10,curr,currb))
00110                 return 0;
00111            }
00112            c2=basetab[1][c];
00113            if(c2!=0) {
00114               c2=curr[c2-'A'];
00115               for(i=0;i<=c;i++) {
00116                   c1=basetab[0][i];
00117                   if(c1==0) break;
00118                   sum=c2*curr[c1-'A']+carry[2+c][i];
00119                   carry[2+c][i+1]=sum/10;
00120                   if(!putvalue(basetab[2+c][i],sum%10,curr,currb))
00121                     return 0;
00122               }
00123            }
00124            for(i=sum=0;i<=c && i<linecnt-3;i++) {
00125               ch=basetab[2+i][c-i];
00126               if(ch!=0) sum+=curr[ch-'A'];
00127            }
00128            goto lastline;
00129        }
00130        
00131               /* short multiplication */
00132        case '$': {
00133            char c1,c2;
00134            for(j=sum=0;j<=c;j++) {
00135               c1=basetab[0][j]; c2=basetab[1][c-j];
00136               if(c1==0) break;
00137               if(c2==0) continue;
00138               sum+=curr[c1-'A']*curr[c2-'A'];
00139            }
00140            goto lastline;
00141        }
00142        
00143        
00144        default: return 0;
00145     }
00146 }
00147 
00148 void column(int c, char prev[], char prevb[])
00149 {
00150     char curr[32], currb[16];
00151     int lreg[MAX_LINES],lfix[MAX_LINES];
00152     int i,j,icarry;
00153     char ch;
00154 
00155     memset(lreg,0,sizeof(lreg));
00156     memset(lfix,0,sizeof(lfix));
00157 
00158     for(i=0;i<linecnt;i++) {
00159        if(!active[i]) continue;
00160        ch=basetab[i][c]; 
00161        if(ch==0 || prev[ch-'A']!=-1) lfix[i]=1;
00162     }
00163     for(icarry=0;;icarry=1) {
00164        memmove(curr,prev,sizeof(curr));
00165        memmove(currb,prevb,sizeof(currb));
00166        for(i=0;i<linecnt;i++) {
00167            if(!active[i] || lfix[i]) continue;
00168            for(j=lreg[i]+icarry;j<10 && prevb[j]!=0;j++);
00169            if(j>=10) {
00170               for(j=0;j<10 && prevb[j]!=0;j++);
00171               if(j>=10) return;
00172               icarry=1;
00173            }
00174            else icarry=0;
00175            lreg[i]=j;
00176        }
00177        if(icarry) break;
00178        for(i=0;i<linecnt;i++) {
00179            if(!active[i] || lfix[i]) continue;
00180            if(!putvalue(basetab[i][c],lreg[i],curr,currb)) goto loopend;
00181        }
00182        if(!colcompute(c,curr,currb)) continue;
00183        if(c<activelen-1) column(c+1,curr,currb);
00184        else {
00185            for(i=activelen;i<maxlen;i++) {
00186               if(!colcompute(i,curr,currb)) goto loopend;
00187            }
00188            for(i=0;i<linecnt;i++) {
00189               if(active[i]) continue;
00190               if(carry[i][maxlen]) goto loopend;
00191            }
00192            if(!checklead(curr)) goto loopend;
00193            total++;
00194            printresult(curr);
00195        }
00196        loopend:
00197     }
00198 }
00199 
00200 int main(int argc, char *argv[])
00201 {
00202     char *p,*p2,*p3;
00203     int i;
00204     input=getenv("wims_exec_parm");
00205        /* nothing to do if no problem */
00206     if(input==NULL || *input==0) return 0;
00207 
00208     memset(basetab,0,sizeof(basetab));
00209     memset(corresp,-1,sizeof(corresp));
00210     memset(bcorresp,0,sizeof(bcorresp));
00211     memset(carry,0,sizeof(carry));
00212     memset(active,0,sizeof(active));
00213 
00214     for(p=input+strlen(input);p>input && isspace(*(p-1));p--);
00215     *p=0;
00216     activelen=maxlen=0;
00217     active[0]=active[1]=1;
00218     for(linecnt=0,p=input;*p!=0 && linecnt<MAX_LINES;p=p3) {
00219        p2=strchr(p,'\n');
00220        if(p2==NULL) {
00221            p2=p+strlen(p);p3=p2;
00222        }
00223        else p3=p2+1;
00224        while(isspace(*p)) p++;
00225        if(strchr("+-*/=.",*p)!=NULL) {
00226            style[linecnt]=*p;p++;
00227            while(isspace(*p)) p++;
00228        }
00229        else style[linecnt]='+';
00230        if(*p3==0) style[linecnt]='=';
00231        if(linecnt>1) {
00232            switch(style[1]) {
00233               case '+':
00234               case '-': {
00235                   if(*p3!=0) active[linecnt]=1;
00236                   break;
00237               }
00238               
00239               case '*':
00240               case '/':
00241               case '=':
00242               break;
00243            }
00244        }
00245        while(p2>p && isspace(*(p2-1))) p2--;
00246        if(p2>p+MAX_CHARS) p2=p+MAX_CHARS;
00247        *p2=0;
00248        if(p2<=p) continue;
00249        for(i=0;i<p2-p;i++) {
00250            char ch;
00251            ch=toupper(*(p2-i-1));
00252               /* bad char */
00253            if(ch<'A' || ch>'Z') return 1;
00254            basetab[linecnt][i]=ch;
00255        }
00256        charcnt[linecnt]=p2-p;
00257        if(active[linecnt] && p2-p>activelen) activelen=p2-p;
00258        if(p2-p>maxlen) maxlen=p2-p;
00259        linecnt++;
00260     }
00261        /* multiplication */
00262     if(style[1]=='*') {
00263        if(linecnt==3) style[1]='$';
00264        else {
00265            if(linecnt!=charcnt[1]+3) return 1;
00266            for(i=3;i<linecnt-1;i++)
00267              if(charcnt[i]+i-2>maxlen) maxlen=charcnt[i]+i-2;
00268        }
00269     }
00270 
00271     column(0,corresp,bcorresp);
00272 printf("\n!total %d solution(s).\n\n",total);
00273     return 0;
00274 }
00275