{+R}   { Enable range checking. }
PROGRAM SingleSeatElections(INPUT,OUTPUT,FOR001);

{ This program implements a variety of single-seat election systems.
See http://www.ghg.net/redflame/irv.htm. 

There is ABSOLUTELY NO WARRANTY.  Please email me with bug reports.
In the unlikely event that there are any questions about copyright, 
refer to the GNU General Public License (free "copyleft" software).

Last modified 12-30-2000 by Peter A. Taylor, peter.a.taylor@earthlink.net .

The input file, FOR001.DAT, consists of one line per ballot, with 
no headers.  Each line or "ballot" is a list of candidate ID numbers 
(integers between 1 and NumCans) separated by anything but $ symbols, 
arranged in order from most attractive to least attractive.  (A minus
sign is interpreted as a delimiter.)  Anything after a $ symbol is 
ignored.  The list may be truncated at any point.  Blank lines and 
repeated or out-of-bounds candidate ID numbers are ignored.  The only 
part of this program that I think is potentially controversial is 
dealing with ballots that are incomplete or "spoiled" in some way.  
I decided to simply ignore bad data without discarding any ballots.  
I also decided not to allow voters to put a candidate at the bottom 
of their orders of preference without filling in all the others above 
him or her.

Plurality voting: only 1st preference counts.  "First past the post" wins.
Approval voting: listed candidates are approved (truncate others).  Each 
  "approved" candidate on a ballot gets one vote.  The most votes wins.
Borda count: candidates get N points for 1st preference, N-1 for 2nd....
  The most points wins.
Instant Runoff: Look at the first preference on each ballot.  Eliminate 
  the candidate with the fewest votes.  Recount ballots, ignoring all 
  eliminated candidates.  Repeat until there is only one candidate left.
Condorcet: Look at all N*(N-1) possible pairings of two candidates.
  Examine each ballot to see which candidate is preferred by a majority 
  in each of the N*(N-1) pairings.  If there is a candidate who wins 
  all N-1 of the pairings he is involved in, he wins.  Otherwise there
  is a circular tie, a "rock-paper-scissors" game played by a subset of
  the candidates called the Smith set.  Use a tiebreaker within the Smith
  set.
Young: Break a Condorcet circular tie by choosing the candidate who was
  defeated the fewest times.  (This, too is likely to result in a tie.)
  This is guaranteed to be a member of the Smith set.  
Black: Break a Condorcet circular tie by using the Borda count.
Dodgeson: Break a Condorcet circular tie by choosing the candidate whose
  largest margin of defeat in any pairing was the smallest.
Nanson (Borda elimination): Perform the Borda count, but instead of the 
  candidate with the most points winning, the candidate with the
  fewest points is eliminated and the ballots are recounted as if he had 
  never existed.  The process repeats until only one candidate is left.
  This is guaranteed to be a member of the Smith set (the Condorcet 
  winner if there is one). }

CONST MaxCans=45;
      MaxVoters=1000;
TYPE IntVec=ARRAY[1..MaxCans] OF INTEGER;
     LongIntVec=ARRAY[1..MaxCans] OF LONGINT;
     BooVec=ARRAY[1..MaxCans] OF BOOLEAN;
VAR Preferences: ARRAY[1..MaxVoters,1..MaxCans] OF BYTE;
    i,j,NumCans,Count,Young,Dodgeson,Borda,Nanson,PairTies,
         IRVmax,IRVmin: INTEGER;
    FindCan: IntVec;
    BallotID,NumBallots,TruncFix,MiniMax,Delta,Dummy: LONGINT;
    BallotVec,Plurality,Approval,Losses,BordaVec,IRVvec: LongIntVec;
    PairMat: ARRAY[1..MaxCans,1..MaxCans] OF LONGINT;
    AvgTrunc: REAL;
    Valid,Tie,CondorcetExists,Verbose: BOOLEAN;
    Smith,Standing,NeedSeed: BooVec;
    BooMat:ARRAY[1..MaxCans]OF BooVec;
    Ans: CHAR;
    FOR001: TEXT;

