fork download
copy 
  1. import java.util.List;
  2. import java.util.LinkedList;
  3. import java.util.ArrayList;
  4. import java.util.Random;
  5. import java.util.Collection;
  6.  
  7. class NutsAndBolts {
  8.     /**
  9.      * Given a set of bolts and an equally large set of nuts,
  10.      * where for each bolt there is a exactly one fitting nut,
  11.      * this algorithm finds a corresponding nut for every bolt.
  12.      * We cannot compare the sizes of two bolts or two nuts,
  13.      * the only thing we can do is to tell whether the nut is
  14.      * too big for the bolt or too small.
  15.      *
  16.      * The algorithm runs in O(NlgN) time and
  17.      * requires O(N) additional space (to copy the contents of
  18.      * the `nuts` and `bolts` lists.
  19.      */
  20.     static <T extends Comparable<T>> List<Pair<Nut<T>, Bolt<T>>>
  21.             pairNutsAndBolts(Collection<Nut<T>> nuts,
  22.             Collection<Bolt<T>> bolts) {
  23.         if (nuts.size() != bolts.size()) {
  24.             throw new IllegalArgumentException(String.format(
  25.                 "Expected: same amount of nuts as bolts"
  26.                 + " Got: len(nuts) = %d, len(bolts) = %d",
  27.                 nuts.size(), bolts.size()
  28.             ));
  29.         }
  30.  
  31.         List<Nut<T>> copyNuts = new ArrayList<>(nuts);
  32.         List<Bolt<T>> copyBolts = new ArrayList<>(bolts);
  33.  
  34.         Random random = new Random();
  35.         shuffle(copyNuts, random);
  36.         shuffle(copyBolts, random);
  37.  
  38.         List<Pair<Nut<T>, Bolt<T>>> list =
  39.             new LinkedList<Pair<Nut<T>, Bolt<T>>>();
  40.         pairNutsAndBolts(list, copyNuts, copyBolts, 0, nuts.size()); 
  41.         return list;
  42.     }
  43.  
  44.     private static <T extends Comparable<T>> void pairNutsAndBolts(
  45.             List<Pair<Nut<T>, Bolt<T>>> list,
  46.             List<Nut<T>> nuts, List<Bolt<T>> bolts, int lo, int hi) {
  47.         if (hi - lo == 1) {
  48.             list.add(new Pair<>(nuts.get(lo), bolts.get(lo)));
  49.         } else if (hi - lo > 1) {
  50.             int mid = partition(nuts, bolts.get(lo), lo, hi);
  51.             partition(bolts, nuts.get(mid), lo, hi);
  52.             list.add(new Pair<>(nuts.get(mid), bolts.get(mid)));
  53.  
  54.             pairNutsAndBolts(list, nuts, bolts, lo, mid);
  55.             pairNutsAndBolts(list, nuts, bolts, mid + 1, hi);
  56.         }
  57.     }
  58.  
  59.     private static <T extends Comparable<U>, U> int partition(
  60.             List<T> array, U pivot, int lo, int hi) {
  61.         for (int i = lo; i < hi; i++) {
  62.             if (array.get(i).compareTo(pivot) == 0) {
  63.                 swap(array, lo, i);
  64.                 break;
  65.             }
  66.         }
  67.         int iLeft = lo, iRight = hi;
  68.         do {
  69.             iLeft++;
  70.             while (iLeft < hi - 1
  71.                     && array.get(iLeft).compareTo(pivot) < 0) {
  72.                 iLeft++;
  73.             }
  74.             iRight--;
  75.             while (iRight > lo
  76.                     && array.get(iRight).compareTo(pivot) > 0) {
  77.                 iRight--;
  78.             }
  79.             if (iLeft < iRight) {
  80.                 swap(array, iLeft, iRight);
  81.             }
  82.         }
  83.         while (iLeft < iRight);
  84.  
  85.         swap(array, lo, iRight);
  86.         return iRight;
  87.     }
  88.  
  89.     private static <T> void shuffle(List<T> array, Random random) {
  90.         final int n = array.size();
  91.         for (int i = 0; i < n - 1; i++) {
  92.             swap(array, i, i + random.nextInt(n - i - 1) + 1);
  93.         }
  94.     }
  95.  
  96.     private static <T> void swap(List<T> array, int i, int j) {
  97.         assert i >= 0 && j >= 0
  98.             && i < array.size() && j < array.size();
  99.  
  100.         T temp = array.get(i);
  101.         array.set(i, array.get(j));
  102.         array.set(j, temp);
  103.     }
  104.  
  105.     static class Nut<T extends Comparable<T>>
  106.             implements Comparable<Bolt<T>> {
  107.         private T value; 
  108.  
  109.         public Nut(T value) {
  110.             this.value = value;
  111.         }
  112.  
  113.         @Override
  114.         public int compareTo(Bolt<T> bolt) {
  115.             return this.value.compareTo(bolt.value);
  116.         }
  117.  
  118.         @Override
  119.         public String toString() {
  120.             return value.toString();
  121.         }
  122.     }
  123.  
  124.     static class Bolt<T extends Comparable<T>> 
  125.             implements Comparable<Nut<T>> {
  126.         T value;
  127.  
  128.         public Bolt(T value) {
  129.             this.value = value;
  130.         }
  131.  
  132.         @Override
  133.         public int compareTo(Nut<T> nut) {
  134.             return this.value.compareTo(nut.value);
  135.         }
  136.  
  137.         @Override
  138.         public String toString() {
  139.             return value.toString();
  140.         }
  141.     }
  142.  
  143.     static class Pair<T, U> {
  144.         private T first;
  145.         private U second;
  146.  
  147.         public Pair(T first, U second) {
  148.             this.first = first;
  149.             this.second = second;
  150.         }
  151.  
  152.         public T getFirst() {
  153.             return first;
  154.         }
  155.  
  156.         public U getSecond() {
  157.             return second;
  158.         }
  159.  
  160.         @Override
  161.         public String toString() {
  162.             return String.format("(%s, %s)", first, second);
  163.         }
  164.     }
  165.  
  166.     public static void main(String[] args) {
  167.         List<Nut<Integer>> nuts = new ArrayList<>();
  168.         List<Bolt<Integer>> bolts = new ArrayList<>();
  169.  
  170.         for (int i = 0; i < 10; i++) {
  171.             nuts.add(new Nut<>(i));
  172.             bolts.add(new Bolt<>(9 - i));
  173.         }
  174.         for (Pair<Nut<Integer>, Bolt<Integer>> pair
  175.                 : pairNutsAndBolts(nuts, bolts)) {
  176.             System.out.println(pair);
  177.         }
  178.     }
  179. }
Success #stdin #stdout 0.12s 34252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(8, 8)
(0, 0)
(4, 4)
(3, 3)
(2, 2)
(1, 1)
(6, 6)
(5, 5)
(7, 7)
(9, 9)
https://ideone.com/SC6H9P
language:
Java (HotSpot 12)
created:
4 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!