From f76bab93b3b58df4510a480d28e547125b5f3020 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 19 Dec 2018 20:36:14 -0600
Subject: Primitive Calculator done!

Once again, this is a challenging but fun puzzle to solve. Key
reflections are:
1. It pays to read and try to understand the problem as early as
possible. "Sleeping on it" really, really helps. Deep appreciation and
clarity came as I was thinking about it before falling asleep, walking
the dogs, and just be;
2. Small steps, but do take them! They lead to success! Hooray :)---
 .../sources/PrimitiveCalculator.java               | 89 ++++++++++++++++++++++
 .../tests/PrimitiveCalculatorTest.java             | 40 ++++++++++
 2 files changed, 129 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/PrimitiveCalculator.java
 create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/PrimitiveCalculatorTest.java

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/PrimitiveCalculator.java b/AlgoDesignAndTechniqueEdxJava/sources/PrimitiveCalculator.java
new file mode 100644
index 0000000..b46fc78
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/PrimitiveCalculator.java
@@ -0,0 +1,89 @@
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Scanner;
+
+public class PrimitiveCalculator {
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        int n = scanner.nextInt();
+        List<Integer> sequence = optimal_sequence(n);
+        System.out.println(sequence.size() - 1);
+        for (Integer x : sequence) {
+            System.out.print(x + " ");
+        }
+    }
+
+    public static List<Integer> optimal_sequence(int n) {
+        List<Integer> sequence = new ArrayList<Integer>();
+        int[] stepsCount = new int[n];
+        // the path int array indicates the next step to reduce it:
+        // 1: minus 1
+        // 2: divide by 2
+        // 3: divide by 3
+        int[] path = new int[n];
+        int div2Steps, div3Steps, minus1Steps;
+        for (int i = 1; i < stepsCount.length; i++) {
+            int j = i + 1;
+            div2Steps = Integer.MAX_VALUE;
+            div3Steps = Integer.MAX_VALUE;
+            if (j % 3 == 0) {
+                div3Steps = stepsCount[j / 3 - 1];
+            }
+            if (j % 2 == 0) {
+                div2Steps = stepsCount[j / 2 - 1];
+            }
+            minus1Steps = stepsCount[i - 1];
+            // I use a 2-dimensional array (3 by 2) as my data structure
+            // to determine steps and path to get to the current j. Inner
+            // 2-element array is the stepCount and path pair. This 2-dim
+            // array is then sorted by the first element of the pair
+            // (stepCount). This way the stepsCount and path arrays can be
+            // built up from 1 to n eventually.
+            int stepCountAndType[][] = { { minus1Steps, 1 }, { div2Steps, 2 }, { div3Steps, 3 } };
+            Arrays.sort(stepCountAndType, Comparator.comparingInt(arr -> arr[0]));
+            stepsCount[i] = stepCountAndType[0][0] + 1;
+            path[i] = stepCountAndType[0][1];
+        }
+        sequence.add(n);
+        while (n > 1) {
+            int i = path[n - 1];
+            if (i == 3) {
+                n = n / 3;
+                sequence.add(n);
+                continue;
+            }
+            if (i == 2) {
+                n = n / 2;
+                sequence.add(n);
+                continue;
+            }
+            n = n - 1;
+            sequence.add(n);
+        }
+        Collections.reverse(sequence);
+        return sequence;
+    }
+
+    public static List<Integer> greedy_sequence(int n) {
+        // Greedy algo is NOT safe, therefore won't produce
+        // the right results.
+        List<Integer> sequence = new ArrayList<Integer>();
+        while (n >= 1) {
+            sequence.add(n);
+            if (n % 3 == 0) {
+                n /= 3;
+            } else if (n % 2 == 0) {
+                n /= 2;
+            } else {
+                n -= 1;
+            }
+        }
+        Collections.reverse(sequence);
+        return sequence;
+    }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/PrimitiveCalculatorTest.java b/AlgoDesignAndTechniqueEdxJava/tests/PrimitiveCalculatorTest.java
new file mode 100644
index 0000000..11787d4
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/PrimitiveCalculatorTest.java
@@ -0,0 +1,40 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+import org.junit.jupiter.api.Test;
+
+class PrimitiveCalculatorTest {
+
+    @Test
+    void test() {
+        List<Integer> result = new ArrayList<Integer>();
+        result.add(1);
+        assertEquals(result, PrimitiveCalculator.optimal_sequence(1));
+    }
+
+    @Test
+    void test1() {
+        assertEquals(3, PrimitiveCalculator.optimal_sequence(5).size() - 1);
+    }
+
+    @Test
+    void test6() {
+        assertEquals(2, PrimitiveCalculator.optimal_sequence(6).size() - 1);
+    }
+
+    @Test
+    void test2() {
+        assertEquals(14, PrimitiveCalculator.optimal_sequence(96234).size() - 1);
+    }
+
+    @Test
+    void test2DimensionalArraySorting() {
+        int a[][] = { { 2, 2 }, { 1, 3 }, { 3, 3 } };
+        Arrays.sort(a, Comparator.comparingInt(arr -> arr[0]));
+        assertEquals(1, a[0][0]);
+    }
+}
-- 
cgit v1.2.3