gabriellesc/Wordplay with Scrabble.md

## Wordplay with Scrabble.md

      
    Raw
  

              Wordplay with Scrabble.md
            
          
    Wordplay (original host: https://hackpad.com/More-graphs-and-trees-inc-wordplay-Jy4GxlaagVH)
Practical tasks that have been asked in interviews, and which Jessica McKellar was disappointed some Hacker Schoolers had trouble with.
Using the official SOWPODS Scrabble dictionary:

what words contain "UU"? What words contain "Q" without "U"?

what letters, if any, never appear doubled? (by that I mean -- "AA" does appear doubled because it is in "AARDVARK", "BB" does appear doubled because it is in "BUBBLE" -- are there any letters that never appear doubled in a word)

what is the longest palindrome?

what words contain all of the vowels and Y, in alphabetical order?

what words contain all of the vowels and Y, in any order?

what letter makes the most appearances in a single word, and what is that word?

what words are the longest anagrams of each other? (single words, please, no phrases)

Some of these questions are a good opportunity to explore regular expressions.

For each of these questions, after implementing a solution:

what is the big-O complexity of the solution?

what is another way of solving the problem?

is there a faster solution?

As a Wordplay grand finale:

Implement a Scrabble cheater: https://openhatch.org/wiki/Hacker_School_Scrabble_challenge


## wordplayWithScrabble.html
<html>
  <head>
    <meta charset="UTF-8" />
    <title>Wordplay with Scrabble</title>
    <style>pre { font-size: 14px; }</style>
  </head>
  <body>
    <h1>Wordplay with Scrabble</h1>
  </body>
  <footer>
    <script src="wordplayWithScrabble.js"></script>
  </footer>
</html>

## wordplayWithScrabble.js
let src = 'https://raw.githubusercontent.com/jesstess/Scrabble/master/scrabble/sowpods.txt';

var a = document.createElement('a');
a.href = src;
a.textContent = src;

var i = document.createElement('i');
i.appendChild(document.createTextNode('using '));
i.appendChild(a);

document.body.appendChild(i);

let get = fetch(src)
    .then(resp => resp.text())
    .then(processWords);

function print(tag, content) {
    let elem = document.createElement(tag);
    elem.textContent = content;
    document.body.appendChild(elem);
}

function prettyPrint(title, content) {
    let h = document.createElement('h3');
    h.textContent = title;
    document.body.appendChild(h);

    let pre = document.createElement('pre');
    pre.textContent = content;
    pre.style.width = '50em';
    pre.style.columns = '3';
    document.body.appendChild(pre);
}

function processWords(resp) {
    let words = resp.split(/\r*\n/g);
    print('h2', words.length + ' words in total');

    UU(words);

    QU(words);

    undoubled(words);

    longPal(words);

    vowelsY(words);

    freqLetter(words);

    anagrams(words);
}

// what words contain "UU"?
function UU(array) {
    let matches = array.filter(elem => elem.match(/UU/));
    prettyPrint(matches.length + ' words containing "UU"', matches.join('\n'));
}

// What words contain "Q" without "U"?
function QU(array) {
    let matches = array.filter(elem => elem.match(/^[^U]*Q[^U]*$/));
    prettyPrint(matches.length + ' words containing "Q" without "U"', matches.join('\n'));
}

// what letters, if any, never appear doubled?
function undoubled(array) {
    let doubled = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('');

    for (var elem of array) {
	if (!doubled) {
	    break;
	}

	let letters = elem.match(/([A-Z])\1/g);
	if (letters) {
	    letters.forEach(letter => {
		var i = doubled.indexOf(letter[0]);
		if (i != -1) {
		    doubled.splice(i, 1);
		}
	    });
	}
    }

    print('h3', doubled.length + ' letters that never appear doubled: ' + doubled.join(', '));
}

// what is the longest palindrome?
function longPal(array) {
    let pals = array.filter(elem => {
	var start = 0, end = elem.length - 1;

	while (start < end) {
	    if (elem[start] != elem[end]) {
		return false;
	    }
	    start += 1;
	    end -= 1;
	}
	return true;
    });

    let maxLen = 0, maxPal = [];
    for (var pal of pals) {
	var palLen = pal.length;

	if (palLen == maxLen) {
	    maxLen = palLen;
	    maxPal.push(pal);
	} else if (palLen > maxLen) {
	    maxLen = palLen;
	    maxPal = [pal];
	}
    }

    if (maxPal.length > 1) {
	print('h3', maxPal.join(',') + ' are the longest palindromes');
    } else {
	print('h3', maxPal[0] + ' is the longest palindrome');
    }
}

// what words contain all of the vowels and Y, in alphabetical order?
// what words contain all of the vowels and Y, in any order?
function vowelsY(array) {
    let any = array.filter(elem => elem.match(/.*A.*E.*I.*O.*U.*Y/));
    let alph = any.filter(elem => elem.match(/[AEIOUY]/g).reduce((prev, curr) => curr >= prev ? curr : false));

    prettyPrint(alph.length + ' words containing all of the vowels and Y, in alphabetical order',
		alph.join('\n'));

    prettyPrint(any.length + ' words containing all of the vowels and Y, in any order',
		any.join('\n'));
}

// what letter makes the most appearances in a single word, and what is that word?
function freqLetter(array) {
    let freqs = { 'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0,
		  'J': 0, 'K': 0, 'L': 0, 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0,
		  'S': 0, 'T': 0, 'U': 0, 'V': 0, 'W': 0, 'X': 0, 'Y': 0, 'Z': 0 };

    let maxFreq = 0, maxLetter = {};

    for (var word of array) {
	for (var letter of word) {
	    freqs[letter] += 1;
	}

	for (var letter in freqs) {
	    // letter freq is greater in this word than previous max freq of this letter
	    if (freqs[letter] > maxFreq) {
		maxFreq = freqs[letter];
		maxLetter = { [letter]: [word] };

	    // letter freq is equal in this word to max freq of this (or another) letter elsewhere
	    } else if (freqs[letter] && freqs[letter] == maxFreq) {
		if (maxLetter[letter]) {
		    maxLetter[letter].push(word);
		} else {
		    maxLetter[letter] = [word];
		}
	    }

	    // reset freq
	    freqs[letter] = 0;
	}
    }

    let first = true;
    for (var letter in maxLetter) {
	prettyPrint('The letter ' + letter + (first ? '' : ' also') +
		    ' makes the most appearances in a single word, in',
		    maxLetter[letter].join(', '));
	first = false;
    }
}

// what words are the longest anagrams of each other?
function anagrams(array) {
    let 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 };

    let map = {};
    for (var elem of array) {
	let hash = elem.split('').reduce((prod, letter) => primes[letter] * prod, 1);

	if (map[hash]) {
	    map[hash].push(elem);
	} else {
	    map[hash] = [elem];
	}
    }

    let maxLen = 0, maxAna = [];
    for (var ana in map) {
	if (map[ana].length > 1) {
	    var anaLen = map[ana][0].length;

	    if (anaLen == maxLen) {
		maxLen = anaLen;
		maxAna.push(map[ana]);
	    } else if (anaLen > maxLen) {
		maxLen = anaLen;
		maxAna = [map[ana]];
	    }
	}
    }

    print('h3', 'Words that are the longest anagrams of each other:');

    let pre = document.createElement('pre');
    pre.textContent = maxAna.map(ana => ana.join(' & ')).join('\n');
    document.body.appendChild(pre);
}
	<html>
	<head>
	<meta charset="UTF-8" />
	<title>Wordplay with Scrabble</title>
	<style>pre { font-size: 14px; }</style>
	</head>
	<body>
	<h1>Wordplay with Scrabble</h1>
	</body>
	<footer>
	<script src="wordplayWithScrabble.js"></script>
	</footer>
	</html>
	let src = 'https://raw.githubusercontent.com/jesstess/Scrabble/master/scrabble/sowpods.txt';

	var a = document.createElement('a');
	a.href = src;
	a.textContent = src;

	var i = document.createElement('i');
	i.appendChild(document.createTextNode('using '));
	i.appendChild(a);

	document.body.appendChild(i);

	let get = fetch(src)
	.then(resp => resp.text())
	.then(processWords);

	function print(tag, content) {
	let elem = document.createElement(tag);
	elem.textContent = content;
	document.body.appendChild(elem);
	}

	function prettyPrint(title, content) {
	let h = document.createElement('h3');
	h.textContent = title;
	document.body.appendChild(h);

	let pre = document.createElement('pre');
	pre.textContent = content;
	pre.style.width = '50em';
	pre.style.columns = '3';
	document.body.appendChild(pre);
	}

	function processWords(resp) {
	let words = resp.split(/\r*\n/g);
	print('h2', words.length + ' words in total');

	UU(words);

	QU(words);

	undoubled(words);

	longPal(words);

	vowelsY(words);

	freqLetter(words);

	anagrams(words);
	}

	// what words contain "UU"?
	function UU(array) {
	let matches = array.filter(elem => elem.match(/UU/));
	prettyPrint(matches.length + ' words containing "UU"', matches.join('\n'));
	}

	// What words contain "Q" without "U"?
	function QU(array) {
	let matches = array.filter(elem => elem.match(/^[^U]Q[^U]$/));
	prettyPrint(matches.length + ' words containing "Q" without "U"', matches.join('\n'));
	}

	// what letters, if any, never appear doubled?
	function undoubled(array) {
	let doubled = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'.split('');

	for (var elem of array) {
	if (!doubled) {
	break;
	}

	let letters = elem.match(/([A-Z])\1/g);
	if (letters) {
	letters.forEach(letter => {
	var i = doubled.indexOf(letter[0]);
	if (i != -1) {
	doubled.splice(i, 1);
	}
	});
	}
	}

	print('h3', doubled.length + ' letters that never appear doubled: ' + doubled.join(', '));
	}

	// what is the longest palindrome?
	function longPal(array) {
	let pals = array.filter(elem => {
	var start = 0, end = elem.length - 1;

	while (start < end) {
	if (elem[start] != elem[end]) {
	return false;
	}
	start += 1;
	end -= 1;
	}
	return true;
	});

	let maxLen = 0, maxPal = [];
	for (var pal of pals) {
	var palLen = pal.length;

	if (palLen == maxLen) {
	maxLen = palLen;
	maxPal.push(pal);
	} else if (palLen > maxLen) {
	maxLen = palLen;
	maxPal = [pal];
	}
	}

	if (maxPal.length > 1) {
	print('h3', maxPal.join(',') + ' are the longest palindromes');
	} else {
	print('h3', maxPal[0] + ' is the longest palindrome');
	}
	}

	// what words contain all of the vowels and Y, in alphabetical order?
	// what words contain all of the vowels and Y, in any order?
	function vowelsY(array) {
	let any = array.filter(elem => elem.match(/.A.E.I.O.U.Y/));
	let alph = any.filter(elem => elem.match(/[AEIOUY]/g).reduce((prev, curr) => curr >= prev ? curr : false));

	prettyPrint(alph.length + ' words containing all of the vowels and Y, in alphabetical order',
	alph.join('\n'));

	prettyPrint(any.length + ' words containing all of the vowels and Y, in any order',
	any.join('\n'));
	}

	// what letter makes the most appearances in a single word, and what is that word?
	function freqLetter(array) {
	let freqs = { 'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0,
	'J': 0, 'K': 0, 'L': 0, 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0,
	'S': 0, 'T': 0, 'U': 0, 'V': 0, 'W': 0, 'X': 0, 'Y': 0, 'Z': 0 };

	let maxFreq = 0, maxLetter = {};

	for (var word of array) {
	for (var letter of word) {
	freqs[letter] += 1;
	}

	for (var letter in freqs) {
	// letter freq is greater in this word than previous max freq of this letter
	if (freqs[letter] > maxFreq) {
	maxFreq = freqs[letter];
	maxLetter = { [letter]: [word] };

	// letter freq is equal in this word to max freq of this (or another) letter elsewhere
	} else if (freqs[letter] && freqs[letter] == maxFreq) {
	if (maxLetter[letter]) {
	maxLetter[letter].push(word);
	} else {
	maxLetter[letter] = [word];
	}
	}

	// reset freq
	freqs[letter] = 0;
	}
	}

	let first = true;
	for (var letter in maxLetter) {
	prettyPrint('The letter ' + letter + (first ? '' : ' also') +
	' makes the most appearances in a single word, in',
	maxLetter[letter].join(', '));
	first = false;
	}
	}

	// what words are the longest anagrams of each other?
	function anagrams(array) {
	let 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 };

	let map = {};
	for (var elem of array) {
	let hash = elem.split('').reduce((prod, letter) => primes[letter] * prod, 1);

	if (map[hash]) {
	map[hash].push(elem);
	} else {
	map[hash] = [elem];
	}
	}

	let maxLen = 0, maxAna = [];
	for (var ana in map) {
	if (map[ana].length > 1) {
	var anaLen = map[ana][0].length;

	if (anaLen == maxLen) {
	maxLen = anaLen;
	maxAna.push(map[ana]);
	} else if (anaLen > maxLen) {
	maxLen = anaLen;
	maxAna = [map[ana]];
	}
	}
	}

	print('h3', 'Words that are the longest anagrams of each other:');

	let pre = document.createElement('pre');
	pre.textContent = maxAna.map(ana => ana.join(' & ')).join('\n');
	document.body.appendChild(pre);
	}