a-conjecture-of-mine

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

Commit
603cba9fb6a4b9074f2df50a591e41049a4c0941
Parent
16e9d394f26efcb584a1a61bc8153acb16f1b5fe
Author
Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
Date

Optimized the rust implementation

Preallocated space for vectors of known capacity.

Diffstat

10 files changed, 61 insertions, 105 deletions

Status File Name N° Changes Insertions Deletions
Modified .gitignore 2 2 0
Modified Haskell/app/Main.hs 8 5 3
Modified README.md 12 6 6
Modified Rust/src/main.rs 21 13 8
Modified script.js 49 16 33
Deleted script.min.js 2 0 2
Modified script.py 26 8 18
Modified script.rb 17 3 14
Modified script.ts 24 8 16
Deleted script.ts.js 5 0 5
diff --git a/.gitignore b/.gitignore
@@ -1,3 +1,5 @@
+.vscode
 *.exe
+*.ts.js
 Statistics
 Latex 
\ No newline at end of file
diff --git a/Haskell/app/Main.hs b/Haskell/app/Main.hs
@@ -1,3 +1,8 @@
+-- The following program is a simple test for the following conjecture:
+
+-- Let S: N -> N be the sum of the digits of a positive integer.
+-- For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
+
 module Main where
 
 import Numeric
@@ -7,9 +12,6 @@ import GHC.Conc
 
 main :: IO ()
 main = do
-    -- Configure the number of threads used by the program
-    setNumCapabilities 1
-
     putStrLn "\nThis program is a simple test for the following conjecture:\n"
     putStrLn "Let S: N -> N be the sum of the digits of a positive integer."
     putStrLn "For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n"
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# Conjecture Testing
+# A Conjecture of Mine
 An exercise on _polyglossy_. The same problem solved on multiple languages.
 
 ## Problem
@@ -11,9 +11,9 @@ The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by
 
 |Language      |Time   |Number of Threads Used|
 |--------------|-------|----------------------|
-|**Rust**      |22 _s_ |2                     |
-|**Haskell**   |48 _s_ |1                     |
-|**JavaScript**|197 _s_|1                     |
-|**TypeScript**|219 _s_|1                     |
+|**Rust**      |15 _s_ |2                     |
+|**Haskell**   |58 _s_ |1                     |
+|**TypeScript**|212 _s_|1                     |
+|**JavaScript**|224 _s_|1                     |
 |**Ruby**      |273 _s_|1                     |
