Merge pull request #8813 from packy/challenge-237

Challenge 237 solutions by Packy Anderson

1 files changed, 121 insertions, 0 deletions

diff --git a/challenge-237/packy-anderson/java/Ch2.java b/challenge-237/packy-anderson/java/Ch2.java
new file mode 100644
index 0000000000..4768d8d7ec
--- /dev/null
+++ b/challenge-237/packy-anderson/java/Ch2.java
@@ -0,0 +1,121 @@
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.stream.Collectors;
+
+public class Ch2 {
+  public static String joined(int[] ints) {
+    // we're using it more than once, make it a method
+    return Arrays.stream(ints)
+                 .mapToObj(String::valueOf)
+                 .collect(Collectors.joining(", "));
+  }
+
+  public static int greatness(int[] nums, int[] perm) {
+    // determine the "greatness" of a permutation
+    // relative to the original array; accepts two
+    // arrays to do the comparison
+    int greatness_num = 0;
+    for (int i = 0; i < nums.length; i++) {
+      if (nums[i] < perm[i]) {
+        greatness_num++;
+      }
+    }
+    return greatness_num;
+  }
+
+  public static int[] greatestPermutation(int[] nums) {
+    // first, count up how many of each num we have
+    HashMap<Integer, Integer> num_count =
+      new HashMap<Integer, Integer>();
+    for (int i = 0; i < nums.length; i++) {
+      num_count.put(
+        nums[i],
+        num_count.getOrDefault(nums[i], 0) + 1
+      );
+    }
+
+    // make a list of the available numbers
+    // to put in a permutation
+    List<Integer> available =
+      new ArrayList<>(num_count.keySet());
+    Collections.sort(available);
+
+    // now, build a permutation that maximizes "greatness"
+    List<Integer> perm = new ArrayList<>();
+    for (Integer num : nums) {
+      // default to the smallest available number
+      int num_to_add = available.get(0);
+      for (int i = 0; i < available.size(); i++) {
+        int this_num = available.get(i);
+        if (num < this_num) {
+          num_to_add = this_num;
+          break;
+        }
+      }
+      perm.add(num_to_add);
+
+      // decrement the count of that number available
+      num_count.put(
+        num_to_add,
+        num_count.get(num_to_add) - 1
+      );
+  
+      // if there are no more of that number, remove it
+      // from available list
+      if ( num_count.get(num_to_add) == 0 ) {
+        // filter array to not include $num
+        int size = available.size();
+        for (int i = 1; i < size; i++) {
+          int this_num = available.get(i);
+          if (num_to_add == this_num) {
+            available.remove(i);
+            break;
+          }
+        }
+      }
+    }
+
+    // because we built the permutations in a List,
+    // convert the list to an int array for return
+    int[] perm_return = new int[perm.size()];
+    for (int i = 0; i < perm.size(); i++) {
+      perm_return[i] = perm.get(i);
+    }
+    return perm_return;
+  }
+
+  public static void solution(int[] nums) {
+    System.out.println(String.format(
+      "Input: @nums = (%s)", joined(nums)
+    ));
+    int[] greatest = greatestPermutation(nums);
+    int greatness_num = greatness(nums, greatest);
+    System.out.println(String.format(
+      "Output: %d", greatness_num
+    ));
+    System.out.println(String.format(
+      "\nOne possible permutation: (%s)", joined(greatest)
+    ));
+    System.out.println(String.format(
+      "which returns %d greatness as below:", greatness_num
+    ));
+    for (int i = 0; i < nums.length; i++) {
+      if (nums[i] < greatest[i]) {
+        System.out.println(String.format(
+          "nums[%d] < perm[%d]", i, i
+        ));
+      }
+    }
+  }
+
+  public static void main(String[] args) {
+    System.out.println("Example 1:");
+    solution(new int[] {1, 3, 5, 2, 1, 3, 1});
+
+    System.out.println("\nExample 2:");
+    solution(new int[] {1, 2, 3, 4});
+  }
+}