PROCEDURE FindMax(VAR i:INTEGER; VAR Tie:BOOLEAN; V: LongIntVec);
 VAR j: INTEGER;
 BEGIN
  i:=1;
  FOR j:=2 TO NumCans DO IF V[j]>V[i] THEN i:=j;
  Tie:=False;
  FOR j:=1 TO NumCans DO IF (i<>j) AND (V[i]=V[j]) THEN Tie:=TRUE;
 END;

PROCEDURE FindMin(VAR i:INTEGER; VAR Tie:BOOLEAN; V: LongIntVec);
 VAR j: INTEGER;
 BEGIN
  i:=1;
  FOR j:=2 TO NumCans DO IF V[j]<V[i] THEN i:=j;
  Tie:=False;
  FOR j:=1 TO NumCans DO IF (i<>j) AND (V[i]=V[j]) THEN Tie:=TRUE;
 END;

PROCEDURE FillSmith(VAR s:BooVec; seed:INTEGER);
{ If the Smith set includes seed, it must include all of set s. }
VAR i: INTEGER;
    complete: BOOLEAN;
BEGIN
 FOR i:=1 TO NumCans DO s[i]:=FALSE;
 s[seed]:=TRUE;
 REPEAT
  complete:=TRUE;
  FOR i:=1 TO NumCans DO
   IF s[i] THEN
    FOR j:=1 TO NumCans DO
     IF (PairMat[j,i]>PairMat[i,j]) AND NOT s[j] THEN BEGIN
      s[j]:=TRUE;
      complete:=FALSE;
     END;
 UNTIL complete;
END;

FUNCTION Subset(a,b:BooVec):BOOLEAN;   { Include improper subsets. }
VAR i:INTEGER;
BEGIN
 Subset:=TRUE;
 FOR i:=1 TO NumCans DO
  IF a[i] AND NOT b[i] THEN Subset:=FALSE;
END;

PROCEDURE ReadBallot(VAR NumBallots: LONGINT; VAR BallotVec: LongIntVec);
 VAR i,Place: INTEGER;
     D: CHAR;
     Bad: BOOLEAN;
 BEGIN
  NumBallots:=NumBallots+1;
  FOR i:=1 TO MaxCans DO BallotVec[i]:=0;
  Place:=1;
  Bad:=FALSE;
  WHILE NOT (EOF(FOR001) OR EOLN(FOR001)) DO BEGIN   { Read one ballot. }
   READ(FOR001,D);   { Read one character. }
   IF D IN ['0'..'9'] THEN
    BallotVec[Place]:=BallotVec[Place]*10+ORD(D)-ORD('0');
   IF EOLN(FOR001) OR EOF(FOR001) OR NOT (D IN ['0'..'9']) THEN
    IF BallotVec[Place]>0 THEN BEGIN   { Discard garbage & delimiters. }
{ Check for uniqueness and out of bounds. }
     IF BallotVec[Place]>NumCans THEN Valid:=FALSE ELSE Valid:=TRUE;
     FOR i:=1 TO Place-1 DO   { Discard duplicates. }
      IF BallotVec[Place]=BallotVec[i] THEN Valid:=FALSE;
     IF NOT Valid THEN Bad:=TRUE;
     IF Valid THEN Place:=Place+1 ELSE BallotVec[Place]:=0;
    END;
{ Treat $ as start of comment. }
   IF D='$' THEN
    WHILE NOT (EOLN(FOR001) OR EOF(FOR001)) DO READ(FOR001,D);
  END;
  READLN(FOR001);   { Done reading one ballot. }
  IF NOT (Place IN [1..NumCans+1]) THEN Bad:=TRUE;
  IF Verbose AND Bad THEN WRITELN(' Bad input on line ',NumBallots:1);
 END;

