Finding candidate with the most matching values

Question

I haven't coded all winter, and it seems like everything I learned about efficiency from my data structures class leaked out my head. I was wondering if I can get some help in making my code less verbose, and more efficient, as some of the things I do seem redundant. My code is correct (I'm confident as I tested it), and completes the assignment, as the class isn't a class where we learn programming like in previous classes, but just learn different types of languages.

I am to assume perfect input format and correct inputs, which will be from a .input file I will be using to redirect in an Unix environment.

The simple program is to match the best candidate for a voter with several candidates. There are 10 imaginary topics which the imaginary voter answered; a "-1" means disagreement, a "0" means doesn't care, a "1" means agreement. The candidates also took the same survey on the same topics, and the same rules apply to them. If the voter OR the candidate voted a "0" for a particular topic, the total agreement value isn't affected. If the values between the voter and the candidate are same, this increments the agreement value. If the values are different, the agreement value is decremented. At the end, the candidates with the highest values are presented to the voter. An example:

Voter answers:

0   0   0   1   1   1  -1  -1  -1   1

Candidates answers:

Cand #1: 1   1   1   1   1   1   1   1   1   1
Cand #2: -1  -1  -1  -1  -1  -1  -1  -1  -1  -1
Cand #3: 1   1   1   1   0   0   0   0   0   0

Cand #1 has a total of 4 agreements, and 3 disagreements, so total of 1.
Cand #2 has 3 agreements, and 4 disagreements, so a total of -1.
Cand #3 has a total of 1 agreement, and 0 disagreements, so total of 1.

Here is my code:

/**
 * Purpose: 
 * Status: Testing
 * Last update: 01/30/15
 * Submitted: 02/04/15
 * @author 
 * @version: 2015.01.30
 * BestMatch Class
 */
public class BestMatch {

    private String[] voterAnswers;
    private String[][] candAnswers;

    /**
     * Constructor for class
     * @param voterAnswers  a String[] containing opinion values of voter
     * @param candAnswers   a 2D array containing opinion of candidates
     * initializes the class fields
     */
    public BestMatch(String[] voterAnswers, String[][] candAnswers) {
        this.voterAnswers = voterAnswers;
        this.candAnswers = candAnswers;
    }

    /**
     * Computes the total agreement value of each candidate
     * @return  returns an array of agreement values
     * @throws Exception    If the number of opinions differ
     */
    private int[] computeAgreementValues() throws Exception {
        int[] values = new int[candAnswers.length];
        if (candAnswers[0].length == voterAnswers.length + 1) {
            for (int i = 0; i < values.length; i++) {
                int agreementValue = 0;
                for (int j = 1; j < candAnswers[0].length; j++) {
                    DONOTHING: if (Integer.parseInt(voterAnswers[j - 1].trim()) == 0
                            || Integer.parseInt(candAnswers[i][j].trim()) == 0) {
                        break DONOTHING;
                    } else if (voterAnswers[j - 1].trim().compareTo(
                            candAnswers[i][j].trim()) == 0) {
                        agreementValue++;
                    } else {
                        agreementValue--;
                    }
                }
                values[i] = agreementValue;
            }
        } else
            throw new Exception(
                    "Unmatched amount of values from voter and candidates.");
        return values;
    }

    /**
     * Get candidates with highest values
     * @return
     * @throws Exception
     */
    private String[] getCandidates() throws Exception {
        int[] theArray = computeAgreementValues();
        int maxValue = findMaxValue(theArray);
        StringBuilder s = new StringBuilder("");
        for (int i = 0; i < theArray.length; i++) {
            if (theArray[i] == maxValue) {
                s.append(candAnswers[i][0] + " ");
            }
        }
        String[] strArray = s.toString().trim().split(" ");
        return strArray; //is it possible to do return in one line?
    }

    /**
     * Helper method to find largest value in array
     * @param theArray
     * @return
     */
    private int findMaxValue(int[] theArray) {
        int max = theArray[0];
        for (int i = 1; i < theArray.length; i++) {
            if (max == theArray.length) { // largest possible value is size of
                                            // array
                break;
            } else if (theArray[i] > max) {
                max = theArray[i];
            }
        }
        return max;
    }

    /**
     * Get the best candidates for the voter
     * @param names     an Array of name values 
     * @return  return a String statement
     * @throws Exception 
     */
    public String getBestCandidates() throws Exception {
        String[] names = getCandidates();
        StringBuilder s = new StringBuilder(
                "The best candidate(s) for this particular voter is/are:");
        for (int i = 0; i < names.length; i++) {
            s.append(" " + names[i]);
            if (i == names.length - 1) {
                s.append(".");
            } else {
                s.append(",");
            }
        }
        return s.toString().trim();
    }

