Countdown: Difference between revisions

Content added Content deleted

Inline

@@ Line 36: / Line 36: @@
 use Libraries.Containers.Iterator
 use Libraries.System.DateTime
+use Libraries.Compute.Math
+class Countdown
-action Main
-    DateTime datetime
-    number start = datetime:GetEpochTime()
-    List<integer> numbers
-    numbers:Add(100)
-    numbers:Add(75)
-    numbers:Add(50)
-    numbers:Add(25)
-    numbers:Add(6)
-    numbers:Add(3)
-    Solution(952,numbers)
-    number stop = datetime:GetEpochTime()
-    output stop-start + " ms"
-end
+    integer best = 0
-action Solution(integer target, List<integer> numbers) returns boolean
+    action Main
+        DateTime datetime
+        number start = datetime:GetEpochTime()
+        List<integer> numbers
+        numbers:Add(100)
+        numbers:Add(75)
+        numbers:Add(50)
+        numbers:Add(25)
+        numbers:Add(6)
+        numbers:Add(3)
+        if not Solution(952,0,numbers)
+            output "Best solution found is " + best
+        end
+        number stop = datetime:GetEpochTime()
+        output stop-start + " ms"
+    end
+    action Solution(integer target, integer res, List<integer> numbers) returns boolean
-    if numbers:GetSize() = 1
-        return false
-    end
+        Math math
+        // Check closest solution
-    Iterator<integer> it0 = numbers:GetIterator()
+        if math:AbsoluteValue(target-best) > math:AbsoluteValue(target-res)
-    repeat while it0:HasNext()
+            best = res
-        integer n0 = it0:Next()
+        end
+        // No remaining operations to be done
-        List<integer> numbers1 = cast(List<integer>, numbers:Copy())
-        numbers1:Remove(n0)
+        if numbers:GetSize() = 0
+            return false
+        end
-        Iterator<integer> it1 = numbers1:GetIterator()
-        repeat while it1:HasNext()
+        // Initial call only
+        if res not= 0
+            numbers:Add(res)
+        end
-            integer n1 = it1:Next()
+        Iterator<integer> it0 = numbers:GetIterator()
+        repeat while it0:HasNext()
-            List<integer> numbers2 = cast(List<integer>, numbers1:Copy())
-            numbers2:Remove(n1)
+            integer n0 = it0:Next()
-            integer res = 0
+            List<integer> numbers1 = cast(List<integer>, numbers:Copy())
-            List<integer> numbersNew
+            numbers1:Remove(n0)
-            res = n0 + n1
+            Iterator<integer> it1 = numbers1:GetIterator()
-            numbersNew = cast(List<integer>, numbers2:Copy())
+            repeat while it1:HasNext()
-            numbersNew:Add(res)
-            if res = target or Solution(target, numbersNew)
+                integer n1 = it1:Next()
-                output res + " = " + n0 + " + " + n1
+                List<integer> numbers2 = cast(List<integer>, numbers1:Copy())
-                return true
+                numbers2:Remove(n1)
-            end
+                res = n0 + n1
-            res = n0 * n1
+                if res = target or Solution(target, res, cast(List<integer>, numbers2:Copy()))
-            numbersNew = cast(List<integer>, numbers2:Copy())
+                    output res + " = " + n0 + " + " + n1
-            numbersNew:Add(res)
-            if res = target or Solution(target, numbersNew)
-                output res + " = " + n0 + " * " + n1
-                return true
-            end
-            if n0 < n1
-                integer temp = n0
-                n0 = n1
-                n1 = temp
-            end
-            if n0 not= n1
-                res = n0 - n1
-                numbersNew = cast(List<integer>, numbers2:Copy())
-                numbersNew:Add(res)
-                if res = target or Solution(target, numbersNew)
-                    output res + " = " + n0 + " - " + n1
                     return true
                 end
-            end
+                res = n0 * n1
+                if res = target or Solution(target, res, cast(List<integer>, numbers2:Copy()))
-            if n0 mod n1 = 0
-                res = n0 / n1
+                    output res + " = " + n0 + " * " + n1
-                numbersNew = cast(List<integer>, numbers2:Copy())
-                numbersNew:Add(res)
-                if res = target or Solution(target, numbersNew)
-                    output res + " = " + n0 + " / " + n1
                     return true
+                end
+                // Substraction and division are not symetrical operations
+                if n0 < n1
+                    integer temp = n0
+                    n0 = n1
+                    n1 = temp
+                end
+                if n0 not= n1
+                    res = n0 - n1
+                    if res = target or Solution(target, res, cast(List<integer>, numbers2:Copy()))
+                        output res + " = " + n0 + " - " + n1
+                        return true
+                    end
+                end
+                if n0 mod n1 = 0
+                    res = n0 / n1
+                    if res = target or Solution(target, res, cast(List<integer>, numbers2:Copy()))
+                        output res + " = " + n0 + " / " + n1
+                        return true
+                    end
                 end
             end
         end
+        return false
     end
-    return false
 end
 </syntaxhighlight>