a-conjecture-of-mine

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

Commit
f7d801fc7978968a707ebe619ebb27e73908bb7e
Parent
88f3f2cac3e0ac7856d42020878fefa8d9f80af3
Author
Gark Garcia <37553739+GarkGarcia@users.noreply.github.com>
Date

Merge branch 'master' of https://github.com/GarkGarcia/A-Conjecture-of-Mine into go

Diffstat

2 files changed, 29 insertions, 37 deletions

Status File Name N° Changes Insertions Deletions
Modified README.md 4 2 2
Modified Rust/src/main.rs 62 27 35
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**      |108         |
-|**Go**        |112         |
+|**Rust**      |115         |
 |**Kotlin**    |137         |
+|**Go**        |138         |
 |**C**         |271         | 
 |**JavaScript**|656         |
 |**Ruby**      |9850        |
diff --git a/Rust/src/main.rs b/Rust/src/main.rs
@@ -9,7 +9,26 @@ extern crate rand;
 
 use std::{env, thread, time::Instant, sync::{Arc, mpsc::{self, Sender, Receiver}}};
 use crossterm::{terminal, input};
-use rand::prelude::*;
+
+struct ArithmeticProg {
+    curr: usize,
+    delta: usize
+}
+
+impl ArithmeticProg {
+    pub fn new(start: usize, delta: usize) -> Self {
+        ArithmeticProg {curr: start, delta}
+    }
+}
+
+impl Iterator for ArithmeticProg {
+    type Item = usize;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.curr += self.delta;
+        Some(self.curr)
+    }
+}
 
 fn main() {
     let args: Vec<String> = env::args().collect();
@@ -52,44 +71,17 @@ fn main() {
 }
 
 fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> {
-    let sums = Arc::new(get_sums(max));
+    let sums_cache = Arc::new(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();
         let mut child_threads = Vec::with_capacity(n_threads);
-        let range_lenght = max / n_threads;
-        let mut range: Vec<usize> = (0..max).collect();
-
-        // Shuffle the values in the range to get an even distribution of
-        // calculations across all threads
-        range.shuffle(&mut thread_rng());
-
-        // Separate a specific slice of the range and assign it to the thread
-        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;
-            sub_ranges.push(range[(start as usize)..(end as usize)].to_vec());
-        }
-
-        // 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 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;
-            let mut remainders = range[(max - max % n_threads)..max].to_vec();
-
-            while let Some(val) = remainders.pop() {
-                sub_ranges[rng.gen_range(0, end)].push(val);
-            }
-        }
 
         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 thread_range = ArithmeticProg::new(i, n_threads).take_while(move |&x| x <= max);
+            let thread_sums = sums_cache.clone();
 
             let child = thread::spawn(move || {
                 thread_countr_sd.send(get_range_countrexpl(thread_range, thread_sums, max))
@@ -108,16 +100,16 @@ fn get_countrexpl(max: usize, n_threads: usize) -> Option<(usize, usize)> {
 
         None
     } else {
-        get_range_countrexpl((0..max).collect(), sums, max)
+        get_range_countrexpl(0..max, sums_cache, max)
     }
 }
 
-fn get_range_countrexpl(range: Vec<usize>, sums: Arc<Vec<isize>>, max: usize) -> Option<(usize, usize)> {
+fn get_range_countrexpl<T: IntoIterator<Item = usize>>(range: T, sums_cache: Arc<Vec<isize>>, max: usize) -> Option<(usize, usize)> {
     for a in range {
         for b in a..max {
-            let difference = sums[a + b] - sums[a] - sums[b];
+            let diff = sums_cache[a + b] - sums_cache[a] - sums_cache[b];
 
-            if difference % 9 != 0 {
+            if diff % 9 != 0 {
                 return Some((a, b));
             }
         }