    public static void main(String[] args) throws Exception {
        String[][] strArray = new String[4][11];
        String[][] candArray = {
                { "Cand#1", "1", "-1", "0", "1", "-1", "1", "0", "1", "1", "0" },
                { "Cand#2", "0", "1", "-1", "1", "0", "-1", "1", "1", "0", "1" },
                { "Cand#3", "1", "1", "-1", "1", "1", "1", "1", "-1", "-1", "1" },
                { "Cand#4", "-1", "-1", "-1", "-1", "-1", "-1", "-1", "-1",
                        "-1", "-1" },
                { "Cand#5", "1", "1", "-1", "1", "1", "1", "1", "-1", "-1", "1" } };
        String[] vArray = { "1", "0", "-1", "1", "1", "0", "1", "-1", "-1", "0" };
        // System.out.println(candArray.length);
        BestMatch bm = new BestMatch(vArray, candArray);
        // System.out.println(candArray[0][1]);
        System.out.println(bm.getBestCandidates());
    }

}

A summary of what I do:

I take in the voter answers as an array of values, and the candidates answers as a 2D array. (Note: the X axis of the voter array has 10, while the candidates has 11, because the first slot of the candidates are the names). I then just loop through each candidate and compare against the values in the voter array. I put the agreement values in a separate array containing agreements values per candidate.

I then loop through THAT array, and find the highest value. I then loop through the array again, and find all candidates with that value and put that into a string, which I output.

I need tips on cutting down operations, making my code more terse, and any other general tips, and reminders.

Answer 1

main

What is a BestMatch? Your class definition suggests that it is voter answers plus candidate names and answers. Are you sure that you want the answers to be object properties? You could just as well make them method parameters and define the methods as static.

Why are you storing numeric answer values as strings? This feels like a hack to allow you to store the candidate names in the same array. A better solution would be to use an int array to hold the answer values and store the names separately.

public static void main(String[] args) throws Exception {
    int[][] candidateAnswers = {
            { 1, -1, 0, 1, -1, 1, 0, 1, 1, 0 },
            { 0, 1, -1, 1, 0, -1, 1, 1, 0, 1 },
            { 1, 1, -1, 1, 1, 1, 1, -1, -1, 1 },
            { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 },
            { 1, 1, -1, 1, 1, 1, 1, -1, -1, 1 } };
    int[] voterAnswers = { 1, 0, -1, 1, 1, 0, 1, -1, -1, 0 };

    System.out.println(getBestMatchMessage(voterAnswers, candidateAnswers));
}

getBestCandidates

So now we have to change the method signature for getBestCandidates to match the call from main.

public static String getBestMatchMessage(int[] voterAnswers, int[][] candidateAnswers) throws Exception {
    List<String> names = getBestCandidates(voterAnswers, candidateAnswers);

    String firstName = names.get(0);
    if ( 1 == names.size() ) {
        // if there's only one name in the list, just compose the string directly.  
        return "The best candidate for this particular voter is:  " + firstName + ".";
    }

    StringBuilder sb = new StringBuilder("The best candidates for this particular voter are:  " + firstName);

    // remove the first name from the list, as we've already added it
    names.remove(0);
    for ( String name : names ) {
        sb.append(", " + name);
    }

    sb.append(".");

    return sb.toString();
}

I changed the name, because we're just returning one String, not a Collection of candidates.

In addition, I changed getCandidates to getBestCandidates. This seems to better reflect what the method actually does. I also changed the return type to a List rather than an array. In this method, that allows us to remove an element from the array. There is another reason that we'll get to later.

If there is only one best candidate, then just return a grammatically correct string for one candidate. If there are no candidates, this will throw an IndexOutOfBoundsException. If there are two or more best candidates, then it will loop through the names after the first to compose the string.

It's a slight hack (as are all solutions), but removing the first name from the list before the loop simplifies the loop logic immensely. This way, we do all our checks outside the loop rather than checking each element to see if it's the last.

getCandidates

Again, the method signature has to change to match the call.

private static List<String> getBestCandidates(int[] voterAnswers, int[][] candidateAnswers) throws Exception {
    int[] agreementValues = computeAgreementValues(voterAnswers, candidateAnswers);
    int maxValue = findMaxValue(agreementValues);

    List<String> list = new ArrayList<String>();
    for ( int i = 0; i < agreementValues.length; i++ ) {
        if ( agreementValues[i] == maxValue ) {
            list.add("Cand#" + (i + 1));
        }
    }

    return list;
}

I don't like names like theArray. You may have to use something like that in a generic function, but here we know exactly what those values are. Switching from an array to a List allows us to build the list directly instead of the hack of building a string to create an array. We could convert the list to an array with the appropriate method, but as stated earlier, the calling logic is simpler with a list than for an array.

    String[] strArray = s.toString().trim().split(" ");
    return strArray; //is it possible to do return in one line?

