/**
 * Main solver routines.  Here's where most of the action is.
 *
 * Author: Ramkumar Natarajan
 **/

#include "solver.h"

int aleph_codes[26] =
    {
        ALEPH_A,
        ALEPH_B,
        ALEPH_C,
        ALEPH_D,
        
        ALEPH_E,
        ALEPH_F,
        ALEPH_G,
        ALEPH_H,

        ALEPH_I,
        ALEPH_J,
        ALEPH_K,
        ALEPH_L,
        
        ALEPH_M,
        ALEPH_N,
        ALEPH_O,
        ALEPH_P,
        
        ALEPH_Q,
        ALEPH_R,
        ALEPH_S,
        ALEPH_T,
        
        ALEPH_U,
        ALEPH_V,
        ALEPH_W,
        ALEPH_X,
        
        ALEPH_Y,
        ALEPH_Z,
    };

LOCAL Bool isLegendPossible(CipherWord **cwptrs, int start, int end, int *currentmap) {
    int i;

    for ( i = start; i < end; ++i ) {
        CipherWord  *cwptr      = cwptrs[i];
        char       **wordlist   = cwptr->possiblewords;
        char        *cipherword = cwptr->word;
        int          len        = cwptr->len;
        int          npossibles = cwptr->npossibles;
        int          j;

        if ( cwptr->isIgnored)
            continue;
        for ( j = 0; j < npossibles; ++j ) {
            char *cptr = wordlist[j];
            int   k;
            
            for ( k = 0; k < len; ++k) {
                int cipherchar;
                int plainchar;

                if ( k == cwptr->nonalphapos )
                    continue;
                cipherchar = CHAR_TO_INDEX(cipherword[k]);
                plainchar  = CHAR_TO_INDEX(cptr[k]);
                if ( ! (currentmap[cipherchar] & aleph_codes[plainchar]) )
                    break;
            }
            if ( k == len ) {
                cwptr->curmatch = j;
                break;
            }
        }

        if ( npossibles && j == npossibles )
            return FALSE;
    }

    return TRUE;
}

LOCAL Bool addToMap(char *cipherword, char *plainword, int len, int *currentmap, int nonalphapos) {
    int i;
    int excludes  = 0;

    for ( i = 0; i < len; ++i ) {
        int cipherchar = cipherword[i];
        int plainchar  = plainword[i];
        
        if ( i == nonalphapos )
            continue;

        cipherchar = CHAR_TO_INDEX(cipherchar);
        plainchar  = CHAR_TO_INDEX(plainchar);
        if ( ! (currentmap[cipherchar] & aleph_codes[plainchar]) )
            return FALSE;
        excludes  |= aleph_codes[plainchar];
    }

    for ( i = 0; i < ALPHA_SZ_; ++i ) {
        currentmap[i] &= ~excludes;
    }

    for ( i = 0; i < len; ++i ) {
        int plainchar = plainword[i];
        int cipherchar = cipherword[i];

        if ( i == nonalphapos )
            continue;
        
        plainchar = CHAR_TO_INDEX(plainchar);
        cipherchar = CHAR_TO_INDEX(cipherchar);
        currentmap[cipherchar] = aleph_codes[plainchar];
    }
    
    return TRUE;
}

LOCAL void convertMapToChars(CipherChar *ccptr, int *map, char *plainmap) {
    int i, j;

    for ( i = 0; i < ALPHA_SZ_; ++i ) {
        if ( !ccptr[i].isPresent || !map[i] || (map[i] & (map[i] - 1)) ) {
            plainmap[i] = '?';
        }
        else {
            j = 0;
            while ( map[i] >>= 1 )
                ++j;
            plainmap[i] = 'a' + j;
        }
    }
}

LOCAL Bool solveWords(CipherWord **cipherwordptrs, int ncipherwords, int *newmap) {
    int  i;
    Bool nosolution;
    
    for ( i = 0; i < ALPHA_SZ_; ++i )
        newmap[i] = ALEPH_ALL;
    i = 0;
    nosolution   = FALSE;
    while ( i < ncipherwords ) {
        CipherWord *cwptr      = cipherwordptrs[i];
        char      **possibles  = cwptr->possiblewords;
        int         npossibles = cwptr->npossibles;
        int         curattempt = cwptr->curmatch;
        int         len        = cwptr->len;
        char       *cipherword = cwptr->word;
        Bool        isPossible = FALSE;

        if ( cwptr->isIgnored ) {
            ++i;
            continue;
        }

        while ( !isPossible && curattempt < npossibles ) {
            char *attempt = possibles[curattempt++];
            memcpy(cwptr->map, newmap, sizeof *newmap * ALPHA_SZ_);
            if ( !addToMap(cipherword, attempt, len, newmap, cwptr->nonalphapos) ) {
                continue;
            }
            isPossible = isLegendPossible(cipherwordptrs, i+1, ncipherwords, newmap);
            if ( !isPossible && curattempt < npossibles ) {
                memcpy(newmap, cwptr->map, sizeof *newmap * ALPHA_SZ_);
            }
        }
		
        cwptr->curmatch = curattempt;
        if ( isPossible ) {
            ++i;
        }
        else {
            int j;

            for ( j = i; j >= 0; --j ) {
                cwptr = cipherwordptrs[j];
                if ( cwptr->isIgnored )
                    continue;
                if ( cwptr->curmatch < cwptr->npossibles )
                    break;
                cwptr->curmatch = 0;
            }
            if ( j < 0 ) {
                nosolution = TRUE;
                break;
            }
            i = j;
            cwptr = cipherwordptrs[i];
            assert(cwptr->curmatch < cwptr->npossibles);
            memcpy(newmap, cwptr->map, sizeof *newmap * ALPHA_SZ_);
        }
    }

    return nosolution;
}

