Trie example for Baba Is You

README.txt

Pseudocode rather than Javascript, but I wanted the syntax highlighting.

Not tested at all.

trie.js

var input = "babaisyouwallisstopgjhhfflagiswinothasand"

var sentences = findSentences(input)

// expected output: [["baba", "is", "you", "wall", "is", "stop"], ["flag", "is", "win"], ["not", "has", "and"]]


function findSentences (input)
{
	var sentences = []
	var checked = []

	for (i in 0..input.length)
	{
		if (checked[i])
		{
			continue
		}
		
		var sentencesHere = findSentencesStartingAt(input, i)
		
		for (sentence in sentencesHere)
		{
			if (sentence.length < 3)
			{
				// I think there's no valid 2-word sentences in Baba Is You?
				// If you want all possible sentences including 1-word sentences, remove this code
				continue
			}
			
			sentences.push(sentence)
			
			// Prevent looking at substrings that are just the end of this sentence
			// If you want all possible sentences including all subsets of sentences, remove this code
			
			startingWordsLength = 0
			
			for (word in sentence)
			{
				startingWordsLength += word.length
				checked[i + startingWordsLength] = true
			}
		}
	}
	
	return sentences
}

function findSentencesStartingAt (input, startIndex)
{
	var sentences = []
	
	var wordsHere = findWordsStartingAt(input, startIndex)
	
	for (word in wordsHere)
	{
		var sentencesFollowing = findSentencesStartingAt(input, startIndex + word.length)
		
		if (sentencesFollowing.length == 0)
		{
			// No words immediately after this one, but it could be the end of a sentence
			// If you want all possible sentences including all subsets of sentences, do this even if sentencesFollowing.length > 0
			sentences.push(word);
		}
		else
		{
			for (sentence in sentencesFollowing)
			{
				sentence.unshift(word) // add the first word to the front of the sentence
				
				sentences.push(sentence)
			}
		}
	}
	
	return sentences
}

// Brute force implementation

function findWordsStartingAt (input, startIndex)
{
	var wordsFound = []
	
	for (word in allWords)
	{
		for (i in 0..word.length)
		{
			if (word[i] == input[i + startIndex])
			{
				wordsFound.push(word)
			}
		}
	}
	
	return wordsFound
}

// trie implementation

var trie = makeTrie(allWords)

/*
example trie: makeTrie(["me", "meat", "meta", "my", "you"])

{
	"m": {
		"e": {
			"": true,
			"a": {
				"t": {
					"": true
				}
			},
			"t": {
				"a": {
					"": true
				}
			},
		},
		"y": {
			"": true
		}
	},
	"y": {
		"o": {
			"u": {
				"": true
				
			}
		}
	}
}

*/

function findWordsStartingAt (input, startIndex)
{
	var words = []
	
	var wordSoFar = ""
	
	var subtrie = trie;
	
	for (i in startIndex..input.length)
	{
		var subtrie = subtrie[input[i]]
		
		if (! subtrie)
		{
			// No more words to find
			return words
		}
		
		wordSoFar += input[i]
		
		if (subtrie[""])
		{
			words.push(wordSoFar)
		}
	}
	
	return words
}

function makeTrie (allWords)
{
	var trie = {}
	
	for (word in allWords)
	{
		var subtrie = trie
		
		for (i in 0..word.length)
		{
			var letter = word[i]
			
			if (! subtrie[letter])
			{
				subtrie[letter] = {}
			}
			
			subtrie = subtrie[letter]
		}
		
		// end of word
		
		subtrie[""] = true
	}
	
	return trie
}