//==========================================================================
// POTM ENTRY: CrozzApp
//             JAMES ROTHENBERGER
//             jar@rdga3.att.com
//
// COMPILE INSTRUCTIONS: javac CrozzApp.java
//
// TO RUN:   java CrozzApp
//
//==========================================================================

import java.io.*;

class WordInfo {
    public char  word[];
    public int   len;
    public int   score;
    public float fitability;
    public int   crossings;
    public int   used;
    public int   direction;
    public int   x;
    public int   y;
}


class Crozzilla {

        final int VERTICAL   = 1;
        final int HORIZONTAL = 0;
        final int MAXWORDS   = 200;
        final int MATSIZE    = 20;

        final int LONGEST    = 0;
        final int FITABLE    = 1;
        final int LONGFIT    = 2;

        final int STRAT_EDGES_AND_FIT    = 0;
        final int STRAT_EDGES_ONLY       = 1;
        final int STRAT_EDGES_AND_LENGTH = 2;
        final int STRAT_EDGES_AND_COLLS  = 3;
        final int STRAT_MIDS_AND_LENGTH  = 4;
        final int STRAT_MIDS             = 5;
        final int STRAT_GRAVITY          = 6;
        final int NUM_STRATS             = 7;

        WordInfo   wordArray[];
        char       charMatrix[][];
        int        dirMatrix[][];
        int        letterDistrib[];
        WordInfo   usedStack[];
        String     stratString[];
        String     firstString[];

        int        wordsPlaced = 0;
        int        wordsCrossed = 0;
        int        usedStackPointer = 0;
        boolean    debugFlag = false;
        float      averageFit = 0;
        int        averageLen = 0;
        int        contCeil = 49;
        int        gravityX;
        int        gravityY;

        int        stratMatrix1[][][]; // score/direction first
        int        stratMatrix2[][][]; // crossings/direction first

        
public Crozzilla()
{
        wordArray = new WordInfo[MAXWORDS];
        charMatrix = new char[MATSIZE][MATSIZE];
        dirMatrix = new int[MATSIZE][MATSIZE];
        letterDistrib = new int[26];
        usedStack = new WordInfo[MAXWORDS];
        stratMatrix1 = new int[NUM_STRATS][2][3];
        stratMatrix2 = new int[NUM_STRATS][2][3];
        stratString = new String[NUM_STRATS];
        firstString = new String[3];

        stratString[0] = "Edges and Fit";
        stratString[1] = "Edges Only";
        stratString[2] = "Edges and Length";
        stratString[3] = "Edges and Collisions";
        stratString[4] = "Middles and Length";
        stratString[5] = "Middles";
        stratString[6] = "Gravity";

        firstString[0] = "Longest First";
        firstString[1] = "Fitable First";
        firstString[2] = "Longest Fitable First";
}


public int readWordFile(String filename)
{
    int ch = 0, len, y = 0, longest = 0;
    RandomAccessFile file_p;

    File infile = new File(filename);

    if (infile.isFile() && infile.canRead()) {
        try {
            file_p = new RandomAccessFile(infile,"r");
            StringBuffer word = new StringBuffer();

            while (ch != -1) {
                len = 0;
                word.setLength(0);
                while ((ch = file_p.read()) != -1 && ch != '\n') {
                      if (ch != '\r') {
                          word.append((char)ch);
                          len++;
                      }
                }
                if (ch != -1) {
                        String wordString = word.toString();
                        if (len > longest) longest = len;
                        wordArray[y] = new WordInfo();
                        wordArray[y].len  = len;
                        wordArray[y].word = new char[wordString.length()];
                        wordArray[y].word = wordString.toCharArray();
                        wordArray[y].used = 0;
                        y++;
                }
            }
            file_p.close();
        } catch (IOException e) {
                System.out.println("IOException opening" + filename);
                return(-1);
        }
    } else {
        System.out.println("Can't read file " + filename);
    }
    return (y);
}


public void printWordArray()
{
    int x = 0;
    while (wordArray[x] != null) {
        System.out.println("Word " + x + " is " + wordArray[x].word +
                           " : Score = " + wordArray[x].score +
                           " : Fitability = " + wordArray[x].fitability);
        x++;
    }
}


public void reInitWordArray()
{
    int x = 0;
    while (wordArray[x] != null) {
        wordArray[x].used = 0;
        wordArray[x].x = 0;
        wordArray[x].y = 0;
        x++;
    }
}


public void initMatrix()
{
    wordsPlaced = 0;
    wordsCrossed = 0;
    for (int y = 0; y < MATSIZE; y++) {
        for (int x = 0; x < MATSIZE; x++) {
            charMatrix[x][y] = '-';
            dirMatrix[x][y] = -1;
        }
    }
}


public void initStats()
{
    int x;
    for (x = 0; x < 26; x++) {
        letterDistrib[x] = 0;
    }
    for (x = 0; x < NUM_STRATS; x++) {
        for (int y = 0; y < 2; y++) {
            for (int z = 0; z < 3; z++) {
                stratMatrix1[x][y][z] = 0;
                stratMatrix2[x][y][z] = 0;
            }
        }
    }
}


public void printMatrix()
{
    char temp[] = new char[20];
    StringBuffer word = new StringBuffer();


    for (int y = 0; y < MATSIZE; y++) {
        word.setLength(0);
        for (int x = 0; x < MATSIZE; x++) {
            word.insert(x,(char)charMatrix[x][y]);
        }
        System.out.println(new String(word.toString()));
    }
}


public void gatherStats()
{
    int x = 0, y, score, c;

    while (wordArray[x] != null) {
        int len = wordArray[x].len;
        for (y = 0; y < len; y++) {
            c = wordArray[x].word[y];
            if (c > 96 && c < 123) {
                letterDistrib[c - 97]++;
            }
        }
        x++;
    }
    x = 0;
    while (wordArray[x] != null) {
        int len = wordArray[x].len;
        for (y = 0; y < len; y++) {
            if (wordArray[x].word[y] > 96 && wordArray[x].word[y] < 123) {
                score = letterDistrib[wordArray[x].word[y] - 97];
                wordArray[x].score = wordArray[x].score + score;
                wordArray[x].fitability = (float) wordArray[x].score / len;
            }
        }
        averageFit = averageFit + wordArray[x].fitability;
        averageLen = averageLen + len;
        x++;
    }
    averageFit = averageFit / x;
    averageLen = averageLen / x;

    if (averageLen >= 10) {
        contCeil = 18;
    }
    if (averageLen >= 13) {
        contCeil = 9;
    }
    if (averageLen >= 15) {
        contCeil = 0;
    }
    if (averageLen  bestStratNum) {
                    bestStratNum = stratMatrix1[strat][dir][x];
                    bestStratNum2 = stratMatrix2[strat][dir][x];
                    bestStrat = strat;
                    bestDir = dir;
                    bestfirst = x;
                } else if (stratMatrix1[strat][dir][x] == bestStratNum) {
                    if (stratMatrix2[strat][dir][x] > bestStratNum2) {
                        bestStratNum = stratMatrix2[strat][dir][x];
                        bestStrat = strat;
                        bestDir = dir;
                        bestfirst = x;
                    }
                }
            }
        }
    }
    // Do best one more time!!
    calcAnswer(bestStrat, bestDir, bestfirst);
    if (debugFlag) {
        System.out.println("=================================================")
;
        System.out.println(wordsPlaced + " words: " + stratString[bestStrat] +
                           " " + firstString[bestfirst] + "(" + wordsCrossed +
                           " crossings)");
    }
}


void calcAnswer(int strategy, int initDir, int first)
{
    WordInfo wip;

    initMatrix();
    reInitWordArray();
    wip = getFirstWord(first);
    // Put first good word int the ceter of the matrix
    // We could do alot more here!!
    wip.direction = initDir;
    if (initDir == HORIZONTAL) {
        wip.y = 9;
        wip.x = 9 - wip.len / 2;
    } else {
        wip.x = 9;
        wip.y = 9 - wip.len / 2;
    }
    gravityX = gravityY = 9; // Set gravity
    wip.used = 1;
    insertWord(wip);
    placeNextWord1(wip, strategy);
    stratMatrix1[strategy][initDir][first] = wordsPlaced;
    stratMatrix2[strategy][initDir][first] = wordsCrossed;
}


