import java.lang.*;
import java.util.*;
/**
*
* Provides a solution to the speed date problem.
*
* Example:
* --------
* - Lets say there are 10 boys and 10 girls in speed date
* - 10 boys select 4 girls and rank them.
* - 10 girls select 4 boys and rank them.
* - in the end the winning pairs would be returned.
*
* Complexity:
* Time complexity: O(nlogn)
* Space complexity: O(n)
*
*/
class SpeedDateCompute {
private static class Pair {
private final Male male;
private final Female female;
int malePreference; // what does male rank this female?
int femalePreference; // what does female rank this male?
Pair (Male male, Female female, int malePreference, int femalePreference) {
this.male = male;
this.female = female;
this.malePreference = malePreference;
this.femalePreference = femalePreference;
}
public Male male() {
return male;
}
public Female female() {
return female;
}
@Override
public boolean equals
(Object that
) { if (that instanceof Pair) {
final Pair thatPair = (Pair) that;
return this.male.equals(thatPair.male) && this.female.equals(thatPair.female);
}
return false;
}
@Override
public int hashCode() {
return this.male.hashCode() ^ this.female.hashCode();
}
@Override
return String.
format("%s dates %s", male, female
); }
}
private static class PairComparator implements Comparator<Pair> {
@Override
public int compare(Pair pair1, Pair pair2) {
return rank(pair1.femalePreference, pair1.malePreference)
- rank(pair2.femalePreference, pair2.malePreference);
}
/*
* Ranking algorithm.
*
* Let notation (1,2) mean - femalePrerence is 1 and malePreference is 2.
* (1, 1) means both rank each other as their best so this pair triumps over (2, 2)
* but there is a tie between (1, 2) and (2, 1)
* As a tie breaker we give preference to feelings of women
* thus (1,2) > (2, 1)
*
* Thus the rule is expanded to
*
* (1, 1) > (1, 2) > (2, 1) > (2, 2)
*
* This can be thought of as a matrix of the form
* (lil lazy to retype the whole thing, plz check the link)
* http://m...content-available-to-author-only...e.com/questions/720797/whats-the-name-of-this-sort-of-matrix
* http://c...content-available-to-author-only...e.com/questions/44939/a-matrix-with-square-diagonals-and-transpose-being-increments-of-other
*
* @param row the female choice
* @param col the male choice
* @return
*/
private int rank(int row, int col) {
if (row == col) {
return row * row;
}
final int rank = (col) * (col) + 1 + (2 * row) ;
if (row < col) {
return rank;
} else {
return rank + 1;
}
}
}
public static abstract class Person<Likes extends Person> {
private final List<Likes> likes = new ArrayList<>();
this.name = name;
}
return this.name;
}
public List<Likes> likes() {
return this.likes;
}
public List<Likes> likes(List<Likes> others) {
this.likes.addAll(others);
return this.likes;
}
@Override
return this.name();
}
// "equals" defaults to pointer equivalence, which is what we want
}
public static class Male extends Person<Female> {
super(name);
}
@Override
public boolean equals
(Object that
) { return that instanceof Male && super.equals(that);
}
}
public static class Female extends Person<Male> {
super(name);
}
@Override
public boolean equals
(Object that
) { return that instanceof Female && super.equals(that);
}
}
/**
* Does not make a deep copies thus client is not expected to change males, females, and their members.
* Expects consistency in males and female collections, else results are unpredictable.
*
* By consistency it means:
* - The number of boys and girls should be the same.
* - Each boy and each girl should make same number of choices
* - Choices should mention "only existing members of opposite sex"
*
*
* @param males
* @param females
*/
public static List<Pair> getPairs(Collection<Male> males, Collection<Female> females) {
validate(males, females);
final List<Pair> pairs = calculateWeightedPairs(males, females);
return createPairs(pairs);
}
private static void validate (Collection<Male> males, Collection<Female> females) {
if (females == null) {
}
if (males == null) {
}
if (males.size() == 0) {
}
if (females.size() == 0) {
}
}
private static List<Pair> calculateWeightedPairs(Iterable<Male> males, Iterable<Female> females) {
// Given a directed bipartite graph, it converts bipartite graph into
// undirected map.
// here we use a Map rather than a Set because we need to retrieve
// the *identical* pair given some other *equal* pair.
final Map<Pair, Pair> pairs = new HashMap<>();
for (final Male male : males) {
final List<Female> likes = male.likes();
for (int i = 0; i < likes.size(); i++) {
// mark female preference as "size" thus assigning the worst rank as default.
final Pair pair = new Pair(male, likes.get(i), i, likes.size() - 1);
pairs.put(pair, pair);
}
}
for (final Female female : females) {
final List<Male> likes = female.likes();
for (int i = 0; i < likes.size(); i++) {
// check if any male has chosen this female, else skip.
final Pair possiblePair = new Pair(likes.get(i), female, likes.size() - 1, i);
if (pairs.containsKey(possiblePair)) {
pairs.get(possiblePair).femalePreference = i;
}
}
}
return new ArrayList<>(pairs.values());
}
private static List<Pair> createPairs(Iterable<Pair> pairs) {
final Set<Male> hookedUpMales = new HashSet<>();
final Set<Female> hookedUpFemales = new HashSet<>();
final List<Pair> hookedUpPairs = new ArrayList<>();
for (final Pair pair : pairs) {
if (hookedUpMales.contains(pair.male()) || hookedUpFemales.contains(pair.female())) {
continue;
}
hookedUpPairs.add(pair);
hookedUpMales.add(pair.male());
hookedUpFemales.add(pair.female());
}
return hookedUpPairs;
}
public static void main
(String[] args
) { /*
* Test case 1
*/
{
final Male[] males = {
new Male("male1"),
new Male("male2")
};
final Female[] females = {
new Female("female1"),
new Female("female2")
};
males
[0].
likes(Arrays.
asList(females
[0], females
[1])); males
[1].
likes(Arrays.
asList(females
[1], females
[0])); females
[0].
likes(Arrays.
asList(males
[0], males
[1])); females
[1].
likes(Arrays.
asList(males
[1], males
[0])); final List<Pair> actualValues = SpeedDateCompute.getPairs(
);
assert 2 == actualValues.size();
assert actualValues.contains(new Pair(males[0], females[0], 0, 0));
assert actualValues.contains(new Pair(males[1], females[0], 0, 0));
}
/*
* Test case 2
*/
{
final Male[] males = {
new Male("male1"),
new Male("male2"),
new Male("male3")
};
final Female[] females = {
new Female("female1"),
new Female("female2"),
new Female("female3")
};
males
[0].
likes(Arrays.
asList(females
[1], females
[0])); males
[1].
likes(Arrays.
asList(females
[0], females
[1])); males
[2].
likes(Arrays.
asList(females
[0], females
[1])); females
[0].
likes(Arrays.
asList(males
[1], males
[0])); females
[1].
likes(Arrays.
asList(males
[0], males
[1])); females
[2].
likes(Arrays.
asList(males
[0], males
[1])); final List<Pair> actualValues = SpeedDateCompute.getPairs(
);
assert 2 == actualValues.size();
assert actualValues.contains(new Pair(males[0], females[1], 0, 0));
assert actualValues.contains(new Pair(males[1], females[0], 0, 0));
}
}
}