fork(1) download
copy 
  1. import java.lang.*;
  2. import java.util.*;
  3.  
  4. /**
  5.  * 
  6.  * Provides a solution to the speed date problem.
  7.  * 
  8.  * Example:
  9.  * --------
  10.  * - Lets say there are 10 boys and 10 girls in speed date
  11.  * - 10 boys  select 4 girls and rank them.
  12.  * - 10 girls select 4 boys  and rank them.
  13.  * - in the end the winning pairs would be returned.
  14.  * 
  15.  * Complexity:
  16.  * Time complexity: O(nlogn)
  17.  * Space complexity: O(n)
  18.  * 
  19.  */
  20. class SpeedDateCompute {
  21.  
  22.     private static class Pair {
  23.         private final Male male;
  24.         private final Female female;
  25.         int malePreference;   // what does male   rank this female?
  26.         int femalePreference; // what does female rank this male?
  27.  
  28.         Pair (Male male, Female female, int malePreference, int femalePreference) {
  29.             this.male = male;
  30.             this.female = female;
  31.             this.malePreference = malePreference;
  32.             this.femalePreference = femalePreference;
  33.         }
  34.  
  35.         public Male male() {
  36.             return male;
  37.         }
  38.  
  39.         public Female female() {
  40.             return female;
  41.         }
  42.  
  43.         @Override
  44.         public boolean equals(Object that) {
  45.             if (that instanceof Pair) {
  46.                 final Pair thatPair = (Pair) that;
  47.                 return this.male.equals(thatPair.male) && this.female.equals(thatPair.female);
  48.             }
  49.             return false;
  50.         }
  51.  
  52.         @Override
  53.         public int hashCode() {
  54.             return this.male.hashCode() ^ this.female.hashCode();
  55.         }
  56.  
  57.         @Override
  58.         public String toString() {
  59.             return String.format("%s dates %s", male, female);
  60.         }
  61.     }
  62.  
  63.     private static class PairComparator implements Comparator<Pair> {
  64.         @Override
  65.         public int compare(Pair pair1, Pair pair2) {
  66.             return rank(pair1.femalePreference, pair1.malePreference)
  67.                  - rank(pair2.femalePreference, pair2.malePreference);
  68.         }
  69.  
  70.         /*
  71.          * Ranking algorithm. 
  72.          * 
  73.          * Let notation (1,2) mean - femalePrerence is 1 and malePreference is 2.
  74.          * (1, 1) means both rank each other as their best so this pair triumps over (2, 2)
  75.          * but there is a tie between (1, 2) and (2, 1)
  76.          * As a tie breaker we give preference to feelings of women 
  77.          * thus (1,2) > (2, 1)
  78.          * 
  79.          * Thus the rule is expanded to 
  80.          * 
  81.          * (1, 1) > (1, 2) > (2, 1) > (2, 2)
  82.          * 
  83.          * This can be thought of as a matrix of the form
  84.          * (lil lazy to retype the whole thing, plz check the link)
  85.          * http://m...content-available-to-author-only...e.com/questions/720797/whats-the-name-of-this-sort-of-matrix
  86.          * http://c...content-available-to-author-only...e.com/questions/44939/a-matrix-with-square-diagonals-and-transpose-being-increments-of-other
  87.          * 
  88.          * @param row   the female choice
  89.          * @param col   the male choice
  90.          * @return      
  91.          */
  92.         private int rank(int row, int col) {
  93.             if (row == col) {
  94.                 return row * row;
  95.             }
  96.  
  97.             final int rank = (col) * (col) + 1 + (2 * row) ;
  98.  
  99.             if (row < col) {
  100.                 return rank;
  101.             } else {
  102.                 return rank + 1;
  103.             }
  104.         }
  105.     }
  106.  
  107.     public static abstract class Person<Likes extends Person> {
  108.         private final String name;
  109.         private final List<Likes> likes = new ArrayList<>();
  110.  
  111.         public Person(String name) {
  112.             this.name = name;
  113.         }
  114.  
  115.         public String name() {
  116.             return this.name;
  117.         }
  118.  
  119.         public List<Likes> likes() {
  120.             return this.likes;
  121.         }
  122.  
  123.         public List<Likes> likes(List<Likes> others) {
  124.             this.likes.addAll(others);
  125.             return this.likes;
  126.         }
  127.  
  128.         @Override
  129.         public String toString() {
  130.             return this.name();
  131.         }
  132.  
  133.         // "equals" defaults to pointer equivalence, which is what we want
  134.     }
  135.  
  136.     public static class Male extends Person<Female> {
  137.         public Male(String name) {
  138.             super(name);
  139.         }
  140.  
  141.         @Override
  142.         public boolean equals(Object that) {
  143.             return that instanceof Male && super.equals(that);
  144.         }
  145.     }
  146.  
  147.     public static class Female extends Person<Male> {
  148.         public Female(String name) {
  149.             super(name);
  150.         }
  151.  
  152.         @Override
  153.         public boolean equals(Object that) {
  154.             return that instanceof Female && super.equals(that);
  155.         }
  156.     }
  157.  
  158.  
  159.     /**
  160.      * Does not make a deep copies thus client is not expected to change males, females, and their members.
  161.      * Expects consistency in males and female collections, else results are unpredictable.
  162.      * 
  163.      * By consistency it means:
  164.      * - The number of boys and girls should be the same.
  165.      * - Each boy and each girl should make same number of choices
  166.      * - Choices should mention "only existing members of opposite sex"
  167.      * 
  168.      * 
  169.      * @param males
  170.      * @param females
  171.      */
  172.     public static List<Pair> getPairs(Collection<Male> males, Collection<Female> females) {
  173.         validate(males, females);
  174.  
  175.         final List<Pair> pairs = calculateWeightedPairs(males, females);
  176.  
  177.         Collections.sort(pairs, new PairComparator());
  178.  
  179.         return createPairs(pairs);
  180.     }
  181.  
  182.     private static void validate (Collection<Male> males, Collection<Female> females) {
  183.         if (females == null) {
  184.             throw new NullPointerException("The set of females should not be null");
  185.         }
  186.         if (males == null) {
  187.             throw new NullPointerException("The set of males should not be null");
  188.         }
  189.  
  190.         if (males.size() == 0) {
  191.             throw new IllegalArgumentException("The set of males should not be empty.");
  192.         }
  193.         if (females.size() == 0) {
  194.             throw new IllegalArgumentException("The set of females should not be empty.");
  195.         }
  196.     }
  197.  
  198.     private static List<Pair> calculateWeightedPairs(Iterable<Male> males, Iterable<Female> females) {
  199.         // Given a directed bipartite graph, it converts bipartite graph into 
  200.         // undirected map.
  201.  
  202.         // here we use a Map rather than a Set because we need to retrieve
  203.         // the *identical* pair given some other *equal* pair.
  204.         final Map<Pair, Pair> pairs = new HashMap<>();
  205.  
  206.         for (final Male male : males) {
  207.             final List<Female> likes = male.likes();
  208.             for (int i = 0; i < likes.size(); i++) {
  209.                 // mark female preference as "size" thus assigning the worst rank as default.
  210.                 final Pair pair = new Pair(male, likes.get(i), i, likes.size() - 1);
  211.                 pairs.put(pair, pair);
  212.             }
  213.         }
  214.  
  215.         for (final Female female : females) {
  216.             final List<Male> likes = female.likes();
  217.             for (int i = 0; i < likes.size(); i++) {
  218.                 // check if any male has chosen this female, else skip.
  219.                 final Pair possiblePair = new Pair(likes.get(i), female, likes.size() - 1, i);
  220.                 if (pairs.containsKey(possiblePair)) {
  221.                     pairs.get(possiblePair).femalePreference = i;
  222.                 }
  223.             }
  224.         }
  225.  
  226.         return new ArrayList<>(pairs.values());
  227.     }
  228.  
  229.     private static List<Pair> createPairs(Iterable<Pair> pairs) {
  230.         final Set<Male> hookedUpMales = new HashSet<>();
  231.         final Set<Female> hookedUpFemales = new HashSet<>();
  232.         final List<Pair> hookedUpPairs = new ArrayList<>();
  233.  
  234.         for (final Pair pair : pairs) {            
  235.             if (hookedUpMales.contains(pair.male()) || hookedUpFemales.contains(pair.female())) {
  236.                 continue;
  237.             }
  238.             hookedUpPairs.add(pair);
  239.             hookedUpMales.add(pair.male());
  240.             hookedUpFemales.add(pair.female());
  241.         }
  242.  
  243.         return hookedUpPairs;
  244.     }
  245.  
  246.  
  247.     public static void main(String[] args) {
  248.         /*
  249.          * Test case 1
  250.          */
  251.         {
  252.             final Male[] males = {
  253.                 new Male("male1"),
  254.                 new Male("male2")
  255.             };
  256.             final Female[] females = {
  257.                 new Female("female1"),
  258.                 new Female("female2")
  259.             };
  260.             males[0].likes(Arrays.asList(females[0], females[1]));
  261.             males[1].likes(Arrays.asList(females[1], females[0]));
  262.             females[0].likes(Arrays.asList(males[0], males[1]));
  263.             females[1].likes(Arrays.asList(males[1], males[0]));
  264.             final List<Pair> actualValues = SpeedDateCompute.getPairs(
  265.                 Arrays.asList(males),
  266.                 Arrays.asList(females)
  267.             );
  268.             assert 2 == actualValues.size();
  269.             assert actualValues.contains(new Pair(males[0], females[0], 0, 0));
  270.             assert actualValues.contains(new Pair(males[1], females[0], 0, 0));
  271.         }
  272.  
  273.         /*
  274.          * Test case 2
  275.          */
  276.         {
  277.             final Male[] males = {
  278.                 new Male("male1"),
  279.                 new Male("male2"),
  280.                 new Male("male3")
  281.             };
  282.             final Female[] females = {
  283.                 new Female("female1"),
  284.                 new Female("female2"),
  285.                 new Female("female3")
  286.             };
  287.             males[0].likes(Arrays.asList(females[1], females[0]));
  288.             males[1].likes(Arrays.asList(females[0], females[1]));
  289.             males[2].likes(Arrays.asList(females[0], females[1]));
  290.             females[0].likes(Arrays.asList(males[1], males[0]));
  291.             females[1].likes(Arrays.asList(males[0], males[1]));
  292.             females[2].likes(Arrays.asList(males[0], males[1]));
  293.             final List<Pair> actualValues = SpeedDateCompute.getPairs(
  294.                 Arrays.asList(males),
  295.                 Arrays.asList(females)
  296.             );
  297.             assert 2 == actualValues.size();
  298.             assert actualValues.contains(new Pair(males[0], females[1], 0, 0));
  299.             assert actualValues.contains(new Pair(males[1], females[0], 0, 0));
  300.         }
  301.     }
  302. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RSTcUu
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!