Logo Search packages:      
Sourcecode: wims version File versions  Download package

cryptarith.c

/*    Copyright (C) 1998 XIAO, Gang of Universite de Nice - Sophia Antipolis
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

 /* Solves cryptarithms, to be interfaced by wims. */

#define MAX_LINES 64
#define MAX_CHARS 32

#include "../wims.h"

char basetab[MAX_LINES][MAX_CHARS];
int carry[MAX_LINES][MAX_CHARS+8];
char corresp[32],bcorresp[16];
int linecnt,charcnt[MAX_LINES],activelen,maxlen;
int active[MAX_LINES];
int style[MAX_LINES];
int total=0;

char *input;

      /* Print the result */
void printresult(char curr[])
{
    int i,j;
    char ch;
    for(i=0;i<linecnt;i++) {
      for(j=0;j<charcnt[i];j++) {
          ch=basetab[i][j];
          if(ch==0) ch=' ';
          else if(ch>='A' && ch<='Z') ch=curr[ch-'A'];
          printf(" %d",ch);
      }
      printf("\n");
    }
    printf("\n");
}

      /* returns 1 if OK, 0 if bad. */
int putvalue(char ch, char k, char curr[], char currb[])
{
    int i=ch-'A';
    if(ch==0) {
      if(k>0) return 0; else return 1;
    }
    if((curr[i]!=-1 && curr[i]!=k) || (currb[k]!=0 && currb[k]!=ch))
      return 0;
    curr[i]=k;currb[k]=ch; return 1;
}

      /* check that leading number is not 0. Returns 0 if bad. */
int checklead(char curr[])
{
    int i;
    char ch;
    for(i=0;i<linecnt;i++) {
      ch=basetab[i][charcnt[i]-1];
      if(curr[ch-'A']<=0) return 0;
    }
    return 1;
}

      /* returns 0 if fail, 1 if OK. */
int colcompute(int c,char curr[],char currb[])
{
    int i,j,k,sum;
    char ch;

    switch(style[1]) {
      case '-':
      case '+':
      case '.': {
          for(j=sum=0;j<linecnt;j++) {
            if(!active[j]) continue;
            ch=basetab[j][c];
            if(ch!=0) {
                if(style[j]!='-') sum+=curr[ch-'A'];
                else sum-=curr[ch-'A'];
            }
          }
          lastline:
          sum+=carry[linecnt-1][c];
          carry[linecnt-1][c+1]=(sum+10000)/10-1000; k=(sum+10000)%10;
          return putvalue(basetab[linecnt-1][c],k,curr,currb);
      }
      
      case '*': {
          char c1,c2;
          c2=basetab[0][c];
          if(c2!=0) c2=curr[c2-'A'];
          for(i=0;i<c && i<linecnt-3;i++) {
            c1=basetab[1][i];
            if(c2*c1!=0) sum=c2*curr[c1-'A']+carry[2+i][c];
            else sum=carry[2+i][c];
            carry[2+i][c+1]=sum/10;
            if(!putvalue(basetab[2+i][c],sum%10,curr,currb))
              return 0;
          }
          c2=basetab[1][c];
          if(c2!=0) {
            c2=curr[c2-'A'];
            for(i=0;i<=c;i++) {
                c1=basetab[0][i];
                if(c1==0) break;
                sum=c2*curr[c1-'A']+carry[2+c][i];
                carry[2+c][i+1]=sum/10;
                if(!putvalue(basetab[2+c][i],sum%10,curr,currb))
                  return 0;
            }
          }
          for(i=sum=0;i<=c && i<linecnt-3;i++) {
            ch=basetab[2+i][c-i];
            if(ch!=0) sum+=curr[ch-'A'];
          }
          goto lastline;
      }
      
            /* short multiplication */
      case '$': {
          char c1,c2;
          for(j=sum=0;j<=c;j++) {
            c1=basetab[0][j]; c2=basetab[1][c-j];
            if(c1==0) break;
            if(c2==0) continue;
            sum+=curr[c1-'A']*curr[c2-'A'];
          }
          goto lastline;
      }
      
      
      default: return 0;
    }
}

