Saturday, November 16, 2013

65 redone in Dart

After I made a hole for problem 65 by using Python in 66, I was in a bit of a pickle thinking about what language to use, as this problem is fairly hard in a language that doesn't either have support for arbitrary-integer precision rational numbers or can be made to have such capabilities. Thus, I used Dart, which has arbitrarily large integers and nice classes and such. Though I liked Dart enough the last time I used it, on problem 63, using it on problem 65 showed me why people think it would be a better replacement for Javascript...classes and objects in Javascript can be a real pain to deal with, but in Dart they are very reasonable to work with, it was not hard at all to make a class, do operator overloading, and all that sort of stuff. (also, I discovered that Dart has a succinct syntax for single line functions, which is always nice...and a ternary operator, because every good language needs one). Solution below runs in about 80ms on my machine:
class Rational {
    int n, d;
    static int gcd(a, b) =>
        b == 0 ? a : gcd(b, a%b);

    Rational(int top, int bottom) :
        n = top ~/ gcd(top, bottom), d = bottom ~/ gcd(top, bottom) {}

    operator +(Rational other) => 
        new Rational(this.n*other.d + other.n*this.d, other.d*this.d);

    Rational inverse() => new Rational(this.d, this.n);
}

int digisum(x) => x < 10 ? x : x%10 + digisum(x~/10);

int coeff(n) => n == 1 ? 2 : (n % 3 == 0 ? 2*(n~/3) : 1);

Rational nextDepth(n,N) {
    if (n == N) {
        return new Rational(1,coeff(n));
    } else {
        return new Rational(coeff(n),1) + nextDepth(n+1,N).inverse();
    }
}

Rational nthConv(n) => nextDepth(1,n); 

main() {
    print(digisum(nthConv(100).n));
}

No comments:

Post a Comment