/*This is a java program to solve a matching problem for stable marriage matching problem. In mathematics, economics, and computer science, the stable marriage problem (SMP) is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is stable whenever it is not the case that both:
1. some given element A of the first matched set prefers some given element B of the second matched set over the element to which A is already matched, and
2. B also prefers A over the element to which B is already matched

In other words, a matching is stable when there does not exist any alternative pairing (A, B) in which both A and B are individually better off than they would be with the element to which they are currently matched.

The stable marriage problem is commonly stated as:
Given n men and n women, where each person has ranked all members of the opposite gender with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite gender who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”.*/


import java.util.*;

public class MatchingProblemStableMarriage
{
    static List<String> guys = Arrays.asList(new String[] { "abe", "bob",
                               "col", "dan", "ed", "fred", "gav", "hal", "ian", "jon"
                                                          });
    static List<String> girls = Arrays.asList(new String[] { "abi", "bea",
                                "cath", "dee", "eve", "fay", "gay", "hope", "ivy", "jan"
                                                           });
    static Map<String, List<String>> guyPrefers = new HashMap<String, List<String>>()
    {
        private static final long serialVersionUID = 1L;
        {
            put("abe", Arrays.asList("abi", "eve", "cath", "ivy", "jan", "dee",
                                     "fay", "bea", "hope", "gay"));
            put("bob", Arrays.asList("cath", "hope", "abi", "dee", "eve",
                                     "fay", "bea", "jan", "ivy", "gay"));
            put("col", Arrays.asList("hope", "eve", "abi", "dee", "bea", "fay",
                                     "ivy", "gay", "cath", "jan"));
            put("dan", Arrays.asList("ivy", "fay", "dee", "gay", "hope", "eve",
                                     "jan", "bea", "cath", "abi"));
            put("ed", Arrays.asList("jan", "dee", "bea", "cath", "fay", "eve",
                                    "abi", "ivy", "hope", "gay"));
            put("fred", Arrays.asList("bea", "abi", "dee", "gay", "eve", "ivy",
                                      "cath", "jan", "hope", "fay"));
            put("gav", Arrays.asList("gay", "eve", "ivy", "bea", "cath", "abi",
                                     "dee", "hope", "jan", "fay"));
            put("hal", Arrays.asList("abi", "eve", "hope", "fay", "ivy",
                                     "cath", "jan", "bea", "gay", "dee"));
            put("ian", Arrays.asList("hope", "cath", "dee", "gay", "bea",
                                     "abi", "fay", "ivy", "jan", "eve"));
            put("jon", Arrays.asList("abi", "fay", "jan", "gay", "eve", "bea",
                                     "dee", "cath", "ivy", "hope"));
        }
    };
    static Map<String, List<String>> girlPrefers = new HashMap<String, List<String>>()
    {
        private static final long serialVersionUID = 1L;
        {
            put("abi", Arrays.asList("bob", "fred", "jon", "gav", "ian", "abe",
                                     "dan", "ed", "col", "hal"));
            put("bea", Arrays.asList("bob", "abe", "col", "fred", "gav", "dan",
                                     "ian", "ed", "jon", "hal"));
            put("cath", Arrays.asList("fred", "bob", "ed", "gav", "hal", "col",
                                      "ian", "abe", "dan", "jon"));
            put("dee", Arrays.asList("fred", "jon", "col", "abe", "ian", "hal",
                                     "gav", "dan", "bob", "ed"));
            put("eve", Arrays.asList("jon", "hal", "fred", "dan", "abe", "gav",
                                     "col", "ed", "ian", "bob"));
            put("fay", Arrays.asList("bob", "abe", "ed", "ian", "jon", "dan",
                                     "fred", "gav", "col", "hal"));
            put("gay", Arrays.asList("jon", "gav", "hal", "fred", "bob", "abe",
                                     "col", "ed", "dan", "ian"));
            put("hope", Arrays.asList("gav", "jon", "bob", "abe", "ian", "dan",
                                      "hal", "ed", "col", "fred"));
            put("ivy", Arrays.asList("ian", "col", "hal", "gav", "fred", "bob",
                                     "abe", "ed", "jon", "dan"));
            put("jan", Arrays.asList("ed", "hal", "gav", "abe", "bob", "jon",
                                     "col", "ian", "fred", "dan"));
        }
    };