int placeNextWord1(WordInfo lastWord, int strategy)
{
    push(lastWord);
    WordInfo wip = calculateAndPlace(lastWord, strategy);
    if (wip != null) {
        placeNextWord1(wip, strategy);
    } else {
        wip = pop();            // Flush one
        wip = pop();
        if (wip != null) {
            placeNextWord1(wip, strategy);
        }
    }
    return (0);
}


int placeNextWord2(WordInfo lastWord, int strategy)
{
    WordInfo wip = calculateAndPlace(lastWord, strategy);
    if (wip != null) {
        push(wip);
        placeNextWord2(lastWord, strategy);
    } else {
        wip = pop();
        if (wip != null) {
            placeNextWord2(wip, strategy);
        }
    }
    return (0);
}


WordInfo calculateAndPlace(WordInfo lastWord, int strategy)
{
    int x = 0, bestIndex = -1;
    float score, bestScore = 0;

    while (wordArray[x] != null) {
        if (wordArray[x].used != 1) {
            score = bestFit1(lastWord, wordArray[x], strategy);
            if (score > bestScore) {
                bestScore = score;
                bestIndex = x;
            }
        }
        x++;
    }
    if (bestIndex == -1) {
        return null;
    } else {
        wordArray[bestIndex].used = 1;
        insertWord(wordArray[bestIndex]);
        wordsCrossed = wordsCrossed + wordArray[bestIndex].crossings;
        return wordArray[bestIndex];
    }
}


void insertWord(WordInfo word_p)
{
    if (word_p.direction == HORIZONTAL) {
        for (int x = 0; x < word_p.len; x++) {
            dirMatrix[x + word_p.x][word_p.y] = HORIZONTAL;
            charMatrix[x + word_p.x][word_p.y] = word_p.word[x];
        }
    } else {
        for (int y = 0; y < word_p.len; y++) {
            dirMatrix[word_p.x][y + word_p.y] = VERTICAL;
            charMatrix[word_p.x][y + word_p.y] = word_p.word[y];
        }
    }
    wordsPlaced++;
}


WordInfo getFirstWord(int strat)
{
    switch (strat) {
     case FITABLE: return (getNextMostFitable());
     case LONGEST: return (getNextLongest());
     case LONGFIT: return (getLongestFitable());
    }
    // default !
    return (getNextMostFitable());
}


WordInfo getNextMostFitable()
{
    float fit = 0;
    int x = 0, address = 0;
    while (wordArray[x] != null) {
        if (wordArray[x].used != 1 && wordArray[x].fitability > fit) {
            fit = wordArray[x].fitability;
            address = x;
        }
        x++;
    }
    return wordArray[address];
}


WordInfo getNextLongest()
{
    int len = 0, x = 0, address = 0;

    while (wordArray[x] != null) {
        if (wordArray[x].used != 1 && wordArray[x].len > len) {
            len = wordArray[x].len;
            address = x;
        }
        x++;
    }
    return wordArray[address];
}


WordInfo getLongestFitable()
{
    int len = 0, x = 0, address = 0;
    float fit = 0;

    while (wordArray[x] != null) {
        if (wordArray[x].used != 1 && wordArray[x].fitability > fit &&
            wordArray[x].fitability > averageFit &&
            wordArray[x].len > len) {
            fit = wordArray[x].fitability;
            len = wordArray[x].len;
            address = x;
        }
        x++;
    }
    return wordArray[address];
}


void push(WordInfo word)
{
    usedStack[usedStackPointer] = word;
    usedStackPointer++;
}


WordInfo pop()
{
    if (usedStackPointer == 0) return null;
    usedStackPointer--;
    return usedStack[usedStackPointer];
}


float bestFit1(WordInfo lastWord, WordInfo newWord, int strategy)
{
    int fit, k;
    float score = -1, bestScore = -1;

    // Find an intersection
    for (int j = 0; j < lastWord.len; j++) {
        for (k = 0; k < newWord.len; k++) {
            if (lastWord.word[j] == newWord.word[k]) {
                // Check fit
                // fit will be number of "good collisions"
                // System.out.println("bestFit with words: " + newWord.word +
                //                    " " + lastWord.word);
                fit = checkFit(lastWord, newWord, j, k);
                if (fit != -1) {
                    // Determine score
                    score = calcScore(lastWord, newWord, strategy, j, k, fit);
                    if (score > bestScore) {
                        bestScore = score;
                        // Determine coords
                        if (lastWord.direction == HORIZONTAL) {
                            newWord.x = lastWord.x + j;
                            newWord.y = lastWord.y - k;
                            newWord.direction = VERTICAL;
                        } else {
                            newWord.x = lastWord.x - k;
                            newWord.y = lastWord.y + j;
                            newWord.direction = HORIZONTAL;
                        }
                        newWord.crossings = fit;
                    }
                }
            }
        }
    }
    return (score);
}


float calcScore(WordInfo lastWord, WordInfo newWord, int strat, int j,
                int k, int fit)
{
    int mid1, mid2;
    float edgeScore1, edgeScore2, multiplier1, multiplier2;
    float midScore1 = 0, midScore2 = 0;

    // Determine score
    mid1 = (newWord.len - 1) / 2;
    mid2 = (lastWord.len - 1) / 2;
    if (mid1 == 0) mid1 = 1;
    if (mid2 == 0) mid2 = 1;
    multiplier1 = 10 / mid1;
    multiplier2 = 10 / mid2;
    if (k == mid1) {
        edgeScore1 = 1;
    } else if (k < mid1) {
        edgeScore1 = (mid1 - k) * multiplier1;
        midScore1 = k * multiplier1;
    } else {
        edgeScore1 = (k - mid1) * multiplier1;
        midScore1 = (newWord.len - k) * multiplier1;
    }
    if (j == mid2) {
        edgeScore2 = 1;
    } else if (j < mid2) {
        edgeScore2 = (mid2 - j) * multiplier2;
        midScore2 = j * multiplier2;
    } else {
        edgeScore2 = (j - mid2) * multiplier2;
        midScore2 = (lastWord.len - j) * multiplier1;
    }
    switch (strat) {
     case STRAT_EDGES_AND_FIT:
         return (edgeScore1 + edgeScore2 + newWord.fitability);
     case STRAT_EDGES_ONLY:
         return (edgeScore1 + edgeScore2);
     case STRAT_EDGES_AND_LENGTH:
         return (edgeScore1 + edgeScore2 + newWord.len);
     case STRAT_EDGES_AND_COLLS:
         return (edgeScore1 + edgeScore2 + ((fit - 1) * 10));
     case STRAT_MIDS_AND_LENGTH:
         return (midScore1 + midScore2 + newWord.len);
     case STRAT_MIDS:
         return (midScore1 + midScore2);
     case STRAT_GRAVITY:
         return(gravityScore(lastWord, newWord, j, k));
    }
    return(0);
}


float gravityScore(WordInfo lastWord, WordInfo newWord, int j, int k)
{
    int XCord, YCord;
    float grav;

    // Where j is the intersect on the lastWord, k is the newWord
    // Determine coords
    if (lastWord.direction == HORIZONTAL) {     // VERTICAL
        YCord = lastWord.y - k;
        if (YCord  19) return 0;
    } else {
        if (lastWord.x - k < 0) return 0;       // Check left
        // Check right
        if (lastWord.x + (newWord.len - k - 1) > 19) return 0;
    }
    return (1);
}