BEGIN
 ASSIGN(FOR001,'FOR001.DAT');
 RESET(FOR001);
 REPEAT
  WRITELN('Enter number of candidates (max ',MaxCans:1,').');
  READLN(NumCans);
 UNTIL (NumCans>0) and (NumCans<=MaxCans);
 WRITELN('Do you want verbose mode (y/n)?');
 READLN(Ans);
 IF Ans in ['y','Y'] THEN Verbose:=TRUE ELSE Verbose:=FALSE;
 FOR i:=1 TO MaxCans DO Plurality[i]:=0;
 FOR i:=1 TO MaxCans DO Approval[i]:=0;
 FOR i:=1 TO MaxCans DO FOR j:=1 TO MaxCans DO PairMat[i,j]:=0;
 FOR i:=1 TO MaxVoters DO FOR j:=1 TO MaxCans DO Preferences[i,j]:=0;
 NumBallots:=0;

 WHILE NOT EOF(FOR001) DO BEGIN   { Read ballots.  Main loop. }
  ReadBallot(NumBallots,BallotVec);

{ Now process data from one ballot. }

{ Plurality: }
  IF BallotVec[1] IN [1..NumCans] THEN
   Plurality[BallotVec[1]]:=Plurality[BallotVec[1]]+1;

{ Approval: }
  i:=0;
  REPEAT
   i:=i+1;
   IF BallotVec[i] IN [1..NumCans] THEN
    Approval[BallotVec[i]]:=Approval[BallotVec[i]]+1
   ELSE i:=NumCans+1;
  UNTIL i>=NumCans;

{ Process ballot "pairwise" (Condorcet and related systems): }
{ An element of PairMat represents the number of instances that 
candidate RowID was preferred over candidate ColumnID.  The diagonals 
are all zeros.  The margin of victory of I over J is 
PairMat[i,j]-PairMat[j,i]. }
{ Find position of Ith candidate (set=NumCans+1 if does not appear). }
  FOR i:=1 TO NumCans DO FindCan[i]:=NumCans+1;
  FOR i:=1 TO NumCans DO
   IF BallotVec[i] IN [1..NumCans] THEN FindCan[BallotVec[i]]:=i;
  FOR i:=1 TO NumCans DO   { Identify candidates beaten by Ith candidate. }
   FOR j:=1 TO NumCans DO
    IF FindCan[j]>FindCan[i] THEN PairMat[i,j]:=PairMat[i,j]+1;

{ Instant Runoff Voting (store now--process later): }
  IF NumBallots<=MaxVoters THEN
   FOR i:=1 TO NumCans DO Preferences[NumBallots,i]:=BallotVec[i];

 END;
 WRITELN('Done reading ballots.');
 IF Verbose THEN BEGIN
  WRITELN('Hit return to continue.');
  READLN;
 END;

 WRITELN(NumBallots:1,' ballots read.');
 AvgTrunc:=0.0;
 FOR i:=1 TO NumCans DO AvgTrunc:=AvgTrunc+approval[i];
 AvgTrunc:=AvgTrunc/NumBallots;
 WRITELN('Average no. valid candidates per ballot is ',AvgTrunc:9:7,' .');
 WRITELN;

{ Print out plurality winner.  Check for ties. }
 IF Verbose THEN BEGIN
  WRITELN('The plurality vote totals by candidate were:');
  FOR i:=1 TO NumCans DO BEGIN
   WRITE(' ',plurality[i]:10);
   IF (i=NumCans) OR ((i MOD 7) = 0) THEN WRITELN;
  END;
  WRITELN;
 END;
 FindMax(i,Tie,plurality);
 IF Tie THEN BEGIN
  WRITELN('Plurality voting resulted in a tie.  The winners are:');
  FOR j:=1 TO NumCans DO
   IF plurality[j]=plurality[i] THEN
    WRITELN('     ',j:1,' with ',plurality[j]:1,' votes.');
 END
 ELSE
  WRITELN('The plurality winner is ',i:1,' with ',plurality[i]:1,' votes.');
 WRITELN;
 WRITELN('Hit return to continue.');
 READLN;

