solver.js
/*
		Main algorithm. Starts with one word solutions, which is exactly the words data
		structure. Next it combines them all with each other, finding the two word
		solutions. Then it combines these with the one word solutions, which finds
		the three word solutions. And so on, until it cannot continue.
	*/
Main algorithm. Starts with one word solutions, which is exactly the words data
structure. Next it combines them all with each other, finding the two word
solutions. Then it combines these with the one word solutions, which finds
the three word solutions. And so on, until it cannot continue.
Main algorithm . Starts with one word solutions which is exactly the words data structure . Next it combines them all with each other finding the two word solutions . Then it combines these with the one word solutions which finds the three word solutions . And so on until it cannot continue .
function findSolutions(wordList, firstSet) {
		console.log('Finding solutions...')
		let result = []
		let solutionSet = firstSet
		let wordCount = 1
		while (solutionSet.length > 0) {
			result.push(solutionSet)
			wordCount++
			console.log('Finding solutions with ' + wordCount + ' words...')
			solutionSet = nextSolutions(solutionSet)
		}
		console.log('No solutions with ' + wordCount + ' words.')
		console.log('Combining all solutions...')
		result = _.flatten(result)
		console.log('Translating solutions...')
		result = result.map(translateSolution)
		result = _.flatten(result)
		console.log('Done.')
		return result
		function nextSolutions(solutions) {
			let nextSolutions = {}
			for (let sol = 0 ; sol < solutions.length ; sol++) {
				let solCanon =  solutions[sol].canonical
				let maxLength = numOfBlocks - solCanon.length
				for (let wrd = 0 ; wrd < wordList.length ; wrd ++) {
					let wrdCanon = wordList[wrd].canonical
					if (wrdCanon.length > maxLength) {
						continue
					}
					let combined = canonicalVersion(solCanon + wrdCanon)
					if (canWorkFast(combined)) {
						addToSolutionSet(nextSolutions, combined, solutions[sol], wrdCanon)
					}
				}
			}
			let result = []
			for (let solution in nextSolutions) {
				result.push({
					canonical: solution,
					factors: nextSolutions[solution]
				})
			}
			return result
		}
		function addToSolutionSet(solutionSet, canonical, prev, factor) {
			let newFactors = prev.factors.map((factorList) => {
				return factorList.concat(factor).sort()
			})
			if (solutionSet[canonical]) {
				solutionSet[canonical] = _.uniqBy(solutionSet[canonical].concat(newFactors), (list) => {
					return list.join('-')
				})
			} else {
				solutionSet[canonical] = newFactors
			}
		}
		function translateSolution(solution) {
			let expanded = solution.factors.map((factors) => {
				return factors.map((word) => {
					return wordDict[word]
				})
			})
			let translated = expanded.map((list) => {
				return listCombinations(list, ' ')
			})
			return _.flatten(translated)
		}
	}
function findSolutions ( wordList , firstSet ) { console . log ( 'Finding solutions...' ) let result = [ ] let solutionSet = firstSet let wordCount = 1 while ( solutionSet . length > 0 ) { result . push ( solutionSet ) wordCount ++ console . log ( 'Finding solutions with ' + wordCount + ' words...' ) solutionSet = nextSolutions ( solutionSet ) } console . log ( 'No solutions with ' + wordCount + ' words.' ) console . log ( 'Combining all solutions...' ) result = _ . flatten ( result ) console . log ( 'Translating solutions...' ) result = result . map ( translateSolution ) result = _ . flatten ( result ) console . log ( 'Done.' ) return result function nextSolutions ( solutions ) { let nextSolutions = { } for ( let sol = 0 ; sol < solutions . length ; sol ++ ) { let solCanon = solutions [ sol ] . canonical let maxLength = numOfBlocks - solCanon . length for ( let wrd = 0 ; wrd < wordList . length ; wrd ++ ) { let wrdCanon = wordList [ wrd ] . canonical if ( wrdCanon . length > maxLength ) { continue } let combined = canonicalVersion ( solCanon + wrdCanon ) if ( canWorkFast ( combined ) ) { addToSolutionSet ( nextSolutions , combined , solutions [ sol ] , wrdCanon ) } } } let result = [ ] for ( let solution in nextSolutions ) { result . push ( { canonical : solution , factors : nextSolutions [ solution ] } ) } return result } function addToSolutionSet ( solutionSet , canonical , prev , factor ) { let newFactors = prev . factors . map ( ( factorList ) => { return factorList . concat ( factor ) . sort ( ) } ) if ( solutionSet [ canonical ] ) { solutionSet [ canonical ] = _ . uniqBy ( solutionSet [ canonical ] . concat ( newFactors ) , ( list ) => { return list . join ( '-' ) } ) } else { solutionSet [ canonical ] = newFactors } } function translateSolution ( solution ) { let expanded = solution . factors . map ( ( factors ) => { return factors . map ( ( word ) => { return wordDict [ word ] } ) } ) let translated = expanded . map ( ( list ) => { return listCombinations ( list , ' ' ) } ) return _ . flatten ( translated ) } }
Main algorithm.
Main algorithm .
// By far, the most compute-intensive function // For every solution, try combining it with every word // This double loop is the bottleneck of the entire algorithm // Some optimization - a length check is faster than canWorkFast(canonicalVersion(solCanon + wrdCanon)) // Convert back to list // This isn't the bottleneck, but any optimization here would be pretty big, and there definitely could be optimization // Replace each canonical form with the array of real words // Generate the possible sentences with the real words