From b282e055140ff65879296d4654ad269cc7ff8185 Mon Sep 17 00:00:00 2001 From: Jed Barber Date: Fri, 27 Jan 2017 17:39:05 +1100 Subject: Code a lot cleaner, algorithm theoretically improved, yet still slow as fuck probably due to criteria parsing --- readme.txt | 1 - src/Counter.hs | 51 ++++++++-------- src/Criteria.hs | 3 +- src/Election.hs | 169 ++++++++++++++------------------------------------- src/Miscellaneous.hs | 9 +++ 5 files changed, 84 insertions(+), 149 deletions(-) diff --git a/readme.txt b/readme.txt index c314939..dd3f968 100644 --- a/readme.txt +++ b/readme.txt @@ -18,7 +18,6 @@ Aside from base, the cabal packages required to compile this program are: transformers parsec vector - containers diff --git a/src/Counter.hs b/src/Counter.hs index 37b36dc..855b266 100644 --- a/src/Counter.hs +++ b/src/Counter.hs @@ -1,5 +1,4 @@ module Counter( - Criteria, SenateCounter, createSenateCounter, @@ -13,6 +12,7 @@ module Counter( import qualified Candidate as Typ import qualified Preferences as Pref +import qualified Criteria as Crit import qualified CSV as CSV import qualified Storage as Vec import qualified System.IO as IO @@ -25,10 +25,6 @@ import qualified Data.List as List --- represents a criteria used for finding ballots that voted a specific --- way, for example voted for candidate C as #1, candidate F as #2, etc -type Criteria = [(Typ.Ranking,Typ.CandidateID)] - data SenateCounter = SenateCounter { prefData :: Vec.Store , ballotMap :: Typ.BelowLineBallot @@ -40,40 +36,45 @@ data SenateCounter = SenateCounter createSenateCounter :: FilePath -> Typ.AboveLineBallot -> Typ.BelowLineBallot -> IO SenateCounter createSenateCounter f a b = do numLines <- File.countLines f - arrayData <- Vec.createStore numLines (length b) + prefStore <- Vec.createStore numLines (length b) h <- IO.openFile f IO.ReadMode let readFunc n p = if (n > numLines) then return p else do t0 <- IO.hGetLine h - let t1 = CSV.parseRecord CSV.defaultSettings (t0 ++ "\n") - t2 = Maybe.listToMaybe . reverse . Either.fromRight $ t1 - t3 = Pref.parsePreferences (length a) (length b) (Maybe.fromJust t2) - t4 = Pref.normalise a b (Either.fromRight t3) - t5 = Maybe.fromJust t4 - if (Either.isRight t1) && (Maybe.isJust t2) && (Either.isRight t3) && (Maybe.isJust t4) - then mapM_ (Vec.setPref arrayData n) t5 >> readFunc (n + 1) (p + 1) + let prefs = parseRawLine a b t0 + result = Maybe.fromJust prefs + if (Maybe.isJust prefs) + then Vec.setPrefs prefStore n result >> readFunc (n + 1) (p + 1) else readFunc (n + 1) p p <- readFunc 1 0 IO.hClose h - return (SenateCounter arrayData b p) + return (SenateCounter prefStore b p) + + +parseRawLine :: Typ.AboveLineBallot -> Typ.BelowLineBallot -> String -> Maybe [Pref.Preference] +parseRawLine a b input = + let t1 = CSV.parseRecord CSV.defaultSettings (input ++ "\n") + t2 = Maybe.listToMaybe . reverse . Either.fromRight $ t1 + t3 = Pref.parsePreferences (length a) (length b) (Maybe.fromJust t2) + t4 = Pref.normalise a b (Either.fromRight t3) + in if (Either.isRight t1 && Maybe.isJust t2 && Either.isRight t3) + then t4 + else Nothing -doCount :: SenateCounter -> Criteria -> IO Int -doCount sen criteria = do - let isValidCriteria = all (\(x,y) -> y `List.elem` (ballotMap sen)) criteria - let critToPref (a,b) = (Maybe.fromJust (List.elemIndex b (ballotMap sen)) + 1, a) - neededPrefs = map critToPref criteria - checkFunc n r = if (n > numBallots sen) then return r else do - t <- Con.liftM and (mapM (Vec.checkPref (prefData sen) n) neededPrefs) - if t then checkFunc (n + 1) (r + 1) else checkFunc (n + 1) r - if isValidCriteria - then checkFunc 1 0 - else return 0 +doCount :: SenateCounter -> Crit.Criteria -> IO Int +doCount sen criteria = + let tailFunc n r = if (n > numBallots sen) then return r else do + prefs <- Vec.getPrefs (prefData sen) n + if (Crit.evaluate (ballotMap sen) prefs criteria) + then tailFunc (n + 1) (r + 1) + else tailFunc (n + 1) r + in tailFunc 1 0 diff --git a/src/Criteria.hs b/src/Criteria.hs index 5df9cf1..7f46970 100644 --- a/src/Criteria.hs +++ b/src/Criteria.hs @@ -42,7 +42,8 @@ evaluate ballot preferences criteria = isValidInput :: Typ.BelowLineBallot -> [Pref.Preference] -> Bool isValidInput ballot preferences = - all (\(x,y) -> x > 0 && x <= length ballot && y > 0 && y <= length ballot) preferences + all (\(x,y) -> x > 0 && x <= length ballot + && y > 0 && y <= length ballot) preferences diff --git a/src/Election.hs b/src/Election.hs index 39bcb22..0789fcf 100644 --- a/src/Election.hs +++ b/src/Election.hs @@ -12,13 +12,15 @@ import qualified System.IO as IO import qualified Control.Monad as Con import qualified Control.Monad.Trans.Either as ET import qualified Control.Monad.IO.Class as MIO -import qualified Data.Map.Strict as Map +import Data.List ( (\\) ) import qualified Data.List as List import qualified Data.Maybe as Maybe import qualified Data.Either.Unwrap as Either import qualified Counter as Sen import qualified Candidate as Typ +import qualified Criteria as Crit import qualified CSV as CSV +import Miscellaneous ( (.:) ) import qualified Miscellaneous as Misc @@ -50,9 +52,15 @@ data Entry = Entry deriving (Eq) data Trace = Trace - { getCriteria :: Sen.Criteria + { getCriteria :: Crit.Criteria , getTransferVal :: Float } - deriving (Eq) + +-- can't check for equality on functions, unfortunately, +-- so this'll have to do +instance Eq Trace where + a == b = + (length (getCriteria a) == length (getCriteria b)) + && (getTransferVal a == getTransferVal b) data Status = Running | Elected | Eliminated deriving (Show, Eq) @@ -60,28 +68,22 @@ data Status = Running | Elected | Eliminated data Transfer = Transfer { getWhoFrom :: Typ.CandidateID , getVoteAmount :: Int + , getNewValue :: Float , getWhatToDist :: [Trace] } --- the ints here are the raw count values of the ballots --- that satisfy the criteria in each trace -type TransferMap = Map.Map Typ.CandidateID [(Int,Trace)] - createElection :: FilePath -> Sen.SenateCounter -> Int -> Bool -> IO Election createElection outDir counter numToElect verbosity = do entries <- mapM (candToEntry counter) (Sen.getBallot counter) - let mainLog = outDir ++ "/" ++ "log.txt" - total = Sen.getTotal counter - quota = droopQuota total numToElect return (Election { getEntries = entries , getCounter = counter , getLogDir = outDir - , getTotalPapers = total - , getQuota = quota - , getMainLog = mainLog + , getTotalPapers = Sen.getTotal counter + , getQuota = droopQuota (Sen.getTotal counter) numToElect + , getMainLog = outDir ++ "/" ++ "log.txt" , getNextLogNum = 1 , getSeats = numToElect , getVacancies = numToElect @@ -100,9 +102,15 @@ droopQuota votes seats = +compareVotes :: Entry -> Entry -> Ordering +compareVotes x y = compare (getTotalVotes x) (getTotalVotes y) + + + + candToEntry :: Sen.SenateCounter -> Typ.CandidateID -> IO Entry candToEntry counter candidate = do - let criteria = [(1,candidate)] + let criteria = [Crit.matchID candidate] trace = Trace criteria 1 firstPrefs <- Sen.doCount counter criteria return (Entry @@ -206,13 +214,12 @@ doElectCandidate e = do electedEntry = List.maximumBy compareVotes running (beforeEntries, afterEntries) = Misc.partBeforeAfter electedEntry (getEntries e) - newTransferValue = (fromIntegral (getTotalVotes electedEntry - getQuota e)) / - (fromIntegral (getTotalVotes electedEntry)) - transferFunction x = x { getTransferVal = newTransferValue * getTransferVal x } newTransfer = Transfer { getWhoFrom = getID electedEntry , getVoteAmount = getTotalVotes electedEntry - getQuota e - , getWhatToDist = map transferFunction (getCritTrace electedEntry) } + , getNewValue = (fromIntegral (getTotalVotes electedEntry - getQuota e)) / + (fromIntegral (getTotalVotes electedEntry)) + , getWhatToDist = getCritTrace electedEntry } revisedElectedEntry = electedEntry { getStatus = Elected @@ -228,7 +235,7 @@ doElectCandidate e = do ET.right (e { getEntries = allRevised , getTransferQueue = (getTransferQueue e) ++ [newTransfer] - , getNextToElect = 1 + getNextToElect e + , getNextToElect = getNextToElect e + 1 , getVacancies = getVacancies e - 1 }) else ET.left e @@ -245,7 +252,7 @@ checkIfDone e = --- redistributing votes in STV is surprisingly complex +-- redistributing votes in STV is annoying as hell transferVotes :: Election -> ET.EitherT Election IO Election transferVotes e = if (length (getTransferQueue e) > 0) @@ -260,23 +267,29 @@ doVoteTransfer e = do let (currentTransfer:remainingTransfers) = getTransferQueue e fromEntry = Maybe.fromJust (List.find ((== getWhoFrom currentTransfer) . getID) (getEntries e)) (beforeEntries, afterEntries) = Misc.partBeforeAfter fromEntry (getEntries e) - - mapKeys = map getID (beforeEntries ++ afterEntries) - notRunningKeys = map getID (filter ((/= Running) . getStatus) (getEntries e)) - transferMap <- MIO.liftIO $ Con.foldM (addToTransferMap (getCounter e) mapKeys) Map.empty (getWhatToDist currentTransfer) - revisedMap <- MIO.liftIO $ redistNotRunning (getCounter e) mapKeys notRunningKeys transferMap - - let reviseFunc entry = - if (getStatus entry == Running) - then transferToEntry revisedMap entry - else entry + notRunningIDs = map getID (filter ((/= Running) . getStatus) (getEntries e)) + + reviseTrace candID trace = trace + { getCriteria = getCriteria trace ++ + [Crit.many (Crit.matchFromList notRunningIDs), Crit.matchID candID] + , getTransferVal = getTransferVal trace * getNewValue currentTransfer } + + reviseFunc entry = do + let newTraces = map (reviseTrace (getID entry)) (getWhatToDist currentTransfer) + rawVoteChanges <- mapM (Sen.doCount (getCounter e)) (map getCriteria newTraces) + let totalVoteChange = sum (zipWith (floor .: (*)) (map fromIntegral rawVoteChanges) (map getTransferVal newTraces)) + return (entry + { getVoteChange = totalVoteChange + , getTotalVotes = getTotalVotes entry + totalVoteChange + , getCritTrace = getCritTrace entry ++ newTraces }) revisedFromEntry = fromEntry { getVoteChange = -(getVoteAmount currentTransfer) , getTotalVotes = getTotalVotes fromEntry - (getVoteAmount currentTransfer) - -- this last bit needs to be replaced with something more accurate - , getCritTrace = [] } - allRevised = (map reviseFunc beforeEntries) ++ [revisedFromEntry] ++ (map reviseFunc afterEntries) + , getCritTrace = (getCritTrace fromEntry) \\ (getWhatToDist currentTransfer) } + revisedBeforeEntries <- MIO.liftIO $ mapM reviseFunc beforeEntries + revisedAfterEntries <- MIO.liftIO $ mapM reviseFunc afterEntries + let allRevised = revisedBeforeEntries ++ [revisedFromEntry] ++ revisedAfterEntries ET.left (e { getEntries = allRevised @@ -285,88 +298,6 @@ doVoteTransfer e = do -addToTransferMap :: Sen.SenateCounter -> [Typ.CandidateID] -> TransferMap -> Trace -> IO TransferMap -addToTransferMap counter mapKeys transferMap traceToAdd = do - let newTraces = map (addToTrace traceToAdd) mapKeys - keyed = zip mapKeys newTraces - noDupes = filter (not . criteriaHasDupe . getCriteria . snd) keyed - counted <- mapM (\(k,t) -> Sen.doCount counter (getCriteria t) >>= (\x -> return (k,(x,t)))) noDupes - let notZero (k,xt) = floor ((fromIntegral (fst xt)) * getTransferVal (snd xt)) > 0 - noZeroMap = filter notZero counted - listed = map (\(k,xt) -> (k,xt:[])) noZeroMap - return (Map.unionWith (++) transferMap (Map.fromList listed)) - - - - -redistNotRunning :: Sen.SenateCounter -> [Typ.CandidateID] -> [Typ.CandidateID] -> TransferMap -> IO TransferMap -redistNotRunning counter mapKeys notRunningKeys transferMap = - let lookupNotRunning k m = - if (length k == 0) - then Nothing - else let x = Map.lookup (head k) m - in if (Maybe.isJust x) - then Just (head k, Maybe.fromJust x) - else lookupNotRunning (tail k) m - item = lookupNotRunning notRunningKeys transferMap - in if (Maybe.isJust item) - then do - let (key,valList) = Maybe.fromJust item - removedMap = Map.delete key transferMap - revisedMap <- Con.foldM (addToTransferMap counter mapKeys) removedMap (map snd valList) - redistNotRunning counter mapKeys notRunningKeys revisedMap - else return transferMap - - - - -transferToEntry :: TransferMap -> Entry -> Entry -transferToEntry transferMap entry = - let lookupVal = Map.lookup (getID entry) transferMap - valList = Maybe.fromJust lookupVal - - voteChanges = map (\(x,y) -> floor ((fromIntegral x) * getTransferVal y)) valList - addedTraces = map snd valList - revisedEntry = entry - { getVoteChange = sum voteChanges - , getTotalVotes = getTotalVotes entry + sum voteChanges - , getCritTrace = getCritTrace entry ++ addedTraces } - - in if (Maybe.isJust lookupVal) - then revisedEntry - else entry - - - - -criteriaHasDupe :: Sen.Criteria -> Bool -criteriaHasDupe crit = - let test seen toCheck = - if (length toCheck == 0) - then False - else if (elem (snd (head toCheck)) seen) - then True - else test ((snd (head toCheck)):seen) (tail toCheck) - in test [] crit - - - - -addToCriteria :: Typ.CandidateID -> Sen.Criteria -> Sen.Criteria -addToCriteria candID crit = - let maxRank = fst (List.maximumBy (\x y -> compare (fst x) (fst y)) crit) - in (maxRank + 1, candID):crit - - - - -addToTrace :: Trace -> Typ.CandidateID -> Trace -addToTrace trace candID = trace - { getCriteria = addToCriteria candID (getCriteria trace) } - - - - -- needs to be modified to take into account ties checkNoQuota :: Election -> ET.EitherT Election IO Election checkNoQuota e = do @@ -381,7 +312,6 @@ checkNoQuota e = do if ((getStatus entry == Running) && (entry /= minimumEntry)) then makeElect entry else entry - revisedMinEntry = if (length running <= getVacancies e) then makeElect minimumEntry @@ -407,6 +337,7 @@ excludeSomeone e = do newTransfer = Transfer { getWhoFrom = getID excludedEntry , getVoteAmount = getTotalVotes excludedEntry + , getNewValue = 1 , getWhatToDist = getCritTrace excludedEntry } revisedExcludedEntry = excludedEntry @@ -421,9 +352,3 @@ excludeSomeone e = do else ET.right e - - -compareVotes :: Entry -> Entry -> Ordering -compareVotes x y = compare (getTotalVotes x) (getTotalVotes y) - - diff --git a/src/Miscellaneous.hs b/src/Miscellaneous.hs index 5f018e6..ba9ca98 100644 --- a/src/Miscellaneous.hs +++ b/src/Miscellaneous.hs @@ -1,6 +1,7 @@ module Miscellaneous( if', (?), + (.:), selectFrom, readMaybe, partBeforeAfter @@ -29,6 +30,14 @@ infixr 1 ? +-- with this, I have truly gone dotty +infixr 9 .: +(.:) :: (a -> b) -> (c -> d -> a) -> c -> d -> b +(.:) = (.).(.) + + + + -- kinda functions like poor man's sql -- first argument is the indices of the items you want in the results -- second argument is index-item pairs to dictate what records are acceptable to select from -- cgit