Subversion Repositories wimsdev

Rev

Rev 7676 | 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 "../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.  
  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.