From a5df8ebce9dcad0b60cf3c381b0e856a0f047ada Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 19 Dec 2018 22:05:36 -0600
Subject: Primitive calculator done!

Relatively easy since I worked it out in Java and Python. Slight change
of getting rid of the 2 dimensional array, which is probably better and
should have been done in Java and Python. Man, C++ is way more efficient
than Java and Python.---
 PlaygroundCpp/Sources/Playground.cpp | 89 ++++++++++++++++++++++++++++--------
 1 file changed, 69 insertions(+), 20 deletions(-)

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 070cf04..45bb5fc 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,32 +1,81 @@
 #include <iostream>
 #include <climits>
+#include <vector>
+#include <algorithm>
 //#include <gtest/gtest.h>
 
-int getChange(int money) {
-	// denominations: 1, 3, 4
-	int denominations[3] = { 1, 3, 4 };
-	int minNumCoins[money + 1] = { };
-	for (int m = 1; m < money + 1; m++) {
-		minNumCoins[m] = INT_MAX;
-		for (int i = 0; i < 3; i++) {
-			if (m >= denominations[i]) {
-				int numCoins = minNumCoins[m - denominations[i]] + 1;
-				if (numCoins < minNumCoins[m]) {
-					minNumCoins[m] = numCoins;
-				}
-			}
+using std::vector;
+
+vector<int> optimal_sequence(int n) {
+	vector<int> sequence;
+	int stepsCount[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[n];
+	int div2Steps, div3Steps, minus1Steps;
+	for (int i = 1; i < n; i++) {
+		int j = i + 1;
+		div2Steps = INT_MAX;
+		div3Steps = INT_MAX;
+		if (j % 3 == 0) {
+			div3Steps = stepsCount[j / 3 - 1];
+		}
+		if (j % 2 == 0) {
+			div2Steps = stepsCount[j / 2 - 1];
+		}
+		minus1Steps = stepsCount[i - 1];
+
+		int minStepsCount = std::min(minus1Steps,
+				std::min(div2Steps, div3Steps));
+		stepsCount[i] = minStepsCount + 1;
+		if (minStepsCount == minus1Steps) {
+			path[i] = 1;
+			continue;
+		}
+		if (minStepsCount == div2Steps) {
+			path[i] = 2;
+			continue;
+		}
+		if (minStepsCount == div3Steps) {
+			path[i] = 3;
 		}
 	}
-	return minNumCoins[money];
+	sequence.push_back(n);
+	while (n > 1) {
+		int i = path[n - 1];
+		if (i == 3) {
+			n = n / 3;
+			sequence.push_back(n);
+			continue;
+		}
+		if (i == 2) {
+			n = n / 2;
+			sequence.push_back(n);
+			continue;
+		}
+		n = n - 1;
+		sequence.push_back(n);
+	}
+	reverse(sequence.begin(), sequence.end());
+	return sequence;
 }
 
-//TEST(SortPoint, Sort1) {
-//	ASSERT_EQ(2, getChange(2));
-//	ASSERT_EQ(9, getChange(34));
+//TEST(PrimitiveCalc, Calc1) {
+//	ASSERT_EQ(2, optimal_sequence(6).size() - 1);
+//}
+//
+//TEST(PrimitiveCalc, Calc2) {
+//	ASSERT_EQ(14, optimal_sequence(96234).size() - 1);
 //}
 
 int main() {
-  int m;
-  std::cin >> m;
-  std::cout << getChange(m) << '\n';
+	int n;
+	std::cin >> n;
+	vector<int> sequence = optimal_sequence(n);
+	std::cout << sequence.size() - 1 << std::endl;
+	for (size_t i = 0; i < sequence.size(); ++i) {
+		std::cout << sequence[i] << " ";
+	}
 }
-- 
cgit v1.2.3