LabyrinthianWordChooser.js

//
//This is what happens when you get Markov Chains wrong. Magic! >:{D
//

var markov_id = 0;
var markovChain = [];

function parseNameCSVData(){
    var rawWordData = $('#name-csv-data').val().split(',');
    var words = [];
    for(var i = 0; i < rawWordData.length; i++){
        words.push(rawWordData[i].trim());
    }

    //Reset our variables
    markov_id = 0;
    markovChain = [];

    //Implement the primary function for building our markov chain
    CreateCharacterMarkovChain(words);

    $('#application-status').text('Markov chain created successfully.');
    $('#generate-names-btn').on('click', function(){
        generateNewWords();
    });
}

function generateNewWords(){
    var outputWordList = [];
    var numberOfWords = parseInt($('#number-of-generated-names').val());

    for(var i = 0; i < numberOfWords; i++){
        var letterList = [];

        //Determine the first letter of the word via a roulette style random number selector
        var firstLetters = [];
        for(var m = 0; m < markovChain.length; m++){
            if(markovChain[m].isBeginningNode){
                firstLetters.push(markovChain[m]);
            }
        }
        var orderedFirstLetters = firstLetters.sort(function(a, b){
            return a.probability - b.probability;
        });

        var randSelection = Math.random();
        var totalProb = 0.0;
        var currentlySelectedId;

        var totalCurrentProbability = 0.0;
        var currentlySelectedId;
        for(var c = 0; c < orderedFirstLetters.length; c++){
            totalCurrentProbability += orderedFirstLetters[c].probability;

            if(randSelection <= totalCurrentProbability){
                currentlySelectedId = orderedFirstLetters[c].id;
                letterList.push(markovChain[currentlySelectedId].propertyVal);
                break;
            }
        }

        //Now, given this first selected letter, determine the next letter iteratively until
        //we reach a markov chain node that represents the final letter in the chain
        var isNotEndLetter = true;
        while(isNotEndLetter){
            currentlySelectedId = markovChain[currentlySelectedId].chooseChild();
            letterList.push(markovChain[currentlySelectedId].propertyVal);
            if(markovChain[currentlySelectedId].isEndNode){
                isNotEndLetter = false;
            }
        }

        //Concactonate our letters into a string and append it to our list
        outputWordList.push(letterList.join(''));
    }

    //Output these words to the page so that the user can enjoy the results of our work
    $('#generated-names').empty();
    for(w in outputWordList){
        $('#generated-names').append('<div class="generated-word-result">' + outputWordList[w] +'</div>');
    }

    $('#application-status').text(numberOfWords + ' new words created from the current markov chain.');
}

function CreateCharacterMarkovChain(wordList){
    //Determine the beginning word nodes
    var firstLetterUnnormalizedProbability = [];
    var totalForNormalization = 0.0;
    for(var w = 0; w < wordList.length; w++){
        var firstLetter = wordList[w].charAt(0);
        var exists = firstLetterUnnormalizedProbability.indexOf(firstLetter);

        if(firstLetter in firstLetterUnnormalizedProbability){
            firstLetterUnnormalizedProbability[firstLetter]++;
        }
        else{
            firstLetterUnnormalizedProbability[firstLetter] = 1.0;
        }

        totalForNormalization++;
    }

    //Now add the normalized values into a set of new markov chain strands
    for(var key in firstLetterUnnormalizedProbability){
        var normalizedProbability = firstLetterUnnormalizedProbability[key] / totalForNormalization;
        var newMarkovNode = new MarkovNode(key, normalizedProbability, null, 0);
        newMarkovNode.isBeginningNode = true;
        markovChain.push(newMarkovNode);
    }

    //Go through all of our markov chain elements and recursively build out their children
    for(var mc in markovChain){
        //Go through the word list and determine
        for(var w = 0; w < wordList.length; w++){
            //Who's your daddy?
            if(wordList[w].charAt(0) === markovChain[mc].propertyVal){
                recursiveChildBuilder(wordList[w], 1, markovChain[mc].id);
            }
        }
    }

    //Once again go through our markov chain elements and recursively normalize their children
    for(var mn = 0; mn < markovChain.length; mn++){
        if(markovChain[mn].isBeginningNode){
            //Normalize this set of children
            //And implement this on each of the child elements
            recursiveNormalizer(markovChain[mn].id);
        }
    }
}

function recursiveNormalizer(parentId){
    markovChain[parentId].normalizeChildProbabilities();

    for(var c = 0; c < markovChain[parentId].childIds.length; c++){
        recursiveNormalizer(markovChain[parentId].childIds[c]);
    }
}

function recursiveChildBuilder(word, depth, parentId){
    //First, check that this is even a character, if it is then proceed,
    //otherwise mark the previous parent node as an end node
    //Note To Self: Apparently an empty string is not the same as null. And when no string is found at a location,
    //an empty string is exactly what this hell-spawn returns.
    if(word.charAt(depth) === ''){
        markovChain[parentId].isEndNode = true;
    }
    else{
        //First check if any children exist with this property
        var foundLocation = markovChain[parentId].searchChildren(word.charAt(depth));

        //If it exists, then iterate it's value, otherwise create a new node
        if(foundLocation !== -1){
            markovChain[foundLocation].probability++;
        }
        else if(word.charAt(depth) != null){
            foundLocation = markovChain[parentId].createChildren(word.charAt(depth), depth, 1.0);
        }

        //Increase the depth and re-implement the recursion method
        recursiveChildBuilder(word, depth + 1, foundLocation);
    }
}

var MarkovNode = function(propertyVal, probability, parent_node, depth){
    this.propertyVal = propertyVal;
    this.probability = probability;
    this.parent_node = null;
    if(parent_node !== null){
        this.parent_node = parent_node;
    }
    this.id = markov_id;
    this.childIds = [];
    this.isEndNode = false;
    this.depth = depth;
    this.isBeginningNode = false;
    markov_id++;

    this.createChildren = function(propertyVal, depth, probability){
        var newNode = new MarkovNode(propertyVal, probability, markovChain[this.id], depth);

        markovChain[newNode.id] = newNode;
        this.childIds.push(newNode.id);

        return newNode.id;
    };

    this.normalizeChildProbabilities = function(){
        var sumTotal = 0.0;
        for(var c = 0; c < this.childIds.length; c++){
            sumTotal += markovChain[this.childIds[c]].probability;
        }

        //Now divide out each of the values in the children by these values
        for(var c = 0; c < this.childIds.length; c++){
            markovChain[this.childIds[c]].probability = markovChain[this.childIds[c]].probability / sumTotal;
        }
    };

    this.searchChildren = function(property){
        returnVal = -1;
        for(var c = 0; c < this.childIds.length; c++){
            if(markovChain[this.childIds[c]].propertyVal === property){
                 returnVal = this.childIds[c];
            }
        }
        return returnVal;
    }

    this.chooseChild = function(){
        //Gather all child elements
        var children = [];
        for(var c = 0; c < this.childIds.length; c++){
            children.push(markovChain[this.childIds[c]]);
        }

        //Organize the children according to their probability
        var orderedChildren =  children.sort(function(a, b){
            return (a.probability - b.probability);
        });

        //Use a roulette style probability chooser to find the child most likely to be
        var randSelection = Math.random();

        var totalCurrentProbability = 0.0;
        var selectedId;
        for(var c = 0; c < orderedChildren.length; c++){
            totalCurrentProbability += orderedChildren[c].probability;
            if(randSelection <= totalCurrentProbability){
                selectedId = orderedChildren[c].id;
                break;
            }
        }

        return selectedId;
    };
}