summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-19 20:36:14 -0600
committerHaidong Ji2018-12-19 20:36:14 -0600
commitf76bab93b3b58df4510a480d28e547125b5f3020 (patch)
tree51e05f245c3f87d78cea3b216e356700a1e7e839
parent1e7ce107613c578fdb99d3480e2e04e351434ac6 (diff)
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 :)
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/PrimitiveCalculator.java89
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/PrimitiveCalculatorTest.java40
2 files changed, 129 insertions, 0 deletions
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]);
+ }
+}