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: 416b7ca9325abe3c259646309fcb3e689abaff1f
Parent: a9c7828bc78fdc18005836a93bbd43e4da0a6509
Author: Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
Date: Tue, 2 Apr 2019 07:38:43 -0300

Optmized mutiple implementations by caching the sum of the digits of the tested numbers.

Diffstat

8 files changed, 98 insertions, 38 deletions

Status	File Name	N° Changes	Insertions	Deletions
Modified	C/main.c	10	8	2
Modified	Haskell/.gitignore	9	7	2
Modified	Haskell/app/Main.hs	26	14	12
Modified	README.md	12	6	6
Modified	Rust/src/main.rs	22	18	4
Modified	script.js	13	12	1
Modified	script.py	30	20	10
Modified	script.rb	14	13	1

diff --git a/C/main.c b/C/main.c
@@ -1,3 +1,4 @@
+#include <stdlib.h>
 #include <stdio.h>
 #include <time.h>
 
@@ -33,12 +34,17 @@ int main()
     printf("\nLOADING. . .");
     clock_t start = clock(), end;
 
+    int sums_c = 2 * (MAX + 1), *sums;
+    sums = malloc(sizeof(int) * sums_c);
+    for (int i = 0; i <= sums_c; i++)
+        sums[i] = sum_digits(i);
+
     for (int a = 0; a <= MAX; a++)
         for (int b = a; b <= MAX; b++)
-            if ((sum_digits(a + b) - (sum_digits(a) +sum_digits(b))) % 9 != 0)
+            if ((sums[a + b] - (sums[a] + sums[b])) % 9 != 0)
             {
                 end = clock();
-                printf("\nLOADED. . . in %ums\n", (unsigned)((end - start) * 1000 / CLOCKS_PER_SEC));
+                printf("\nLOADED. . . in %ums [1 Thread]\n", (unsigned)((end - start) * 1000 / CLOCKS_PER_SEC));
                 printf("\nThe conjecture is disproved! Here's a counterexample: (%u, %u)", a, b);
 
                 return 0;

diff --git a/Haskell/.gitignore b/Haskell/.gitignore
@@ -1 +1,6 @@
-.stack-work-
\ No newline at end of file
+.stack-work
+src
+test
+*.cabal
+LICENSE
+stack.yaml+
\ No newline at end of file

diff --git a/Haskell/app/Main.hs b/Haskell/app/Main.hs
@@ -21,30 +21,32 @@ main = do
         [(max, "")] -> do
             putStrLn "\nLOADING. . ."
             start <- getTime Monotonic
-
+            
             case counter' 0 max of
-                [] -> do 
+                Nothing -> do
                     end <- getTime Monotonic
                     putStrLn $ "LOADED. . . in " ++ formatMils (end - start) ++ "ms [1 Thread]"
                     putStrLn $ "\nThe conjecture is proved for all natural numbers smaller or equals to " ++ show max ++ "!"
-                counter -> putStrLn $ "\nThe conjecture is disproved! Here's a counterexample: ("++ (show $ fst $ head $counter)
-                    ++ ", " ++ (show $ snd $ head $counter) ++ ")"
+                Just counter -> do
+                    end <- getTime Monotonic
+                    putStrLn $ "LOADED. . . in " ++ formatMils (end - start) ++ "ms [1 Thread]"
+                    putStrLn $ "\nThe conjecture is disproved! Here's a counterexample: (" ++ (show $ fst $ counter) 
+                        ++ ", " ++ (show $ snd $ counter) ++ ")"
                 
         _ -> putStrLn $ "\n'" ++ maxStr ++ "' is not a natural number!"
 
-digs :: Natural -> [Natural]
-digs x = case x of
-    0 -> [0]
-    x -> digs (x `div` 10) ++ [x `mod` 10]
-
 sum' :: Natural -> Natural
-sum' x = sum $ digs x
+sum' x = case x of
+    0 -> 0
+    x -> (x `mod` 10) + sum' (x `div` 10)
 
 test' :: Natural -> Natural -> Bool
 test' a b = ((fromEnum $ sum' (a + b)) - (fromEnum $ sum' a) - (fromEnum $ sum' b)) `mod` 9 == 0
 
-counter' :: Natural -> Natural -> [(Natural, Natural)]
-counter' min max = [(a, b) | a <- [min..max], b <- [a..max], not $ test' a b]
+counter' :: Natural -> Natural -> Maybe (Natural, Natural)
+counter' min max = case [(a, b) | a <- [min..max], b <- [a..max], not $ test' a b] of
+    [] -> Nothing
+    fst : _ -> Just fst
 
 formatMils :: TimeSpec -> [Char]
 formatMils t = show (sec t * 10^3 + nsec t `div` 10^6) 
\ No newline at end of file

diff --git a/README.md b/README.md
@@ -11,9 +11,9 @@ The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by
 
 |Language      |Milliseconds|
 |--------------|------------|
-|**Rust**      |1100        |
-|**C**         |4913        | 
-|**JavaScript**|39168       |
-|**Ruby**      |46253       |
-|**Haskell**   |48263       |
-|**Python**    |134988      |
+|**Rust**      |80          |
+|**C**         |271         | 
+|**JavaScript**|656         |
+|**Ruby**      |9850        |
+|**Python**    |16032       |
+|**Haskell**   |28365       |

