a-conjecture-of-mine

An exercise on polyglossy: the same problem solved on multiple languages

git clone: git://git.pablopie.xyz/a-conjecture-of-mine
Log
Files
Refs

Commit: 5ebfb1b49ac5de87d00137d89d22b3d55f30201a
Parent: 145ef3b83b6887e610b12efbf01f88e854e024d1
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Fri, 27 Dec 2019 11:35:52 -0200

Optimized the Elixir implementation to cache the values of `sum n`.

Currently the values are cached in a per-process-basis. The implementation could be further optimized if we were able to cache the values globally. This could be accoplished via message passing, sending requests to the `main` process and collecting the responses.

Diffstat

1 file changed, 40 insertions, 17 deletions

Status	File Name	N° Changes	Insertions	Deletions
Modified	Elixir/digital_sum.ex	57	40	17

diff --git a/Elixir/digital_sum.ex b/Elixir/digital_sum.ex
@@ -34,33 +34,47 @@ defmodule Conjecture do
   def get_counterexpl start, max, n_processes do
     receive do
       parent_pid ->
-        if counterexpl start, max, n_processes do
-          send parent_pid, :fail
-        else
-          send parent_pid, :ok
+        case counterexpl start, max, n_processes, %{} do
+          :found -> send parent_pid, :fail
+          _ -> send parent_pid, :ok
         end
     end
   end
 
-  def counterexpl a, max, n_processes do
-    cond do
-      iter a, 0 -> true
-      a + n_processes <= max ->
-        counterexpl (a + n_processes), max, n_processes
-      true -> false
+  def counterexpl a, max, n_processes, sums_cache do
+    case iter a, 0, sums_cache do
+      :found -> :found
+      sums_cache_updated ->
+        if a + n_processes <= max do
+          counterexpl (a + n_processes), max, n_processes, sums_cache_updated
+        else
+          sums_cache_updated
+        end
     end
   end
 
-  def iter a, b do
-    cond do
-      test a, b -> true
-      b + 1 < a -> iter a, b + 1
-      true -> false
+  def iter a, b, sums_cache do
+    case test a, b, sums_cache do
+      :found -> :found
+      sums_cache_updated ->
+        if b + 1 < a do
+          iter a, b + 1, sums_cache_updated
+        else
+          sums_cache_updated
+        end
     end
   end
 
-  def test a, b do
-    0 != rem(sum(a + b) - sum(a) - sum(b), 9)
+  def test a, b, sums_cache do
+    {sums_cache_a, sum_a} = lookup sums_cache, a
+    {sums_cache_b, sum_b} = lookup sums_cache_a, b
+    {sums_cache_a_b, sum_a_b} = lookup sums_cache_b, a + b
+
+    if 0 != rem(sum_a_b - sum_a - sum_b, 9) do
+      :found
+    else
+      sums_cache_a_b
+    end
   end
 
   def sum 0 do 0 end
@@ -71,4 +85,13 @@ defmodule Conjecture do
 
     d + sum r
   end
+
+  def lookup map, n do
+    if Map.has_key? map, n do
+      {map, map[n]}
+    else
+      sum_n = sum n
+      {Map.put(map, n, sum_n), sum_n}
+    end
+  end
 end