7
\$\begingroup\$

I implemented an algorithm to solve a constraint satisfaction problem. It is a non-trivial one, so I do not intend to take your time with its details. I am mainly looking for good code suggestions rather than the specific details on the logic.

How could I made the code better? Any comments/recommendations are appreciated.

package com.muratdozen.playground.spotify;

import com.muratdozen.playground.util.io.FastReader;

import java.io.PrintWriter;
import java.util.*;

/**
 * Spotify Challenge, Cat vs. Dog
 *
 * @author Murat Derya Ozen
 * @since: 10/2/13 10:47 AM
 * @see <a href="https://www.spotify.com/us/jobs/tech/catvsdog/">
 *      https://www.spotify.com/us/jobs/tech/catvsdog/</a>
 */
public class CatVsDog {

    public static class Vote {
        public final boolean catLover;
        public final int keep;
        public final int throwout;

        public Vote(final boolean catLover, final int keep, final int throwout) {
            this.catLover = catLover;
            this.keep = keep;
            this.throwout = throwout;
        }

        public boolean isConflicting(Vote vote) {
            return this.catLover != vote.catLover
                    && (this.keep == vote.throwout || this.throwout == vote.keep);
        }
    }

    // some kind of a bipartite graph matching
    private static final int maxMatchings(final Map<Vote,Set<Vote>> conflictingVotes,
                                          final Map<Vote,Set<Vote>> reverseConflictingVotes) {

        // assign each cat lover vote to a conflicting dog lover vote
        // we need to find out the maximum number of such assignments (matchings)
        // we assign each cat lover vote to a conflicting vote by starting from
        // the cat lover vote that has the least number of options (conflicting votes)

        // list of cat lover votes sorted by the number of options each vote has
        final List<Vote> catLoversVotes = new ArrayList<Vote>(conflictingVotes.keySet());
        Collections.sort(catLoversVotes, new Comparator<Vote>() {
            @Override
            public int compare(Vote vote, Vote vote2) {
                final Set<Vote> set1 = conflictingVotes.get(vote);
                final Set<Vote> set2 = conflictingVotes.get(vote2);
                return Integer.valueOf(set1.size()).compareTo(set2.size());
            }
        });

        int result = 0;

        final int len = catLoversVotes.size();
        // assign each cat lover vote
        for (int i = 0; i < len; ++i) {
            final Vote vote = catLoversVotes.get(i);
            // when choosing which conflicting dog lover vote to assign,
            // choose the one that affects the least amount of remaining cat lover voters
            final Set<Vote> choices = conflictingVotes.get(vote);
            if (choices == null || choices.isEmpty())
                continue;
            Vote minAffectingVote = null; /* dog lover vote that is to be assigned */
            int min = Integer.MAX_VALUE;
            for (Vote choice : choices) {
                final Set<Vote> set = reverseConflictingVotes.get(choice);
                if (set == null || set.isEmpty())
                    continue;
                final int numAffecting = set.size();
                if (numAffecting < min) {
                    min = numAffecting;
                    minAffectingVote = choice;
                }
            }
            if (minAffectingVote != null) {
                reverseConflictingVotes.remove(minAffectingVote);
                ++result;
            }
        }

        return result;
    }

    private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {
        Set<Vote> votes = map.get(key);
        if (votes == null) {
            votes = new HashSet<Vote>();
            votes.add(vote);
            map.put(key, votes);
        } else {
            votes.add(vote);
        }
    }

    private static final int solveTestCase(final FastReader fastReader) {

        // indexes of cat lover votes and dog lover votes
        final Set<Vote> catLovers = new HashSet<Vote>();
        final Map<Integer, Set<Vote>> dogLoversIndexedByKeep = new HashMap<Integer, Set<Vote>>();
        final Map<Integer, Set<Vote>> dogLoversIndexedByThrowout = new HashMap<Integer, Set<Vote>>();

        // parse and collect data from input
        final int c = fastReader.nextInt();
        final int d = fastReader.nextInt();
        final int v = fastReader.nextInt();

        if (v == 1) return 1;

        // fill in catLovers, dogLoversIndexedByKeep and dogLoversIndexedByThrowout
        for (int j = 0; j < v; ++j) {
            final String keepStr = fastReader.next();
            final String throwoutStr = fastReader.next();
            final int keep = Character.getNumericValue(keepStr.charAt(1));
            final int throwout = Character.getNumericValue(throwoutStr.charAt(1));
            final boolean catLover = keepStr.charAt(0) == 'C';
            final Vote vote = new Vote(catLover, keep, throwout);
            if (catLover) {
                catLovers.add(vote);
            } else {
                addToMap(dogLoversIndexedByKeep, keep, vote);
                addToMap(dogLoversIndexedByThrowout, throwout, vote);
            }
        }

        // build a map of conflicting votes
        // conflictingVotes has cat lovers' votes as keys. each key maps to a set of
        // dog lovers' votes that conflict with key.
        // similarly, reverseConflictingVotes contains dogLovers' votes mapped to a set
        // of conflicting votes.
        final Map<Vote, Set<Vote>> conflictingVotes = new HashMap<Vote, Set<Vote>>(catLovers.size());
        final Map<Vote, Set<Vote>> reverseConflictingVotes = new HashMap<Vote, Set<Vote>>();
        for (Vote catLover : catLovers) {
            final Set<Vote> conflicts = new HashSet<Vote>();
            if (dogLoversIndexedByKeep.containsKey(catLover.throwout)) {
                conflicts.addAll(dogLoversIndexedByKeep.get(catLover.throwout));
            }
            if (dogLoversIndexedByThrowout.containsKey(catLover.keep)) {
                conflicts.addAll(dogLoversIndexedByThrowout.get(catLover.keep));
            }
            conflictingVotes.put(catLover, conflicts);
            for (Vote dogLoverVote : conflicts) {
                addToMap(reverseConflictingVotes, dogLoverVote, catLover);
            }
        }

        // match as many conflicting votes as possible
        // and return number of votes - number of matches
        return v - maxMatchings(conflictingVotes, reverseConflictingVotes);
    }

