fork download
copy 
  1. import java.util.*;
  2. import java.util.HashMap;
  3.  
  4. public class ShippingMatcher {
  5.     private HashMap<String, ArrayList<Integer>> internationals = new HashMap<String, ArrayList<Integer>>();
  6.     private HashMap<String, ArrayList<Integer>> domestics = new HashMap<String, ArrayList<Integer>>();
  7.  
  8.     //class to order the results so we can pick from the countries with the most people in them first
  9.     private static class SizeComparator implements Comparator<String> {
  10.         private HashMap<String, ArrayList<Integer>> data;
  11.         private SizeComparator(HashMap<String, ArrayList<Integer>> data) {
  12.             this.data = data;
  13.         }
  14.  
  15.         @Override
  16.         public int compare(String s1, String s2) {
  17.             //assumes no nulls
  18.             Integer size1 = data.get(s1).size();
  19.             Integer size2 = data.get(s2).size();
  20.             return -1 * size1.compareTo(size2);
  21.         }
  22.     }
  23.  
  24.     public List<? extends List<Integer>> getMatches(ArrayList<ArrayList> inputData) {
  25.         readData(inputData);
  26.  
  27.         ArrayList<ArrayList<Integer>> matches = new ArrayList<ArrayList<Integer>>();
  28.  
  29.         countryLabel:
  30.         for (String country : domestics.keySet()) {
  31.             ArrayList<Integer> ids = domestics.get(country);
  32.             while (ids.size() < 2) {
  33.                 //no valid chains, try to grab an international shipper and put them in here
  34.                 if (internationals.get(country) == null) {
  35.                     //can't make a valid domestic chain
  36.                     //so make the domestics ship international
  37.                     internationals.get(country).addAll(ids);
  38.                     continue countryLabel;
  39.                 }
  40.  
  41.                 ids.add(internationals.get(country).get(0));
  42.                 internationals.get(country).remove(0);
  43.                 if (internationals.get(country).size() == 0) {
  44.                     internationals.remove(country);
  45.                 }
  46.             }
  47.  
  48.             for (int i = 0; i < ids.size() - 1; i++) {
  49.                 ArrayList<Integer> match = new ArrayList<Integer>();
  50.                 match.add(ids.get(i));
  51.                 match.add(ids.get(i + 1));
  52.                 matches.add(match);
  53.             }
  54.  
  55.             ArrayList<Integer> match = new ArrayList<Integer>();
  56.             match.add(ids.get(ids.size()-1));
  57.             match.add(ids.get(0));
  58.             matches.add(match);
  59.         }
  60.  
  61.         PriorityQueue<String> targets = new PriorityQueue<String>(internationals.size(), new SizeComparator(internationals));
  62.         targets.addAll(internationals.keySet());
  63.  
  64.         //making a chain of international shippers
  65.         String [] countries = new String[2];
  66.         int[] ids = new int[2];
  67.  
  68.         //record the next match index so we can complete the chain at the end
  69.         int startMatchIdx = matches.size();
  70.  
  71.         countries[0] = targets.poll();
  72.         countries[1] = targets.poll();
  73.         while (internationals.size() > 1) {
  74.             ids[0] = internationals.get(countries[0]).get(0);
  75.             ids[1] = internationals.get(countries[1]).get(0);
  76.  
  77.             ArrayList<Integer> match = new ArrayList<Integer>();
  78.             match.add(ids[0]);
  79.             match.add(ids[1]);
  80.             matches.add(match);
  81.  
  82.             for (int i = 0; i < 2; i++) {
  83.                 internationals.get(countries[i]).remove(0);
  84.                 if (internationals.get(countries[i]).isEmpty()) {
  85.                     internationals.remove(countries[i]);
  86.                 } else {
  87.                     targets.add(countries[i]);
  88.                 }
  89.             }
  90.  
  91.             countries[0] = targets.poll();
  92.             countries[1] = targets.poll();
  93.         }
  94.  
  95.         if (internationals.size() == 1) {
  96.             //complete the chain
  97.             if (startMatchIdx < matches.size()) {
  98.                 ArrayList<Integer> startMatch = matches.get(startMatchIdx);
  99.                 ArrayList<Integer> match = new ArrayList<Integer>();
  100.                 match.add(internationals.get(countries[0]).get(0));
  101.                 match.add(startMatch.get(0));
  102.                 matches.add(match);
  103.                 internationals.get(countries[0]).remove(0);
  104.             }
  105.  
  106.             //a little fubared, try to make a chain of internationals ship domestic
  107.             startMatchIdx = matches.size();
  108.             while (internationals.get(countries[0]).size() > 2) {
  109.                 ids[0] = internationals.get(countries[0]).get(0);
  110.                 ids[1] = internationals.get(countries[0]).get(1);
  111.  
  112.                 ArrayList<Integer> match = new ArrayList<Integer>();
  113.                 match.add(ids[0]);
  114.                 match.add(ids[1]);
  115.                 matches.add(match);
  116.  
  117.                 internationals.get(countries[0]).remove(0);
  118.                 internationals.get(countries[0]).remove(1);
  119.             }
  120.  
  121.             if (startMatchIdx < matches.size()) {
  122.                 ArrayList<Integer> startMatch = matches.get(startMatchIdx);
  123.                 ArrayList<Integer> match = new ArrayList<Integer>();
  124.                 match.add(internationals.get(countries[0]).get(0));
  125.                 match.add(startMatch.get(0));
  126.                 matches.add(match);
  127.                 internationals.get(countries[0]).remove(0);
  128.             }
  129.  
  130.             //wow this is fucked, just insert the dude into a love triangle with the last match
  131.             if (internationals.get(countries[0]).size() == 1) {
  132.                 ArrayList<Integer> lastMatch = matches.get(matches.size()-1);
  133.                 matches.remove(matches.size()-1);
  134.                 ArrayList<Integer> match1 = new ArrayList<Integer>();
  135.                 match1.add(lastMatch.get(0));
  136.                 match1.add(internationals.get(countries[0]).get(0));
  137.                 matches.add(match1);
  138.                 ArrayList<Integer> match2 = new ArrayList<Integer>();
  139.                 match2.add(internationals.get(countries[0]).get(0));
  140.                 match2.add(lastMatch.get(1));
  141.                 matches.add(match2);
  142.             }
  143.         }
  144.  
  145.         return matches;
  146.     }
  147.  
  148.     private void readData(ArrayList<ArrayList> inputData) {
  149.         internationals.clear();
  150.         domestics.clear();
  151.         for (ArrayList participant : inputData) {
  152.             try {
  153.                 Integer id = (Integer)participant.get(0);
  154.                 String country = (String)participant.get(1);
  155.                 Boolean internationalShip = (Boolean)participant.get(2);
  156.  
  157.                 if (id != null && country != null && internationalShip != null) {
  158.                     if (internationalShip) {
  159.                         if (!internationals.containsKey(country)) {
  160.                             internationals.put(country, new ArrayList<Integer>());
  161.                         }
  162.                         internationals.get(country).add(id);
  163.                     } else {
  164.                         if (!domestics.containsKey(country)) {
  165.                             domestics.put(country, new ArrayList<Integer>());
  166.                         }
  167.                         domestics.get(country).add(id);
  168.                     }
  169.                 } else {
  170.                     throw new IllegalArgumentException("Null data");
  171.                 }
  172.             } catch (Exception e) {
  173.                 System.err.println("Caught bad participant data, skipping. " + e.getMessage());
  174.             }
  175.         }
  176.     }
  177. }
  178.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/j8TH4
language:
Java (HotSpot 12)
created:
11 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!