sampleOutput1.txt

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}

sampleOutput2.txt

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}

unrankedSTV.nim

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()