From c023f45e82a5631319563be730f5e7aea9eee861 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 19 Dec 2018 21:28:32 -0600
Subject: Primitive calculator done!

This isn't too bad after I worked out the algo in Java first.---
 .../sources/primitive_calculator.py                | 43 ++++++++++++++++++++++
 1 file changed, 43 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources/primitive_calculator.py')

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=' ')
-- 
cgit v1.2.3