Problem 87 - D

With Project Euler being down, I thought it might be difficult to move on and do more recent problems, but then I realize that between myself and my friends, the next few most recent problems have all been solved by someone. However, on the day when it finally became relevant, Project Euler has re-added the solution checking feature to their website, so there should be no issues related to that moving forward.

Now, for Problem 87, I used D, which I had just recently freed up, having not used it since my initial solution to problem 22. D is a fine language with C-like syntax which compiles directly to native code and lets you do all sorts of stuff that one would want to do in a low or high level language...its a powerful language, which was a nice breath of fresh air having just come from SwiftScript. Problems 87 is  rather simple problem: "how many numbers below 50000000 can be expressed as the sum of a prime square, prime cube, and prime fourth power?": the main issue comes in finding a way to solve it efficiently, which I did by storing all square+cube sums in a set (implemented by hand as an array of bits) and then checking against this set to add in the fourth powers. This was much more efficient than my first solution, which, without going into too many details, took 5min to run.

Other than that, the only issue I had was that I trusted myself too much with my prime sieve. I wrote it from memory based on one I have written in python a number of times, but I made a few small mistakes the first couple of times around that caused it to not quite find all the primes. Of course, this in turn led to some difficulties. However, once I discovered that annoying little error, everything fell into place. Solution runs in 10 seconds on my machine.

import std.stdio;
import std.math;
import std.conv;

/** Writing all the casts is annoying */
int isqrt(int x) {
    return to!int(floor(sqrt(to!float(x))));
}

/** "Basic" Prime Sieve */
int[] sieve(int bound) {
    int[] partial;
    int rbound = isqrt(bound);
    if (bound < 11) {
        return [2, 3, 5, 7];
    } else {
        partial = sieve(rbound);
    }
    int current = rbound;
    if (current % 2 == 0) {
        current += 1;
    }
    int[] newprimes = partial;
    while (current < bound) {
        bool isprime = true;
        int rcurrent = isqrt(current);
        foreach (p; partial) {
            if (p > rcurrent) {
                break;
            }
            if (current % p == 0) {
                isprime = false;
                break;
            }
        }
        if (isprime) {
            newprimes ~= current;
        }
        current += 2;
    }
    return newprimes;
}

int BOUND = 50000000;
/**Set implemented with array of bits
   Not only done for space efficiency, D does not
   allow static arrays with 50000000 elements (at least by default).
   */
uint[50000000/32 + 1] is23sum;

void setIsSum(int elem) {
    if (!isSum(elem)) {
        is23sum[elem / 32] += 1 << (elem % 32);
    }
}

bool isSum(int elem) {
    return ((is23sum[elem / 32] >> (elem % 32)) & 1) > 0;
}
void main() {
    // Get all necessary primes
    int[] primes = sieve(isqrt(BOUND));
    // Precompute arrays
    int[] primes2;
    foreach (p ; primes ) { 
        primes2 ~= pow(p , 2); 
    }
    int[] primes3;
    foreach (p ; primes ) {
        int temp = pow(p, 3);
        if (temp > BOUND) { 
           break;
        } else { 
           primes3 ~= temp;
        }
    }
    int[] primes4;
    foreach (p; primes) {
        int temp = pow(p, 4);
        if (temp > BOUND) {
            break;
        } else {
            primes4 ~= temp;
        }
    }
    is23sum[] = 0;
    // Precompute all numbers that are sums of squares and cubes
    foreach (p2; primes2) {
        foreach (p3; primes3) {
            int s = p2 + p3;
            if (s < BOUND) {
                setIsSum(s);
            }
        }
    }
    int ans = 0;
    // Checking for sum of square, cube, and 4th power
    foreach(i; 27 .. BOUND) {
        foreach (p4; primes4) {
            if ( (i - p4) < 12) {
                break;
            } else if (isSum(i - p4)) {
                ans = ans + 1;
                break;
            }
        }
    }
    writeln(ans);
}

Summertime Problem 22 in SwiftScript

First a note about project euler. The website had its security compromised, and many of the features of the site, including answer checking, are down for now. Therefore, I will likely stick with resolving solved problems, at least for a little while, as this problem is doing. Now, for the problem:

So, I heard about the new language Apple apparently developed to replace Objective-C for their uses, Swift (https://developer.apple.com/swift/), and I thought I might use it, but it seems like all the tools for it are built into Xcode and other Apple things I don't want to have to deal with. However, at the bottom of the page, there is a small note, to compensate for the fact that Apple's Swift is not the first language called Swift: "Looking for the Swift parallel scripting language? Please visit http://swift-lang.org"

So, I visited that website, and found the Swift parallel scripting language. As the name suggests, yes, it is a parallel scripting language. And that basically sums up the issues. One: it is a scripting language. It seems that the developers of Swift only ever intended for it to be used to gather large collections of filenames and commands and run other programs in parallel using it. Two: it is a parallel language, which opens up its own can of worms, such as the fact that all variables can only be written to exactly once.

Problem 22 seemed like a problem that would be doable in SwiftScript, as the largest task of the problem involves reading in a list of names. However, despite having huge amounts of tools for file output, in order to extract a list of strings from a file in SwiftScript, the easiest solution I could find was to treat it as a one-column csv, which then gets parsed as a struct with one string field, which is the name at the top of the list (AARON, which had to have an extra copy added to names.txt), and then getting a normal string array from that.

Another task one would think would be simple: getting the ascii value of a char. SwiftScript has no chars though, only ints and strings, and no way to map from string to int (though there is @toString for the other direction). However, as SwiftScript is built on top of Java, it has a @java directive for calling static methods of Java library classes. So, I used java.lang.Integer.parseInt to tread my names as base-36 integers, in order to extract a mapping a => 1, b => 2, etc.

Sorting the list proved to be incredibly hard in SwiftScript (due to being able to only assign a value to a variable once, and all for loops being executed in parallel, most sorting methods would not work), so to accomplish this task, I used SwiftScripts ability to run other programs and used sort to sort the list.

The last task I had difficulty solving was finding the sum of a list. A recursive funciton (which I use in some places) took far too long to run on a list the size of the number of names this problem must deal with, and you can't just use an accumulator and run through the list, as += does not exist in SwiftScript. However, using a parallel foreach loop to build up an array of running sums does work, as each thread will wait until it has the information to compute the computation.

After completing all of these tasks over a large amount of time, I got to the solution that is below. Runs in 27s on my machine.

type file;
type line {
    string AARON;
}

(int sum) arraysum (int[] arr, int index, int acc) {
    if (index >= @length(arr)) {
        sum = acc;
    } else {
        sum = arraysum(arr, index+1, acc+arr[index]);
    }
}

#Incredibly long winded manner of getting the ascii value
#of a char
(int val) parseInt (string s) {
    int temp = @java("java.lang.Integer", "parseInt", s, 36);
    val = temp - 9;
}

(int val) strvalue (string str) {
    string chars[] = @strsplit(str, "");
    int values[];
    #we start at 1 to chop off strange empty char
    foreach i in [1:@length(chars)-1] {
        values[i-1] = parseInt(chars[i]);
    }
    val = arraysum(values, 0, 0);
}

#Though I might normally find it to be almost like cheating
#to call other programs, this is kind of what SwiftScript
#was made for; and its a program that is pre-installed
#on most UNIX systems.
app (file outfile) sortwords(file infile) {
    sort stdin=@filename(infile) stdout=@filename(outfile);
}

#had to add extra AARON to names.txt to get desired result
#As SwiftScript does not parse strict lists, it requires a 
#category at the top of columns of a csv type file

file original <"names.txt">;
file sorted   <"sorted_names.txt">;
sorted = sortwords(original);
line lines[] = readData("sorted_names.txt");

#Converting the array of lines to strings
string[] names;
foreach i in [0:@length(lines)-1] {
    names[i] =  lines[i].AARON;
}

#Get the name scores
int[] scores;
foreach i in [0:@length(names)-1] {
    scores[i] = (i+1) * strvalue(names[i]);
}

#Workable way to compute the sum of a list
#given the constraints of the language
int[] scoresums;
scoresums[0] = scores[0];
foreach i in [1:@length(names)-1] {
    scoresums[i] = scoresums[i - 1] + scores[i];
}
#Ensures this does not run until
#scoresums is fully written
if (@length(scoresums) == @length(scores)) {
    trace(@toString(scoresums[@length(scoresums)-1]));
}