Subversion Repositories wimsdev

Rev

Rev 8185 | Go to most recent revision | 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 "../wims.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.        
  144.         default: return 0;
  145.     }
  146. }
  147.  
  148. void column(int c, char prev[], char prevb[])
  149. {
  150.     char curr[32], currb[16];
  151.     int lreg[MAX_LINES],lfix[MAX_LINES];
  152.     int i,j,icarry;
  153.     char ch;
  154.  
  155.     memset(lreg,0,sizeof(lreg));
  156.     memset(lfix,0,sizeof(lfix));
  157.  
  158.     for(i=0;i<linecnt;i++) {
  159.         if(!active[i]) continue;
  160.         ch=basetab[i][c];
  161.         if(ch==0 || prev[ch-'A']!=-1) lfix[i]=1;
  162.     }
  163.     for(icarry=0;;icarry=1) {
  164.         memmove(curr,prev,sizeof(curr));
  165.         memmove(currb,prevb,sizeof(currb));
  166.         for(i=0;i<linecnt;i++) {
  167.             if(!active[i] || lfix[i]) continue;
  168.             for(j=lreg[i]+icarry;j<10 && prevb[j]!=0;j++);
  169.             if(j>=10) {
  170.                 for(j=0;j<10 && prevb[j]!=0;j++);
  171.                 if(j>=10) return;
  172.                 icarry=1;
  173.             }
  174.             else icarry=0;
  175.             lreg[i]=j;
  176.         }
  177.         if(icarry) break;
  178.         for(i=0;i<linecnt;i++) {
  179.             if(!active[i] || lfix[i]) continue;
  180.             if(!putvalue(basetab[i][c],lreg[i],curr,currb)) goto loopend;
  181.         }
  182.         if(!colcompute(c,curr,currb)) continue;
  183.         if(c<activelen-1) column(c+1,curr,currb);
  184.         else {
  185.             for(i=activelen;i<maxlen;i++) {
  186.                 if(!colcompute(i,curr,currb)) goto loopend;
  187.             }
  188.             for(i=0;i<linecnt;i++) {
  189.                 if(active[i]) continue;
  190.                 if(carry[i][maxlen]) goto loopend;
  191.             }
  192.             if(!checklead(curr)) goto loopend;
  193.             total++;
  194.             printresult(curr);
  195.         }
  196.         loopend:
  197.     }
  198. }
  199.  
  200. int main(int argc, char *argv[])
  201. {
  202.     char *p,*p2,*p3;
  203.     int i;
  204.     input=getenv("wims_exec_parm");
  205.         /* nothing to do if no problem */
  206.     if(input==NULL || *input==0) return 0;
  207.  
  208.     memset(basetab,0,sizeof(basetab));
  209.     memset(corresp,-1,sizeof(corresp));
  210.     memset(bcorresp,0,sizeof(bcorresp));
  211.     memset(carry,0,sizeof(carry));
  212.     memset(active,0,sizeof(active));
  213.  
  214.     for(p=input+strlen(input);p>input && isspace(*(p-1));p--);
  215.     *p=0;
  216.     activelen=maxlen=0;
  217.     active[0]=active[1]=1;
  218.     for(linecnt=0,p=input;*p!=0 && linecnt<MAX_LINES;p=p3) {
  219.         p2=strchr(p,'\n');
  220.         if(p2==NULL) {
  221.             p2=p+strlen(p);p3=p2;
  222.         }
  223.         else p3=p2+1;
  224.         while(isspace(*p)) p++;
  225.         if(strchr("+-*/=.",*p)!=NULL) {
  226.             style[linecnt]=*p;p++;
  227.             while(isspace(*p)) p++;
  228.         }
  229.         else style[linecnt]='+';
  230.         if(*p3==0) style[linecnt]='=';
  231.         if(linecnt>1) {
  232.             switch(style[1]) {
  233.                 case '+':
  234.                 case '-': {
  235.                     if(*p3!=0) active[linecnt]=1;
  236.                     break;
  237.                 }
  238.                
  239.                 case '*':
  240.                 case '/':
  241.                 case '=':
  242.                 break;
  243.             }
  244.         }
  245.         while(p2>p && isspace(*(p2-1))) p2--;
  246.         if(p2>p+MAX_CHARS) p2=p+MAX_CHARS;
  247.         *p2=0;
  248.         if(p2<=p) continue;
  249.         for(i=0;i<p2-p;i++) {
  250.             char ch;
  251.             ch=toupper(*(p2-i-1));
  252.                 /* bad char */
  253.             if(ch<'A' || ch>'Z') return 1;
  254.             basetab[linecnt][i]=ch;
  255.         }
  256.         charcnt[linecnt]=p2-p;
  257.         if(active[linecnt] && p2-p>activelen) activelen=p2-p;
  258.         if(p2-p>maxlen) maxlen=p2-p;
  259.         linecnt++;
  260.     }
  261.         /* multiplication */
  262.     if(style[1]=='*') {
  263.         if(linecnt==3) style[1]='$';
  264.         else {
  265.             if(linecnt!=charcnt[1]+3) return 1;
  266.             for(i=3;i<linecnt-1;i++)
  267.               if(charcnt[i]+i-2>maxlen) maxlen=charcnt[i]+i-2;
  268.         }
  269.     }
  270.  
  271.     column(0,corresp,bcorresp);
  272. printf("\n!total %d solution(s).\n\n",total);
  273.     return 0;
  274. }
  275.  
  276.