Changes from Version 1 of BitArrayVsArrayOfBoolsExample

Author:

gim (IP: 158.75.88.16)

Timestamp:

06/03/08 23:52:20 (16 years ago)

Comment:

First version

BitArrayVsArrayOfBoolsExample

@@ +1 @@
+= Solution to Google Treasure Hunt 2008 - Task 4 =
+
+The program below can be used to solve a particular instance of the task presented at http://treasurehunt.appspot.com (Task 4, 2008). You are given few numbers, e.g. [1111, 137, 13, 3]. Your task is to find smallest prime that is a sum of 1111 consecutive primes, sum of 137 consecutive primes and so on.
+
+The values are placed in limits array, but you can also pass them as arguments (in descending order!) from command line:
+{{{
+    ./TreasureHunt4 799 415 63 31
+}}}
+
+The code allows to compare [http://dsource.org/projects/tango/docs/current/tango.core.BitArray.html BitArray] with array of booleans. BitArray is a bit slower, but should occupy less memory. Implementation uses Atkin sieve.
+
+Code can be compiled with debug option for additional informations.
+
+{{{
+#!d
+/* Michal 'GiM' Spadliński             <gim913 & gmail * com >
+ * 
+ * Google TreasureHunt task 4 solution
+ * http://treasurehunt.appspot.com/
+ */
+module TreasureHunt4;
+
+//version = BitArray;
+
+import tango.io.Stdout;
+import tango.time.StopWatch;
+import Integer = tango.text.convert.Integer;
+version ( BitArray )
+    import tango.core.BitArray;
+
+
+static const int sqrt_val = 2500;
+// descending order
+int[] limits = [1111, 137, 13, 3];
+
+
+ulong primes[];
+static this()
+{   
+    StopWatch timer;
+    timer.start;
+    some_small_primes = atkin_sieve;
+    foreach (k, a; some_small_primes)
+        if (a)
+            primes ~= k;
+    auto temp = timer.stop;
+    Stdout.formatln ("primes table generated in {} seconds with {} entries", temp, primes.length);
+}
+
+class PrimesSum
+{
+private:
+        ulong _sum;
+        int start;
+        int limit;
+public:
+    this(int lim)
+    {   
+        limit = lim;
+        for (int j=0; j<limit; ++j)
+            _sum += primes[j];
+    }
+    
+    void next()
+    {   
+        _sum -= primes[start];
+        _sum += primes[start+limit];
+        ++start;
+    }
+    void previous()
+    {   
+        --start;
+        _sum -= primes[start+limit];
+        _sum += primes[start];
+    }
+
+    int opCmp(PrimesSum b) { return _sum - b.sum; }
+    int opEquals(PrimesSum b) { return _sum == b.sum; }
+
+    uint sum() { return _sum; }
+
+    char[] toString()
+    {   
+        char[100] tmp = void;
+        return Integer.format (tmp, _sum, Integer.Style.Unsigned, Integer.Flags.None).dup;
+    }
+}
+
+void main(char[][] argv)
+{
+    PrimesSum[] prSums;
+    StopWatch timer;
+
+    if (argv.length > 1)
+    {   
+        limits = [];
+        foreach (char[] arg; argv[1..$])
+            limits ~= Integer.toInt(arg);
+        Stdout(limits).newline;
+    }
+
+    timer.start;
+
+    prSums.length = limits.length;
+    foreach (a, ref b; prSums)
+        b = new PrimesSum(limits[a]);
+
+OUTER_LOOP:
+    for(;;)
+    {   
+        // Sum must be a prime
+        try {
+            while (1)
+            {   
+                if (some_small_primes[prSums[0].sum])
+                    break;
+                else
+                    prSums[0].next;
+            }
+        } catch (Exception e) {
+            assert (0, "Increase the value of sqrt_val in the source file");
+        }
+        debug Stdout.formatln ("0: {} {}", prSums[0].sum, prSums[0].start);
+
+        // check if all the other, smaller sums, sum to the same number
+        for (int idx=1; idx<prSums.length; ++idx)
+        {   
+            while (prSums[idx] < prSums[0])
+                prSums[idx].next;
+            debug Stdout.formatln ("{}: {} {}", idx, prSums[idx].sum, prSums[idx].start);
+            if (prSums[idx] != prSums[0])
+            {   
+                debug Stdout ("differ2").newline;
+                prSums[0].next;
+                for (int i=1; i<=idx; ++i)
+                    while (prSums[i] > prSums[0])
+                        prSums[i].previous;
+                continue OUTER_LOOP;
+            }
+        }
+        // we got you
+        break;
+    }
+    auto temp = timer.stop;
+    Stdout ("The Answer to the Great Question ...")
+        .formatln ("Of Life, the Universe and Everything: {}", prSums[0]);
+    Stdout  ("input data: ") (limits).newline;
+    Stdout.formatln ("Finding answer took {} seconds", temp);
+}
+
+T atkin(T, int sqrt_limit)()
+{
+    const long limit = sqrt_limit*sqrt_limit;
+    T firstSet;
+    firstSet.length = limit;
+    
+    firstSet[2] = 1;
+    firstSet[3] = 1;
+            
+    for (auto x = 1; x<sqrt_limit; ++x)
+    {
+        for (auto y=1; y<sqrt_limit; ++y)
+        {
+            auto n = 4 * x*x + y*y;
+            if (n < limit && ((n % 12) == 1 || (n % 12) == 5))
+                firstSet[n] = cast(bool)1^firstSet[n];
+            n = 3 * x*x + y*y;
+            if (n < limit && ((n % 12) == 7))
+                firstSet[n] = cast(bool)1^firstSet[n];
+            n = 3 * x*x - y*y;
+            if (n < limit && x > y && ((n % 12) == 11))
+                firstSet[n] = cast(bool)1^firstSet[n];
+        }
+    }   
+    for (int n=5; n<sqrt_limit; ++n)
+    {   
+        if (firstSet[n])
+            for (int k=1, j=n*n; j*k<limit; ++k)
+                firstSet[k*j] = 0;
+    }   
+    return firstSet;
+}       
+    
+version ( BitArray )
+{   
+    static const BitArray some_small_primes;
+    alias atkin!(BitArray, sqrt_val) atkin_sieve;
+} else  {
+    static const bool[] some_small_primes;
+    alias atkin!(bool[], sqrt_val) atkin_sieve;
+}   
+}}}
+
+Here is sample run of a program on Core Duo 1.7 with sqrt_val set to 2630, this also show how fast D is:
+
+{{{
+primes table generated in 1.07 seconds with 471342 entries
+[ 799, 415, 63, 31 ]
+The Answer to the Great Question ...Of Life, the Universe and Everything: 6814289
+input data: [ 799, 415, 63, 31 ]
+Finding answer took 0.00 seconds
+}}}