int solveQuip(char *txt, CipherText *ctptr) {
    CipherWord **cipherwordptrs;
    int i;
    int newmap[ALPHA_SZ_];
    int ncipherwords;
    Bool nosolution = FALSE;
    char *ciphertxt = ctptr->ociphertxt;
    char plainmap[ALPHA_SZ_];

    processInput(txt, ctptr);
    if ( ctptr->ncipherwords <= 0 )
        return 1;

    cipherwordptrs = my_malloc(sizeof *cipherwordptrs * ctptr->ncipherwords);
    for ( i = 0; i < ctptr->ncipherwords; ++i ) {
        cipherwordptrs[i] = ctptr->cipherwords[i];
    }
    
    for ( i = 0; i < ctptr->ncipherwords-1; ++i ) {
        int j;
        int ikey = cipherwordptrs[i]->len;
        
        for ( j = i+1; j < ctptr->ncipherwords; ++j ) {
            int jkey = cipherwordptrs[j]->len;
            if ( ikey < jkey ) {
                CipherWord *temp = cipherwordptrs[i];
                cipherwordptrs[i] = cipherwordptrs[j];
                cipherwordptrs[j] = temp;
                ikey = jkey;
            }
        }
    }

    for ( i = 0; i < ctptr->ncipherwords; ++i ) {
        CipherWord *wptr = cipherwordptrs[i];
        getMatchingWordsFromDict(wptr, dicts + wptr->len - 1, ctptr->ciphermap);
    }

    ncipherwords = ctptr->ncipherwords;
    while ( 1 ) {
        int j;
        
        nosolution = solveWords(cipherwordptrs, ncipherwords, newmap);
        if ( !nosolution )
            break;
                
        for ( i = 0; i < ncipherwords; ++i ) {
            if ( cipherwordptrs[i]->isIgnored )
                continue;
            cipherwordptrs[i]->isIgnored = TRUE;
            fprintf(stderr, "Couldn't find a solution, Ignoring %s and trying others\n", cipherwordptrs[i]->word);
            break;
        }
        if ( i == ncipherwords )
            break;
        for ( j = 0; j < ALPHA_SZ_; ++j ) {
            CipherChar *ccptr = ctptr->ciphermap + j;
            if ( ! ccptr->isPresent )
                continue;
            ccptr->plainmap = ALEPH_ALL;
        }
        for ( ++i; i < ncipherwords; ++i ) {
            if ( cipherwordptrs[i]->isIgnored )
                continue;
            cipherwordptrs[i]->curmatch = 0;
            if ( cipherwordptrs[i]->possiblewords )
                MY_FREE(cipherwordptrs[i]->possiblewords);
            getMatchingWordsFromDict(cipherwordptrs[i], dicts + cipherwordptrs[i]->len - 1, ctptr->ciphermap);
        }
    }

    if ( nosolution ) {
        fprintf(stderr, "Couldn't find a solution!\n");
        return 1;
    }
    else {
        convertMapToChars(ctptr->ciphermap, newmap, plainmap);

        memcpy(ctptr->plainmap, newmap, sizeof *newmap * ALPHA_SZ_);
        memcpy(ctptr->plainchars, plainmap, sizeof *plainmap * ALPHA_SZ_);

        ctptr->plaintxt = my_malloc(sizeof *ctptr->plaintxt * strlen(ctptr->ociphertxt));
        strcpy(ctptr->plaintxt, ctptr->ociphertxt);
        ciphertxt = ctptr->plaintxt;
        for ( ; *ciphertxt; ciphertxt++ ) {
            char cipherchar = *ciphertxt;
            int  isupper;
            
            if ( !isalpha((int) cipherchar) )
                continue;
            isupper    = isupper((int) cipherchar);
            cipherchar = tolower((int) cipherchar);
            *ciphertxt = isupper ? toupper((int)plainmap[CHAR_TO_INDEX(cipherchar)]) : plainmap[CHAR_TO_INDEX(cipherchar)];
        }
    }
    return 0;
}