Advertisement
DulcetAirman

find progressions

Dec 28th, 2021
1,247
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ch.claude_martin;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Arrays;
  5. import java.util.Set;
  6. import java.util.TreeSet;
  7.  
  8. class SomeClass {
  9.  
  10.     static boolean test(int a, int b) {
  11.         return a + 2 == b;
  12.     }
  13.  
  14.     public static void main(final String... args) {
  15.         // Take the data from the arguments or use the example list:
  16.         final var data = args.length > 0 ? Arrays.stream(args).mapToInt(Integer::parseInt).sorted().toArray()
  17.                 : new int[] { 1, 2, 5, 7, 8, 9, 11, 12, 14 };
  18.         System.out.println(Arrays.toString(data));// [5, 7, 9, 11, 12, 14]
  19.         final var size = data.length;
  20.         // three pointers are needed for this. Initially we look at the first two
  21.         // elements of the data.
  22.         // When third is used below to find longer progressions and add each sublist to
  23.         // the result set.
  24.         var p0 = 0;
  25.         var p1 = 1;
  26.         // The result set is a collection of sets. Each of those sets is a progression.
  27.         var resultSet = new ArrayList<Set<Integer>>();
  28.         // This loops through all possible pairs, but p1 is always < p1:
  29.         while (p0 < size && p1 < size) {
  30.             // The set contains at least 2 elements if it is part of the result set:
  31.             var set = new TreeSet<Integer>();
  32.             var a = data[p0];
  33.             var b = data[p1];
  34.             if (test(a, b)) {
  35.                 set.add(a);
  36.                 set.add(b);
  37.                 resultSet.add(new TreeSet<>(set));
  38.                 // Now we look for longer progressions that start with the one we just found:
  39.                 for (var p2 = p1 + 1; p2 < size; p2++) {
  40.                     var c = data[p2];
  41.                     if (test(b, c)) {
  42.                         set.add(b = c);
  43.                         resultSet.add(new TreeSet<>(set));
  44.                     }
  45.                 }
  46.             }
  47.             p1++; // increment pointer for "b":
  48.             // But it we go out of bounds we instead increment p0:
  49.             if (p1 == size) {
  50.                 // And p1 points to the one next to the new p0:
  51.                 p1 = ++p0 + 1;
  52.             }
  53.         }
  54.         // Show the result set:
  55.         System.out.println(resultSet);
  56.     }
  57. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement