Monday, February 29, 2016

Oops -- 60 and 103 swap

 I messed up last time and posted my non-working python solution to problem 103 instead of my working Javascript solution.

Working Javascript solution:
function sum(A) {
    var s = 0;
    for (var i = 0; i < A.length; ++i) {
        s += A[i]
    }
    return s
}

function powerSumSet(A) {
    sums = []
    maxes = []
    mins = []
    for (var i = 0; i < A.length; ++i) {
        maxes.push(0);
        mins.push(Infinity)
    }
    for (var i = 0; i < (1 << A.length); ++i) {
        nextSet = getSubSet(i, A)
        nextSum = sum(nextSet)
        if (sums.indexOf(nextSum) < 0) {
            sums.push(nextSum)
        }
        maxes[nextSet.length] = Math.max(maxes[nextSet.length], nextSum)
        mins[nextSet.length] = Math.min(mins[nextSet.length], nextSum)
    }
    return [sums, maxes, mins]
}

function getSubSet(s, set) {
    a = []
    k = 0
    while (s != 0) {
        if ((s & 1) == 1) a.push(set[k])
        k += 1
        s >>= 1
    }
    return a
}

function hasProp(s) {
    data = powerSumSet(s.slice(0, s.length - 1))
    sumset = data[0]
    maxes = data[1]
    mins  = data[2]
    for (var i = 0; i < maxes.length; ++i) {
        if (mins[i] <= s[s.length - 1] + maxes[i - 2]) {
            return false
        }
    }
    for (var i = 0; i < sumset.length; ++i) {
        if (sumset.indexOf(sumset[i] + s[s.length -1 ]) >= 0) {
            return false
        }
    }
    return true
}

// Returns the optimal set of size K, subject to compatibility with rest
var minsum = 256
function opt(K, rest) {
    if (K == 0) return rest
    var nextElem = (rest.length > 0 ? (rest[rest.length -1] + 1) : 1)
    var optimum = []
    while (minsum > sum(rest) + K * nextElem) {
        var nextSet = rest.slice(0, rest.length)
        nextSet.push(nextElem)
        if (hasProp(nextSet)) {
            var test = opt(K - 1, nextSet)
            if (test.length > 0 && sum(test) <= minsum) {
                minsum = sum(test)
                optimum = test
            }
        }
        nextElem += 1
    }
    return optimum
}
console.log(opt(7, []).join(""));

Python solution to 60, in order to offset things:
def isPrime(x):
    if x < 2:
        return False
    elif x % 2 == 0:
        return x == 2
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

def mag(x):
    return 10 if x < 10 else  10 * mag(x // 10)

def concat(x, y):
    return x * mag(y) + y

def getPrimes(N):
    return [x for x in range(N+1) if isPrime(x)]

def satisfies(p,s):
    return all(isPrime(concat(e, p)) and isPrime(concat(p, e)) for e in s)

primes = getPrimes(10000)

def finishSet(s, target, start):
    if len(s) == 5:
        test = sum(s)
        return test if test < target else target
    else:
        for i in range(start, len(primes)):
            p = primes[i]
            if satisfies(p,s):
                cset = s[:]
                cset.append(p)
                test = finishSet(cset,target,i)
                if test < target:
                    target = test
                    break
        return target

print(finishSet([],10000000,0))

No comments:

Post a Comment