void column(int c, char prev[], char prevb[])
{
    char curr[32], currb[16];
    int lreg[MAX_LINES],lfix[MAX_LINES];
    int i,j,icarry;
    char ch;

    memset(lreg,0,sizeof(lreg));
    memset(lfix,0,sizeof(lfix));

    for(i=0;i<linecnt;i++) {
      if(!active[i]) continue;
      ch=basetab[i][c]; 
      if(ch==0 || prev[ch-'A']!=-1) lfix[i]=1;
    }
    for(icarry=0;;icarry=1) {
      memmove(curr,prev,sizeof(curr));
      memmove(currb,prevb,sizeof(currb));
      for(i=0;i<linecnt;i++) {
          if(!active[i] || lfix[i]) continue;
          for(j=lreg[i]+icarry;j<10 && prevb[j]!=0;j++);
          if(j>=10) {
            for(j=0;j<10 && prevb[j]!=0;j++);
            if(j>=10) return;
            icarry=1;
          }
          else icarry=0;
          lreg[i]=j;
      }
      if(icarry) break;
      for(i=0;i<linecnt;i++) {
          if(!active[i] || lfix[i]) continue;
          if(!putvalue(basetab[i][c],lreg[i],curr,currb)) goto loopend;
      }
      if(!colcompute(c,curr,currb)) continue;
      if(c<activelen-1) column(c+1,curr,currb);
      else {
          for(i=activelen;i<maxlen;i++) {
            if(!colcompute(i,curr,currb)) goto loopend;
          }
          for(i=0;i<linecnt;i++) {
            if(active[i]) continue;
            if(carry[i][maxlen]) goto loopend;
          }
          if(!checklead(curr)) goto loopend;
          total++;
          printresult(curr);
      }
      loopend:
    }
}

int main(int argc, char *argv[])
{
    char *p,*p2,*p3;
    int i;
    input=getenv("wims_exec_parm");
      /* nothing to do if no problem */
    if(input==NULL || *input==0) return 0;

    memset(basetab,0,sizeof(basetab));
    memset(corresp,-1,sizeof(corresp));
    memset(bcorresp,0,sizeof(bcorresp));
    memset(carry,0,sizeof(carry));
    memset(active,0,sizeof(active));

    for(p=input+strlen(input);p>input && isspace(*(p-1));p--);
    *p=0;
    activelen=maxlen=0;
    active[0]=active[1]=1;
    for(linecnt=0,p=input;*p!=0 && linecnt<MAX_LINES;p=p3) {
      p2=strchr(p,'\n');
      if(p2==NULL) {
          p2=p+strlen(p);p3=p2;
      }
      else p3=p2+1;
      while(isspace(*p)) p++;
      if(strchr("+-*/=.",*p)!=NULL) {
          style[linecnt]=*p;p++;
          while(isspace(*p)) p++;
      }
      else style[linecnt]='+';
      if(*p3==0) style[linecnt]='=';
      if(linecnt>1) {
          switch(style[1]) {
            case '+':
            case '-': {
                if(*p3!=0) active[linecnt]=1;
                break;
            }
            
            case '*':
            case '/':
            case '=':
            break;
          }
      }
      while(p2>p && isspace(*(p2-1))) p2--;
      if(p2>p+MAX_CHARS) p2=p+MAX_CHARS;
      *p2=0;
      if(p2<=p) continue;
      for(i=0;i<p2-p;i++) {
          char ch;
          ch=toupper(*(p2-i-1));
            /* bad char */
          if(ch<'A' || ch>'Z') return 1;
          basetab[linecnt][i]=ch;
      }
      charcnt[linecnt]=p2-p;
      if(active[linecnt] && p2-p>activelen) activelen=p2-p;
      if(p2-p>maxlen) maxlen=p2-p;
      linecnt++;
    }
      /* multiplication */
    if(style[1]=='*') {
      if(linecnt==3) style[1]='$';
      else {
          if(linecnt!=charcnt[1]+3) return 1;
          for(i=3;i<linecnt-1;i++)
            if(charcnt[i]+i-2>maxlen) maxlen=charcnt[i]+i-2;
      }
    }

    column(0,corresp,bcorresp);
printf("\n!total %d solution(s).\n\n",total);
    return 0;
}


Generated by  Doxygen 1.6.0   Back to index