Euler Problem 76

This problem is all about partitions. So I found a fast integer partitions generator. Well, its not fast enough but it does the trick. This routine still takes a while to run.

#Euler76
class Algorithms:
    def partitionsGen(self, n):
        ms = {n: 1}
        keys = [n]
        yield ms
        while keys != [1]:
            if keys[-1] == 1:
                del keys[-1]
                reuse = ms.pop(1)
            else:
                reuse = 0
            i = keys[-1]
            newcount = ms[i] = ms[i] - 1
            reuse += i
            if newcount == 0:
                del keys[-1], ms[i]
            i -= 1
            q, r = divmod(reuse, i)
            ms[i] = q
            keys.append(i)
            if r:
                ms[r] = 1
                keys.append(r)
            yield ms
class Problem76:
    def __init__(self, limit):
        self.limit = limit
        self.Euler = Algorithms()
    def Solution(self):
        count = 0
        print "Partitioning "+str(self.limit)
        for p in self.Euler.partitionsGen(self.limit):
            count += 1
            if count % 200000 == 0:
                print count
        return "Answer = "+str(count-1)
if __name__ == '__main__':
    P = Problem76(100)
    print P.Solution()

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s