    public static final void main(String[] args) {
        final FastReader fastReader = FastReader.from(System.in);
        final int numTestCases = fastReader.nextInt();

        final PrintWriter writer = new PrintWriter(System.out);
        final String LINE_SEPARATOR = System.getProperty("line.separator");

        for (int i = 0; i < numTestCases; ++i) {
            final int result = solveTestCase(fastReader);
            writer.write(Integer.toString(result));
            writer.write(LINE_SEPARATOR);
        }

        writer.flush();
        writer.close();
    }
}

The code is hosted on GitHub if anyone's interested. I will commit changes if necessary.

\$\endgroup\$

5 Answers 5

6
\$\begingroup\$

Your original:

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {
    Set<Vote> votes = map.get(key);
    if (votes == null) {
        votes = new HashSet<Vote>();
        votes.add(vote);
        map.put(key, votes);
    } else {
        votes.add(vote);
    }
}

Alternative:

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {

    if (null == map.get(key)) {           
        map.put(key, new HashSet<Vote>());
    } 

    map.get(key).add(vote);        
}

Edit to my preferred syntax:

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {
   if (!map.containsKey(key)) {           
     map.put(key, new HashSet<Vote>());
   } 
   map.get(key).add(vote);        
}
\$\endgroup\$
3
  • \$\begingroup\$ Good point and thanks for the answer. However, I wanted to avoid 2 map.get operations for performance reasons. \$\endgroup\$
    – Murat
    Oct 6, 2013 at 18:03
  • \$\begingroup\$ @Murat Then you can still move votes.add(vote); out of the branches (save 2 lines and make clear that vote gets always added). \$\endgroup\$
    – maaartinus
    Jun 15, 2014 at 20:37
  • \$\begingroup\$ @Murat I know this is a very old topic, but I think your performance concerns were unfounded. Map.get appears to be on average an O(1) operation. See: stackoverflow.com/q/1055243/3230218 \$\endgroup\$ Nov 24, 2016 at 12:27
5
\$\begingroup\$

I have not read your code in detail, but a lot of extra complexity comes from handling Map<Vote, Set<Vote>>. I'm a big fan of guava's Multimap<K, V>.

\$\endgroup\$
1
  • \$\begingroup\$ +1 for that. I like Guava and I include it in most of my projects. For this piece of code, however, I wasn't able to use 3rd party libraries. \$\endgroup\$
    – Murat
    Oct 5, 2013 at 22:12
3
\$\begingroup\$

Your methods are enormous. I would start by breaking them down into small segments that only do a single thing.

You also have lots of comments around. This is needed because your methods are so big. In my opinion, ideally, you do not need inline comments because the methods should explain themselves, often by their name alone.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Welcome to Code Review! Your answer came up in the "First Posts" queue. You passed the test! \$\endgroup\$ Jun 13, 2014 at 20:53
1
\$\begingroup\$

Minor comments mostly:

  • Javadoc is missing. For instance, what is the expected input format of the program?
  • Missing {} after a if statement is not recommended
  • I'd place LINE_SEPARATOR as static, but it's just a matter of taste
  • The use of static methods make it impossible to mock up in tests
  • You can shorten a bit addToMap

.

private static final <T> void addToMap(final Map<T,Set<Vote>> map, final T key, final Vote vote) {
    Set<Vote> votes = map.get(key);
    if (votes == null) {
        votes = new HashSet<Vote>();
        map.put(key, votes);
    }
    votes.add(vote);
}
\$\endgroup\$
1
\$\begingroup\$
  • You create an instance of comparator at each call of maxMatchings, ie one per line. You need only one instance for the full program, as a field.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.