{ Print out approval winner.  Check for ties. }
 IF Verbose THEN BEGIN
  WRITELN('The approval vote totals by candidate were:');
  FOR i:=1 TO NumCans DO BEGIN
   WRITE(' ',approval[i]:10);
   IF (i=NumCans) OR ((i MOD 7) = 0) THEN WRITELN;
  END;
  WRITELN;
 END;
 FindMax(i,Tie,approval);
 IF Tie THEN BEGIN
  WRITELN('Approval voting resulted in a tie.  The winners are:');
  FOR j:=1 TO NumCans DO
   IF approval[j]=approval[i] THEN
    WRITELN('     ',j:1,' with ',approval[j]:1,' votes.');
 END
 ELSE
  WRITELN('The approval winner is ',i:1,' with ',approval[i]:1,' votes.');
 WRITELN;
 WRITELN('Hit return to continue.');
 READLN;

 IF Verbose THEN BEGIN
  WRITELN('Would you like to see the detailed pairwise results (y,n)?');
  READLN(Ans);
 END;
 IF Verbose AND (Ans IN ['y','Y']) THEN BEGIN
  Count:=0;
  FOR i:=1 TO NumCans DO
   FOR j:=i+1 TO NumCans DO BEGIN
    Count:=Count+1;
    IF PairMat[i,j]>PairMat[j,i] THEN
     WRITELN(i:4,' defeats',j:4,' by',PairMat[i,j]:11,' to',PairMat[j,i]:11)
    ELSE IF PairMat[i,j]<PairMat[j,i] THEN
     WRITELN(j:4,' defeats',i:4,' by',PairMat[j,i]:11,' to',PairMat[i,j]:11)
    ELSE WRITELN(i:4,'   and  ',j:4,' are tied at',PairMat[i,j]:11);
    IF (Count MOD 20 = 0) THEN BEGIN
     WRITELN('Hit return to continue.');
     READLN;
    END;
   END;
  WRITELN('Hit return to continue.');
  READLN;
 END;

{ If there are conventional ties in the pairwise comparisons, that
complicates things enormously.  Flag this. }
  PairTies:=0;
  FOR i:=1 TO NumCans-1 DO
   FOR j:=i+1 TO NumCans DO
    IF PairMat[i,j]=PairMat[j,i] THEN PairTies:=PairTies+1;
  WRITELN('The number of tied pairwise races is ',PairTies:1,'.');
  WRITELN;

{ Find the Young winner, the candidate with the fewest "pairwise" losses. }
 FOR i:=1 TO NumCans DO Losses[i]:=0;
 FOR i:=1 TO NumCans DO
  FOR j:=1 TO NumCans DO
   IF PairMat[i,j]<PairMat[j,i] THEN Losses[i]:=Losses[i]+1;
 FindMin(Young,Tie,Losses);

{ See if the Condorcet winner (winner of all pairwise comparisons) exists.
If one exists, it will be the Young winner. }
 CondorcetExists:=TRUE;
 IF Tie OR (Losses[Young]>0) THEN CondorcetExists:=FALSE;   { Definite. }
 FOR i:=1 TO NumCans DO
  IF i<>Young THEN
   IF PairMat[i,Young]=PairMat[Young,i] THEN
    CondorcetExists:=FALSE;   { Maybe.  Check the size of the Smith set. }

