Due: Friday, July 20 at 6pm (submit through this Google form)

Late Policy: Files are due by 6pm. No late work will be accepted.

Put your answers to these questions in a file named votes.arr.

For this assignment, you will write some functions that lie at the heart of running elections. There are different methods for counting ballots in elections. This assignment explores two. In our elections, everyone indicates their first and second choice candidates. Some elections will count only the first-choice votes, while others do a weighted combination of the first-choice and second-choice votes.

Two tables will provide the data for an election:

• A ballot is a table with (at least) two columns named candidate and party.

• A vote-record is a table with columns named choice1 and choice2. Each row records a single vote for these two candidates.

Starting from this setup, do the following exercises:

• Write a function num-votes-for that takes a choice (a string) and list of choices (strings) and returns the number of times that the given choice is in the list.

• Sometimes, people vote for "write-in" candidates who were not on the ballot. Develop a function called write-ins that consumes a vote-record (Table) and a ballot (Table) and produces a list of choices that received votes but were not candidates on the ballot. The returned list should not have duplicates.

  • In a comment, write out the list of tasks that go into solving this problem

  • For each task, write down the name of the function (either a built-in or one that you wrote) that implements that task

  Note: Testing such a function can be tricky if you can’t predict the order in which the write-in candidates will appear. One way to do this is to write examples in the following style:

  L.member(write-ins(votes-cast, ballot), "Lucia") is true

  L.length(write-ins(votes-cast, ballot)) is 2

  This checks that specific names are in the returned list, without caring what order they are in.

• In order to report the election results, we need a way to associate each candidate with their numeric voting score. Define a data block with one case called result, which has a candidate name and their numeric score. Write a couple of concrete examples of result data.

• Write a function tally-most-votes that consumes a list of candidates and a vote-record and returns a list of result. There should be one result entry for every candidate in the given list. For the numeric score, count each choice1 vote as 1 point; ignore the choice2 votes.

  A sample tally (the expected output) might look like:

  [list: result("Ali", 5), result("Carmen", 3)]

  (indicating that Ali got 5 points and Carmen got 3).

  Edited 7/16, 7:15pm to clarify original wording around choices and ballots.

• Write a function tally-pref-votes that consumes a list of candidates and a vote-record and returns a list of result. This time, the numeric score counts each choice1 vote as 3 points and each choice2 votes as 1 point. See question 4 for an example of what the resulting list of results might look like.

  Edited 7/16, 7:15pm to clarify original wording around choices

• Write a function same-winner that takes a ballot and a vote-record (the two tables described at the start of the assignment) and produces a boolean indicating whether the two different tally functions return the same winner. Compute the tallies over a combination of the candidates on the ballot and the write-in candidates in the vote-record.

  Hint: Pyret has a function called append that concatenates two lists into one list. You can find details in Pyret’s list documentation.

  Added 7/16, 7:20pm

• Write a function sort-results that takes a list of results and sorts it by descending scores. Resolve ties by sorting candidates alphabetically by name. Use Pyret’s built-in sort-by function, which takes three arguments: the list to sort, a function that takes two list items and returns a boolean indicating whether the first should appear before the second, and a function that takes two list items and returns a boolean indicating whether they are the same value.

  Following example added 7/17, 9:30am

  Here’s an example that sorts a list of numbers into ascending order:

  fun num-lt(x :: Number, y :: Number) -> Boolean:

  doc: "determines whether first number is less than second number"

  x < y

  end

  L.sort-by([list: 7, 5, 4, 8, 2, 5, 1], num-lt, equal-always)

  The equal-always is the function version of the == operator that you’ve been using so far. For purposes of this course, just use equal-always as the third argument to sort-by. The interesting part lies in the function that you need to write to determine whether one item should appear before the other in the sorted output.

  For those who have been exploring using lam for anonymous functions, here’s the same example written with lam:

  L.sort-by([list: 7, 5, 4, 8, 2, 5, 1], lam(x, y): x < y end, equal-always)

  sort-by documentation

• Design an example vote-record in which different candidates would win under each of the two counting methods. You don’t have to write programs to compute winners. Just provide a single table named votes-diff-result that would yield (a) a unique winner under each method (no ties) that is (b) different under each method.

In grading, we will look at your examples/tests, code structure, and code presentation. We expect you to follow the list template when appropriate (unless you are using a built-in list iterator like map or filter, which you are welcome to use if you wish).

Remember to include the collaboration statement.

If you want to check whether your file has the same names as our grading scripts will look for, insert the following code at the bottom of your file. This simply looks for the names and types that we stipulated in the assignment. If one of these checks fails, fix your code, not these checks.

Submit your votes.arr file. Make sure it has this exact file name so we can run our grading program on your work.