RunasSudo
/
OpenTally
1
Fork 0
Code Issues 3 Pull Requests Activity

Implement --ties random

This commit is contained in:
RunasSudo 2021-06-13 03:15:15 +10:00
parent 266d8e2495
commit 4845ebe52f
Signed by: RunasSudo
GPG Key ID: 7234E476BF21C61A
12 changed files with 192 additions and 13 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

63
Cargo.lock generated
View File

@ -38,6 +38,15 @@ version = "1.2.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
[[package]]
name = "block-buffer"
version = "0.9.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "4152116fd6e9dadb291ae18fc1ec3575ed6d84c29642d97890f4b4a3417297e4"
dependencies = [
"generic-array",
]
[[package]]
name = "bstr"
version = "0.2.16"
@ -122,6 +131,15 @@ version = "0.4.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "6245d59a3e82a7fc217c5828a6692dbc6dfb63a0c8c90495621f7b9d79704a0e"
[[package]]
name = "cpufeatures"
version = "0.1.4"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ed00c67cb5d0a7d64a44f6ad2668db7e7530311dd53ea79bcd4fb022c64911c8"
dependencies = [
"libc",
]
[[package]]
name = "crc32fast"
version = "1.2.1"
@ -171,6 +189,15 @@ version = "2.0.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "524cbf6897b527295dff137cec09ecf3a05f4fddffd7dfcd1585403449e74198"
[[package]]
name = "digest"
version = "0.9.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "d3dd60d1080a57a05ab032377049e0591415d2b31afd7028356dbf3cc6dcb066"
dependencies = [
"generic-array",
]
[[package]]
name = "doc-comment"
version = "0.3.3"
@ -195,6 +222,16 @@ dependencies = [
"miniz_oxide",
]
[[package]]
name = "generic-array"
version = "0.14.4"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "501466ecc8a30d1d3b7fc9229b122b2ce8ed6e9d9223f1138d4babb253e51817"
dependencies = [
"typenum",
"version_check",
]
[[package]]
name = "git-version"
version = "0.3.4"
@ -368,6 +405,12 @@ dependencies = [
"autocfg",
]
[[package]]
name = "opaque-debug"
version = "0.3.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "624a8340c38c1b80fd549087862da4ba43e08858af025b236e509b6649fc13d5"
[[package]]
name = "opentally"
version = "0.1.0"
@ -387,6 +430,7 @@ dependencies = [
"num-traits",
"paste",
"rug",
"sha2",
"wasm-bindgen",
"xmltree",
]
@ -524,6 +568,19 @@ version = "1.0.126"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ec7505abeacaec74ae4778d9d9328fe5a5d04253220a85c4ee022239fc996d03"
[[package]]
name = "sha2"
version = "0.9.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "b362ae5752fd2137731f9fa25fd4d9058af34666ca1966fb969119cc35719f12"
dependencies = [
"block-buffer",
"cfg-if 1.0.0",
"cpufeatures",
"digest",
"opaque-debug",
]
[[package]]
name = "static_assertions"
version = "1.1.0"
@ -553,6 +610,12 @@ version = "0.1.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "a7f741b240f1a48843f9b8e0444fb55fb2a4ff67293b50a9179dfd5ea67f8d41"
[[package]]
name = "typenum"
version = "1.13.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "879f6906492a7cd215bfa4cf595b600146ccfac0c79bcbd1f3000162af5e8b06"
[[package]]
name = "unicode-segmentation"
version = "1.7.1"

1
Cargo.toml
View File

@ -13,6 +13,7 @@ git-version = "0.3.4"
ibig = "0.3.2"
itertools = "0.10.1"
num-traits = "0.2"
sha2 = "0.9.5"
wasm-bindgen = "0.2.74"
# Only for WebAssembly - include here for syntax highlighting

11
docs/rng.md Normal file
View File