int collisionCheck(WordInfo lastWord, WordInfo newWord, int j, int k)
{
    int XCord, YCord, x, y, ok_flag, goodColls = 1, limit, offset;

    // Where j is the intersect on the lastWord, k is the newWord
    // Determine coords
    if (lastWord.direction == HORIZONTAL) {     // VERTICAL
        XCord = lastWord.x + j;
        YCord = lastWord.y - k;
        // DIAGONALS ARE OK!! DON'T CHECK NEXTA'S ON -1 AND +!
        limit = YCord + newWord.len + 1;
        for (y = YCord - 1; y < limit && y < 20; y++) {
            if (y < 0) y = 0;
            ok_flag = 0;
            if (charMatrix[XCord][y] != '-' && y != lastWord.y) {
                offset = y - YCord;
                if (offset > -1 && offset < newWord.len) {
                    if (charMatrix[XCord][y] == newWord.word[offset]) {
                        goodColls++;
                        ok_flag = 1;
                    } else {
                        //System.out.println("Coll: " +newWord.word+XCord+y);
                        return -1;
                    }
                } else if (offset == -1 || offset == newWord.len) {
                    if (charMatrix[XCord][y] != '-') {
                        return -1;
                    }
                }
            }
            if (y == YCord - 1 || y == limit - 1) ok_flag = 1;
            if (XCord < 19) {
                if (charMatrix[XCord + 1][y] != '-' && y != lastWord.y && ok_fl
ag == 0) {
                    //System.out.println("Nexta: "+newWord.word+XCord+y);
                    return -1;
                }
            }
            if (XCord > 0) {
                if (charMatrix[XCord - 1][y] != '-' && y != lastWord.y && ok_fl
ag == 0) {
                    //System.out.println("Nexta: "+newWord.word+XCord+y);
                    return -1;
                }
            }
            if (dirMatrix[XCord][y] == VERTICAL) {
                //System.out.println("Overlap: "+newWord.word+XCord+y);
                return -1;
            }
        }
    } else {                    // HORIZONTAL
        XCord = lastWord.x - k;
        YCord = lastWord.y + j;
        limit = XCord + newWord.len + 1;
        for (x = XCord - 1; x < limit && x < 20; x++) {
            if (x < 0) x = 0;
            ok_flag = 0;
            if (charMatrix[x][YCord] != '-' && x != lastWord.x) {
                offset = x - XCord;
                if (offset > -1 && offset < newWord.len) {
                    if (charMatrix[x][YCord] == newWord.word[offset]) {
                        goodColls++;
                        ok_flag = 1;
                    } else {
                        // System.out.println("Coll: " +newWord.word+x+YCord);
                        return -1;
                    }
                } else if (offset == -1 || offset == newWord.len) {
                    if (charMatrix[x][YCord] != '-') {
                        return -1;
                    }
                }
            }
            if (x == XCord - 1 || x == limit - 1) ok_flag = 1;
            if (YCord < 19) {
                if (charMatrix[x][YCord + 1] != '-' && x != lastWord.x && ok_fl
ag == 0) {
                    // System.out.println("Nexta: "+newWord.word+x+YCord);
                    return -1;
                }
            }
            if (YCord > 0) {
                if (charMatrix[x][YCord - 1] != '-' && x != lastWord.x && ok_fl
ag == 0) {
                    // System.out.println("Nexta: " + newWord.word + x + YCord)
;
                    return -1;
                }
            }
            if (dirMatrix[x][YCord] == HORIZONTAL) {
                //System.out.println("Overlap: " + newWord.word +  x + YCord);
                return -1;
            }
        }
    }
    return (goodColls);
}

}


class CrozzApp {

        public static void main(String args[])
        {
            int wordsRead, filearg = 1;
            Crozzilla newCroz = new Crozzilla();
        
            if (args.length > 1) {
                newCroz.debugFlag = true;
                wordsRead = newCroz.readWordFile(args[1]);
            } else {
                wordsRead = newCroz.readWordFile(args[0]);
            }
            newCroz.initStats();
            newCroz.gatherStats();
            newCroz.initMatrix();
            // newCroz.printStats();
            // newCroz.printWordArray();
            newCroz.calcBestAnswer();
            // newCroz.populateMatrix();
            newCroz.printMatrix();
            //if (debugFlag)
                //System.out.println("Placed %d of %d words (%d crossings)\n",
                //                    wordsPlaced, wordsRead, wordsCrossed);
        }
}