In [1], I D Hill describes an implementation of Meek STV written in Pascal, which had been privately circulated since as early as 1999 [2]. The implementation is similar to the earlier ‘Algorithm 123’ Pascal implementation of Meek STV by Hill, Wichmann and Woodall [3], but introduces a number of refinements, such as the deferred transfer of small surpluses.

Hill's Meek STV implementation was available to those working on the rules for Meek STV for elections in New Zealand, and those rules – to date the only large scale implementation of Meek STV – retain the refinements made by Hill.

It would therefore be helpful to be able to use Hill's Meek STV implementation as a reference to validate implementations of the New Zealand electoral rules. When implementing OpenTally, open-source software for election counting, the only publicly available implementation of New Zealand Meek STV was from OpenSTV 1.7. As the New Zealand election counting software is not itself publicly available, the OpenSTV implementation had ‘not been verified’.

Recently, extracts from Hill's election counting software comprising the Pascal code relevant to New Zealand-style Meek STV, which appear to have been provided by Hill to those developing New Zealand's electoral rules, have been published as an ebook by Richard Lung, along with notes on the code by Hill.

The code

The code from Lung's ebook totals 1802 nonblank lines of Pascal. The first line is:

program nzmeek(datafile,outt,tmpp,rslt,confile,oei,ramm,rann);

The final 4 lines are:

shutdown(rslt);erase(tmpp);
anykey(25);
cursoron;initscreen{note 37}
end.

The software in [2] is labelled version 6.4.1, whereas the published code identifies itself as version 6.7.7.

Dealing with nonstandard features

Unlike the Algorithm 123 implementation, Hill's code relies on a number of nonstandard Pascal features, and so some work is required to compile the code on a modern system.

Hill's nzmeek code depends, in Hill's words, on certain ‘compiler-supplied’ types and routines. Some of these appear to be from Turbo Pascal, whereas other are on unknown provenance.

Lines 19 and 20 of the code read:

{$i paspc} {Although in the form of a comment, this is an instruction
to include extra compiler-supplied features}

In modern Pascal, this is a directive to include code from the file paspc.pas. Therefore, we should create a file paspc.pas and implement the relevant ‘compiler-supplied’ functionality. We will target the Free Pascal compiler.

We begin with each ‘compiler-supplied subtype of integer’:

{"Compiler-supplied" types for nzmeek}
type integer = int32;
type integer1 = int8;
type integer2 = int16;

Various ‘compiler-supplied routine’ implementations are already found within the Free Pascal CRT unit. We then need only implement those other CRT-related routines which are not standard in Free Pascal:

uses Crt;

{...}

{"Compiler-supplied" CRT routines}
var ColPaper, ColInk: byte;

const lightgrey = LightGray;

procedure clrvideo;
begin
	ClrScr
end;

procedure getkeyboard(var a: char; var b: byte);
begin
	a := ReadKey
end;

procedure initscreen;
begin
	TextBackground(Black);
	TextColor(LightGray);
	ClrScr
end;

procedure ink(a: byte);
begin
	ColInk := a;
	TextColor(a)
end;

procedure paper(a: byte);
begin
	ColPaper := a;
	TextBackground(a)
end;

procedure putchattr(a: char; b, c, d: byte);
	var x, y: byte;
begin
	x := WhereX();
	y := WhereY();
	TextBackground(b);
	TextColor(c);
	Write(a);
	GotoXY(x, y);
	TextBackground(ColPaper);
	TextColor(ColInk)
end;

procedure soundoff;
begin
	NoSound
end;

Next, we implement each remaining ‘compiler-supplied routine’:

uses Crt, Sysutils;

{...}

{Other "Compiler-supplied" routines}
procedure close(var a: text; b: boolean);
begin
	System.Close(a)
end;

procedure exitprog(a: longint);
begin
	Halt(a)
end;

function get(var a: text): char;
	var c: char;
begin
	Read(a, c);
	get := c
end;

function memavail: integer;
begin
	memavail := 999999
end;