{ Find the Smith set (circular tie, or rock-paper-scissors).  This is the 
smallest nonempty set such that no member was defeated by a non-member.  
But beware conventional ties: "smallest" means the tightest subset.  The 
set, [A], is not "smaller" for my purposes than the set, [B,C,D]. }
{ If there are S members in the Smith set and no tied pairwise races,
non-members of the Smith set must have at least S defeats and members at
most S-1 defeats.  So if there are no tied pairwise races, the Young
winner (fewest defeats) has to be a member of the Smith set.  Further, if 
there are no pairwise ties, the Smith set can be completed by induction. }
 IF CondorcetExists OR (PairTies=0) THEN FillSmith(Smith,Young)
 ELSE BEGIN
{ 1. This is *extremely* unlikely, but there may be a candidate who is 
pairwise tied with each of the members of a different, circular tie.  
2. There may still be a unique winner, tied pairwise with someone who is 
not a member of any Smith set.  3. It is also possible that the Young 
"winner" won by virtue of a lot of ties, having been beaten by a member 
of the Smith set without having beaten any members.  If so, he is not a 
member.  I handle these perverse cases by getting an "opinion" from each 
candidate on who is in the Smith set, discarding any candidate set that 
is a superset of another candidate set, and merging any competing sets 
of winners. }
  FOR i:=1 TO NumCans DO FillSmith(BooMat[i],i);
  FOR i:=1 TO NumCans DO NeedSeed[i]:=TRUE;
  FOR i:=1 TO NumCans DO
   IF NeedSeed[i] THEN
    FOR j:=1 TO NumCans DO
     IF (i<>j) AND NeedSeed[j] THEN
      IF Subset(BooMat[i],BooMat[j]) THEN NeedSeed[j]:=FALSE;
  FOR i:=1 TO NumCans DO Smith[i]:=FALSE;
  FOR i:=1 TO NumCans DO
   IF NeedSeed[i] THEN
    FOR j:=1 TO NumCans DO Smith[j]:=Smith[j] OR BooMat[i,j];
 END;
{ Verify Condorcet. }
 i:=0;
 FOR j:=1 TO NumCans DO IF Smith[j] THEN i:=i+1;
 IF i=1 THEN CondorcetExists:=TRUE ELSE CondorcetExists:=FALSE;

 IF CondorcetExists THEN BEGIN
  WRITELN('The Condorcet winner is ',Young:1,' .');
  WRITELN;
  WRITELN('Hit return to continue.');
  READLN;
 END
 ELSE BEGIN
  WRITE('A Condorcet winner does not exist due to a ');
  IF Losses[Young]=0 THEN WRITELN('conventional tie.')
  ELSE WRITELN('circular tie.');
  WRITELN;
  WRITELN('Hit return to continue.');
  READLN;

{ I dislike the Young criterion for the same "sensitivity to clones" reason
that I dislike the Borda count.  See http://home.earthlink.net/~peter.a.taylor/irv.htm.
It is also likely to produce ties. }
  IF Verbose THEN BEGIN
   WRITELN('The numbers of pairwise defeats by candidate were:');
   FOR i:=1 TO NumCans DO BEGIN
    WRITE(' ',Losses[i]:10);
    IF (i=NumCans) OR ((i MOD 7) = 0) THEN WRITELN;
   END;
   WRITELN;
   IF Tie THEN BEGIN
    WRITELN('The Young criterion (fewest pairwise losses) resulted in a tie:');
    FOR i:=1 TO NumCans DO
     IF Losses[i]=Losses[Young] THEN
      WRITELN('     ',i:1,' with ',Losses[i]:1,' pairwise losses.');
   END
   ELSE
    WRITELN('The Young winner is ',Young:1,' with ',Losses[Young]:1,
         ' pairwise losses (fewest).');
   WRITELN('(This is helpful in identifying the Smith set.)');
   WRITELN;
  END;

  WRITELN('The Smith set (participants in circular or conventional ties):');
  FOR i:=1 TO NumCans DO
   IF Smith[i] THEN WRITE(' ',i:1);
  WRITELN;
  WRITELN('Hit return to continue.');
  READLN;

{ Use Dodgson's method to break circular ties.  The winner is the member of 
the Smith set whose largest margin of defeat is the smallest ("minimax"). }
{ Find largest margin of defeat for each candidate. }
  FOR i:=1 TO NumCans DO BallotVec[i]:=0;
  FOR i:=1 TO NumCans DO
   FOR J:=1 TO NumCans DO
    IF PairMat[j,i]-PairMat[i,j]>BallotVec[i] THEN
     BallotVec[i]:=PairMat[j,i]-PairMat[i,j];
  IF Verbose THEN BEGIN
   WRITELN('The worst pairwise margins of defeat by candidate were:');
   FOR i:=1 TO NumCans DO BEGIN
    WRITE(' ',BallotVec[i]:10);
    IF (i=NumCans) OR ((i MOD 7) = 0) THEN WRITELN;
   END;
   WRITELN;
  END;

