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: 88251862236f73786a82176370f9c72c23dc9603
Parent: 5e3f5a5499df3af91c5902f3993376e6fdff8c5c
Author: Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
Date: Fri, 29 Mar 2019 16:58:31 -0300

Optimized the Rust implementation and stated creating a C implementation.

The rust implementation was optmized by removing the get_digits(n: usize) -> Vec<usize>.

Diffstat

13 files changed, 197 insertions, 51 deletions

Status	File Name	N° Changes	Insertions	Deletions
Added	..gitignore.un~	0	0	0
Added	.README.md.un~	0	0	0
Modified	.gitignore	6	4	2
Added	.gitignore~	6	6	0
Added	C/main.c	148	148	0
Modified	Haskell/app/Main.hs	2	1	1
Modified	README.md	3	2	1
Copied	README.md -> README.md~	0	0	0
Modified	Rust/src/main.rs	62	23	39
Modified	script.js	2	1	1
Modified	script.py	7	4	3
Modified	script.rb	10	7	3
Modified	script.ts	2	1	1

diff --git a/..gitignore.un~ b/..gitignore.un~
Binary files differ.

diff --git a/.README.md.un~ b/.README.md.un~
Binary files differ.

diff --git a/.gitignore b/.gitignore
@@ -2,4 +2,7 @@
 *.exe
 *.ts.js
 Statistics
