longest sequence.js

import {words as _words} from "popular-english-words";

let words = _words.getAll();
//let words = _words.getMostPopular(100000);
let set = new Set(words);

function findSmallestRoot(word, path=null) {
	if (!path) {
		path = [word];
	}
	
	// base case - one-letter word obvs has no subwords
	
	if (word.length === 1) {
		return {root: word, path};
	}
	
	// get word minus last char ("l") and minus first char ("r")
	// see if they're words, and if they are return the one that leads
	// to the shortest word
	
	let l = word.substr(0, word.length - 1);
	let r = word.substr(1);
	
	let lRoot;
	let rRoot;
	
	if (isWord(l)) {
		lRoot = findSmallestRoot(l, [l, ...path]);
	}
	
	if (isWord(r)) {
		rRoot = findSmallestRoot(r, [r, ...path]);
	}
	
	// cases where none or only one shortening is a word
	
	if (!lRoot && !rRoot) {
		// if none, this is the same as for single-letter words -
		// just return the given word
		return {root: word, path};
	} else if (lRoot && !rRoot) {
		return lRoot;
	} else if (rRoot && !lRoot) {
		return rRoot;
	}
	
	// both shortenings are words - return the one that led to the shortest
	// word
	
	// this will be the one that went to the highest depth of recursion,
	// by going longer without hitting the case where neither shortening is
	// a word
	
	if (lRoot.root.length < rRoot.root.length) {
		return lRoot;
	} else if (rRoot.root.length < lRoot.root.length) {
		return rRoot;
	}
	
	// it crashed when I first ran it without the below line,
	// as "the" has equal length roots ("th" is in the list)
	
	// it doesn't matter which one we return I don't think, as by
	// this point we have already done the recursive bit to check
	// if we can go further - the two words we have are guaranteed
	// to be irreducible
	
	return lRoot;
}

function isWord(w) {
	return set.has(w);
}

function findLongestSequence() {
	let longestSeq = null;
	
	for (let word of words) {
		let {path} = findSmallestRoot(word);
		
		if (!longestSeq || path.length > longestSeq.length) {
			longestSeq = path;
		}
	}
	
	return longestSeq;
}

console.time();
let seq = findLongestSequence();

console.timeEnd();
console.log(seq);