{ Find improper Dodgeson winner (not restricted to Smith set). }
  FindMin(Dodgeson,Tie,BallotVec);
  MiniMax:=BallotVec[Dodgeson];
  WRITELN('Dodgeson winner (minimax margin of defeat):');
  WRITELN('If the winner is (improperly) not restricted to the Smith set');
  IF Tie THEN BEGIN
   WRITELN('there is a tie involving:');
   FOR i:=1 TO NumCans DO
    IF BallotVec[i]=MiniMax THEN
     WRITELN('Candidate ',i:1,' with defeat by ',BallotVec[i]:1,' votes.');
  END
  ELSE
   WRITELN('the Dodgeson winner is ',Dodgeson:1,' with defeat by ',
        MiniMax:1,' votes.');
  WRITELN;

{ Find proper Dodgeson winner (restricted to Smith set). }
  Dodgeson:=Young;
  MiniMax:=BallotVec[Young];
  FOR i:=1 TO NumCans DO
   IF Smith[i] AND (BallotVec[i]<MiniMax) THEN BEGIN
    Dodgeson:=i;
    MiniMax:=BallotVec[i];
   END;
  Tie:=FALSE;
  FOR i:=1 TO NumCans DO
   IF Smith[i] AND (i<>Dodgeson) AND (BallotVec[i]=MiniMax) THEN Tie:=TRUE;
  WRITELN('If the winner is (properly) restricted to the Smith set');
  IF Tie THEN BEGIN
   WRITELN('there is a tie involving:');
   FOR i:=1 TO NumCans DO
    IF Smith[i] AND (BallotVec[i]=MiniMax) THEN
     WRITELN('Candidate ',i:1,' with defeat by ',BallotVec[i]:1,' votes.');
  END
  ELSE
   WRITELN('the Dodgeson winner is ',Dodgeson:1,' with defeat by ',
        MiniMax:1,' votes.');
  WRITELN;
  WRITELN('Hit return to continue.');
  READLN;
 END;   { Done with Condorcet-Young and Condorcet-Dodgeson. }

{ For Borda and Nanson, I need to compensate for ballot truncation.  Each 
ballot should assign N*(N-1)/2 total points.  Otherwise we introduce a 
bias against candidates who were often unlisted.  The unaccounted-for 
points need to be divided evenly among the candidates who were not listed.  
In effect, PairMat needs to be padded with half votes so that sum of A[i,j] 
and A[j,i] is constant for all j<>i.  In order to be able to use integer 
arithmetic, I will double all the numbers in PairMat. }
 FOR i:=1 TO NumCans DO
  FOR j:=1 TO NumCans DO
   PairMat[i,j]:=PairMat[i,j]*2;
 TruncFix:=NumBallots*NumCans*(NumCans-1);
 FOR i:=1 TO NumCans DO
  FOR j:=i+1 TO NumCans DO BEGIN
   Delta:=(TruncFix-(PairMat[i,j]+PairMat[j,i])) DIV 2;
   PairMat[i,j]:=PairMat[i,j]+Delta;
   PairMat[j,i]:=PairMat[j,i]+Delta;
  END;

