/* ALPHAMETIC PUZZLE SOLVER - TEST (MARCH 24, 2006)
 *
 * The following program intends to solve ALPHAMETIC puzzles in which 
 * the operand is strictly addition.
 *
 * Original version by Naoyuki Tamura (tamura@kobe-u.ac.jp)
 * Copyright (C) Naoyuki Tamura (tamura@kobe-u.ac.jp)
 * Department of CS, Kobe University, Japan
 * http://bach.istc.kobe-u.ac.jp/llp/crypt.html
 *
 * This version based on the code that was copied by:
 * Anuj Prateek & Upendra Singh, Virtual World, India
 * http://www.geocities.com/anuj_prateekin
 * anuj.prateek&gmail.com, upendra.bits@gmail.com
 *
 * Code cleaned up by Rich Burridge - rich.burridge@sun.com
 *
 * Compile with:
 * $ cc -o alphametic alphametic.c
 *
 * Run with:
 * $ alphametic
 *
 * Use HELP command to learn how to use the program.
 *
 * We have used recursive approach with constraints to solve the
 * alphametics in low order. We first parse the words in a two
 * dimensional array. Then we simply keep track of used integers(0-9)
 * and in an array(sel) keep the current trial values of characters.
 * And go on recursively calling solve function to find all possible
 * solutions within given LIMIT. The number of recursions is optimized
 * by use of constraints derived from the alphametic stored inside an array.
 *
 * For more on related topics refer to: 
 * Rich and Knight: Artificial Intelligence (Second Edition)
 *
 * (Another approach that the authors had in mind while planning the 
 * program was use of heuristics but due to time constraints we had to 
 * resort to recursive approach).
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <setjmp.h>
#include <string.h>
#include <limits.h>

#define BASE            (10)
#define PUZ_SIZE        (1000)
#define YES             (1)
#define NO              (0)
#define quot(x,y)       ((x)/(y))
#define mod(x,y)        ((x)%(y))

char **puzzle;                
char puz[PUZ_SIZE];
int sel[UCHAR_MAX];
int sel_copy[UCHAR_MAX];
int lower[UCHAR_MAX];
int used[BASE];
int count;
int limit = 0;
int unique = NO;
int num_tested = 0;
int num_unique = 0;
jmp_buf jmpbuf;
long usertime0;

char *example[] = {
    "A+MERRY+XMAS=TURKEY",
    "ADAM+AND+EVE=MOVED",
    "ALPHABET+LETTERS=SCRABBLE",
    "APPLE+GRAPE+PLUM=BANANA",
    "BASE+BALL=GAMES",
    "BEST+MAKE=MASER",
    "BILL+WILLIAM+MONICA=CLINTON",
    "BONGO+BONGO+BONGO+ON+THE=CONGO",
    "COCA+COLA=OASIS",
    "CROSS+ROADS=DANGER",
    "CRYPT+ARITH+METIC=CREATE",
    "DID+HE+READ+HER=DIARY",
    "DONALD+GERALD=ROBERT",
    "DOS+DOS+TRES=SIETE",
    "EARTH+AIR+WATER+FIRE=NATURE",
    "EIN+EIN+EIN+EIN=VIER",
    "FIFTY+STATES=AMERICA",
    "GEE+I+SEE+A+RARE+MAGIC=SQUARE",
    "GRAPE+APPLE=CHERRY",
    "LEARN+LINEAR+LOGIC=PROLOG",
    "LISP+LISP+LOGIC+LOGIC=PROLOG",
    "LLP+LINEAR+LOGIC=PROLOG",
    "LOGIC+JAVA+JAVA=PROLOG",
    "LOGIC+LOGIC=PROLOG",
    "LYNNE+LOOKS=SLEEPY",
    "MONEY+POP+SOME+MONEY=PLEASE",
    "NEPTUNE+SATURN+URANUS+PLUTO=PLANETS",
    "NEVER+ALWAYS=NEARLY",
    "NO+SNOW+IN+VIEW+ON+ROOFS+IN=VENICE",
    "OSAKA+HAIKU+SUSHI=JAPAN",
    "PEANUT+TEETH=CARTER",
    "PRIME+CRYPT+ARITH=METIC",
    "RIDE+DRIVE=NEVER",
    "SEND+MORE=MONEY",
    "TERRIBLE+NUMBER=THIRTEEN",
    "THIS+ISA+GREAT+TIME=WASTER",
    "USA+USSR=PEACE",
    "WE+WANT+NO+NEW+ATOMIC=WEAPON",
    "WHO+IS+THIS=IDIOT",
    "WINTER+IS+WINDIER+SUMMER+IS=SUNNIER",
    "SIX+SEVEN+SEVEN=TWENTY",
    "TEN+TEN+FORTY=SIXTY",
    "ONE+NINE+TWENTY+FIFTY=EIGHTY",
    "THREE+SEVEN+TEN+TWENTY+THIRTY=SEVENTY",
    "FIVE+SEVEN+ELEVEN+TWELVE+FIFTEEN+TWENTY=SEVENTY",
    "SIX+SEVEN+NINE+TWELVE+SIXTEEN+TWENTY=SEVENTY",
    "ONE+TWO+FIVE+NINE+ELEVEN+TWELVE+FIFTY=NINETY",
    "UN+UN+NEUF=ONZE",
    "EINS+ZWEI+SIEBEN+SECHZIG=SIEBZIG",
    "SEIS+CATORCE+SETENTA=NOVENTA",
    "WWW+BUG+BILL=GATES",
    "WWW+WS+UNIX=CRASH",
    "OSAKA+KYOTO=TOKYO",
    "TOMATO+POTATO=PUMPKIN",
    "FUJITSU+FUJITSU=HITACHI",
    "SYSTEM5+ERROR=SOLARIS"
};


long
usertime()
{
    return (1000.0 * clock() / CLOCKS_PER_SEC);
}


void
usage()
{
    printf("\n           ALPHAMETIC PUZZLE SOLVER - TEST (MARCH 24, 2006)\n");
    printf("\n           Copyleft (C) Anuj Prateek & Upendra Singh\n");
    printf("\n           Virtual World, India\n");
    printf("\n           http://www.geocities.com/anuj_prateekin\n");
    printf("\n           anuj.prateek&gmail.com, upendra.bits@gmail.com\n");
}


void
quit()
{
    if (unique) {
        printf("%d UNIQUE-SOLUTION ALPHAMETIC FOUND \n", num_unique);
        printf("(%d examined)\n", num_tested);
    }
    printf("Total time = %ld msec.\n", usertime() - usertime0);
    exit(0);
}


int
parse(char *q, char **pp)
{
    int len = 0;

    while (*q) {
        if (isspace(*q) || *q == '+' || *q == '=') {
            *q++ = '\0';
            continue;
        }
        if (isalnum(*q)) {
            *pp++ = q;
            ++len;
            while (isalnum(*q))
                ++q;
            continue;
        }
        return 0;
    }
    *pp = NULL;

    return len;
}


void
command(char *cmd, char *arg)
{
    if (strcmp(cmd, "HELP") == 0) {
        printf("  ANUJ JUNA PRAT : ALPHAMETIC FORMAT 1 or\n");
        printf("  ANUJ+JUNA=PRAT : ALPHAMETIC FORMAT 2 \n");
        printf("  HELP           : Show Help\n");
        printf("  EXAMPLE        : Shows An Crypt At Random\n");
        printf("  LIMIT NUM      : Show At Most NUM Solutions (0 means no-limit)\n");
        printf("  UNIQUE NUM     : Shows The Solution Only If NUM Unique Solutions\n");
        printf("  QUIT           : Quit\n");
        printf("  VERSION        : Prints The Version Of This Program\n");
    } else if (strcmp(cmd, "LIMIT") == 0 && arg != NULL) {
        limit = atoi(arg);
    } else if (strcmp(cmd, "UNIQUE") == 0 && arg != NULL) {
        unique = atoi(arg);
    } else if (strcmp(cmd, "VERSION") == 0) {
        usage();
    } else if (strcmp(cmd, "QUIT") == 0) {
        quit();
    } else {
        printf("\nTYPE 'HELP' FOR HELP\n");
    }
}


char *
setup()
{
    int c, maxlen, min, max, k, i, j;
    char **pp, *p;

    for (c = 0; c < UCHAR_MAX; ++c)
        sel[c] = -2;
    for (c = '0'; c <= '9'; ++c)
        sel[c] = c - '0';
    pp = puzzle;
    if (*puzzle == NULL || *(puzzle+1) == NULL)
        return "ERROR WITH ALPHAMETIC : Too Short";
    maxlen = 0;
    min = 0;
    max = 0;
    for (pp = puzzle; *(pp+1) != NULL; ++pp) {
        if (strlen(*pp) == 0)
            return NO;
        maxlen = maxi(maxlen, strlen(*pp));
        min += min_value(*pp);
        max += max_value(*pp);
    }

    maxlen = maxi(maxlen, strlen(*pp));
    if (maxi(min, min_value(*pp)) > mini(max, max_value(*pp))) {
        return "ERROR WITH ALPHAMETIC : Range Is Invalid";
    }
    k = 0;
    for (pp = puzzle; *pp != NULL; ++pp) {
        for (p = *pp; *p; ++p) {
            if (isalpha(*p) && sel[(unsigned)*p] == -2) {
                sel[(unsigned)*p] = -1;
                ++k;
            }
        }
    }
    if (k > BASE)
        return "ERROR WITH ALPHAMETIC : Number Of Alphabets Too High";
    p = puz;
    for (i = 1; i <= maxlen; ++i) {
        for (pp = puzzle; *pp != NULL; ++pp) {
            j = strlen(*pp) - i;
            if (j < 0)
                continue;
            if (*(pp+1) != NULL)
                *p++ = '+';
            else
                *p++ = '=';
            *p++ = *(*pp+j);
            if (p >= puz + PUZ_SIZE)
                return "ERROR WITH ALPHAMETIC : Alphametic Too Long";
        }
    }
    *p = '\0';
    for (c = 0; c < UCHAR_MAX; ++c) {
        lower[c] = 0;
    }
    for (pp = puzzle; *pp != NULL; ++pp)
        if (isalpha(**pp))
            lower[**pp] = 1;

    return NULL;
}

int
min_value(char *p)
{
    unsigned int min = 0;
    char *q;

    for (q = p; *q; ++q) {
        min *= BASE;
        if (isalpha(*q))
            min += (q == p) ? 1 : 0;
        else if (isdigit(*q))
            min += *q - '0';
    }

    return (int) min;
}


int
max_value(char *p)
{
    int max = 0;

    while(*p) {
        max *= BASE;
        if (isalpha(*p))
            max += BASE - 1;
        else if (isdigit(*p))
            max += *p - '0';
        ++p;
    }

    return max;
}


int
mini(int x, int y)
{
    return (x < y) ? x : y;
}


int
maxi(int x, int y)
{
    return (x > y) ? x : y;
}


void
show_sol()
{
    char **pp, *p;

    for (pp = puzzle; *pp != NULL; ++pp) {
        if (*(pp+1) == NULL)
            printf("=");
        else if (pp > puzzle)
            printf("+");
        for (p = *pp; *p; ++p)
            printf("%d", sel[(unsigned) *p]);
    }
}


void
solve(char *p, int s)
{
    unsigned int c;
    int d;

    if (*p == '\0' && s == 0) {
        ++count;
        if (unique) {
            memcpy(sel_copy, sel, sizeof(sel));
        } else {
            printf("  ");
            show_sol();
            printf("\n");
        }
        if (limit > 0 && count >= limit)
            longjmp(jmpbuf, 1);
        return;
    }
    c = *(p+1);
    switch (*p) {
        case '+': if (sel[c] >= 0) {
                      solve(p+2, s+sel[c]);
                  } else {
                      for (d = lower[c]; d < BASE; ++d) {
                          if (used[d])
                              continue;
                          used[d] = YES;
                          sel[c] = d;
                          solve(p+2, s+d);
                          used[d] = NO;
                          sel[c] = -1;
                      }
                  }
                  break;

        case '=': d = mod(s, BASE);
                  if (sel[c] >= 0) {
                      if (sel[c] == d)
                          solve(p+2, quot(s, BASE));
                  } else {
                      if (!used[d] && d >= lower[c]) {
                          used[d] = YES;
                          sel[c] = d;
                          solve(p+2, quot(s, BASE));
                          used[d] = NO;
                          sel[c] = -1;
                      }
                  }
                  break;
    }
}


void
show_puzzle()
{
    char **pp;

    for (pp = puzzle; *pp != NULL; ++pp) {
        if (*(pp+1) == NULL)
            printf("=");
        else if (pp > puzzle)
            printf("+");
        printf(*pp);
    }
}


int
alphametic(char **pp)
{
    char *msg;
    int d;
    long t0 = usertime();

    ++num_tested;
    puzzle = pp;
    count = 0;
    for (d = 0; d < BASE; ++d)
        used[d] = NO;
    if (unique) {
        if (setup() != NULL)
            return NO;
        limit = 2;
        if (setjmp(jmpbuf) == 0) {
            solve(puz, 0);
            if (count == 1) {
                ++num_unique;
                memcpy(sel, sel_copy, sizeof(sel));
                show_puzzle();
                printf(" (");
                show_sol();
                printf(")\n");
            }
        }
    } else {
        printf("  ");
        show_puzzle();
        printf("\n");
        if ((msg = setup()) != NULL) {
            printf("  BLUNDER-(%s)\n", msg);
            return NO;
        }
        if (setjmp(jmpbuf) == 0) {
            solve(puz, 0);
            printf("  %d solution(s)", count);
        } else {
            printf("  %d or more solution(s)", count);
        }
        printf(", %ld msec.\n", usertime()-t0);
    }

    return YES;
}


int
main(int argc, char *argv[])
{
    char buff[PUZ_SIZE];
    char *pp[PUZ_SIZE];
    int len, s, i;

    usertime0 = usertime();
    srand((unsigned int) time(NULL));

    usage();
    printf("\nTYPE 'HELP' FOR HELP\n");
    printf("> ");

    while (fgets(buff, PUZ_SIZE, stdin) != NULL) {
        if (*buff == '\n' || *buff == '#')
            continue;
        len = parse(buff, pp);
        if (len == 0) {
            printf("SYNTAX ERROR : Error Trapped While Parsing.\n");
            continue;
        }
        if (strcmp(pp[0], "EXAMPLE") == 0 && pp[1] == NULL) {
            s = (sizeof example / sizeof (char *));
            i = rand() % s;
            printf("EXAMPLE:- %d/%d\n", i, s);
            strcpy(buff, example[i]);
            parse(buff, pp);
            alphametic(pp);
        } else if (len <= 2) {
            command(pp[0], pp[1]);
        } else {
            alphametic(pp);
        }
        printf("> ");
    }
    quit();
}