-|**Python**    |522 _s_|1                     |
+|**Python**    |562 _s_|1                     |
diff --git a/Rust/src/main.rs b/Rust/src/main.rs
@@ -35,8 +35,8 @@ fn main() {
 
     match user_input.trim().parse::<usize>() {
         Ok(max) => {
-            let start_time = Instant::now();
             println!("\nLOADING. . .");
+            let start_time = Instant::now();
             let counterexpls = get_all_countrexpls(max, n_threads);
             let duration = start_time.elapsed();
 
@@ -48,7 +48,7 @@ fn main() {
                 println!("The conjecture is disproved! Here are the counter examples:");
 
                 let counterexpls_str: Vec<String> = counterexpls.iter().map(|(a, b)| format!("({}, {})", a, b)).collect();
-                println!("{}\n", counterexpls_str.join(","));
+                println!("{}\n", counterexpls_str.join(", "));
             }
         }, 
         Err(_) => println!("'{}' is not a natural number!", user_input.trim())
@@ -60,7 +60,7 @@ fn get_all_countrexpls(max: usize, n_threads: usize) -> Vec<(usize, usize)> {
 
         // Thread related variables
         let (coutexpl_sender, coutexpl_reciever): (Sender<Vec<(usize, usize)>>, Receiver<Vec<(usize, usize)>>) = mpsc::channel();
-        let mut child_threads = Vec::new();
+        let mut child_threads = Vec::with_capacity(n_threads);
         let range_lenght = max / n_threads;
         let mut range: Vec<usize> = (0..max).collect();
 
@@ -72,7 +72,7 @@ fn get_all_countrexpls(max: usize, n_threads: usize) -> Vec<(usize, usize)> {
         range.shuffle(&mut thread_rng());
 
         // Separate a specific slice of the range and assign it to the thread
-        let mut sub_ranges = Vec::new();
+        let mut sub_ranges = Vec::with_capacity(n_threads);
         for i in 0..n_threads {
             let start = i * range_lenght;
             let end = start + range_lenght;
@@ -81,7 +81,7 @@ fn get_all_countrexpls(max: usize, n_threads: usize) -> Vec<(usize, usize)> {
 
         // Account for the fact that the maximum number tested may not be
         // a multiple of the numbers of threads used for computations, hence
-        // the number of test performed by each thread may not be constant
+        // the number of tests performed by each thread may not be constant
         if max % n_threads != 0 {
             let mut rng = thread_rng();
             let end = sub_ranges.len() - 1;
@@ -135,10 +135,15 @@ fn get_digits(n: usize) -> Vec<usize> {
     if n == 0 {
         vec![0]
     } else {
-        let mut digs = vec![n % 10];
-        digs.append(&mut get_digits(n / 10));
+        let mut output = Vec::with_capacity((n as f64).log(10.0).floor() as usize + 2);
+        let mut part = n;
+
+        while part != 0 {
+            output.push(part % 10);
+            part /= 10;
+        }
 
-        digs
+        output
     }
 }
 
diff --git a/script.js b/script.js
@@ -5,36 +5,28 @@
 
 const readline = require('readline');
 
-Array.prototype.none = function() {
-    return this.length == 0;
-}
-
 Number.prototype.digits = function() {
-    return Array.from(String(this)).map(char => Number(char));
-}
-
-Number.prototype.divides = function(n) {
-    return (n / this) % 1 == 0;
+    return Array.from(Math.abs(Math.round(this)).toString()).map(char => Number(char));
 }
 
 Number.prototype.sumDigits = function() {
     return this.digits().reduce((a, b) => a + b);
 }
 
-function askQuestion(query) {
+function ask(question) {
     const rl = readline.createInterface({
         input: process.stdin,
         output: process.stdout,
     });
 
-    return new Promise(resolve => rl.question(query, ans => {
+    return new Promise(resolve => rl.question(question, ans => {
         rl.close();
         resolve(ans);
     }))
 }
 
 function getCounterExp(max) {
-    const starTime = new Date();
+    const starTime = new Date;
 
     const counterexmpls = [];
     let loadBar = 0;
@@ -49,39 +41,30 @@ function getCounterExp(max) {
             console.log(`LOADING. . . ${loadBar}%`);
         }
 
-        for (b = a; b <= max; b++) {
-            // Check if the difference between S(a + b) and (S(a) + S(b)) is a multiple of 9
-            const conjectureHolds = (9).divides((a + b).sumDigits() - (a.sumDigits() + b.sumDigits()));
-            if (!conjectureHolds) counterexmpls.push([a, b]);
+        for (let b = a; b <= max; b++) {
+            const diff = (a + b).sumDigits() - (a.sumDigits() + b.sumDigits());
+            if (diff % 9 !== 0) counterexmpls.push([a, b]);
         }
     }
 
-    const elepsedTime = (new Date() - starTime) / 1000;
-    console.clear();
-    console.log(`LOADED. . . ${loadBar}% in ${elepsedTime}s\n`);
+    const elepsedTime = Math.round((new Date().getTime() - starTime.getTime()) / 100) / 10;
+    console.log(`LOADED. . . in ${elepsedTime}s\n`);
     return counterexmpls;
 }
 
-console.log(`This script is a simple test for the following conjecture:
-    
-Let S: N -> N be the sum of the digits of a positive integer.
-For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
-`);
+console.log("\nThis script is a simple test for the following conjecture:\n");
+console.log("Let S: N -> N be the sum of the digits of a positive integer.");
+console.log("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n");
 
-askQuestion("What value would you like to test the conjecture for? ").then(ans => {
+ask("What value would you like to test the conjecture for? ").then(ans => {
     if (!isNaN(Number(ans))) {
         const max = Math.round(Number(ans)), counterexmpls = getCounterExp(max);
 
-        if (counterexmpls.none())
+        if (counterexmpls.length === 0)
             console.log(`The conjecture is proved for all natural numbers smaller or equals to ${max}!`);
         else {
             console.log("The conjecture is disproved! Here are the counter examples:");
-
-            let counterexmplsStr = "";
-            for (pair in counterexmpls)
-                counterexmpls = `${counterexmplsStr}, (${pair[0]}, ${pair[1]})`;
-            
-            console.log(counterexmplsStr);
+            console.log(counterexmpls.map(pair => `(${pair[0]}, ${pair[1]})`).join(", "));
         }
-    } else console.log(`'${ans}' is not an interger!`);
+    } else console.log(`'${ans}' is not a natural number!`);
 }); 
\ No newline at end of file
diff --git a/script.min.js b/script.min.js
@@ -1 +0,0 @@
-const e=require("readline");Array.prototype.t=function(){return 0==this.length},Number.prototype.o=function(){return Array.from(String(this)).map(e=>Number(e))},Number.prototype.s=function(e){return e/this%1==0},Number.prototype.i=function(){let e=0;const t=this.o();for(n of t)e+=n;return e},console.log("This script is a simple test for the following conjecture:\n    \nLet S: N -> N be the sum of the digits of a positive integer.\nFor all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n"),function(n){const t=e.createInterface({input:process.stdin,output:process.stdout});return new Promise(e=>t.question(n,n=>{t.close(),e(n)}))}("What value would you like to test the conjecture for? ").then(e=>{if(isNaN(Number(e)))console.log(`'${e}' is not an interger!`);else{const n=Math.round(Number(e)),t=function(e){const n=new Date,t=[];let r=0;for(let n=1;n<=e;n++){const o=Math.round(100*n/e);for(r!=o&&(console.clear(),r=o,console.log(`LOADING. . . ${r}%`)),b=n;b<=e;b++)9..s((n+b).i()-(n.i()+b.i()))||t.push([n,b])}const o=(new Date-n)/1e3;return console.clear(),console.log(`LOADED. . . ${r}% in ${o}s\n`),t}(n);if(t.t())console.log(`The conjecture is proved for all natural numbers smaller or equals to ${n}!`);else{console.log("The conjecture is disproved! Here are the counter examples:");let e="";for(pair in t)t=`${e}, (${pair[0]}, ${pair[1]})`;console.log(e)}}});-
\ No newline at end of file
diff --git a/script.py b/script.py
@@ -3,9 +3,7 @@
 # Let S: N -> N be the sum of the digits of a positive integer.
 # For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
 
-import sys
-import os
-import time
+import sys, os, time
 from functools import reduce
 
 # A function for clearing the prompt
@@ -35,21 +33,18 @@ def get_counterexmpls(n):
             diff = sum_digits(a + b) - (sum_digits(a) + sum_digits(b))
 
             if not diff % 9 == 0:
-                counterexmpls.append([a, b])
+                counterexmpls.append((a, b))
 
     # Mesure the elepsed time
     elepsed = time.time() - start
-    clear()
-    print("LOADED. . . {}% in {}s\n".format(load_bar, elepsed))
+    print("LOADED. . . in {:.1f}s\n".format(elepsed))
     
     return counterexmpls    
 
 
-print("""The following script is a simple test for the following conjecture:
-
-Let S: N -> N be the sum of the digits of a positive integer.
-For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
-""")
+print("\nThe following script is a simple test for the following conjecture:\n")
+print("Let S: N -> N be the sum of the digits of a positive integer.")
+print("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n")
 user_input = input("What value would you like to test the conjecture for? ")
 
 try:
@@ -61,11 +56,6 @@ try:
         print("The conjecture is proved for all natural numbers smaller or equals to {}!".format(maximum))
     else:
         print("The conjecture is disproved! Here are the counter examples:")
-
-        counterexmpls_str = ""
-        for pair in counterexmpls:
-            counterexmpls_str = "{}, ({}, {})".format(counterexmpls_str, pair[0], pair[1])
-        
-        print(counterexmpls_str)
+        print(", ".join(map(lambda pair: "({}, {})".format(pair[0], pair[1]), counterexmpls)))
 except:
-    print("'{}' isn't a valid number!".format(user_input))
+    print("'{}' isn't a natural number!".format(user_input))
diff --git a/script.rb b/script.rb
@@ -58,14 +58,6 @@ def clear
     end
 end
 
-def pause
-    if /win32|win64|\.NET|windows|cygwin|mingw32/i.match(RUBY_PLATFORM)
-        system('pause')
-    else
-        system('read')
-    end
-end
-
 puts "The following script is a simple test for the following conjecture:\n\n"
 puts "Let S: N -> N be the sum of the digits of a positive integer."
 puts "For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n\n"
@@ -75,7 +67,7 @@ user_input = gets
 
 # Check if the input provided by the user in an iteger
 if /^(?:-?[1-9]\d*$)|(?:^0)$/.match(user_input)
-    max = user_input.to_i()
+    max = user_input.to_i
     counterexpls = get_counterexpls(max)
 
     if counterexpls.length == 0
@@ -92,7 +84,4 @@ if /^(?:-?[1-9]\d*$)|(?:^0)$/.match(user_input)
     end
 else
     puts "'#{user_input.chomp}' isn't an iteger!"
-end
-
-puts ""
-pause()-
\ No newline at end of file
+end+
\ No newline at end of file
diff --git a/script.ts b/script.ts
@@ -35,7 +35,7 @@ function getCounterExp(max: number) {
 
     for (let a = 0; a <= max; a++) {
 
-        const newLoadBar = a * 100 / max;
+        const newLoadBar = Math.round(a * 100 / max);
         if (loadBar != newLoadBar) {
             console.clear();
             loadBar = newLoadBar;
@@ -46,17 +46,14 @@ function getCounterExp(max: number) {
             if (!test(a, b)) counterexmpls.push([a, b]);
     }
 
-    const elepsedTime = (new Date().getTime() - starTime.getTime()) / 1000;
-    console.clear();
-    console.log(`LOADED. . . ${loadBar}% in ${elepsedTime}s\n`);
+    const elepsedTime = Math.round((new Date().getTime() - starTime.getTime()) / 100) / 10;
+    console.log(`LOADED. . . in ${elepsedTime}s\n`);
     return counterexmpls;
 }
 
-console.log(`This script is a simple test for the following conjecture:
-    
-Let S: N -> N be the sum of the digits of a positive integer.
-For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
-`);
+console.log("\nThis script is a simple test for the following conjecture:\n");
+console.log("Let S: N -> N be the sum of the digits of a positive integer.");
+console.log("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n");
 
 ask("What value would you like to test the conjecture for? ").then(ans => {
     if (!isNaN(parseInt(ans))) {
@@ -66,12 +63,7 @@ ask("What value would you like to test the conjecture for? ").then(ans => {
             console.log(`The conjecture is proved for all natural numbers smaller or equals to ${max}!`);
         else {
             console.log("The conjecture is disproved! Here are the counter examples:");
-
-            let counterexmplsStr = "";
-            for (const pair of counterexmpls)
-                counterexmplsStr = `${counterexmplsStr}, (${pair[0]}, ${pair[1]})`;
-            
-            console.log(counterexmplsStr);
+            console.log(counterexmpls.map(pair => `(${pair[0]}, ${pair[1]})`).join(", "));
         }
-    } else console.log(`'${ans}' is not an interger!`);
+    } else console.log(`'${ans}' is not a natural number!`);
 }).catch(console.error); 
\ No newline at end of file
diff --git a/script.ts.js b/script.ts.js
@@ -1,4 +0,0 @@
-// The following script is a simple test for the following conjecture:
-// Let S: N -> N be the sum of the digits of a positive integer.
-// For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.
-const e=require("readline");function o(e){return function(e){return Array.from(Math.round(Math.abs(e)).toString()).map(e=>parseInt(e))}(e).reduce((e,o)=>e+o)}function t(e,t){return(o(e+t)-(o(e)+o(t)))%9==0}console.log("This script is a simple test for the following conjecture:\n    \nLet S: N -> N be the sum of the digits of a positive integer.\nFor all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an interger.\n"),function(o){const t=e.createInterface({input:process.stdin,output:process.stdout});return new Promise(e=>t.question(o,o=>{t.close(),e(o)}))}("What value would you like to test the conjecture for? ").then(e=>{if(isNaN(parseInt(e)))console.log(`'${e}' is not an interger!`);else{const o=parseInt(e),n=function(e){const o=new Date,n=[];let r=0;for(let o=0;o<=e;o++){const s=100*o/e;r!=s&&(console.clear(),r=s,console.log(`LOADING. . . ${r}%`));for(let r=o;r<=e;r++)t(o,r)||n.push([o,r])}const s=((new Date).getTime()-o.getTime())/1e3;return console.clear(),console.log(`LOADED. . . ${r}% in ${s}s\n`),n}(o);if(0==n.length)console.log(`The conjecture is proved for all natural numbers smaller or equals to ${o}!`);else{console.log("The conjecture is disproved! Here are the counter examples:");let e="";for(const o of n)e=`${e}, (${o[0]}, ${o[1]})`;console.log(e)}}}).catch(console.error);-
\ No newline at end of file