{ Done compensating for truncation.  Now proceed with Borda and Nanson. }
 FOR i:=1 TO NumCans DO BordaVec[i]:=0;
 FOR i:=1 TO NumCans DO
  FOR j:=1 TO NumCans DO
   BordaVec[i]:=BordaVec[i]+PairMat[i,j];
 FindMax(Borda,Tie,BordaVec);
 IF CondorcetExists THEN BEGIN
  WRITELN('Since the Condorcet winner exists, the Condorcet-Black');
  WRITELN('"tiebreaker" winner is the Condorcet winner, ',Young:1,' .');
 END
 ELSE BEGIN
  WRITELN('Since no Condorcet winner exists, the Condorcet-Black');
  WRITELN('"tiebreaker" winner is the winner of the Borda count, which');
  WRITELN('is a point system only indirectly related to Condorcet.');
 END;
 WRITELN;
 IF Tie THEN BEGIN
  WRITELN('The Borda count produces a tie among the following');
  WRITELN('candidates, each with an average of');
  WRITELN(BordaVec[Borda]*0.5/NumBallots:9:7,' points per ballot:');
  FOR i:=1 TO NumCans DO
   IF BordaVec[i]=BordaVec[Borda] THEN WRITE(' ',i:1);
  WRITELN;
 END
 ELSE BEGIN
  WRITELN('The winner of the Borda count is ',Borda:1,' with an average ');
  WRITELN('of ',BordaVec[Borda]*0.5/NumBallots:9:7,' points per ballot.');
 END;
 WRITELN;
 IF NOT CondorcetExists THEN BEGIN
  WRITELN('If non-members of the Smith set were disqualified from winning,');
  WRITELN('but still included in the Borda count, the Borda winner would');
  Borda:=Young;
  FOR i:=1 TO NumCans DO
   IF Smith[i] AND (BordaVec[i]>BordaVec[Borda]) THEN Borda:=i;
  Tie:=FALSE;
  FOR i:=1 TO NumCans DO
   IF Smith[i] AND (Borda<>i) AND (BordaVec[i]=BordaVec[Borda]) THEN
    Tie:=TRUE;
  IF Tie THEN BEGIN
   WRITELN('be a tie among the following candidates, each with an average');
   WRITELN('of ',BordaVec[Borda]*0.5/NumBallots:9:7,' points per ballot:');
   FOR i:=1 TO NumCans DO
    IF BordaVec[i]=BordaVec[Borda] THEN WRITE(' ',i:1);
   WRITELN;
  END
  ELSE BEGIN
   WRITELN('be candidate ',Borda:1,' with an average of');
   WRITELN(BordaVec[Borda]*0.5/NumBallots:9:7,' points per ballot.');
  END;
 END;
 WRITELN;
 WRITELN('Hit return to continue.');
 READLN;

{ Now use Nanson's method.  I eliminate tied candidates together in 
order to avoid making the results dependent on the candidates' order 
of appearance on the ballot or on any random factors.  It is also 
possible to have a conventional tie for first place. }
 IF Verbose THEN WRITELN('Nanson''s method:');
 FOR i:=1 TO NumCans DO Standing[i]:=TRUE;
 Count:=0;
 REPEAT   { Reload BordaVec on each iteration. }
  FOR i:=1 TO NumCans DO BEGIN
   BordaVec[i]:=0;
   IF Standing[i] THEN
    FOR j:=1 TO NumCans DO
     IF Standing[j] THEN BordaVec[i]:=BordaVec[i]+PairMat[i,j];
  END;
  i:=0;   { Find the first candidate not eliminated. }
  REPEAT
   i:=i+1
  UNTIL Standing[i];
  Borda:=i;    { Max points }
  Nanson:=i;   { Min points }
  FOR j:=i+1 TO NumCans DO
   IF Standing[j] AND (BordaVec[j]>BordaVec[Borda]) THEN Borda:=j;
  FOR j:=i+1 TO NumCans DO
   IF Standing[j] AND (BordaVec[j]<BordaVec[Nanson]) THEN Nanson:=j;
{ Eliminate weakest candidate.  Beware ties for who gets eliminated as 
well as ties for first place. }
  IF BordaVec[Borda]=BordaVec[Nanson] THEN Nanson:=Borda   { Finished }
  ELSE
   FOR i:=1 TO NumCans DO
    IF BordaVec[i]=BordaVec[Nanson] THEN BEGIN
     Standing[i]:=FALSE;
     IF Verbose THEN BEGIN
      WRITELN('Candidate ',i:1,' eliminated.');
      Count:=Count+1;
      IF Count MOD 20 = 0 THEN BEGIN
       WRITELN('Hit return to continue.');
       READLN;
      END;
     END;
    END;
 UNTIL Nanson=Borda;   { Done with Borda elimination process. }
 Tie:=FALSE;
 FOR i:=1 TO NumCans DO
  IF Standing[i] and (i<>Nanson) THEN Tie:=TRUE;
 IF Tie THEN BEGIN
  WRITELN('Nanson''s method (Borda elimination) produced a tie among:');
  FOR i:=1 TO NumCans DO
   IF standing[i] THEN
    WRITE(' ',i:1);
  WRITELN;
 END
 ELSE
  WRITELN('The Nanson (Borda elimination) winner is ',Nanson:1,' .');
 WRITELN;
 WRITELN('Hit return to continue.');
 READLN;

