Subversion Repositories wimsdev

Compare Revisions

Ignore whitespace Rev 9 → Rev 10

/trunk/wims/src/Misc/cryptarith.c
0,0 → 1,275
/* Copyright (C) 1998-2003 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;
}