-Latex-
\ No newline at end of file
+Latex
+X86
+C/*
+!C/main.c

diff --git a/.gitignore~ b/.gitignore~
@@ -0,0 +1,6 @@
+.vscode
+*.exe
+*.ts.js
+Statistics
+Latex
+X86

diff --git a/C/main.c b/C/main.c
@@ -0,0 +1,147 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <errno.h>
+#include <time.h>
+
+// This 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 integer.
+
+enum capacity {None, Single, Tuple};
+
+typedef struct option
+{
+    enum capacity status;
+    unsigned int *value;
+}option;
+
+option *none()
+{
+    option *output = malloc(sizeof(option));
+    output->status = None;
+
+    return output;
+}
+
+option *single(unsigned int n)
+{
+    option *output = malloc(sizeof(option));
+    output->status = Single;
+    output->value = &n;
+
+    return output;
+}
+
+option *tuple(unsigned int a, unsigned int b)
+{
+    option *output = malloc(sizeof(option));
+    output->status = Tuple;
+
+    static unsigned int value[2];
+    value[0] = a;
+    value[1] = b;
+    output->value = &value;
+
+    return output;
+}
+
+int sum_digits(unsigned int n) {
+    int parc = n;
+    int sum = 0;
+
+    while (parc > 0)
+    {
+        sum += parc % 10;
+        parc /= 10;
+    }
+
+    return sum;
+}
+
+option *get_counter_exp(unsigned int max) {
+    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)
+                return tuple(a, b);
+
+    return none();
+}
+
+option *parse_int(const char * str) {
+    char *end;
+    for (long i = strtol(str, &end, 10); str != end;)
+    {
+        if (errno == ERANGE)
+        {
+            errno = 0;
+            return none();
+        }
+
+        return i >= 0 ? single((unsigned int)i) : none();
+    }
+
+    return none();
+}
+
+char *scan_line(char *line)
+{
+    int ch;
+
+    if((line = malloc(sizeof(char))) == NULL)
+    {
+        printf("Unsuccessful allocation");
+        exit(1);
+    }
+
+    line[0]='\0';
+
+    for(int i = 0; ((ch = getchar())!='\n') && (ch != EOF) ; i++)
+    {
+        if((line = realloc(line, sizeof(char) * (i + 2))) == NULL)
+        {
+            printf("Unsuccessful reallocation");
+            exit(1);
+        }
+
+        line[i] = (char)ch;
+        line[i + 1] = '\0'; //inserting null character at the end
+    }
+
+    return line;
+}
+
+int main() {
+    printf("\nThis program is a simple test for the following conjecture:\n");
+    printf("Let S: N -> N be the sum of the digits of a positive integer.\n");
+    printf("For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.\n");
+    printf("\nWhat value would you like to test the conjecture for?");
+
+    const char *MAX_STR = scan_line(NULL);
+    unsigned int MAX;
+    option *MAX_OPT = parse_int(MAX_STR);
+
+    if (MAX_OPT->status != None)
+        MAX = *MAX_OPT->value;
+    else
+    {
+        printf("\n'%s' is not a natural number!", MAX_STR);
+        return 0;
+    }
+
+    printf("\nLOADING. . .");
+
+    clock_t start, end;
+    start = clock();
+    const option *counter_expl = get_counter_exp(MAX);
+    end = clock();
+    printf("\nLOADED. . . in %.1fs\n", (float)(end - start) / CLOCKS_PER_SEC);
+
+    if (counter_expl->status == None)
+        printf("\nThe conjecture is proved for all natural numbers smaller or equals to %u!", MAX);
+    else printf("\nThe conjecture is disproved! Here is a counter example: (%u, %u)",
+            *counter_expl->value,*(counter_expl->value + sizeof(unsigned int)));
+
+    return 0;
+}+
\ No newline at end of file

diff --git a/Haskell/app/Main.hs b/Haskell/app/Main.hs
@@ -20,8 +20,8 @@ main = do
 
     case readDec maxStr :: [(Natural, String)] of
         [(max, "")] -> do
-            start <- getTime Monotonic
             putStrLn "\nLOADING. . ."
+            start <- getTime Monotonic
 
             case exceptions' 0 max of
                 [] -> do

diff --git a/README.md b/README.md
@@ -11,7 +11,8 @@ The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by
 
 |Language      |Time   |
 |--------------|-------|
-|**Rust**      |14 _s_ |
+|**Rust**      |0 _s_  |
+|**C**         |5 _s_  | 
 |**Haskell**   |48 _s_ |
 |**TypeScript**|181 _s_|
 |**JavaScript**|191 _s_|

diff --git a/README.md b/README.md~

diff --git a/Rust/src/main.rs b/Rust/src/main.rs
@@ -31,42 +31,34 @@ fn main() {
 
     // Listen for user input
     let _ = prompt.write("\nWhat value would you like to test the conjecture for? ");
-    let user_input = input().read_line().unwrap_or(String::new());
+    let user_input = input().read_line().unwrap_or_default();
 
     match user_input.trim().parse::<usize>() {
         Ok(max) => {
             println!("\nLOADING. . .");
             let start_time = Instant::now();
-            let counterexpls = get_all_countrexpls(max, n_threads);
+            let counterexpl = get_countrexpl(max, n_threads);
             let duration = start_time.elapsed();
 
             // Print the results
             println!("LOADED. . . in {}s [{} Threads]\n", duration.as_secs(), n_threads);
-            if counterexpls.len() == 0 {
-                println!("The conjecture is proved for all natural numbers smaller or equals to {}!", max);
-            } else {
-                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(", "));
+            match counterexpl {
+                None => println!("The conjecture is proved for all natural numbers smaller or equals to {}!", max),
+                Some((a, b)) => println!("The conjecture is disproved! Here's a counter example: ({}, {})", a, b)
             }
         }, 
         Err(_) => println!("'{}' is not a natural number!", user_input.trim())
     }
 }
 
-fn get_all_countrexpls(max: usize, n_threads: usize) -> Vec<(usize, usize)> {
+fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> {
     if max / n_threads > 0 && n_threads > 1 {
 
-        // Thread related variables
-        let (coutexpl_sender, coutexpl_reciever): (Sender<Vec<(usize, usize)>>, Receiver<Vec<(usize, usize)>>) = mpsc::channel();
+        let (coutexpl_sender, coutexpl_reciever): (Sender<Option<(usize, usize)>>, Receiver<Option<(usize, usize)>>) = mpsc::channel();
         let mut child_threads = Vec::with_capacity(n_threads);
         let range_lenght = max / n_threads;
         let mut range: Vec<usize> = (0..max).collect();
 
-        // Conjecture related variables
-        let mut counterexpls: Vec<(usize, usize)> = Vec::new();
-
         // Shuffle the values in the range to get an even distribution of
         // calculations across all threads
         range.shuffle(&mut thread_rng());
@@ -97,56 +89,48 @@ fn get_all_countrexpls(max: usize, n_threads: usize) -> Vec<(usize, usize)> {
             let thread_range = sub_ranges.pop().unwrap();
 
             let child = thread::spawn(move || {
-                thread_countr_sd.send(get_range_countrexpls(thread_range, max))
+                thread_countr_sd.send(get_range_countrexpl(thread_range, max))
                     .expect(&format!("Thread n°{} was unable to sent a message trought the channel", i));
             });
             
             child_threads.push(child);
-            counterexpls.append(&mut coutexpl_reciever.recv().unwrap());
+            if let Ok(Some(c_expl)) = coutexpl_reciever.recv() {
+                return Some(c_expl);
+            }
         }
 
         for child in child_threads {
             child.join().expect("Child thread panicked");
         }
 
-        counterexpls
+        None
     } else {
-        get_range_countrexpls((0..max).collect(), max)
+        get_range_countrexpl((0..max).collect(), max)
     }
 }
 
-fn get_range_countrexpls(range: Vec<usize>, max: usize) -> Vec<(usize, usize)> {
-    let mut counterexpls = Vec::new();
-
+fn get_range_countrexpl(range: Vec<usize>, max: usize) -> Option<(usize, usize)> {
     for a in range {
         for b in a..max {
             let difference = sum_digits(a + b) - sum_digits(a) - sum_digits(b);
 
             if difference % 9 != 0 {
-                counterexpls.push((a, b));
+                return Some((a, b));
             }
         }
     }
 
-    counterexpls
+    None
 }
 
-fn get_digits(n: usize) -> Vec<usize> {
-    if n == 0 {
-        vec![0]
-    } else {
-        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;
-        }
+fn sum_digits(n: usize) -> isize {
+    let mut sum = 0;
+    let mut part = n;
 
-        output
+    while part != 0 {
+        sum += (part % 10) as isize;
+        part /= 10;
     }
-}
 
-fn sum_digits(n: usize) -> isize {
-    get_digits(n).iter().sum::<usize>() as isize
+    sum
 } 
\ No newline at end of file

diff --git a/script.js b/script.js
@@ -1,4 +1,4 @@
-// The following script is a simple test for the following conjecture:
+// 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.

diff --git a/script.py b/script.py
@@ -1,4 +1,4 @@
-# The following script is a simple test for the following conjecture:
+# 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.
@@ -22,7 +22,7 @@ def get_counterexmpls(n):
             if not diff % 9 == 0:
                 counterexmpls.append((a, b))
     
-    return counterexmpls    
+    return counterexmpls   
 
 
 print("\nThis script is a simple test for the following conjecture:\n")
@@ -46,4 +46,4 @@ try:
         print("The conjecture is disproved! Here are the counter examples:")
         print(", ".join(map(lambda pair: "({}, {})".format(pair[0], pair[1]), counterexmpls)))
 except:
-    print("'{}' isn't a natural number!".format(user_input))
+    print("'{}' isn't a natural number!".format(user_input))+
\ No newline at end of file

diff --git a/script.rb b/script.rb
@@ -1,10 +1,15 @@
+# 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.
+
 class Integer
     def divides(n)
         return n % self == 0
     end
 
     def digits(base: 10)
-        quotient, remainder = divmod(base)
+        (quotient, remainder) = divmod(base)
         return quotient == 0 ? [remainder] : [*quotient.digits(base: base), remainder]
     end
 
@@ -30,13 +35,12 @@ end
 
 puts "\nThis 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"
+puts "For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer.\n\n"
 puts "What value would you like to test the conjecture for?"
 
 user_input = gets
 puts "\nLOADING. . ."
 
-# Check if the input provided by the user in an iteger
 if /^\d+$/.match(user_input.chomp)
     max = user_input.chomp.to_i
     start = Time.now

diff --git a/script.ts b/script.ts
@@ -1,4 +1,4 @@
-// The following script is a simple test for the following conjecture:
+// 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.