{ Now use Instant Runoff Voting, IRV, alias the Alternative Vote, Hare's 
Method, Australian Ballot.  I try to read the entire set of ballots into 
memory at once, and if it overflows, I just re-read the file rather than 
doing anything fancy. }

{ Start with the plurality results. }
 IF Verbose THEN
  WRITELN('Instant Runoff aka Alternative, Australian, Hare elimination:');
 FOR i:=1 TO NumCans DO Standing[i]:=TRUE;
 IRVvec:=plurality;
 Count:=0;
 FindMax(IRVmax,Tie,IRVvec);
 FindMin(IRVmin,Tie,IRVvec);
 IF IRVvec[IRVmax]>IRVvec[IRVmin] THEN
  FOR i:=1 TO NumCans DO
   IF IRVvec[i]=IRVvec[IRVmin] THEN BEGIN
    Standing[i]:=FALSE;
    IF Verbose THEN WRITELN('Candidate ',i:1,' eliminated.');
    Count:=Count+1;
   END;

 REPEAT   { Main IRV elimination loop. }
  FOR i:=1 TO NumCans DO IRVvec[i]:=0;
  IF NumBallots>MaxVoters THEN BEGIN
   CLOSE(FOR001);
   RESET(FOR001);
  END;
  FOR BallotID:=1 TO NumBallots DO BEGIN
   Dummy:=0;
   IF NumBallots>MaxVoters THEN ReadBallot(Dummy,BallotVec)
   ELSE FOR i:=1 TO NumCans DO BallotVec[i]:=Preferences[BallotID,i];
   i:=0;
   REPEAT   { Find the first candidate left alive on each ballot. }
    i:=i+1;
    j:=BallotVec[i];
    IF Standing[j] THEN IRVvec[j]:=IRVvec[j]+1;
   UNTIL (i>=NumCans) OR Standing[j];
  END;   { Done reading ballots for this iteration. }
  i:=0;
  REPEAT
   i:=i+1
  UNTIL Standing[i];
  IRVmax:=i;
  IRVmin:=i;
  FOR j:=i+1 TO NumCans DO IF Standing[j] THEN BEGIN
   IF IRVvec[j]>IRVvec[IRVmax] THEN IRVmax:=j;
   IF IRVvec[j]<IRVvec[IRVmin] THEN IRVmin:=j;
  END;
  IF IRVvec[IRVmax]>IRVvec[IRVmin] THEN
   FOR i:=1 TO NumCans DO
    IF Standing[i] AND (IRVvec[i]=IRVvec[IRVmin]) THEN BEGIN
     Standing[i]:=FALSE;
     IF Verbose THEN BEGIN
      WRITELN('Candidate ',i:1,' eliminated.');
      Count:=Count+1;
      IF Count MOD 20 = 0 THEN BEGIN
       WRITELN('Hit return to continue.');
       READLN;
      END;
     END;
    END;
 UNTIL IRVvec[IRVmax]=IRVvec[IRVmin];   { Done with IRV eliminations. }
 FindMax(IRVmax,Tie,IRVvec);
 IF Tie THEN BEGIN
  WRITELN('Instant Runoff Voting produced a tie among:');
  FOR i:=1 TO NumCans DO
   IF Standing[i] THEN
    WRITE(' ',i:1);
  WRITELN;
 END
 ELSE
  WRITELN('The Instant Runoff Voting winner is ',i:1,' .');
 WRITELN;
 WRITELN('Hit return to continue.');
 READLN;
 CLOSE(FOR001);
END.