441 lines
17 KiB
JavaScript
441 lines
17 KiB
JavaScript
'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));
|
|
}
|
|
}
|
|
|
|
get width() {
|
|
let colOffset = -Math.min(...this.clues.map(clue => clue.col));
|
|
|
|
let numCols = colOffset+Math.max(...this.clues.map(clue => clue.afterCol));
|
|
return numCols;
|
|
}
|
|
|
|
get height() {
|
|
let rowOffset = -Math.min(...this.clues.map(clue => clue.row));
|
|
|
|
let numRows = rowOffset+Math.max(...this.clues.map(clue => clue.afterRow));
|
|
return numRows;
|
|
}
|
|
|
|
get largestDimension() {
|
|
return Math.max(this.width, this.height);
|
|
}
|
|
}
|
|
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 selectRandomCrossword(crosswords) {
|
|
let best = [];
|
|
let smallestSize = null;
|
|
|
|
crosswords.forEach(crossword => {
|
|
let size = crossword.largestDimension;
|
|
if (smallestSize == null || size < smallestSize) {
|
|
best = [crossword];
|
|
smallestSize = size;
|
|
} else if(size == smallestSize) {
|
|
best.push(crossword);
|
|
}
|
|
});
|
|
|
|
return best[getRandomInt(best.length)];
|
|
}
|
|
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?
|
|
return selectRandomCrossword(possibleClues.map(selectedClue => 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 selectRandomCrossword(crosswords);
|
|
}
|
|
|
|
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;
|
|
}
|
|
}
|