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: a9c7828bc78fdc18005836a93bbd43e4da0a6509
Parent: 88251862236f73786a82176370f9c72c23dc9603
Author: Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
Date: Sat, 30 Mar 2019 20:38:53 -0300

Optimized the JS, Python, Ruby and C implementations.

The TS implementation was removed from the repo.

Diffstat

13 files changed, 109 insertions, 297 deletions

Status	File Name	N° Changes	Insertions	Deletions
Deleted	..gitignore.un~	0	0	0
Deleted	.README.md.un~	0	0	0
Modified	.gitignore	3	0	3
Deleted	.gitignore~	6	0	6
Modified	C/main.c	132	19	113
Modified	Haskell/app/Main.hs	18	9	9
Modified	README.md	23	11	12
Deleted	README.md~	19	0	19
Modified	Rust/src/main.rs	4	2	2
Modified	script.js	41	21	20
Modified	script.py	46	24	22
Modified	script.rb	49	23	26
Deleted	script.ts	65	0	65

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
@@ -1,8 +1,5 @@
 .vscode
 *.exe
-*.ts.js
 Statistics
 Latex
 X86
-C/*
-!C/main.c

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

diff --git a/C/main.c b/C/main.c
@@ -1,7 +1,4 @@
-#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:
@@ -9,45 +6,8 @@
 // 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)
+int sum_digits(unsigned n)
 {
-    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;
 
@@ -60,88 +20,34 @@ int sum_digits(unsigned int n) {
     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 main()
 {
-    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;
-    }
+    unsigned MAX = 0;
+    scanf_s("%u", &MAX);
 
     printf("\nLOADING. . .");
+    clock_t start = clock(), end;
 
-    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);
+    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)
+            {
+                end = clock();
+                printf("\nLOADED. . . in %ums\n", (unsigned)((end - start) * 1000 / CLOCKS_PER_SEC));
+                printf("\nThe conjecture is disproved! Here's a counterexample: (%u, %u)", a, b);
+
+                return 0;
+            }
 
-    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)));
+
+    end = clock();
+    printf("\nLOADED. . . in %ums\n", (unsigned)((end - start) * 1000 / CLOCKS_PER_SEC));
+    printf("\nThe conjecture is proved for all natural numbers smaller or equals to %u!", MAX);
 
     return 0;
 } 
\ No newline at end of file

diff --git a/Haskell/app/Main.hs b/Haskell/app/Main.hs
@@ -8,7 +8,6 @@ module Main where
 import Numeric
 import Numeric.Natural
 import System.Clock
-import GHC.Conc
 
 main :: IO ()
 main = do
@@ -23,12 +22,13 @@ main = do
             putStrLn "\nLOADING. . ."
             start <- getTime Monotonic
 
-            case exceptions' 0 max of
+            case counter' 0 max of
                 [] -> do 
                     end <- getTime Monotonic
-                    putStrLn $ "LOADED. . . in " ++ formatTime (end - start) ++ "s [1 Thread]"
+                    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 are the counter examples:\n" ++ (init $ tail $ show counter)
+                counter -> putStrLn $ "\nThe conjecture is disproved! Here's a counterexample: ("++ (show $ fst $ head $counter)
+                    ++ ", " ++ (show $ snd $ head $counter) ++ ")"
                 
         _ -> putStrLn $ "\n'" ++ maxStr ++ "' is not a natural number!"
 
@@ -43,8 +43,8 @@ sum' x = sum $ digs x
 test' :: Natural -> Natural -> Bool
 test' a b = ((fromEnum $ sum' (a + b)) - (fromEnum $ sum' a) - (fromEnum $ sum' b)) `mod` 9 == 0
 
-exceptions' :: Natural -> Natural -> [(Natural, Natural)]
-exceptions' min max = [(a, b) | a <- [min..max], b <- [a..max], not $ test' a b]
+counter' :: Natural -> Natural -> [(Natural, Natural)]
+counter' min max = [(a, b) | a <- [min..max], b <- [a..max], not $ test' a b]
 
-formatTime :: TimeSpec -> [Char]
-formatTime t = show (sec t) ++ "." ++ show (nsec t `div` 10^8)-
\ No newline at end of file
+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
@@ -2,19 +2,18 @@
 An exercise on _polyglossy_. The same problem solved on multiple languages.
 
 ## Problem
-Let  <img src="https://latex.codecogs.com/gif.latex?S:\mathbb{N}&space;\mapsto&space;\mathbb{N}" title="S:\mathbb{N} \mapsto \mathbb{N}" /> be the sum of the digits of a positive integer.
+Let  <img src="https://latex.codecogs.com/gif.latex?S:\mathbb{N}&space;\mapsto&space;\mathbb{N}"/> be the sum of the digits of a positive integer.
 
-Prove that <img src="https://latex.codecogs.com/gif.latex?\forall&space;a,&space;b&space;\in\mathbb{N}&space;:&space;S_{a&space;&plus;&space;b}&space;=&space;S_a&space;&plus;&space;S_b&space;&plus;&space;9&space;k,&space;k&space;\in&space;\mathbb{Z}" title="\forall a, b \in\mathbb{N} : S_{a + b} = S_a + S_b + \nu \cdot k, k \in \mathbb{Z}" />.
+Prove that <img src="https://latex.codecogs.com/gif.latex?\forall&space;a,&space;b&space;\in\mathbb{N}&space;:&space;S_{a&space;&plus;&space;b}&space;=&space;S_a&space;&plus;&space;S_b&space;&plus;&space;9&space;k,&space;k&space;\in&space;\mathbb{Z}"/>.
 
 ## Performance
-The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by_exhaustion) for the interval <img src="https://latex.codecogs.com/gif.latex?[0;10^3]" title="[0;10^3]" /> in multiple language implementations. The performance of each language was then avaliated as the following:
+The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by_exhaustion) for the interval <img src="https://latex.codecogs.com/gif.latex?[0;10^4]"/> in multiple language implementations. The performance of each language was then avaliated as the following:
 
-|Language      |Time   |
-|--------------|-------|
-|**Rust**      |0 _s_  |
-|**C**         |5 _s_  | 
-|**Haskell**   |48 _s_ |
-|**TypeScript**|181 _s_|
-|**JavaScript**|191 _s_|
-|**Ruby**      |268 _s_|
-|**Python**    |503 _s_|
+|Language      |Milliseconds|
+|--------------|------------|
+|**Rust**      |1100        |
+|**C**         |4913        | 
+|**JavaScript**|39168       |
+|**Ruby**      |46253       |
+|**Haskell**   |48263       |
+|**Python**    |134988      |

diff --git a/README.md~ b/README.md~
@@ -1,19 +0,0 @@
-# A Conjecture of Mine
-An exercise on _polyglossy_. The same problem solved on multiple languages.
-
-## Problem
-Let  <img src="https://latex.codecogs.com/gif.latex?S:\mathbb{N}&space;\mapsto&space;\mathbb{N}" title="S:\mathbb{N} \mapsto \mathbb{N}" /> be the sum of the digits of a positive integer.
-
-Prove that <img src="https://latex.codecogs.com/gif.latex?\forall&space;a,&space;b&space;\in\mathbb{N}&space;:&space;S_{a&space;&plus;&space;b}&space;=&space;S_a&space;&plus;&space;S_b&space;&plus;&space;9&space;k,&space;k&space;\in&space;\mathbb{Z}" title="\forall a, b \in\mathbb{N} : S_{a + b} = S_a + S_b + \nu \cdot k, k \in \mathbb{Z}" />.
-
-## Performance
-The conjecture was [proved by exhaustion](https://en.wikipedia.org/wiki/Proof_by_exhaustion) for the interval <img src="https://latex.codecogs.com/gif.latex?[0;10^3]" title="[0;10^3]" /> in multiple language implementations. The performance of each language was then avaliated as the following:
-
-|Language      |Time   |
-|--------------|-------|
-|**Rust**      |14 _s_ |
-|**Haskell**   |48 _s_ |
-|**TypeScript**|181 _s_|
-|**JavaScript**|191 _s_|
-|**Ruby**      |268 _s_|
-|**Python**    |503 _s_|

diff --git a/Rust/src/main.rs b/Rust/src/main.rs
@@ -41,10 +41,10 @@ fn main() {
             let duration = start_time.elapsed();
 
             // Print the results
-            println!("LOADED. . . in {}s [{} Threads]\n", duration.as_secs(), n_threads);
+            println!("LOADED. . . in {}ms [{} Threads]\n", duration.as_millis(), n_threads);
             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)
+                Some((a, b)) => println!("The conjecture is disproved! Here's a counterexample: ({}, {})", a, b)
             }
         }, 
         Err(_) => println!("'{}' is not a natural number!", user_input.trim())

diff --git a/script.js b/script.js
@@ -3,14 +3,20 @@
 // 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 readline = require('readline');
+const readline = require("readline");
 
-Number.prototype.digits = function() {
-    return Array.from(Math.abs(Math.round(this)).toString()).map(char => Number(char));
-}
+Number.prototype.sum = function() {
+    if (isNaN(this) || !isFinite(this) || !this)
+        throw new TypeError
+
+    let parc = Math.abs(this), sum = 0;
+
+    while (parc > 0) {
+        sum += parc % 10;
+        parc = Math.floor(parc / 10);
+    }
 
-Number.prototype.sumDigits = function() {
-    return this.digits().reduce((a, b) => a + b);
+    return sum;
 }
 
 function ask(question) {
@@ -26,15 +32,13 @@ function ask(question) {
 }
 
 function getCounterExp(max) {
-    const counterexmpls = [];
-
     for (let a = 1; a <= max; a++)
         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 diff = (a + b).sum() - (a.sum() + b.sum());
+            if (diff % 9 !== 0) return [a, b];
         }
 
-    return counterexmpls;
+    return null;
 }
 
 console.log("\nThis script is a simple test for the following conjecture:\n");
@@ -47,16 +51,13 @@ ask("What value would you like to test the conjecture for? ").then(ans => {
 
         const max = Math.round(Number(ans))
             , starTime = new Date
-            , counterexmpls = getCounterExp(max)
-            , elepsed = Math.round((new Date().getTime() - starTime.getTime()) / 100) / 10;
+            , counterexmpl = getCounterExp(max)
+            , elepsed = new Date().getTime() - starTime.getTime();
 
-        console.log(`LOADED. . . in ${elepsed}s\n`);
+        console.log(`LOADED. . . in ${elepsed}ms\n`);
 
-        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:");
-            console.log(counterexmpls.map(pair => `(${pair[0]}, ${pair[1]})`).join(", "));
-        }
+        if (counterexmpl === null) console.log(`The conjecture is proved for all natural numbers smaller or equals to ${max}!`);
+        else console.log(`The conjecture is disproved! Here's a counterexample: (${counterexmpl[0]}, ${counterexmpl[1]})`);
+        
     } else console.log(`\n'${ans}' is not a natural number!`);
 }); 
\ No newline at end of file

diff --git a/script.py b/script.py
@@ -3,47 +3,50 @@
 # 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 time
-from functools import reduce
-
-def digits(n):
-    return map(lambda c: int(c), list(str(n)))
+from time import time
 
 def sum_digits(n):
-    return reduce((lambda a, b: a + b), digits(n))
+    parc = abs(n)
+    sum_d = 0
+
+    while parc > 0:
+        sum_d += parc % 10
+        parc //= 10
 
-def get_counterexmpls(n):
-    counterexmpls = []
+    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))
 
             if not diff % 9 == 0:
-                counterexmpls.append((a, b))
+                return (a, b)
     
-    return counterexmpls   
+    return None  
 
 
 print("\nThis 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? ")
+max_str = input("What value would you like to test the conjecture for? ")
 print("\nLOADING. . .")
 
 try:
-    maximum = abs(int(user_input))
+    maximum = int(max_str)
+    if maximum < 0:
+        raise ValueError
 
-    start = time.time()
-    counterexmpls = get_counterexmpls(maximum)
-    
-    elepsed = time.time() - start
-    print("LOADED. . . in {:.1f}s\n".format(elepsed))
+    start = time()
+    counterexmpl = get_counterexmpl(maximum)
+    elepsed = time() - start
+
+    print("LOADED. . . in {:.0f}ms\n".format(elepsed * 10**3))
 
-    if len(counterexmpls) == 0:
+    if counterexmpl == None:
         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:")
-        print(", ".join(map(lambda pair: "({}, {})".format(pair[0], pair[1]), counterexmpls)))
+        (a, b) = counterexmpl
+        print("The conjecture is disproved! Here's a counterexample: ({}, {})".format(a, b))
 except:
-    print("'{}' isn't a natural number!".format(user_input))-
\ No newline at end of file
+    print("'{}' isn't a natural number!".format(max_str))

diff --git a/script.rb b/script.rb
@@ -4,33 +4,31 @@
 # 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 sum
+        part = self.abs()
+        sum = 0
 
-    def digits(base: 10)
-        (quotient, remainder) = divmod(base)
-        return quotient == 0 ? [remainder] : [*quotient.digits(base: base), remainder]
-    end
+        while part > 0
+            sum += part % 10
+            part /= 10
+        end
 
-    def sum_digits
-        return self.digits.inject(0, &:+)
+        return sum
     end
 end
 
-def get_counterexpls(max)
-    counterexpls = []
+def get_counterexpl(max)
     for a in (0..max)
         for b in (a..max)
-            difference = (a + b).sum_digits - a.sum_digits - b.sum_digits
+            diff = (a + b).sum() - a.sum() - b.sum()
 
-            if !9.divides(difference)
-                counterexpls.push([a, b])
+            if diff % 9 != 0
+                return [a, b]
             end
         end
     end
 
-    return counterexpls
+    return nil
 end
 
 puts "\nThis script is a simple test for the following conjecture:\n\n"
@@ -38,23 +36,22 @@ 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 integer.\n\n"
 puts "What value would you like to test the conjecture for?"
 
-user_input = gets
+max_str = gets.chomp
 puts "\nLOADING. . ."
 
-if /^\d+$/.match(user_input.chomp)
-    max = user_input.chomp.to_i
-    start = Time.now
-    counterexpls = get_counterexpls(max)
+if /^\d+$/.match(max_str)
+    max = max_str.chomp.to_i
+    start = Time.now()
+    counterexpl = get_counterexpl(max)
 
-    elepsed = Time.now - start
-    puts "LOADED. . . in #{elepsed.round(1)}s\n\n"
+    elepsed = Time.now() - start
+    puts "LOADED. . . in #{(elepsed * 1000).round()}ms\n\n"
 
-    if counterexpls.length == 0
+    if counterexpl == nil
         puts "The conjecture is proved for all natural numbers smaller or equals to #{max}!"
     else
-        puts "The conjecture is disproved! Here are the counter examples:"
-        puts counterexpls.join(", ")
+        puts "The conjecture is disproved! Here's a counterexample: (#{counterexpl[0]}, #{counterexpl[1]})"
     end
 else
-    puts "'#{user_input.chomp}' isn't a natural number!"
+    puts "'#{max_str}' isn't a natural number!"
 end 
\ No newline at end of file

diff --git a/script.ts b/script.ts
@@ -1,64 +0,0 @@
-// 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.
-
-const readline = require('readline');
-
-function digits(n: number) {
-    return Array.from(Math.round(Math.abs(n)).toString()).map(c => parseInt(c));
-}
-
-function sum(n: number) {
-    return digits(n).reduce((a, b) => a + b);
-}
-
-function test(a: number, b: number) {
-    return (sum(a + b) - (sum(a) + sum(b))) % 9 == 0;
-}
-
-function ask(question: string): Promise<string> {
-    const rl = readline.createInterface({
-        input: process.stdin,
-        output: process.stdout,
-    });
-
-    return new Promise(resolve => rl.question(question, (ans: string) => {
-        rl.close();
-        resolve(ans);
-    }));
-}
-
-function getCounterExp(max: number) {
-    const counterexmpls: [number, number][] = [];
-
-    for (let a = 0; a <= max; a++)
-        for (let b = a; b <= max; b++)
-            if (!test(a, b)) counterexmpls.push([a, b]);
-
-    return counterexmpls;
-}
-
-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))) {
-        console.log(`\nLOADING. . .`);
-
-        const max = parseInt(ans)
-            , start = new Date
-            , counterexmpls = getCounterExp(max)
-            , elepsed = Math.round((new Date().getTime() - start.getTime()) / 100) / 10;
-
-        console.log(`LOADED. . . in ${elepsed}s\n`);
-
-        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:");
-            console.log(counterexmpls.map(pair => `(${pair[0]}, ${pair[1]})`).join(", "));
-        }
-    } else console.log(`'${ans}' is not a natural number!`);
-}).catch(console.error);-
\ No newline at end of file