• Choose a category
• All
• Classic-Fiction

By Root 1387 0

convicted felons, are ineligible to vote, but occasionally attempt to register and vote anyway. Using your newfound algorithm skills, you could write a simple voter registration auditing function that checks the voter rolls for certain anomalies.

The Voter Registration Audit Problem Statement

The voter registration audit function should audit the voters’ information. Assume that voter registrations are stored by district in a map that maps district names to a list of voters. Your audit function should take this map and a list of convicted felons as parameters, and should remove all convicted felons from the lists of voters. Additionally, the function should find all voters who are registered in more than one district and should remove those names from all districts. Voters with duplicate registrations must have all their registrations removed, and therefore become ineligible to vote. For simplicity, assume that the list of voters is simply a list of string names. A real application would obviously require more data, such as address and party affiliation.

The auditVoterRolls Function

The auditVoterRolls() function works in three steps:

1. Find all the duplicate names in all the registration lists by making a call to getDuplicates().

2. Combine the set of duplicates and the list of convicted felons.

3. Remove from every voter list all the names found in the combined set of duplicates and convicted felons. The approach taken here is to use for_each() to process each list in the map, applying a lambda expression to remove the offending names from each list.

The following typedefs are used in the code:

typedef map> VotersMap;

typedef pair> DistrictPair;

Code snippet from AuditVoterRolls\AuditVoterRolls.cpp

Here’s the implementation of auditVoterRolls():

// Expects a map of string/list pairs keyed on district names

// and containing lists of all the registered voters in those districts.

// Removes from each list any name on the convictedFelons list and

// any name that is found on any other list.

void auditVoterRolls(VotersMap& votersByDistrict,

const list& convictedFelons)

{

// get all the duplicate names

set toRemove = getDuplicates(votersByDistrict);

// combine the duplicates and convicted felons -- we want

// to remove names on both lists from all voter rolls

toRemove.insert(convictedFelons.cbegin(), convictedFelons.cend());

// Now remove all the names we need to remove using

// nested lambda expressions and the remove-erase-idiom

for_each(votersByDistrict.begin(), votersByDistrict.end(),

[&toRemove](DistrictPair& district) {

auto it = remove_if(district.second.begin(),

district.second.end(), [&](const string& name) {

return (toRemove.count(name) > 0);

});

district.second.erase(it, district.second.end());

});

}

Code snippet from AuditVoterRolls\AuditVoterRolls.cpp

The getDuplicates Function

The getDuplicates() function must find any name that is on more than one voter registration list. There are several different approaches one could use to solve this problem. To demonstrate the adjacent_find() algorithm, this implementation combines the lists from each district into one big list and sorts it. At that point, any duplicate names between the different lists will be next to each other in the big list. Now getDuplicates() can use the adjacent_find() algorithm on the big, sorted, list to find all consecutive duplicates and store them in a set called duplicates. Here is the implementation:

// getDuplicates()

//

// Returns a set of all names that appear in more than one list in

// the map.

set getDuplicates(const VotersMap& votersByDistrict)

{

// Collect all the names from all the lists into one big list

list allNames;

for (auto& district : votersByDistrict) {

allNames.insert(allNames.end(), district.second.begin(),

district.second.end());

}

// sort the list -- use the list version, not the general algorithm,

// because the list version is faster

allNames.sort();

// Now it's