procedure ramfile(var a: text);
begin
	Assign(a, GetTempFileName)
end;

{FIXME: Stub implementation not necessary for nzmeek to run}
function fstat(a:string): boolean; begin fstat:=false; end;
procedure time(var a,b,c,d:integer); begin end;

This implements all of the necessary ‘compiler-supplied’ types and routines used by nzmeek; however, nzmeek also appears to use the pointer dereference operator to ‘peek’ into opened files. This is not supported in Free Pascal (and, indeed, I struggled to identify any Pascal variant where this is supported). Pointer dereference is one of only 2 operators in Free Pascal which cannot be overloaded, and so we must modify the code to remove this use.

For example, line 991 of the nzmeek code reads:

else if ramm^='0' then ended:=true;

To make this compliant with Free Pascal syntax, we must replace this with:

else if peek(ramm)='0' then ended:=true;

There are a total of 16 such modifications which need to be made.

Finally, we add a definition of peek into paspc.pas:

{Peek function instead of dereference}
function peek(var a: text): char;
	var c: char;
begin
	Read(a, c);
	Dec(TextRec(a).bufpos);
	peek := c
end;

Other patches

Lines 1380 to 1391 of the nzmeek code read:

command('dir votes.dat >votes.tep',nn);{note 32}
assign(tmpp,'votes.tep');reset(tmpp);
repeat
readln(tmpp,str1)
until(pos('VOTES',str1)>0)and(pos('DAT',str1)>0);
filesize:=0;nn:=1;
while(str1[nn]<'0')or(str1[nn]>'9')do nn:=nn+1;
repeat
filesize:=10*filesize+ord(str1[nn])-48;
nn:=nn+1
until str1[nn]=' ';
erase(tmpp);

In the notes accompanying the code, it is noted that an external command (MS-DOS dir) is used to determine the filesize of the input file, which is stored in filesize. Clearly, MS-DOS commands are not portable across different operating systems. Additionally, the value of filesize is used only to determine whether to store temporary data on disk or in memory. Memory is not as scarce as it was circa 1999, and so this check is unimportant.

Therefore, we can simply replace these lines with:

filesize:=0;

No other changes are required to allow nzmeek to compile and run; however, there is a minor bug due to the cleaning up of temporary data. In the original code, it appears that temporary data was stored purely in RAM, but in our paspc.pas we have implemented this using temporary files, so those files must be closed and deleted in order to avoid a resource leak.

We can fix this by changing the line originally numbered 1799 (now 1788) from:

shutdown(rslt);erase(tmpp);

to

shutdown(rslt);close(tmpp,true);erase(tmpp);close(ramm,true);erase(ramm);

The final product

We can now compile the software as usual:

$ fpc nzmeek.pas
Free Pascal Compiler version 3.2.2 [2021/05/31] for x86_64
Copyright (c) 1993-2021 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling nzmeek.pas
nzmeek.pas(975,5) Note: Local variable "j" not used
nzmeek.pas(977,1) Note: Local variable "str1" not used
nzmeek.pas(1030,10) Note: Local variable "mm" not used
nzmeek.pas(1030,13) Note: Local variable "marker" not used
nzmeek.pas(1032,21) Note: Local variable "tot1" not used
nzmeek.pas(1032,26) Note: Local variable "tot2" not used
nzmeek.pas(1264,5) Note: Local variable "arg1" not used
nzmeek.pas(1264,10) Note: Local variable "arg2" not used
nzmeek.pas(1305,1) Note: Local variable "answered" not used
nzmeek.pas(32,39) Note: Local variable "nn" not used
nzmeek.pas(35,1) Note: Local variable "constrained" is assigned but never used
nzmeek.pas(39,7) Note: Local variable "conmarker" is assigned but never used
nzmeek.pas(42,7) Note: Local variable "str1" not used
Linking nzmeek
1896 lines compiled, 0.2 sec
13 note(s) issued

As documented in the notes accompanying the software, nzmeek takes a BLT file (same format as described in [3]) named votes.dat and outputs the results to votes.res (result summary), votes.oei (detailed results data) and votes.rlt (computer-readable results).

