summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py43
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/primitive_calculatorTest.py20
2 files changed, 63 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py b/AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py
new file mode 100644
index 0000000..3451956
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py
@@ -0,0 +1,43 @@
+# Uses python3
+import sys
+
+
+def optimal_sequence(n):
+ sequence = []
+ stepsCount = [0] * n
+ path = [0] * n
+ for i in range(1, n):
+ j = i + 1;
+ div2Steps = float('inf')
+ div3Steps = float('inf')
+ if j % 3 == 0:
+ div3Steps = stepsCount[j // 3 - 1]
+ if j % 2 == 0:
+ div2Steps = stepsCount[j // 2 - 1]
+ minus1Steps = stepsCount[i - 1]
+ stepCountAndType = [(minus1Steps, 1), (div2Steps, 2), (div3Steps, 3)]
+ stepCountAndType.sort()
+ stepsCount[i] = stepCountAndType[0][0] + 1
+ path[i] = stepCountAndType[0][1]
+ sequence.append(n)
+ while n > 1:
+ i = path[n - 1]
+ if i == 3:
+ n = n // 3
+ sequence.append(n)
+ continue
+ if i == 2:
+ n = n // 2
+ sequence.append(n)
+ continue
+ n = n - 1
+ sequence.append(n)
+ return reversed(sequence)
+
+
+input = sys.stdin.read()
+n = int(input)
+sequence = list(optimal_sequence(n))
+print(len(sequence) - 1)
+for x in sequence:
+ print(x, end=' ')
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/primitive_calculatorTest.py b/AlgoDesignAndTechniqueEdxPython/tests/primitive_calculatorTest.py
new file mode 100644
index 0000000..00788d4
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/primitive_calculatorTest.py
@@ -0,0 +1,20 @@
+'''
+Created on Dec 19, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.primitive_calculator import optimal_sequence
+
+
+class Test(unittest.TestCase):
+
+ def testName(self):
+ self.assertEqual(3, len(list(optimal_sequence(5))) - 1)
+ self.assertEqual(14, len(list(optimal_sequence(96234))) - 1)
+
+
+if __name__ == "__main__":
+ # import sys;sys.argv = ['', 'Test.testName']
+ unittest.main()