    public static void main(String[] args)
    {
        Map<String, String> matches = match(guys, guyPrefers, girlPrefers);
        for (Map.Entry<String, String> couple : matches.entrySet())
            {
                System.out.println(couple.getKey() + " is engaged to "
                                   + couple.getValue());
            }
        if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
            {
                System.out.println("Marriages are stable");
            }
        else
            {
                System.out.println("Marriages are unstable");
            }
        String tmp = matches.get(girls.get(0));
        matches.put(girls.get(0), matches.get(girls.get(1)));
        matches.put(girls.get(1), tmp);
        System.out.println(girls.get(0) + " and " + girls.get(1)
                           + " have switched partners");
        if (checkMatches(guys, girls, matches, guyPrefers, girlPrefers))
            {
                System.out.println("Marriages are stable");
            }
        else
            {
                System.out.println("Marriages are unstable");
            }
    }

    private static Map<String, String> match(List<String> guys,
            Map<String, List<String>> guyPrefers,
            Map<String, List<String>> girlPrefers)
    {
        Map<String, String> engagedTo = new TreeMap<String, String>();
        List<String> freeGuys = new LinkedList<String>();
        freeGuys.addAll(guys);
        while (!freeGuys.isEmpty())
            {
                String thisGuy = freeGuys.remove(0); // get a load of THIS guy
                List<String> thisGuyPrefers = guyPrefers.get(thisGuy);
                for (String girl : thisGuyPrefers)
                    {
                        if (engagedTo.get(girl) == null)
                            {
                                // girl is free
                                engagedTo.put(girl, thisGuy); // awww
                                break;
                            }
                        else
                            {
                                String otherGuy = engagedTo.get(girl);
                                List<String> thisGirlPrefers = girlPrefers.get(girl);
                                if (thisGirlPrefers.indexOf(thisGuy) < thisGirlPrefers
                                        .indexOf(otherGuy))
                                    {
                                        // this girl prefers this guy to the guy she's engaged
                                        // to
                                        engagedTo.put(girl, thisGuy);
                                        freeGuys.add(otherGuy);
                                        break;
                                    }// else no change...keep looking for this guy
                            }
                    }
            }
        return engagedTo;
    }

    private static boolean checkMatches(List<String> guys, List<String> girls,
                                        Map<String, String> matches, Map<String, List<String>> guyPrefers,
                                        Map<String, List<String>> girlPrefers)
    {
        if (!matches.keySet().containsAll(girls))
            {
                return false;
            }
        if (!matches.values().containsAll(guys))
            {
                return false;
            }
        Map<String, String> invertedMatches = new TreeMap<String, String>();
        for (Map.Entry<String, String> couple : matches.entrySet())
            {
                invertedMatches.put(couple.getValue(), couple.getKey());
            }
        for (Map.Entry<String, String> couple : matches.entrySet())
            {
                List<String> shePrefers = girlPrefers.get(couple.getKey());
                List<String> sheLikesBetter = new LinkedList<String>();
                sheLikesBetter.addAll(shePrefers.subList(0,
                                      shePrefers.indexOf(couple.getValue())));
                List<String> hePrefers = guyPrefers.get(couple.getValue());
                List<String> heLikesBetter = new LinkedList<String>();
                heLikesBetter.addAll(hePrefers.subList(0,
                                                       hePrefers.indexOf(couple.getKey())));
                for (String guy : sheLikesBetter)
                    {
                        String guysFinace = invertedMatches.get(guy);
                        List<String> thisGuyPrefers = guyPrefers.get(guy);
                        if (thisGuyPrefers.indexOf(guysFinace) > thisGuyPrefers
                                .indexOf(couple.getKey()))
                            {
                                System.out.printf("%s likes %s better than %s and %s"
                                                  + " likes %s better than their current partner\n",
                                                  couple.getKey(), guy, couple.getValue(), guy,
                                                  couple.getKey());
                                return false;
                            }
                    }
                for (String girl : heLikesBetter)
                    {
                        String girlsFinace = matches.get(girl);
                        List<String> thisGirlPrefers = girlPrefers.get(girl);
                        if (thisGirlPrefers.indexOf(girlsFinace) > thisGirlPrefers
                                .indexOf(couple.getValue()))
                            {
                                System.out.printf("%s likes %s better than %s and %s"
                                                  + " likes %s better than their current partner\n",
                                                  couple.getValue(), girl, couple.getKey(), girl,
                                                  couple.getValue());
                                return false;
                            }
                    }
            }
        return true;
    }
}

/*
abi is engaged to jon
bea is engaged to fred
cath is engaged to bob
dee is engaged to col
eve is engaged to hal
fay is engaged to dan
gay is engaged to gav
hope is engaged to ian
ivy is engaged to abe
jan is engaged to ed
Marriages are stable
abi and bea have switched partners
fred likes bea better than abi and bea likes fred better than their current partner
Marriages are unstable