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: f37336eec8f051a71cc76a10a543bd69c1c0c3e7
Parent: c838bc72e5ba595d05458ab0567aac21bb955e0f
Author: Pablo Escobar Gaviria <gark.garcia@protonmail.com>
Date: Sat, 11 Jan 2020 18:03:51 -0200

Cleaned the Rust and the Go implementations.

Diffstat

4 files changed, 160 insertions, 137 deletions

Status	File Name	N° Changes	Insertions	Deletions
Deleted	Go/conjecture.go	120	0	120
Added	Go/main.go	120	120	0
Modified	Rust/src/main.rs	44	27	17
Added	Wasm/test	13	13	0

diff --git a/Go/conjecture.go b/Go/conjecture.go
@@ -1,120 +0,0 @@
-package main
-
-// 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 interger.
-
-import (
-	"os"
-	"strconv"
-)
-
-type iter struct {
-	Start    uint
-	Max      uint
-	Interval uint
-}
-
-const success = 0
-const fail = 1
-const invalidInput = 2
-
-func main() {
-	if len(os.Args) > 0 {
-		nThreads := uint(1)
-
-		if len(os.Args) > 1 {
-			if arg, err := strconv.ParseUint(os.Args[2], 10, 64); err == nil && arg >= 1 {
-				nThreads = uint(arg)
-			}
-		}
-
-		if max, err := strconv.ParseUint(os.Args[0], 10, 64); err == nil {
-			if getCounterexample(uint(max), nThreads) {
-				os.Exit(fail)
-			} else {
-				os.Exit(success)
-			}
-		} else {
-			os.Exit(invalidInput)
-		}
-	} else {
-		os.Exit(invalidInput)
-	}
-
-}
-
-func getCounterexample(max uint, nThreads uint) bool {
-	sums := getSums(max)
-
-	if nThreads > 1 {
-		channels := make([](chan bool), nThreads)
-
-		// Compute the result of each sub-range
-		for i := 0; i < int(nThreads); i++ {
-			channels[i] = make(chan bool)
-			it := iter{uint(i), max, nThreads}
-
-			go getCounterIter(it, &sums, channels[i])
-		}
-
-		// Listen for the computation to finish
-		for _, c := range channels {
-			if msg := <-c; msg {
-				return true
-			}
-		}
-	} else {
-		c := make(chan bool)
-		it := iter{0, max, 1}
-
-		go getCounterIter(it, &sums, c)
-
-		return <-c
-	}
-
-	return false
-}
-
-func getCounterIter(it iter, sums *[]int, c chan bool) {
-	for a := it.Start; a <= it.Max; a += it.Interval {
-		for b := a; b <= it.Max; b++ {
-			diff := (*sums)[a+b] - (*sums)[a] - (*sums)[b]
-
-			if diff%9 != 0 {
-				c <- true
-				close(c)
-
-				return
-			}
-		}
-	}
-
-	c <- false
-	close(c)
-}
-
-func getSums(max uint) []int {
-	maxRange := 2*max + 1
-	sums := make([]int, maxRange)
-
-	for i := range sums {
-		sums[i] = sumDigits(uint(i))
-	}
-
-	return sums
-}
-
-func sumDigits(n uint) int {
-	var sum uint
-
-	for {
-		if n <= 0 {
-			return int(sum)
-		}
-
-		sum += n % 10
-		n /= 10
-	}
-}

diff --git a/Go/main.go b/Go/main.go
@@ -0,0 +1,120 @@
+package main
+
+// 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 interger.
+
+import (
+	"os"
+	"strconv"
+)
+
+type iter struct {
+	Start    uint
+	End      uint
+	Step uint
+}
+
+const success = 0
+const fail = 1
+const invalidInput = 2
+
+func main() {
+	if len(os.Args) > 0 {
+		var nGoRoutines uint = 1
+
+		if len(os.Args) > 1 {
+			if arg, err := strconv.ParseUint(os.Args[2], 10, 64); err == nil && arg >= 1 {
+				nGoRoutines = uint(arg)
+			}
+		}
+
+		if max, err := strconv.ParseUint(os.Args[0], 10, 64); err == nil {
+			if counterexample(uint(max), nGoRoutines) {
+				os.Exit(fail)
+			} else {
+				os.Exit(success)
+			}
+		} else {
+			os.Exit(invalidInput)
+		}
+	} else {
+		os.Exit(invalidInput)
+	}
+
+}
+
+func counterexample(max uint, nGoRoutines uint) bool {
+	sums := getSums(max)
+
+	if nGoRoutines > 1 {
+		channels := make([](chan bool), nGoRoutines)
+
+		// Compute the result of each sub-range
+		for i := uint(0); i < nGoRoutines; i++ {
+			channels[i] = make(chan bool)
+			it := iter{uint(i), max, nGoRoutines}
+
+			go counterIter(it, &sums, channels[i])
+		}
+
+		// Listen for the computation to finish
+		for _, c := range channels {
+			if msg := <-c; msg {
+				return true
+			}
+		}
+	} else {
+		c := make(chan bool)
+		it := iter{0, max, 1}
+
+		go counterIter(it, &sums, c)
+
+		return <-c
+	}
+
+	return false
+}
+
+func counterIter(it iter, sums *[]int, c chan bool) {
+	for a := it.Start; a <= it.End; a += it.Step {
+		for b := a; b <= it.End; b++ {
+			diff := (*sums)[a+b] - (*sums)[a] - (*sums)[b]
+
+			if diff%9 != 0 {
+				c <- true
+				close(c)
+
+				return
+			}
+		}
+	}
+
+	c <- false
+	close(c)
+}
+
+func getSums(max uint) []int {
+	maxRange := 2*max + 1
+	sums := make([]int, maxRange)
+
+	for i := range sums {
+		sums[i] = sumDigits(uint(i))
+	}
+
+	return sums
+}
+
+func sumDigits(n uint) int {
+	var sum uint
+
+	for {
+		if n <= 0 {
+			return int(sum)
+		}
+
+		sum += n % 10
+		n /= 10
+	}
+}