For example, the results when counting my ballot papers for the ERS97 model election are:

New Zealand demonstration
Version 6.7.7 - NZ rules
 Number of candidates = 11
 Number of seats = 6



                    ERS97 Model Election

 Table: 1 Count: 1            Quota: 107.57

Candidate            Keep Transfer Votes

Smith                100.0%     0.0%    134.00 >>> Elected
Carpenter            100.0%     0.0%     81.00
Wright               100.0%     0.0%     27.00
Glazier              100.0%     0.0%     24.00
Duke                 100.0%     0.0%    105.00

Prince               100.0%     0.0%     91.00
Baron                100.0%     0.0%     64.00
Abbot                100.0%     0.0%     59.00
Vicar                100.0%     0.0%     55.00
Monk                 100.0%     0.0%     23.00

Freeman              100.0%     0.0%     90.00

Non-transferable                          0.00

Total                                   753.00



>>>>> Smith elected <<<<<



                    ERS97 Model Election

 Table: 2 Count: 2            Quota: 107.26

Candidate            Keep Transfer Votes

Smith                 80.3%    19.7%    107.57 >>> Elected
Carpenter            100.0%     0.0%     87.90
Wright               100.0%     0.0%     31.93
Glazier              100.0%     0.0%     30.11
Duke                 100.0%     0.0%    106.58

Prince               100.0%     0.0%     91.00
Baron                100.0%     0.0%     64.00
Abbot                100.0%     0.0%     59.79
Vicar                100.0%     0.0%     55.00
Monk                 100.0%     0.0%     23.39

Freeman              100.0%     0.0%     93.55

Non-transferable                          2.17

Total                                   753.00


Lowest candidate cannot overtake, so can safely be excluded.

>>>>> Monk excluded <<<<<



                    ERS97 Model Election

 Table: 3 Count: 3            Quota: 107.26

Candidate            Keep Transfer Votes

Smith                 80.0%    20.0%    108.86 >>> Elected
Carpenter            100.0%     0.0%     87.98
Wright               100.0%     0.0%     31.99
Glazier              100.0%     0.0%     30.19
Duke                 100.0%     0.0%    108.80 >>> Elected

Prince               100.0%     0.0%     91.00
Baron                100.0%     0.0%     64.00
Abbot                100.0%     0.0%     64.80
Vicar                100.0%     0.0%     69.20
Monk                   0.0%   100.0%      0.00 Excluded

Freeman              100.0%     0.0%     93.99

Non-transferable                          2.19

Total                                   753.00



>>>>> Duke elected <<<<<



                    ERS97 Model Election

 Table: 4 Count: 4            Quota: 107.02

Candidate            Keep Transfer Votes

Smith                 78.9%    21.1%    107.26 >>> Elected
Carpenter            100.0%     0.0%     88.40
Wright               100.0%     0.0%     32.28
Glazier              100.0%     0.0%     30.55
Duke                  98.6%     1.4%    107.36 >>> Elected

Prince               100.0%     0.0%     91.00
Baron                100.0%     0.0%     64.00
Abbot                100.0%     0.0%     64.85
Vicar                100.0%     0.0%     69.21
Freeman              100.0%     0.0%     94.23

Non-transferable                          3.86

Total                                   753.00


Lowest candidate cannot overtake, so can safely be excluded.

>>>>> Glazier excluded <<<<<



                    ERS97 Model Election

 Table: 5 Count: 5            Quota: 106.36

Candidate            Keep Transfer Votes

Smith                 78.7%    21.3%    109.38 >>> Elected
Carpenter            100.0%     0.0%     96.46
Wright               100.0%     0.0%     33.97
Glazier                0.0%   100.0%      0.00 Excluded
Duke                  98.3%     1.7%    117.85 >>> Elected

Prince               100.0%     0.0%     91.19
Baron                100.0%     0.0%     64.00
Abbot                100.0%     0.0%     65.85
Vicar                100.0%     0.0%     70.70
Freeman              100.0%     0.0%     95.11

