#!/bin/bash

# Shaddi Hasan, Oct 2010. Instant Runoff Voting in bash.

# input: comma delimited text file w/ choice numbers. each vote on seperate line

cp irv.txt irv.txt.tmp

VOTES=`wc -l < irv.txt.tmp` # total number of votes cast

SHOW_WORK=0

while : 
do

	if [ $SHOW_WORK -eq 1 ]
	then
		# show intermediate step
		echo "tallies: "
		cat irv.txt.tmp | cut -f1 -d, | sort | uniq -c | sort -rn
		echo "raw:"
		cat irv.txt.tmp
		echo " "
	fi
	
	# pull out the top choice and number of votes 
	TOP_VOTES=`cat irv.txt.tmp | cut -f1 -d, | sort | uniq -c | sort -rn | head -n 1 | tr -s " " | cut -f2 -d" " `
	TOP_CHOICE=`cat irv.txt.tmp | cut -f1 -d, | sort | uniq -c | sort -rn | head -n 1 | tr -s " " | cut -f3 -d" " `

	# keep track of the current top choice vote proportion
	# we keep a rounded version (between 1 and 2) because bash can't handle floating point
	TOP_SCORE=`echo "$TOP_VOTES/$VOTES" | bc -l`
	TOP_SCORE_ROUND=`echo "1+$TOP_VOTES/$VOTES*2" | bc -l | cut -f1 -d"."`

	# if the top choice has a majority, quit. Note .5*2 = 1, 1+1 = 2, which triggers this break.
	if [ $TOP_SCORE_ROUND -ge 2 ]
	then
		break
	fi

	# no majority, eliminate lowest vote. first get the choice with lowest vote total.
	BCH=`cat irv.txt.tmp | cut -f1 -d, | sort | uniq -c | sort -rn | tail -n 1 | tr -s " " | cut -f3 -d" "`
	BCHC="$BCH,"
	CBCH=",$BCH"
	CBCHC=",$BCH,"
	
	if [ $SHOW_WORK -eq 1 ]
	then
		echo eliminating $BCH
	fi
	
	# remove all instances of lowest ranked choice
	cat irv.txt.tmp | sed "s/^$BCHC//g" | sed "s/$CBCH$//g" | sed "s/$CBCHC/,/g" > irv.txt.tmp1

	# get ready for next round!
	cp irv.txt.tmp1 irv.txt.tmp
	rm irv.txt.tmp1
	
done

rm irv.txt.tmp

echo "The winner is: $TOP_CHOICE (with `echo $TOP_SCORE*100 | bc -l`% of votes)"