anagram-games/www/crossword/crossword.js

'use strict';

class Clue {
    constructor(answer, row, col, horizontal) {
        this.answer = answer;
        this.row = row;
        this.col = col;
        this.horizontal = horizontal;
        this.solved = false;
        this.length = answer.length;
    }

    get afterRow() {
        if (this.horizontal) {
            return this.row + 1;
        } else {
            return this.row + this.length;
        }
    }

    get afterCol() {
        if (this.horizontal) {
            return this.col + this.length;
        } else {
            return this.col + 1;
        }
    }

    static fromFragment(fragment, sortedLetters) {
        let horizontal = fragment[0] == 'H';
        let [row, col, length, permutation] = fragment.substring(1).split(',');
        let answer = '';
        permutation = parseInt(permutation, 36);
        for (let i = 0; i < length; i++) {
            answer = sortedLetters[permutation % sortedLetters.length] + answer;
            permutation = Math.floor(permutation / sortedLetters.length);
        }
        return new Clue(answer, Number(row), Number(col), horizontal);
    }

    toFragment(sortedLetters) {
        let permutation = 0;
        this.answer.split('').forEach(letter => {
            permutation *= sortedLetters.length;
            permutation += sortedLetters.indexOf(letter);
        });
        return (this.horizontal ? 'H' : 'V') + this.row + ',' + this.col
            + ',' + this.length + ',' + permutation.toString(36);
    }

    get letterPositions() {
        let res = [];
        if (this.horizontal) {
            for (let i = 0; i < this.length; i++) {
                res.push({'letter': this.answer[i],
                          'row': this.row, 'col': this.col + i});
            }
        } else {
            for (let i = 0; i < this.length; i++) {
                res.push({'letter': this.answer[i],
                          'row': this.row + i, 'col': this.col});
            }
        }
        return res;
    }

    get beforePosition() {
        if (this.horizontal) {
            return {'row': this.row, 'col': this.col-1};
        } else {
            return {'row': this.row-1, 'col': this.col};
        }
    }

    get afterPosition() {
        if (this.horizontal) {
            return {'row': this.row, 'col': this.col + this.length};
        } else {
            return {'row': this.row + this.length, 'col': this.col};
        }
    }

    get adjacentPositions() {
        if (this.horizontal) {
            return this.letterPositions.map(pos => [
                {'row': pos.row-1, 'col': pos.col},
                {'row': pos.row+1, 'col': pos.col},
            ]);
        } else {
            return this.letterPositions.map(pos => [
                {'row': pos.row, 'col': pos.col-1},
                {'row': pos.row, 'col': pos.col+1},
            ]);
        }
    }
}
class CrosswordPuzzle {
    constructor(clues, letters) {
        this.clues = clues === undefined ? [] : clues;
        this.letters = clues === undefined ? new Map() : letters;
    }

    withClue(clue) {
        // TODO Check if valid to add clue?
        let newClues = this.clues.slice();
        newClues.push(clue);

        let newLetters = new Map(this.letters);
        clue.letterPositions.forEach(pos => {
            let key = pos.row + ';' + pos.col;
            let baseDir = clue.horizontal ? 'H' : 'V';
            let dir = newLetters.has(key) && newLetters.get(key).dir != baseDir ? 'B' : baseDir;
            newLetters.set(key, {'letter': pos.letter, 'dir': dir});
        });

        return new CrosswordPuzzle(newClues, newLetters);
    }

    get normalizedClues() {
        let rowOffset = -Math.min(...this.clues.map(clue => clue.row));
        let colOffset = -Math.min(...this.clues.map(clue => clue.col));

        let numRows = rowOffset+Math.max(...this.clues.map(clue => clue.afterRow));
        let numCols = colOffset+Math.max(...this.clues.map(clue => clue.afterCol));

        // If puzzle is too wide, flip it.
        if (numRows < numCols && numCols > 15) {
            return this.clues
                  .map(clue => new Clue(clue.answer,
                                        clue.col+colOffset,
                                        clue.row+rowOffset,
                                        !clue.horizontal));
        } else {
            return this.clues
                  .map(clue => new Clue(clue.answer,
                                        clue.row+rowOffset,
                                        clue.col+colOffset,
                                        clue.horizontal));
        }
    }
}
class Crossword {
    constructor(letters, clues, minGuessLength, allTopWords) {
        this.minGuessLength = minGuessLength;
        this.clues = clues;
        this.unansweredClues = this.clues;
        this.guesses = new Set();

        this.numLetters = letters.length;
        this.availableLetters = letters.split('').sort();

        this.allTopWords = allTopWords !== undefined ? allTopWords :
            new Set(topWords
                    .map(topWord => topWord.word)
                    .filter(word => this.isValidGuess(word)));

        this.numRows = Math.max(...clues.map(clue => clue.afterRow));
        this.numCols = Math.max(...clues.map(clue => clue.afterCol));
    }