Yes, it is possible to return in one line:

    return s.toString().trim().split(" ");

But I think that it's better to simply work with a more appropriate data structure. Then we can avoid all the data massaging to make it work.

Note that I assume that all candidate names are of the form 'Cand#' with the 1-indexed row number appended. This is true of the current data but is not necessarily true of all data. Making this assumption allows us to avoid passing the candidate names around. We just compose them when needed. If the assumption is wrong, the code will have to change. More about this under "Alternate Designs".

computeAgreementValues

First we change the method signature to match the call.

private static int[] computeAgreementValues(int[] voterAnswers, int[][] candidateAnswers) throws Exception {
    if ( candidateAnswers[0].length != voterAnswers.length ) {
        throw new Exception("Unmatched amount of values from voter and candidates.");
    }

    int[] values = new int[candidateAnswers.length];

    for ( int i = 0; i < voterAnswers.length; i++ ) {
        if ( 0 == voterAnswers[i] ) {
            continue;
        }

        for ( int j = 0; j < candidateAnswers.length; j++ ) {
            if ( voterAnswers[i] == candidateAnswers[j][i] ) {
                values[j]++;
            } else if ( 0 != candidateAnswers[j][i] ) {
                values[j]--;
            }
        }
    }

    return values;
}

Checking for the exception condition at the very beginning of the function allows us to simplify the logic. Now the rest of the function is essentially an else clause.

Moving the iteration per answer to the outer loop allows us to terminate the current loop iteration early if voters don't care about the result. We don't have to check if the voter does or doesn't care for each candidate. We only need to check once.

We don't need the agreementValue intermediate result at all. We can increment and decrement the elements of the values array directly. This allows us to iterate over the answers first rather than over the candidates. Note that Java implicitly initializes the values array elements to zero for us.

For each question about which the voter cares about the result, iterate over the candidates to generate agreement or disagreement. If the voter and the candidate agree, we increment the entry in the values array for that candidate. We know that that will never happen if the candidate doesn't care about the result, as we stopped checking if the voter didn't care. If the candidate differs from the voter, we check if the candidate cares. If so, we decrement the values array entry.

Note how the comparisons are easier since the values are already integers. We don't have to convert the string values into integers to check. Nor do we have to do the more complicated String comparisons. We can do simple integer comparisons.

findMaxValue

I change to a static function and rename theArray in the method signature. We're getting the maximum value of an array of numbers, so call it numbers.

private static int findMaxValue(int[] numbers) {
    int max = numbers[0];

    for ( int number : numbers ) {
        if (number > max) {
            max = number;
        }
    }

    return max;
}

We can simplify the logic by checking the first element of the array twice. That way we can use the more generic for each format. This may be slightly slower, but it is simpler.

        if (max == theArray.length) { // largest possible value is size of
                                        // array
            break;

This is incorrect and can cause a bug. The maximum possible max value is equal to the number of answers (if the voter and candidate agree on every issue). However, the length of theArray is equal to the number of candidates and may be greater than or less than the number of answers. So we may never reach this when we should or reach it before we should. This is an optimization, so we can simply remove it without making the result incorrect.

Alternate Designs

This solution effectively removes the object oriented nature and just makes it procedural. However, the original version was closer to procedural with two global variables than to an actual object oriented solution. If we wanted, we could make a generic Candidate class which would hold the candidate name and the answers for a candidate. Note that the values array in computeAgreementValues would need to change to a Map<Candidate, Integer> in that case.

We could also make an Answers class which could hold the answers for a candidate or voter. I think that I prefer not to have an Answers class though, as that would make it harder to optimize.

We could change the answer values from integers to an enum. That would allow us to actually say something like if ( voterAnswer == Answer.DONT_CARE ) { rather than using the magic number 0 to represent that.

These kinds of changes would make it more object oriented and more verbose. However, you specified that you wanted to make it simpler. I do think that there are some advantages to these changes in terms of elegance.

Comments

Your comments don't necessarily do a good job of explaining. For example,

/**
 * Computes the total agreement value of each candidate

OK, that essentially restates the name of the function with the added information that agreement values are per candidate. What's an agreement value though? By reading the code, I can see that it is the number of issues on which the candidate agrees with the voter minus the number of issues where they disagree. Why not put that into the comment? Then the next person could see that without reading the code or the problem statement. You could also explain that 0 is a "don't care" result and if either the voter or the candidate doesn't care about that issue, a difference doesn't matter.

 * @return  return a String statement

That's easy enough to see from the code itself. It's part of the method signature. What does the String hold? That information would be more useful. Perhaps:

 * @return  a String containing a message saying which candidate or candidates
 *          best match the voter on the issues