Sunday, November 10, 2013

Problem 60 - Javascript

Problem 60 was a bit annoying - its a problem that I had never solved in my past life of doing Euler problems without language restrictions, but everything turned out O.K. My first solution was excessively slow (2-5min), but I noticed something really dumb I was doing that caused me to search way more combinations than necessary. The code below runs in <1s. And now I am formally up in another multiple of 10 - the 60's are upon us.
function isPrime(x) {
    if (x < 2) {
        return false
    } else if (x % 2 == 0) {
        return x == 2
    }

    for (var i = 3; i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
function mag(x) {
    return x < 10 ? 10 : 10 * mag(x / 10)
}
function concat(x, y) {
    return x * mag(y) + y
}

function getPrimes(N) {
    p = new Array()
    for (var i = 2; i <= N; ++i) {
        if (isPrime(i)) {
            p.push(i)
        }
    }
    return p
}

function satisfies(p,s) {
    for (var i = 0; i < s.length; ++i) {
        if (!(isPrime(concat(s[i],p)) && isPrime(concat(p,s[i])))) {
            return false
        }
    }
    return true
}
function setSum(set) {
    sum = 0;
    for (var i = 0; i < set.length; ++i) {
        sum += set[i]
    }
    return sum 
}
function scopy(set) {
    return set.slice(0)
}

primes = getPrimes(10000)
function finishSet(set, target, start) {
    if (set.length == 5) {
        test = setSum(set)
        return test < target ? test : target
    } else {
        for (var i = start; i < primes.length; ++i) {
            p = primes[i]
            if (satisfies(p,set)) {
                cset = scopy(set)
                cset.push(p)
                test = finishSet(cset,target,i)
                if (test < target) {
                    target = test
                    break
                }
            }
        }
    }
    return target
}
/** this is 'main' */
function euler60() {
    ans = finishSet(new Array(),10000000,0)
    console.log(ans)
    alert(ans)
}

No comments:

Post a Comment