Program 4: Campaign 2002

CS100J, Fall 2002

Due in Lecture, Thursday, October 17

Goals

In this assignment, you get practice using arrays.

Application

In the Hare voting system, each voter casts votes for one or more of the candidates in order of preference. The winner is the first to achieve a majority when the ballots are counted using the following rules:

· Count the highest preference votes of each voter.

· If some candidate has a majority (more votes than half the number of ballots) declare that candidate the winner.

· Otherwise, determine a candidate not yet eliminated with the fewest highest preference votes and eliminate that candidate from all ballots. If several candidates tie for fewest first preference votes, choose one of them arbitrarily.

· In general, because a ballot need not list all candidates, it is possible that all of the choices listed on a given ballot get eliminated. In this case, the ballot is ignored.

· Repeat the above until there is a winner.

You are asked to write a program that counts votes and declares the winner.

Requirements

The candidates are known by the initial upper-case letters of the alphabet, i.e., A, B, C, etc. Thus, there are 26 possible candidates.

The input consists of between 1 and 100 ballots followed by the word "end" in lower case. Each ballot is a word listing one or more candidates in order of preference, i.e., the first letter of the ballot is the most preferred candidate and the last letter is the least preferred candidate.

For a small election with 5 candidates and 10 voters, in which every voter votes for every candidate (which need not be the case) the input might be:

ABCDE BCDEA CEDBA DECBA EBCDA

ABCDE BCDEA CDBAE DCAEB ABCDE

end

The output of your program should be the winner of the election. For the above data, the output might be:

Candidate B is the winner.

How was B determined to be the winner? Let's figure it out by hand. Initially, E has only 1 highest preference vote and all others have at least 2, so E is eliminated leaving the ballots looking like:

ABCD BCDA CDBA DCBA BCDA

ABCD BCDA CDBA DCAB ABCD

Now A and B each have 3 votes and C and D each have 2. Eliminate either C or D --- say C. The ballots look like:

ABD BDA DBA DBA BDA

ABD BDA DBA DAB ABD

A and B each have 3 votes and D has 4. Eliminate either A or B --- say A. The ballots look like:

BD BD DB DB BD

B has 6 votes, a majority, so B is declared the winner. Notice that if B had been eliminated at the previous step, then the ballots would be

AD DA DA DA DA

AD DA DA DA AD

in which case D would be declared the winner. When there is a tie for the candidate to eliminate, make an arbitrary choice. As can be seen from the above, such a choice may affect the outcome of the election.

You may assume that every ballot is legal --- that is, it contains one or more upper-case letters of the alphabet without repetition.

Hints and Suggestions

Possibly relevant information and suggestions:

· Although the final program produces only one line of output, you will probably find it useful to solve this problem in parts, and produce temporary diagnostic output during development. It is up to you to decide what parts make sense.

· Method readString() of TokenReader reads the next word in the input, i.e., it stops at a blank.

· If s1 and s2 are two Strings, you can test whether they have the same sequence of characters by

if( s1.equals(s2) ) . . .

Don't use the code

if( s1==s2 ) . . .

which tests whether s1 and s2 refer to the same object. Two different String objects may contain the same sequence of characters!

· If s is a String, then s.toCharArray() is an array of characters, i.e., an object of type char[].

· Constant values of type char are written in Java using single quotes, i.e., 'a', 'b', 'c', etc.

· If s is a String, then s.charAt(i) is the char at position i, where i must be in the range 0 up through one less than the length of s. For example, the value of the expression

"abcdefg".charAt(3)=='d'

is true.

· If s is a String, then the value of the expression

s.substring(offset,endIndex)

is the substring of s consisting of the characters with indices offset through endIndex-1 inclusive. For example, the value of

"abcdefg".substring(3,6)

is "def". One way to visualize this is to think of offset and endIndex as specifying positions between characters:

0 1 2 3 4 5 6 7

|a|b|c|d|e|f|g|

· You can delete a character c in a string variable v by replacing the contents of v with a new string computed by concatenating the substring of v before c with the substring of v after c.

· If c1 and c2 are char values, then the value of expression c1-c2 is the distance between them. For example, the value of expression 'C'-'A' is the int value 2.

· For debugging and testing purposes, you may find it convenient to temporarily hard wire input into the program rather than providing input data. Just comment out the input code, and replace it with direct assignment statements. This will be particularly helpful if you use the Debugger, which doesn’t work well with input.

· You can type the input data into a file and save it. Then, when you run your program, you can Copy the input from the saved file and Paste it into the console (input/output) window.

What To Hand In

Run your program on the following data:

ABCDE BCDEA CDEAB DEBAC EBACD

ABCDE B EAB DEBAC AEBCD

end

and any other data you think is appropriate to show the correctness of your program. Turn in a listing of the program and its output on all test data.

Administrivia ¾ Please Read!

Programs are due at the end of lecture on the day assigned. No late assignments will be accepted. Programs will not be accepted in Carpenter on the day they are due, but you may hand in your program to a consultant in Carpenter until the close of business the day before the program is due. You must give the program to a consultant personally. Do not just leave it on a desk or table.

Program listings must be printed. Output must be printed and be exactly as produced by the program handed in. All printouts must be separate pages, without perforated edges, and stapled together in order, with a copy of a completed cover sheet. The first comment in the program must contain your (and your partner's) name, Cornell ID#, section's day & time & instructor, and the assignment number. These cannot be written in by hand. You (both) must sign the first page of the program.

Be sure to use good style. Since we have not specified how you are to solve this problem, you are likely to do it your own way. Thus, it is crucial that you write clear code so that the graders can understand it.