var fetch = require('node-fetch');
var src = 'https://raw.githubusercontent.com/jesstess/Scrabble/master/scrabble/sowpods.txt';
var dict;
// fetch and clean the dictionary
fetch(src)
.then(resp => resp.text())
.then(text => {
dict = text.split(/\r*\n/g);
dict = dict.filter(word => word.length); // remove any empty words
console.log(dict.length + ' words in total');
});
dict.filter(word => /UU/.test(word));
The solution is $O(n)$ for an input word of length $n$ (with the coefficient of $n$ depending on the regex matcher implementation).
Other ways of solving the problem are either directly equivalent to or less efficient than this method.
For example, we could implement filtering and regex matching ourselves ($O(n)$):
var UU = [];
for (var word of dict) {
for (var i = 0; i < word.length - 1; i++) {
// equivalent to regex matching
if (word[i] == 'U') {
if (word[i+1] == 'U') {
UU.push(word);
break;
} else {
i++; // skip the following letter, since it can't be the start of 'UU'
}
}
}
}
There is no faster solution: in the worst case (the word doesn't contain "UU"), all $n$ letters in a word must be examined to check for a match with this regular expression.
// match any number of characters other than 'U', then 'Q', then any number of characters other than 'U'
dict.filter(word => /^[^U]*Q[^U]*$/.test(word));
The solution is $O(n)$ for an input word of length $n$ (with the coefficient of $n$ depending on the regex matcher implementation).
Other ways of solving the problem are either directly equivalent to or less efficient than this method.
For example, we could filter by words containing "Q" and then by words not containing "U" ($O(n^2)$):
dict.filter(word => /Q/.test(word))
.filter(word => !/U/.test(word));
There is no faster solution: in the worst case (the word doesn't contain either "Q" or "U"), all $n$ letters in a word must be examined to check for a match with this regular expression.
var undoubled = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; // letters that have not appeared doubled
for (var word of dict) {
for (var i = 0; i < word.length - 1; i++) {
// if all the letters have already appeared doubled, stop looking
if (!undoubled) {
break;
}
if (word[i] == word[i+1]) {
// remove a doubled letter
undoubled = undoubled.replace(word[i], '');
i++;
}
}
}
console.log(undoubled.split(''));
The solution is $O(n)$ for a set of input words of total length $n$ (that is, $n$ is the sum of the lengths of all of the words in the set).
Alternatively, the solution is $O(m)$ for a set of input words of size $m$ (that is, there are $m$ words in the set).
Other ways of solving the problem are either directly equivalent to or less efficient than this method.
For example, we could search for each pair of doubled letters individually ($O(n)$, with a larger coefficient of $n$ than in the original solution):
var undoubled = [],
doubled;
for (var letter of 'ABCDEFGHIJKLMNOPQRSTUVWXYZ') {
var regex = new RegExp(letter + letter); // construct a regex matching the current letter, doubled
doubled = false;
// search for the doubled letter in each word
for (var word of dict) {
if (regex.test(word)) {
doubled = true;
break;
}
}
// if the letter has not appeared doubled in any word, add it to undoubled
if (!doubled) {
undoubled.push(letter);
}
}
There is no faster solution: in the worst case (no letters ever appear doubled), every letter of every word must be examined to look for a doubled letter.
var maxLen = 0,
maxPal = [];
for (var word of dict) {
var wordLen = word.length;
// advance the start and end indices until they meet
for (var start = 0, end = wordLen - 1;
// if the letters at start and end do not match, the word is not a palindrome
start < end && word[start] == word[end];
start++, end--);
// if the start and end indices met, the word is a palindrome
if (start >= end) {
if (wordLen > maxLen) {
// this palindrome is longer than the previous longest
maxLen = wordLen;
maxPal = [word];
} else if (wordLen == maxLen) {
// this palindrome is as long as the previous longest
maxPal.push(word);
}
}
}
console.log(maxPal);
The solution is $O(n)$ for a set of input words of total length $n$ (that is, $n$ is the sum of the lengths of all of the words in the set).
Other ways of solving the problem are either directly equivalent to or less efficient than this method.
For example, we could sort the words by decreasing length and then search for a palindrome from the start.
With a typical comparison-based sorting algorithm, in the worst case (none of the words are palindromes), this is $O(m\log(m) + n)$, where $m$ is the total number of input words.
// make a copy of the list of words and sort it in-place by decreasing length
var sortDict = [...dict];
sortDict.sort((wordA, wordB) => wordA.length > wordB.length ? -1 : 1);
var maxPal = [],
maxLen = 0;
for (var word of sortDict) {
// we have checked all the words of the same or greater length as the longest
// palindrome, so stop looking
if (word.length < maxLen) {
break;
}
// advance the start and end indices until they meet
for (var start = 0, end = word.length - 1;
// if the letters at start and end do not match, the word is not a palindrome
start < end && word[start] == word[end];
start++, end--);
// if the start and end indices met, the word is a palindrome
if (start >= end) {
maxPal.push(word);
maxLen = word.length;
}
}
There is no faster solution: in the worst case (every word is a palindrome), every letter of each word must be examined to verify that it is a palindrome.
var all = [],
// map of vowels and Y to powers of 2
bits = { 'A': 1, 'E': 2, 'I': 4, 'O': 8, 'U': 16, 'Y': 32 };
for (var word of dict) {
vowels = 0;
for (var letter of word) {
// if the letter is a vowel or Y, set the bit in vowels corresponding to this letter
if (letter in bits) {
vowels |= bits[letter];
}
// if all vowels and Y have been found in the word, stop looking
if (vowels == 63) {
all.push(word);
break;
}
}
}
console.log(all);
The solution is $O(n)$ for an input word of length $n$.
Other ways of solving the problem are either directly equivalent to or less efficient than this method.
For example, we could search that a word contains each vowel and Y, independently ($O(n)$, with a larger coefficient of $n$ than in the original solution):
dict.filter(word => (/A/.test(word) &&
/E/.test(word) &&
/I/.test(word) &&
/O/.test(word) &&
/U/.test(word) &&
/Y/.test(word)));
There is no faster solution: in the worst case (either the word contains all of the vowels, with a unique vowel at the end of the word, or the word contains all but one of the vowels, with a consonant at the end of the word), all $n$ letters in a word must be examined.
// match any number of non-vowel characters, then A, then any number of non-vowel characters or A,
// then E, then any number of non-vowel characters or E, etc.
dict.filter(word => /^[^AEIOUY]*A[^EIOUY]*E[^AIOUY]*I[^AEOUY]*O[^AEIUY]*U[^AEIOY]*Y[^AEIOU]*$/.test(word));
The solution is $O(n)$ for an input word of length $n$ (with the coefficient of $n$ depending on the regex matcher implementation).
Other ways of solving the problem are either directly equivalent to or less efficient than this method.
For example, we could remove all of the letters that are not vowels or Y, then check that the result is "AEIOUY", possibly with repeated letters ($O(n)$):
dict.filter(word => /^A+E+I+O+U+Y+$/.test(word.replace(/[^AEIOUY]/g, '')));
There is no faster solution: in the worst case (the word contains all of the vowels in alphabetical order, without Y or with the only Y at the end of the word), all $n$ letters in a word must be examined to check for a match with this regular expression.
// return the letter(s) that appears most frequently in word, and the number of appearances
function freqLetter(word) {
var freqs = {};
// map each letter to the number of times it appears in the word
for (var letter of word) {
freqs[letter] = freqs[letter] ? (freqs[letter]+1) : 1;
}
var maxFreq = 0,
maxLetter = [];
// find the letter(s) with the most appearances
for (var letter in freqs) {
if (freqs[letter] > maxFreq) {
maxFreq = freqs[letter];
maxLetter = [letter];
} else if (freqs[letter] == maxFreq) {
maxLetter.push(letter);
}
}
return { maxFreq, maxLetter };
}
// maxLetterAll: the letter(s) that appear most frequently in any word, mapped
// to a list of the word(s) in which they appear most frequently
var maxFreqAll = 0,
maxLetterAll = {};
for (var word of dict) {
// find the most frequent letter(s) in this word
var { maxFreq, maxLetter } = freqLetter(word);
// this word has a letter(s) that appears more frequently than the previous most
// frequent letter(s)
if (maxFreq > maxFreqAll) {
maxFreqAll = maxFreq;
maxLetterAll = {};
for (var l of maxLetter) {
maxLetterAll[l] = [word];
}
// this word has a letter(s) that appears with the same frequency as the previous
// most frequent letter(s)
} else if (maxFreq == maxFreqAll) {
for (var l of maxLetter) {
if (!maxLetterAll[l]) {
maxLetterAll[l] = [];
}
maxLetterAll[l].push(word);
}
}
}
console.log(maxLetterAll);
// map of letters to unique primes
var primes = { 'A': 2, 'B': 3, 'C': 5, 'D': 7, 'E': 11, 'F': 13, 'G': 17, 'H': 19, 'I': 23,
'J': 29, 'K': 31, 'L': 37, 'M': 41, 'N': 43, 'O': 47, 'P': 53, 'Q': 59, 'R': 61,
'S': 67, 'T': 71, 'U': 73, 'V': 79, 'W': 83, 'X': 89, 'Y': 97, 'Z': 101 };
// hash each word as a product of the primes corresponding to its letters
var hashmap = {};
for (var word of dict) {
var key = word.split('').reduce((prod, letter) => primes[letter] * prod, 1);
if (hashmap[key]) {
hashmap[key].push(word);
} else {
hashmap[key] = [word];
}
}
var maxLen = 0,
maxAna = [];
for (var key in hashmap) {
// multiple words had the same hash (i.e., these words are anagrams of each other)
if (hashmap[key].length > 1) {
var anaLen = hashmap[key][0].length; // length of the words
// these words are the same length as the previous longest anagrams
if (anaLen == maxLen) {
maxAna.push(hashmap[key]);
// these words are longer than the previous longest anagrams
} else if (anaLen > maxLen) {
maxLen = anaLen;
maxAna = [hashmap[key]];
}
}
}
console.log(maxAna);
Write a program that takes a Scrabble rack as an argument and returns all valid Scrabble words that can be constructed from that rack, along with their Scrabble scores, sorted by score.
function cheat(rack) {
// map of letters to unique primes
const primes = { 'A': 2, 'B': 3, 'C': 5, 'D': 7, 'E': 11, 'F': 13, 'G': 17, 'H': 19, 'I': 23,
'J': 29, 'K': 31, 'L': 37, 'M': 41, 'N': 43, 'O': 47, 'P': 53, 'Q': 59, 'R': 61,
'S': 67, 'T': 71, 'U': 73, 'V': 79, 'W': 83, 'X': 89, 'Y': 97, 'Z': 101 };
// hash the rack as a product of primes
var rackHash = rack.split('').reduce((prod, letter) => primes[letter] * prod, 1);
var valid = [],
factoredHash, subset;
// for each word, check whether the rack hash can be (at least partially) factored by its letters
for (var word of dict) {
factoredHash = rackHash; // rack hash being factored
subset = true; // whether this word is a subset of the rack
for (var letter of word) {
// check if the prime corresponding to this letter is a factor of the rack hash (prime product)
if (factoredHash % primes[letter] == 0) {
// the letter is in the rack, so factor it out from the hash ("remove it from the rack")
factoredHash /= primes[letter];
} else {
// the letter is not in the rack, so this word can't be made from this rack
subset = false;
break;
}
}
if (subset) {
valid.push(word);
}
}
// scores for each letter in Scrabble
const scores = { 'A': 1, 'C': 3, 'B': 3, 'E': 1, 'D': 2, 'G': 2,
'F': 4, 'I': 1, 'H': 4, 'K': 5, 'J': 8, 'M': 3,
'L': 1, 'O': 1, 'N': 1, 'Q': 10, 'P': 3, 'S': 1,
'R': 1, 'U': 1, 'T': 1, 'W': 4, 'V': 4, 'Y': 4,
'X': 8, 'Z': 10 }
// map valid words to their scores
valid = valid.map(word => ([word.split('').reduce((sum, letter) => scores[letter] + sum, 0),
word]));
// sort valid words by decreasing score
valid.sort((a, b) => a[0] > b[0] ? -1 : 1);
return valid;
}
console.log(cheat('ZAEFIEE'));
Modify your program to allow blank tiles, which can be used as any letter but contribute no points to the word score.
// use '_' to represent a blank tile in the rack
function cheatWithBlanks(rack) {
// map of letters to unique primes
// (map blank tiles to 1 so that they do not contribute to the rack hash)
const primes = { 'A': 2, 'B': 3, 'C': 5, 'D': 7, 'E': 11, 'F': 13, 'G': 17, 'H': 19, 'I': 23,
'J': 29, 'K': 31, 'L': 37, 'M': 41, 'N': 43, 'O': 47, 'P': 53, 'Q': 59, 'R': 61,
'S': 67, 'T': 71, 'U': 73, 'V': 79, 'W': 83, 'X': 89, 'Y': 97, 'Z': 101, '_': 1 };
// hash the rack as a product of primes
var rackHash = rack.split('').reduce((prod, letter) => primes[letter] * prod, 1);
// count the blank tiles
var blanks = rack.match(/_/g);
blanks = blanks ? blanks.length : 0;
// scores for each letter in Scrabble
const scores = { 'A': 1, 'C': 3, 'B': 3, 'E': 1, 'D': 2, 'G': 2,
'F': 4, 'I': 1, 'H': 4, 'K': 5, 'J': 8, 'M': 3,
'L': 1, 'O': 1, 'N': 1, 'Q': 10, 'P': 3, 'S': 1,
'R': 1, 'U': 1, 'T': 1, 'W': 4, 'V': 4, 'Y': 4,
'X': 8, 'Z': 10 }
var valid = [],
factoredHash, blanksLeft, score, subset;
// for each word, check whether the rack hash can be (at least partially) factored by its letters
for (var word of dict) {
factoredHash = rackHash; // rack hash being factored
blanksLeft = blanks; // how many blank tiles are left to use
score = 0; // score for this word
subset = true; // whether this word is a subset of the rack
for (var letter of word) {
// check if the prime corresponding to this letter is a factor of the rack hash (prime product)
if (factoredHash % primes[letter] == 0) {
// the letter is in the rack, so factor it out from the hash ("remove it from the rack")
factoredHash /= primes[letter];
score += scores[letter]; // add this letter to the score
} else if (blanksLeft) {
// the letter is not in the rack, but we can use a blank tile to represent it
blanksLeft -= 1;
} else {
// the letter is not in the rack, and we have no blank tiles left
subset = false;
break;
}
}
if (subset) {
valid.push([score, word]);
}
}
// sort valid words by decreasing score
valid.sort((a, b) => a[0] > b[0] ? -1 : 1);
return valid;
}
console.log(cheatWithBlanks('ZAEFIE_'));