tieredIVR.js

var ballots = [
	[ ['A'], ['B', 'C'], ['D'], ['E', 'F', 'G', 'H', 'I', 'J'], ['K'] ],
	[ ['A', 'B'],                   ],
	[ ['A', 'B'], ['D'],            ],
	[ ['A', 'B'],                   ],
	[ ['A', 'B'],                   ],
	[ ['D'], ['B'],                   ],
	[ ['D', 'A'], ['C'],              ],
	[ ['C', 'D'], ['B'],              ],
	[ ['C', 'D', 'A'],                ],
	[ ['C', 'D', 'A'],                ],
	[ ['C', 'D', 'A'],                ],
	[ ['D'], ['C', 'B']               ],
]

function tieredIRV(ballots) {
	var flatBallots = flattenBallots(ballots)
	  , canidates = getCanidates(flatBallots)
	  , numCanidates = canidates.length
	  , order = []

	return getWinner(canidates, ballots)
}

function flattenBallots(ballots) {
	var flatBallots = []
	ballots.forEach(function(ballot, i) {
		var flatBallot = []
		ballot.forEach(function(tier) {
			tier.forEach(function(canidate) {
				flatBallot.push(canidate)
			})
		})
		flatBallots.push(flatBallot)
	})
	return flatBallots
}

function getCanidates(ballots, exclude) {
	exclude = exclude || []
	var canidates = []
	ballots.forEach(function(ballot) {
		ballot.forEach(function(canidate) {
			if(canidates.indexOf(canidate) == -1 && exclude.indexOf(canidate) == -1) {
				canidates.push(canidate)
			}
		})
	})
	return canidates
}

function getWinner(remainingCanidates, ballots) {
	if(remainingCanidates.length == 1)
		return remainingCanidates[0]

	var canidateVotePairs = getCanidateVotePairs(remainingCanidates, ballots)

	if(leaderHasMajority(canidateVotePairs)) {
		return canidateVotePairs[0][0]
	}

	eliminateLosingCanidate(canidateVotePairs, ballots, remainingCanidates)

	return getWinner(remainingCanidates, ballots)
}

function leaderHasMajority(canidateVotePairs) {
	var total = sumVotes(canidateVotePairs)
	  , topCanidateVotePair = canidateVotePairs[0]
	return topCanidateVotePair[1] / total > 0.5
}

function sumVotes(canidateVotePairs) {
	var total = 0
	canidateVotePairs.forEach(function(pair) {
		total += pair[1]
	})
	return total
}

function eliminateLosingCanidate(canidateVotePairs, ballots, remainingCanidates) {
	var losingCanidate = getLosingCanidate(canidateVotePairs, ballots)

	console.log('eliminated', losingCanidate)

	removeValueFromArray(losingCanidate, remainingCanidates)
}

function getLosingCanidate(canidateVotePairs, ballots) {
	var nonLeadingCanidates
	  , losingCanidateVotePair
	  , losingCanidate

	while(canidateVotePairs.length > 2) {
		nonLeadingCanidates = getAllCanidatesButLeader(canidateVotePairs)
		canidateVotePairs = getCanidateVotePairs(nonLeadingCanidates, ballots)
	}

	losingCanidateVotePair = getLastValueInArray(canidateVotePairs)
	losingCanidate = losingCanidateVotePair[0]

	return losingCanidate
}

function getAllCanidatesButLeader(canidateVotePairs) {
	return convertPairsToKeyArray(canidateVotePairs.slice(1))
}

function getLastValueInArray(array) {
	return array[array.length-1]
}

function removeValueFromArray(value, array) {
	var index = array.indexOf(value)
	array.splice(index, 1)
}

function getCanidateVotePairs(remainingCanidates, ballots) {
	var votesByCanidate = getVotesByCanidate(remainingCanidates, ballots)
	  , canidateVotePairs = convertObjectToArrayPairs(votesByCanidate)
	canidateVotePairs.sort(byVotesAsc)
	console.log(JSON.stringify(canidateVotePairs))
	return canidateVotePairs
}

function getVotesByCanidate(remainingCanidates, ballots) {
	var votesByCanidate = createCanidateVotes(remainingCanidates)
	ballots.forEach(function(ballot) {
		var votes = getVotesForBallot(remainingCanidates, ballot)
		addVotesToCanidates(votes, votesByCanidate)
	})
	return votesByCanidate
}

function createCanidateVotes(canidates) {
	var votesByCanidate = {}
	canidates.forEach(function(canidate) {
		votesByCanidate[canidate] = 0
	})
	return votesByCanidate
}

function addVotesToCanidates(votes, votesByCanidate) {
	Object.keys(votes).forEach(function(canidate) {
		votesByCanidate[canidate] += votes[canidate]
	})
}

function getVotesForBallot(remainingCanidates, ballot) {
	var votes = {}
	  , tier = getHighestTierWithRemainingCanidates(remainingCanidates, ballot)
	  , remainingCanidatesInTier
	
	if(tier) {
		remainingCanidatesInTier = getValuesInBothArrays(tier, remainingCanidates)
		remainingCanidatesInTier.forEach(function(canidate, i) {
			votes[canidate] = 1-Math.pow(i/(remainingCanidates.length-1), 2)
		})
	}

	return votes
}

function getHighestTierWithRemainingCanidates(remainingCanidates, ballot) {
	var highestTierWithRemainingCanidates
	ballot.some(function(tier) {
		if(tierContainsCanidate(tier, remainingCanidates)) {
			highestTierWithRemainingCanidates = tier
			return true
		}
	})
	return highestTierWithRemainingCanidates
}

function tierContainsCanidate(tier, canidates) {
	return tier.some(function(canidate) {
		return canidates.indexOf(canidate) != -1
	})
}

function getValuesInBothArrays(array1, array2) {
	var both = []
	array1.forEach(function(value) {
		if(array2.indexOf(value) != -1) {
			both.push(value)
		}
	})
	return both
}

function convertObjectToArrayPairs(object) {
	var array = []
	Object.keys(object).forEach(function(key) {
		array.push([key, object[key]])
	})
	return array
}

function convertPairsToKeyArray(pairs) {
	var keys = []
	pairs.forEach(function(pair) {
		keys.push(pair[0])
	})
	return keys
}

function byVotesAsc(a, b) {
	return b[1] - a[1]
}