diff --git a/Rust/src/main.rs b/Rust/src/main.rs
@@ -52,6 +52,8 @@ fn main() {
 }
 
 fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> {
+    let sums = get_sums(max);
+
     if max / n_threads > 0 && n_threads > 1 {
 
         let (coutexpl_sender, coutexpl_reciever): (Sender<Option<(usize, usize)>>, Receiver<Option<(usize, usize)>>) = mpsc::channel();
@@ -87,9 +89,10 @@ fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> {
         for i in 0..n_threads {
             let thread_countr_sd = coutexpl_sender.clone();
             let thread_range = sub_ranges.pop().unwrap();
+            let thread_sums = sums.clone();
 
             let child = thread::spawn(move || {
-                thread_countr_sd.send(get_range_countrexpl(thread_range, max))
+                thread_countr_sd.send(get_range_countrexpl(thread_range, max, &thread_sums))
                     .expect(&format!("Thread n°{} was unable to sent a message trought the channel", i));
             });
             
@@ -105,14 +108,14 @@ fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> {
 
         None
     } else {
-        get_range_countrexpl((0..max).collect(), max)
+        get_range_countrexpl((0..max).collect(), max, &sums)
     }
 }
 
-fn get_range_countrexpl(range: Vec<usize>, max: usize) -> Option<(usize, usize)> {
+fn get_range_countrexpl(range: Vec<usize>, max: usize, sums: &Vec<isize>) -> Option<(usize, usize)> {
     for a in range {
         for b in a..max {
-            let difference = sum_digits(a + b) - sum_digits(a) - sum_digits(b);
+            let difference = sums[a + b] - sums[a] - sums[b];
 
             if difference % 9 != 0 {
                 return Some((a, b));
@@ -133,4 +136,15 @@ fn sum_digits(n: usize) -> isize {
     }
 
     sum
+}
+
+fn get_sums(max: usize) -> Vec<isize> {
+    let range_max = 2 * (max + 1);
+    let mut output = Vec::with_capacity(range_max);
+
+    for i in 0..range_max {
+        output.push(sum_digits(i));
+    }
+
+    output
 } 
\ No newline at end of file

diff --git a/script.js b/script.js
@@ -19,6 +19,15 @@ Number.prototype.sum = function() {
     return sum;
 }
 
+Number.sums = function getSums(max) {
+    const output = [], maxRange = 2 * (max + 1);
+    
+    for (let i = 0; i <= maxRange; i++)
+        output.push(i.sum());
+
+    return output;
+}
+
 function ask(question) {
     const rl = readline.createInterface({
         input: process.stdin,
@@ -32,9 +41,11 @@ function ask(question) {
 }
 
 function getCounterExp(max) {
+    const sums = Number.sums(max);
+
     for (let a = 1; a <= max; a++)
         for (let b = a; b <= max; b++) {
-            const diff = (a + b).sum() - (a.sum() + b.sum());
+            const diff = sums[a + b] - sums[a] - sums[b];
             if (diff % 9 !== 0) return [a, b];
         }

diff --git a/script.py b/script.py
@@ -5,7 +5,7 @@
 
 from time import time
 
-def sum_digits(n):
+def sum_digits(n: int) -> int:
     parc = abs(n)
     sum_d = 0
 
@@ -15,15 +15,25 @@ def sum_digits(n):
 
     return sum_d
 
-def get_counterexmpl(n):
-    for a in range(n + 1):
-        for b in range(a, n + 1):
-            diff = sum_digits(a + b) - (sum_digits(a) + sum_digits(b))
+def get_counterexmpl(max: int) -> (int, int):
+    sums = get_sums(max)
+
+    for a in range(max + 1):
+        for b in range(a, max + 1):
+            diff = sums[a + b] - sums[a] - sums[b]
 
             if not diff % 9 == 0:
                 return (a, b)
     
-    return None  
+    return None
+
+def get_sums(max: int) -> list:
+    output = []
+
+    for i in range(2 * (max + 1) + 1):
+        output.append(sum_digits(i))
+
+    return output
 
 
 print("\nThis script is a simple test for the following conjecture:\n")
@@ -33,18 +43,18 @@ max_str = input("What value would you like to test the conjecture for? ")
 print("\nLOADING. . .")
 
 try:
-    maximum = int(max_str)
-    if maximum < 0:
+    max = int(max_str)
+    if max < 0:
         raise ValueError
 
     start = time()
-    counterexmpl = get_counterexmpl(maximum)
+    counterexmpl = get_counterexmpl(max)
     elepsed = time() - start
 
     print("LOADED. . . in {:.0f}ms\n".format(elepsed * 10**3))
 
     if counterexmpl == None:
-        print("The conjecture is proved for all natural numbers smaller or equals to {}!".format(maximum))
+        print("The conjecture is proved for all natural numbers smaller or equals to {}!".format(max))
     else:
         (a, b) = counterexmpl
         print("The conjecture is disproved! Here's a counterexample: ({}, {})".format(a, b))

diff --git a/script.rb b/script.rb
@@ -15,12 +15,24 @@ class Integer
 
         return sum
     end
+
+    def self.sums(max)
+        output = []
+        
+        for i in 0..((max + 1) * 2)
+            output << i.sum()
+        end
+
+        return output
+    end
 end
 
 def get_counterexpl(max)
+    sums = Integer.sums(max)
+
     for a in (0..max)
         for b in (a..max)
-            diff = (a + b).sum() - a.sum() - b.sum()
+            diff = sums[a + b] - sums[a] - sums[b]
 
             if diff % 9 != 0
                 return [a, b]