SHARE
TWEET

Untitled

a guest Jun 12th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // it is prob a bad idea to import everything but
  2. import java.util.*;
  3. import java.io.*;
  4.  
  5. class Main {
  6.     public static void main(String[] args) {
  7.         // init set of items. O(n)[for each line] * O(1)[hash set insertion] -> O(n)
  8.         LinkedHashSet<String> items = new LinkedHashSet<>();
  9.         Scanner inFile = null;
  10.         try {
  11.             inFile = new Scanner(new File(args[0]));
  12.         } catch (FileNotFoundException e) {
  13.             e.printStackTrace();
  14.         }
  15.         while (inFile.hasNextLine()) {
  16.             items.add(inFile.nextLine().replace("\"", ""));
  17.         }
  18.         // build maps. O(n)[for each element] * (O(1)[hash map lookup] + O(1)[hash map insertion]) -> O(n)
  19.         ArrayList<LinkedHashMap<String, LinkedHashSet<String>>> mappingsStringContainer = new ArrayList<>(3);
  20.         for (int i = 0; i != 3; ++i){ // construct first
  21.             mappingsStringContainer.add(new LinkedHashMap<>());
  22.         }
  23.         for (String e : items){ // fill
  24.             String[] e_array = e.split(";", -1);
  25.             if (e_array.length != 3){
  26.                 throw new RuntimeException("invalid structure of element : " + e);
  27.             }
  28.             for(int i = 0; i < e_array.length; i++) {
  29.                 if (e_array[i].isEmpty()){
  30.                     continue;
  31.                 }
  32.                 LinkedHashMap<String, LinkedHashSet<String>> map = mappingsStringContainer.get(i);
  33.                 if (map.containsKey(e_array[i])){
  34.                     map.get(e_array[i]).add(e);
  35.                 } else {
  36.                     map.put(e_array[i], new LinkedHashSet<>(List.of(e)));
  37.                 }
  38.             }
  39.         }
  40.         // process and get results. O(n) [for each element] * O(m) [complexity of processing each one] -> O(n * m), m - max group size
  41.         ArrayList<LinkedHashSet<String>> results = new ArrayList<>();
  42.         while (!items.isEmpty()){
  43.             String items_e = items.iterator().next();
  44.             if (!items.contains(items_e)){
  45.                 continue;
  46.             }
  47.             if (items_e.equals(";;")){ // )':
  48.                 //results.add(new LinkedHashSet<>(List.of(items_e)));
  49.                 items.remove(items_e);
  50.                 continue;
  51.             }
  52.             Set<LinkedHashSet<String>> queue = new LinkedHashSet<>();
  53.             LinkedHashSet<String> res_set = new LinkedHashSet<>();
  54.             String[] items_e_split = items_e.split(";", -1);
  55.             for(int i = 0; i < items_e_split.length; i++) {
  56.                 if (!items_e_split[i].isEmpty()){
  57.                     queue.add(mappingsStringContainer.get(i).get(items_e_split[i])); // O(1) * 2 [LinkedHashMap/ArrayList access] + O(1) [LinkedHashSet insertion] -> O(1)
  58.                 }
  59.             }
  60.             while (!queue.isEmpty()){
  61.                 Iterator<LinkedHashSet<String>> queue_i = queue.iterator();
  62.                 LinkedHashSet<String> queue_set = queue_i.next();
  63.                 queue_i.remove(); // O(1) as well
  64.                 for (String queue_e : queue_set){ // O(m) , m - max group size
  65.                     if (!items.contains(queue_e)){
  66.                         continue;
  67.                     }
  68.                     String[] e_array = queue_e.split(";", -1);
  69.                     for(int i = 0; i < e_array.length; i++) {
  70.                         if (!e_array[i].isEmpty()) {
  71.                             LinkedHashMap<String, LinkedHashSet<String>> map = mappingsStringContainer.get(i);
  72.                             LinkedHashSet<String> set = map.get(e_array[i]); // O(1)
  73.                             if (set != null)
  74.                                 queue.add(set);
  75.                             mappingsStringContainer.get(i).remove(e_array[i]); // O(1) + O(1) -> O(1)
  76.                         }
  77.                     }
  78.                     res_set.add(queue_e); // O(1)
  79.                     items.remove(queue_e);// O(1)
  80.                 }
  81.             }
  82.             results.add(res_set); // O(1)
  83.         }
  84.         // sort. O(n log n)
  85.         Collections.sort(results, Comparator.comparingInt(LinkedHashSet<String>::size));
  86.         try (PrintWriter writer = new PrintWriter(new File(args[1]))) {
  87.             writer.write("number of groups : "+results.size()+"\n");
  88.             writer.write(results.toString());
  89.             for(int i = 0; i != results.size(); ++i) {
  90.                 writer.write("group #" + i + " : \n");
  91.                 for(String e : results.get(i)) {
  92.                     writer.write("\t" + e + "\n");
  93.                 }
  94.             }
  95.         } catch (FileNotFoundException e) {
  96.             System.out.println("Could not write to file." + e.getMessage());
  97.         }
  98.     }
  99. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top