Non-transferable                          8.48

Total                                   753.00


Lowest candidate cannot overtake, so can safely be excluded.

>>>>> Wright excluded <<<<<



                    ERS97 Model Election

 Table: 6 Count: 7            Quota: 103.71

Candidate            Keep Transfer Votes

Smith                 63.0%    37.0%    104.60 >>> Elected
Carpenter            100.0%     0.0%    111.56 >>> Elected
Wright                 0.0%   100.0%      0.00 Excluded
Duke                  87.1%    12.9%    105.66 >>> Elected
Prince               100.0%     0.0%     96.49

Baron                100.0%     0.0%     67.01
Abbot                100.0%     0.0%     68.70
Vicar                100.0%     0.0%     73.07
Freeman              100.0%     0.0%     98.88

Non-transferable                         27.04

Total                                   753.00



>>>>> Carpenter elected <<<<<



                    ERS97 Model Election

 Table: 7 Count: 10           Quota: 101.72

Candidate            Keep Transfer Votes

Smith                 61.4%    38.6%    101.92 >>> Elected
Carpenter             90.7%     9.3%    102.07 >>> Elected
Duke                  83.9%    16.1%    101.94 >>> Elected
Prince               100.0%     0.0%     97.01
Baron                100.0%     0.0%     67.22

Abbot                100.0%     0.0%     68.90
Vicar                100.0%     0.0%     73.25
Freeman              100.0%     0.0%     99.73

Non-transferable                         40.96

Total                                   753.00


Lowest candidate cannot overtake, so can safely be excluded.

>>>>> Baron excluded <<<<<



                    ERS97 Model Election

 Table: 8 Count: 11            Quota: 92.03

Candidate            Keep Transfer Votes

Smith                 61.3%    38.7%    101.72 >>> Elected
Carpenter             90.4%     9.6%    101.79 >>> Elected
Duke                  83.7%    16.3%    101.73 >>> Elected
Prince               100.0%     0.0%     97.05 >>> Elected
Baron                  0.0%   100.0%      0.00 Excluded

Abbot                100.0%     0.0%     68.91
Vicar                100.0%     0.0%     73.26
Freeman              100.0%     0.0%     99.77 >>> Elected

Non-transferable                        108.77

Total                                   753.00



>>>>> Freeman elected <<<<<

>>>>> Prince elected <<<<<



                    ERS97 Model Election

 Table: 9 Count: 19            Quota: 74.49

Candidate            Keep Transfer Votes

Smith                 45.2%    54.8%     75.06 >>> Elected
Carpenter             61.5%    38.5%     75.24 >>> Elected
Duke                  61.1%    38.9%     75.08 >>> Elected
Prince                74.2%    25.8%     75.15 >>> Elected
Abbot                100.0%     0.0%     70.69

Vicar                100.0%     0.0%     75.03 >>> Elected
Freeman               71.5%    28.5%     75.17 >>> Elected

Non-transferable                        231.59

Total                                   753.00



>>>>> Vicar elected <<<<<

>>>>> Abbot excluded <<<<<

because all seats are now filled.


Election complete

With this test case, the OpenTally, OpenSTV 1.7 and nzmeek implementations of New Zealand Meek STV have been validated against each other.

References

[1] Hill ID. Implementing STV by Meek's method. Voting Matters. 2006 Jul; (22): 7–10. http://www.votingmatters.org.uk/ISSUE22/I22P2.pdf

[2] Wichmann BA. Validation of implementation of the Meek algorithm for STV. London: McDougall Trust; 2000 Apr 28. http://www.votingmatters.org.uk/RES/MKVAL.pdf

[3] Hill ID, Wichmann BA, Woodall DR. Algorithm 123: single transferable vote by Meek's method. The Computer Journal. 1987 Jun; 30: 277–81. doi: 10.1093/comjnl/30.3.277. In corrected form at: https://www.dia.govt.nz/diawebsite.NSF/Files/meekm/%24file/meekm.pdf