    static fromFragment(fragment) {
        try {
            if (!fragment.includes('|')) return null;

            let [minGuessLength, sortedLetters, clueFragments] = fragment.split('|');
            let clues = clueFragments
                       .split(';')
                       .map(f => Clue.fromFragment(f, sortedLetters));
            return new Crossword(sortedLetters, clues, Number(minGuessLength));
        } catch (e) {
            return null;
        }
    }

    get fragment() {
        let sortedLetters = this.availableLetters.sort();
        return this.minGuessLength + '|' + sortedLetters.join('') + '|'
            + this.clues.map(clue => clue.toFragment(sortedLetters)).join(';');
    }

    static isMatchingWord(word, sortedLetters) {
        let sortedWord = word.split('').sort();
        let i = 0;
        for (let idx in sortedWord) {
            while (sortedWord[idx] != sortedLetters[i++]) {
                if (i >= sortedLetters.length) return false;
            }
        }
        return true;
    }

    static generateDefault() {
        return new Crossword('there', [
            new Clue('there', 2, 0, true),
            new Clue('the', 0, 2, false),
            new Clue('here', 2, 1, false),
        ]);
    }

    static generateRandom(settings) {
        if (settings === null) return null;

        let maxIters = 1000;
        let iters = 0;

        let regExp = new RegExp('^[a-z]{' + settings.min_word_length + ','
            + settings.max_word_length + '}$');
        let word;
        let sortedLetters;
        let matchingTopWords;
        let minMatches = Math.max(settings.min_matches, settings.num_clues);
        if (settings.max_matches < minMatches) return null;
        do {
            do {
                word = topWords[1000+getRandomInt(30000)].word;
                if (iters++ > maxIters) return null;
            } while (!regExp.test(word) || !isValidWord(word));
            sortedLetters = word.split('').sort();
            let preciseRegExp = new RegExp('^['
                + [...new Set(sortedLetters)].join('')
                + ']{' + settings.min_guess_length + ',}$');
            matchingTopWords =
                topWords
               .filter(topWord => preciseRegExp.test(topWord.word)
                        && Crossword.isMatchingWord(topWord.word,
                                                    sortedLetters)
                        && isValidWord(topWord.word));
        } while(matchingTopWords.length < minMatches
             || matchingTopWords.length > settings.max_matches);

        let allMatchingWords = new Set(matchingTopWords.map(topWord => topWord.word));
        // Sort topWords by length descending.
        matchingTopWords = [...new Set(matchingTopWords.map(topWord => topWord.word.length))].sort((a,b) => b-a).flatMap(wordLen => matchingTopWords.filter(topWord => topWord.word.length == wordLen));

        function possibleCluesForCrossword(crossword, clueWord) {
            let clues = crossword.clues;
            let letters = crossword.letters;

            let possibleCluesForWord = [];
            let maxIntersections = 0;
            if (clues.some(clue => clue.answer == clueWord)) {
                return {'maxIntersections': 0, 'options': []};
            }
            for (let attachIdx = 0; attachIdx < clueWord.length; attachIdx++) {
                let attachLetter = clueWord[attachIdx];
                clues.forEach(clue => {
                    for (let clueIdx in clue.answer) {
                        clueIdx = Number(clueIdx);
                        if (clue.answer[clueIdx] != attachLetter) continue;
                        let newClue;
                        if (clue.horizontal) {
                            newClue = new Clue(clueWord,
                                               clue.row-attachIdx,
                                               clue.col+clueIdx,
                                               false);
                        } else {
                            newClue = new Clue(clueWord,
                                               clue.row+clueIdx,
                                               clue.col-attachIdx,
                                               true);
                        }
                        // TODO Allow two letter words?
                        if ([newClue.beforePosition, newClue.afterPosition].some(pos => letters.has(pos.row + ';' + pos.col))) {
                            continue;
                        }
                        let dir = newClue.horizontal ? 'H' : 'V';
                        let adj = newClue.adjacentPositions;
                        let cluePos = newClue.letterPositions;
                        let lastHasLetter = false;
                        let invalid = false;
                        newClue.intersections = 0;
                        for (let i = 0; i < cluePos.length; i++) {
                            let pos = cluePos[i];
                            let key = pos.row + ';' + pos.col;
                            let thisHasLetter = letters.has(key);
                            if (thisHasLetter) {
                                newClue.intersections++;
                                if (lastHasLetter
                                     || letters.get(key).letter != pos.letter) {
                                    invalid = true;
                                    break;
                                }
                            }
                            else if (adj[i].some(pos => {
                                let key = pos.row + ';' + pos.col;
                                return letters.has(key);
                            })) {
                                invalid = true;
                                break;
                            }
                            if (adj[i].some(pos => {
                                let key = pos.row + ';' + pos.col;
                                return letters.has(key) && letters.get(key) == dir;
                            })) {
                                invalid = true;
                                break;
                            }

                            lastHasLetter = thisHasLetter;
                        }
                        if (!invalid) {
                            possibleCluesForWord.push(newClue);
                            maxIntersections = Math.max(maxIntersections,
                                                        newClue.intersections);
                        }
                    }
                });
            }

            return {'maxIntersections': maxIntersections,
                    'options': possibleCluesForWord};
        }
        function tryAugmentCrosswords(crosswords) {
            let defaultResult = null;
            for (let topWordsIdx in matchingTopWords) {
                let clueWord = matchingTopWords[topWordsIdx].word;

                let possibleClues = crosswords.map(crossword => {
                    return {'baseCrossword': crossword,
                            'possibleClues': possibleCluesForCrossword(
                                                crossword, clueWord)};
                });
                if (possibleClues.some(possibleCluesObj => possibleCluesObj.possibleClues.maxIntersections > 1)) {
                    let maxIntersections = Math.max(...possibleClues.map(crosswordOptions => crosswordOptions.possibleClues.maxIntersections));
                    possibleClues =
                        possibleClues
                       .filter(crosswordOptions => crosswordOptions.possibleClues.maxIntersections
                                        == maxIntersections)
                       .flatMap(crosswordOptions => crosswordOptions.possibleClues.options
                                          .map(option => {
                            return {'baseCrossword': crosswordOptions.baseCrossword,
                                    'newClue': option};
                       }).filter(possibleClue => possibleClue.newClue.intersections
                                        == maxIntersections));
                    // TODO Other considerations for selecting best crossword?
                    let selectedClue = possibleClues[getRandomInt(possibleClues.length)];
                    return selectedClue.baseCrossword.withClue(selectedClue.newClue);
                } else if (defaultResult === null && possibleClues.some(crosswordOptions => crosswordOptions.possibleClues.options.length > 0)) {
                    defaultResult = possibleClues;
                }
            }
            return defaultResult;
        }
        function tryAugmentCrossword(crossword, maxNewWords) {
            let crosswords = [crossword];
            for (let i = 0; i < maxNewWords; i++) {
                let maybeCrossword = tryAugmentCrosswords(crosswords);
                if (maybeCrossword instanceof CrosswordPuzzle) {
                    return maybeCrossword;
                } else if (maybeCrossword === null) {
                    return null;
                } else {
                    crosswords = maybeCrossword
                                .flatMap(crosswordOptions =>
                                    crosswordOptions.possibleClues.options
                                   .map(newClue => crosswordOptions
                                                  .baseCrossword
                                                  .withClue(newClue)));
                }
            }
            return crosswords[getRandomInt(crosswords.length)];
        }

        let crossword = new CrosswordPuzzle()
                       .withClue(new Clue(word, 0, 0, getRandomBool()));
        while (crossword.clues.length < settings.num_clues) {
            crossword = tryAugmentCrossword(crossword, Math.min(4, settings.num_clues - crossword.clues.length));
            if (crossword === null) return null;
        }

        return new Crossword(sortedLetters.join(''), crossword.normalizedClues,
                             settings.min_guess_length, allMatchingWords);
    }

    isValidGuess(guess) {
        if (guess.length < this.minGuessLength) return false;

        let availableLetters = this.availableLetters.slice();
        for (let idx in guess) {
            let letter = guess[idx];
            let letterIdx = availableLetters.indexOf(letter);
            if (letterIdx > -1) {
                availableLetters.splice(letterIdx, 1);
            } else {
                return false;
            }
        }
        return isValidWord(guess);
    }

    get won() {
        return this.unansweredClues.length == 0;
    }

    makeGuess(guess) {
        if (!this.isValidGuess(guess) || this.guesses.has(guess)) return null;
        this.guesses.add(guess);

        let cluesAnswered = this.unansweredClues
                                .filter(clue => clue.answer == guess);
        cluesAnswered.forEach(clue => clue.solved = true);
        this.unansweredClues = this.unansweredClues
                                   .filter(clue => !clue.solved);

        return cluesAnswered;
    }
}