Re: [boost] Re: logo contest status query

From: Jason Hise (chaos_at_[hidden])
Date: 2005-03-31 02:08:21

I thought it would be fun to quickly try to write a program to do IRV 
voting.  Hopefully it can be used to make the lives of the people 
counting the votes a bit easier.  The file piped into cin should list 
each voter's choices in descending order on separate lines after a line 
containing only the string "vote:".  For instance, the following input 
represents four unnamed voters, each of whom was allowed three votes, 
and who made first choices of a, b, c, and a, respectively.

vote:
a
b
c
vote:
b
c
d
vote:
c
d
e
vote:
a
b
f

Running the program with this input results in the following output.

clearing votes for a
clearing votes for b
clearing votes for c
clearing votes for d
clearing votes for e
clearing votes for f
a now has 1 votes
b now has 1 votes
c now has 1 votes
a now has 2 votes
d has been removed from the running
e has been removed from the running
f has been removed from the running
clearing votes for a
clearing votes for b
clearing votes for c
a now has 1 votes
b now has 1 votes
c now has 1 votes
a now has 2 votes
b has been removed from the running
c has been removed from the running
clearing votes for a
a now has 1 votes
a now has 2 votes

WINNER:
a

If I made any errors in my implementation of the voting algorithm, 
please let me know.  I hope someone finds this useful, but if not, at 
least it was fun to write :)

-Jason


#include <string>
#include <vector>
#include <list>
#include <map>
#include <iostream>

using namespace std;

int main (  )
{
    string s;
    list < string > vote;
    vector < list < string > > votes;
    map < string, size_t > candidates;

    while ( true )
    {
        getline ( cin, s );
        if ( cin.eof (  ) )
        {
            if ( !vote.empty (  ) ) votes.push_back ( vote );
            break;
        }

        if ( s == "vote:" )
        {
            if ( !vote.empty (  ) )
            {
                votes.push_back ( vote );
                vote.clear (  );
            }
        }
        else
        {
            candidates.insert ( map < string, size_t >::value_type ( s, 0 ) );
            vote.push_back ( s );
        }
    }

    bool winner = false;
    size_t min_votes;
    map < string, size_t >::iterator c_iter, c_next;
    vector < list < string > >::iterator vl_iter;

    while ( !winner )
    {
        c_iter = candidates.begin (  );
        while ( c_iter != candidates.end (  ) )
        {
            cout << "clearing votes for " << c_iter->first << endl;
            c_iter->second = 0;
            ++c_iter;
        }

        vl_iter = votes.begin (  );
        while ( vl_iter != votes.end (  ) )
        {
            list < string >::iterator v_iter ( vl_iter->begin (  ) );
            while ( v_iter != vl_iter->end (  ) )
            {
                c_iter = candidates.find ( *v_iter );
                if ( c_iter != candidates.end (  ) )
                {
                    ++( c_iter->second );
                    cout << c_iter->first << " now has " << c_iter->second << " votes" << endl;
                    break;
                }

                ++v_iter;
            }

            ++vl_iter;
        }

        c_iter = candidates.begin (  );
        min_votes = c_iter->second;
        winner = true;
        while ( c_iter != candidates.end (  ) )
        {
            if ( c_iter->second < min_votes )
            {
                min_votes = c_iter->second;
                winner = false;
            }
            ++c_iter;
        }

        if ( winner )
        {
            if ( candidates.size (  ) > 1 )
            {
                cout << endl << "TIE, WINNERS WERE:" << endl;
            }
            else
            {
                cout << endl << "WINNER:" << endl;
            }
        }

        c_iter = candidates.begin (  );
        while ( c_iter != candidates.end (  ) )
        {
            c_next = c_iter;
            ++c_next;

            if ( winner )
            {
                cout << c_iter->first << endl;
            }
            else if ( c_iter->second == min_votes )
            {
                cout << c_iter->first << " has been removed from the running" << endl;
                candidates.erase ( c_iter );
            }

            c_iter = c_next;
        }
    }

    return 0;
}