Skip to content

Instantly share code, notes, and snippets.

@rbehrends

rbehrends/sampleOutput1.txt Secret

Created Apr 8, 2015
Embed
What would you like to do?
508 votes for candidate #47
504 votes for candidate #48
504 votes for candidate #46
501 votes for candidate #49
500 votes for candidate #50
469 votes for candidate #1
383 votes for candidate #2
372 votes for candidate #3
363 votes for candidate #4
318 votes for candidate #6
Winners are: {1, 2, 3, 46, 47}
505 votes for candidate #48
504 votes for candidate #49
504 votes for candidate #46
503 votes for candidate #47
500 votes for candidate #50
464 votes for candidate #1
413 votes for candidate #2
392 votes for candidate #3
339 votes for candidate #5
318 votes for candidate #4
Winners are: {1, 2, 3, 48, 49}
import mersenne, math, times, algorithm
const
ballotSize = 5
numRegularBallots = 1000
numSlateBallots = numRegularBallots div 2
numCandidates = 50
slate: array[1..ballotSize, int] = [ 46, 47, 48, 49, 50 ]
type
Dist = ref object
values: seq[int]
total: int
Ballot = ref object
nominations: array[1..ballotSize, int]
candSet = set[1..numCandidates]
var
rng = newMersenneTwister(int((epochTime() * 1e6) mod 1e9))
proc rand(): float =
(rng.getNum and 0x7fffffff) / 0x80000000
proc rand(n: int): int =
int(rand() * n.float)
proc complement[T](s: set[T]): set[T] =
result = {T.low .. T.high} - s
proc genDist(): Dist =
result = Dist(values: @[])
var p = 10000.0
for i in 1..numCandidates:
add(result.values, int(p))
p *= 0.9
result.total = sum(result.values)
proc newBallot(): Ballot =
Ballot()
proc sample(dist: Dist): int =
var k = rand(dist.total)
for i in 0..len(dist.values):
k -= dist.values[i]
if k < 0:
return i
proc sample(s: Dist, n: int): Ballot =
result = newBallot()
for i in 1..ballotSize:
var k = sample(s)
while k in result.nominations:
k = sample(s)
result.nominations[i] = k
proc findWinners(ballots: seq[Ballot]): candSet =
var discarded: candSet
while true:
var votes: array[1..numCandidates, float]
for i in 1..numCandidates:
votes[i] = 0
for ballot in ballots:
var k = 0
for cand in ballot.nominations:
if cand notin discarded:
k += 1
for cand in ballot.nominations:
if cand notin discarded:
votes[cand] += 1 / k
var k = 0
var remain = 0
var lowestyet = float(len(ballots)) + 1
for i in 1..numCandidates:
if votes[i] != 0:
remain += 1
if votes[i] < lowestyet:
k = i
lowestyet = votes[i]
if remain == ballotSize:
result = complement(discarded)
break
incl discarded, k
proc showLeadingVotes(ballots: seq[Ballot]) =
var count: array[1..numCandidates, int]
var ballotsByVoteCount = newSeq[(int, int)]()
for ballot in ballots:
for cand in ballot.nominations:
count[cand] += 1
for j in 1..numCandidates:
var k = 0
var highestyet = 0
for i in 1..numCandidates:
if count[i] > highestyet:
k = i
highestyet = count[i]
add(ballotsByVoteCount, (count[k], k))
count[k] = 0
sort(ballotsByVoteCount, cmp[(int, int)], Descending)
for i in 0..2*ballotSize-1:
let (n, k) = ballotsByVoteCount[i]
echo n, " votes for candidate #", k
proc populateBallots(): seq[Ballot] =
result = @[]
let dist = genDist()
for i in 1..numRegularBallots:
add(result, sample(dist, ballotSize))
# add a slate
for i in 1..numSlateBallots:
add(result, Ballot(nominations: slate))
proc main() =
var ballots = populateBallots()
showLeadingVotes(ballots)
let winners = findWinners(ballots)
echo "Winners are: ", winners
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment