Saturday, February 28, 2009

Australian Voting

Australian Voting was fun, I set up 3 classes: Ballot, Candidate, and Election to simulate the election.

Ballot keeps track of a single ballot and which vote on that ballot is active. Candidate keeps a linked list of the Ballots that that Candidate owns, and it's responsible for redistributing those ballots when it loses. It also keeps track of how many votes it has so we can determine who has won. Election keeps an array of all the ballots and candidates, and runs the actual election process. The main() function reads in the input and drives the Election.

I built the 'array of intermingled linked lists' that Downing discussed when he introduced the project. It's a very elegant method of dealing with the ballots and minimizing the number of ballots which need to be recalculated.

To get the Candidate to be able to talk back to the Election to give its ballots back to other Candidates, I had to move all the class definitions above the method definitions. This isn't that hard, but it means you have to state all the methods as Election::AddBallot() instead of just AddBallot().

I used getline() and istringstream to parse the input, it worked better than using >> on cin for looking at each line.

Unfortunately, UVa was down all Sunday, so I couldn't test my project. All the inputs I gave it seemed to give good results, and it worked against the tests I found on Blackboard, but about 1 in the morning UVa messaged me with a Failure. It would have been nice to know that before the turn in deadline.....

Stable Marriage looks interesting, I remember this problem from my Algorithms class with Plaxton. Everybody always cracks up at the word 'man-optimal'. I'm glad we don't have to prove things about SMP, but it's going to be interesting to implement it efficiently.

No comments:

Post a Comment