diff --git a/Rust/src/main.rs b/Rust/src/main.rs
@@ -5,7 +5,13 @@
 
 extern crate num_cpus;
 
-use std::{env, process, thread, sync::{Arc, mpsc::{self, Sender, Receiver}}};
+use std::{
+    env,
+    process,
+    thread,
+    sync::{Arc, Mutex, mpsc::{self, Sender, Receiver}},
+    collections::hash_map::{HashMap, Entry}
+};
 
 const SUCCESS: i32 = 0;
 const FAIL: i32 = 1;
@@ -28,7 +34,7 @@ fn main() {
         };
 
         match max_str.trim().parse::<usize>() {
-            Ok(max) => if get_countrexpl(max, n_threads) {
+            Ok(max) => if countrexpl(max, n_threads) {
                 process::exit(FAIL);
             } else {
                 process::exit(SUCCESS);
@@ -41,8 +47,8 @@ fn main() {
 }
 
 /// Distributes calculations across threads and collect the results
-fn get_countrexpl(max: usize, n_threads: usize) -> bool {
-    let sums_cache = Arc::new(get_sums(max));
+fn countrexpl(max: usize, n_threads: usize) -> bool {
+    let sums_cache = Arc::new(Mutex::new(HashMap::with_capacity(max)));
 
     if n_threads > 1 {
         let (coutexpl_sender, coutexpl_reciever): (Sender<bool>, Receiver<bool>) = mpsc::channel();
@@ -56,7 +62,7 @@ fn get_countrexpl(max: usize, n_threads: usize) -> bool {
             // value will get tested on a single thread and that all threads will perform roughtly the same number of operations
             let thread_range = (i..max).step_by(n_threads);
 
-            let child = thread::spawn(move || thread_countr_sd.send(get_iter_countrexpl(thread_range, thread_sums, max))
+            let child = thread::spawn(move || thread_countr_sd.send(iter_countrexpl(thread_range, thread_sums, max))
                 .expect(&format!("Thread n°{} was unable to sent a message trought the channel", i)));
             
             child_threads.push(child);
@@ -71,19 +77,22 @@ fn get_countrexpl(max: usize, n_threads: usize) -> bool {
 
         false
     } else {
-        get_iter_countrexpl(0..max, sums_cache, max)
+        iter_countrexpl(0..max, sums_cache, max)
     }
 }
 
 /// Search for counterexamples among the items of a specif iterator.
-fn get_iter_countrexpl<I: IntoIterator<Item = usize>>(
+fn iter_countrexpl<I: IntoIterator<Item = usize>>(
     iter: I,
-    sums_cache: Arc<Vec<isize>>,
+    sums_cache: Arc<Mutex<HashMap<usize, isize>>>,
     max: usize
 ) -> bool {
     for a in iter {
         for b in a..max {
-            let diff = sums_cache[a + b] - sums_cache[a] - sums_cache[b];
+            let sum_a_b = lookup_or_insert(&sums_cache, a + b);
+            let sum_a   = lookup_or_insert(&sums_cache, a);
+            let sum_b   = lookup_or_insert(&sums_cache, b);
+            let diff    = sum_a_b - sum_a - sum_b;
 
             if diff % 9 != 0 {
                 return true;
@@ -106,13 +115,14 @@ fn sum_digits(n: usize) -> isize {
     sum as isize
 }
 
-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));
+fn lookup_or_insert(sums_cache: &Arc<Mutex<HashMap<usize, isize>>>, n: usize) -> isize {
+    if let Ok(ref mut sums_cache) = sums_cache.lock() { 
+        match (*sums_cache).entry(n) {
+            Entry::Vacant(entry) => *(entry.insert(sum_digits(n))),
+            Entry::Occupied(entry) => *(entry.get())
+        }
+    } else {
+        unimplemented!()
     }
-
-    output
 }
+

diff --git a/Wasm/test b/Wasm/test
@@ -0,0 +1,13 @@
+#!/usr/bin/node
+
+const fs = require("fs");
+
+const src = new Uint8Array(fs.readFileSync("./main.wasm"));
+WebAssembly.instantiate(src).then(test).catch(console.error);
+
+function test(mod) {
+    const result =  mod.instance.exports.counterexempl(100);
+
+    console.log(`RESULT: ${result}`);
+}
+