@ -0,0 +1,11 @@
# Deterministic random number generator specification
The deterministic random number generator used in OpenTally is based on an algorithm by [Ronald L Rivest](https://people.csail.mit.edu/rivest/sampler.py).
The algorithm takes a *seed* value, which is an arbitrary character string. The algorithm has, in its internal state, a *counter*, whose value is initially 0.
In order to generate a value between 0 (inclusive) and *n* (exclusive), to the state is appended a comma (",") followed by the value of the counter, and a SHA-256 hash *H* is computed of the resulting string encoded using UTF-8. The hash *H* is represented as an unsigned hexadecimal integer, *k*. The counter is incremented by 1.
In order to avoid modulo bias, if *k* ≥ ⌊*M*/*n*⌋ × *n* (where *M* = 2^256), *k* is discarded and the algorithm is repeated.
Otherwise, the result is *k* modulo *n*.

4
html/index.html
View File

@ -127,10 +127,10 @@
<option value="prompt">Prompt</option>
</select>
</label>
<!--<label>
<label>
Random seed:
<input type="text" id="txtSeed" value="">
</label>-->
</label>
</div>
<!--<div class="subheading">
Constraints:

8
html/index.js
View File

@ -108,6 +108,7 @@ async function clickCount() {
document.getElementById('selQuotaCriterion').value,
document.getElementById('selQuotaMode').value,
document.getElementById('selTies').value.split(','),
document.getElementById('txtSeed').value,
document.getElementById('selTransfers').value,
document.getElementById('selSurplus').value,
document.getElementById('selPapers').value == 'transferable',
@ -129,6 +130,13 @@ async function clickCount() {
});
}
// Provide a default seed
if (document.getElementById('txtSeed').value === '') {
function pad(x) { if (x < 10) { return '0' + x; } return '' + x; }
let d = new Date();
document.getElementById('txtSeed').value = d.getFullYear() + pad(d.getMonth() + 1) + pad(d.getDate());
}
// Print logic
async function printResult() {

3
src/election.rs
View File

@ -17,6 +17,7 @@
use crate::logger::Logger;
use crate::numbers::Number;
use crate::sharandom::SHARandom;
use std::collections::HashMap;
@ -133,6 +134,7 @@ pub struct CountState<'a, N> {
pub forwards_tiebreak: Option<HashMap<&'a Candidate, usize>>,
pub backwards_tiebreak: Option<HashMap<&'a Candidate, usize>>,
pub random: Option<SHARandom<'a>>,
pub quota: Option<N>,
pub vote_required_election: Option<N>,
@ -154,6 +156,7 @@ impl<'a, N: Number> CountState<'a, N> {
loss_fraction: CountCard::new(),
forwards_tiebreak: None,
backwards_tiebreak: None,
random: None,
quota: None,
vote_required_election: None,
num_elected: 0,

1
src/lib.rs
View File

@ -18,6 +18,7 @@
pub mod election;
pub mod logger;
pub mod numbers;
pub mod sharandom;
pub mod stv;
pub mod ties;

5
src/main.rs
View File

@ -108,6 +108,10 @@ struct STV {
#[clap(help_heading=Some("STV VARIANTS"), short='t', long, possible_values=&["forwards", "backwards", "random", "prompt"], default_value="prompt", value_name="methods")]
ties: Vec<String>,
/// Random seed to use with --ties random
#[clap(help_heading=Some("STV VARIANTS"), long, value_name="seed")]
random_seed: Option<String>,
/// Method of surplus distributions
#[clap(help_heading=Some("STV VARIANTS"), short='s', long, possible_values=&["wig", "uig", "eg", "meek"], default_value="wig", value_name="method")]
surplus: String,
@ -192,6 +196,7 @@ where
&cmd_opts.quota_criterion,
&cmd_opts.quota_mode,
&cmd_opts.ties,
&cmd_opts.random_seed,
&cmd_opts.surplus,
&cmd_opts.surplus_order,
cmd_opts.transferable_only,

63
src/sharandom.rs Normal file
View File

@ -0,0 +1,63 @@
/* OpenTally: Open-source election vote counting
* Copyright © 2021 Lee Yingtong Li (RunasSudo)
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*/
use ibig::UBig;
use sha2::{Digest, Sha256};
#[derive(Clone)]
pub struct SHARandom<'r> {
seed: &'r str,
counter: usize,
}
impl<'r> SHARandom<'r> {
pub fn new(seed: &'r str) -> Self {
Self {
seed: seed,
counter: 0,
}
}
pub fn next(&mut self, max: usize) -> usize {
let mut hasher = Sha256::new();
hasher.update(format!("{},{}", self.seed, self.counter).as_bytes());
self.counter += 1;
let hash = hasher.finalize();
let hash = UBig::from_be_bytes(&hash);
if hash >= UBig::from(2_u32).pow(256) / UBig::from(max) * UBig::from(max) {
return self.next(max);
}
return (hash % UBig::from(max)).to_string().parse().unwrap();
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn sharandom1() {
let mut random = SHARandom::new(&"foobar");
assert_eq!(random.next(10), 0);
assert_eq!(random.next(42), 30);
assert_eq!(random.next(64), 13);
}
}

20
src/stv/mod.rs
View File

@ -22,6 +22,7 @@ pub mod wasm;
use crate::numbers::Number;
use crate::election::{Candidate, CandidateState, CountCard, CountState, Parcel, Vote};
use crate::sharandom::SHARandom;
use crate::ties::TieStrategy;
use itertools::Itertools;
@ -31,7 +32,7 @@ use std::cmp::max;
use std::collections::HashMap;
use std::ops;
pub struct STVOptions<'o> {
pub struct STVOptions {
pub round_tvs: Option<usize>,
pub round_weights: Option<usize>,
pub round_votes: Option<usize>,
@ -41,7 +42,7 @@ pub struct STVOptions<'o> {
pub quota: QuotaType,
pub quota_criterion: QuotaCriterion,
pub quota_mode: QuotaMode,
pub ties: Vec<TieStrategy<'o>>,
pub ties: Vec<TieStrategy>,
pub surplus: SurplusMethod,
pub surplus_order: SurplusOrder,
pub transferable_only: bool,
@ -51,7 +52,7 @@ pub struct STVOptions<'o> {
pub pp_decimals: usize,
}
impl<'o> STVOptions<'o> {
impl STVOptions {
pub fn new(
round_tvs: Option<usize>,
round_weights: Option<usize>,
@ -63,6 +64,7 @@ impl<'o> STVOptions<'o> {
quota_criterion: &str,
quota_mode: &str,
ties: &Vec<String>,
random_seed: &Option<String>,
surplus: &str,
surplus_order: &str,
transferable_only: bool,
@ -103,7 +105,7 @@ impl<'o> STVOptions<'o> {
ties: ties.into_iter().map(|t| match t.as_str() {
"forwards" => TieStrategy::Forwards,
"backwards" => TieStrategy::Backwards,
"random" => TieStrategy::Random(&"TODO"),
"random" => TieStrategy::Random(random_seed.as_ref().expect("Must provide a --random-seed if using --ties random").clone()),
"prompt" => TieStrategy::Prompt,
_ => panic!("Invalid --ties"),
}).collect(),
@ -143,6 +145,7 @@ impl<'o> STVOptions<'o> {
if self.normalise_ballots { flags.push("--normalise-ballots".to_string()); }
let ties_str = self.ties.iter().map(|t| t.describe()).join(" ");
if ties_str != "prompt" { flags.push(format!("--ties {}", ties_str)); }
for t in self.ties.iter() { if let TieStrategy::Random(seed) = t { flags.push(format!("--random-seed {}", seed)); } }
if self.quota != QuotaType::DroopExact { flags.push(self.quota.describe()); }
if self.quota_criterion != QuotaCriterion::Greater { flags.push(self.quota_criterion.describe()); }
if self.quota_mode != QuotaMode::Static { flags.push(self.quota_mode.describe()); }
@ -295,7 +298,14 @@ pub enum STVError {
UnresolvedTie,
}
pub fn count_init<N: Number>(mut state: &mut CountState<'_, N>, opts: &STVOptions) {
pub fn count_init<'a, N: Number>(mut state: &mut CountState<'a, N>, opts: &'a STVOptions) {
// Initialise RNG
for t in opts.ties.iter() {
if let TieStrategy::Random(seed) = t {
state.random = Some(SHARandom::new(seed));
}
}
distribute_first_preferences(&mut state);
calculate_quota(&mut state, opts);
elect_meeting_quota(&mut state, opts);

15
src/stv/wasm.rs
View File

@ -56,7 +56,7 @@ macro_rules! impl_type {
#[wasm_bindgen]
#[allow(non_snake_case)]
pub fn [<count_init_$type>](state: &mut [<CountState$type>], opts: &STVOptions) {
stv::count_init(&mut state.0, &opts.0);
stv::count_init(&mut state.0, opts.as_static());
}
#[wasm_bindgen]
@ -141,7 +141,7 @@ impl_type!(NativeFloat64);
impl_type!(Rational);
#[wasm_bindgen]
pub struct STVOptions(stv::STVOptions<'static>);
pub struct STVOptions(stv::STVOptions);
#[wasm_bindgen]
impl STVOptions {
@ -156,6 +156,7 @@ impl STVOptions {
quota_criterion: &str,
quota_mode: &str,
ties: Array,
random_seed: String,
surplus: &str,
surplus_order: &str,
transferable_only: bool,
@ -175,6 +176,7 @@ impl STVOptions {
quota_criterion,
quota_mode,
&ties.iter().map(|v| v.as_string().unwrap()).collect(),
&Some(random_seed),
surplus,
surplus_order,
transferable_only,
@ -186,6 +188,15 @@ impl STVOptions {
}
}
impl STVOptions {
fn as_static(&self) -> &'static stv::STVOptions {
unsafe {
let ptr = &self.0 as *const stv::STVOptions;
&*ptr
}
}
}
// Reporting
fn init_results_table<N: Number>(election: &Election<N>, opts: &stv::STVOptions) -> String {

11
src/ties.rs
View File

@ -27,14 +27,14 @@ use wasm_bindgen::prelude::wasm_bindgen;
use std::io::{stdin, stdout, Write};
#[derive(PartialEq)]
pub enum TieStrategy<'s> {
pub enum TieStrategy {
Forwards,
Backwards,
Random(&'s str),
Random(String),
Prompt,
}
impl<'s> TieStrategy<'s> {
impl TieStrategy {
pub fn describe(&self) -> String {
match self {
Self::Forwards => "forwards",
@ -73,7 +73,10 @@ impl<'s> TieStrategy<'s> {
return Ok(candidates[0]);
}
}
Self::Random(_seed) => { todo!() }
Self::Random(_) => {
state.logger.log_literal(format!("Tie between {} broken at random.", smart_join(&candidates.iter().map(|c| c.name.as_str()).collect())));
return Ok(candidates[state.random.as_mut().unwrap().next(candidates.len())]);
}
Self::Prompt => {
match prompt(candidates) {
Ok(c) => {