p828

p828.py

import itertools
from functools import lru_cache

@lru_cache(maxsize = 10**5)
def recursiveGenerate(A):
    values = set()
    
    #If our subset has a single element, then that element is the only constructable number
    if len(A) == 1:
        values.add(A[0])
        return values
    
    #Otherwise we move to general case
    #This flag is for later, it indicates if our original subset A has values that appear more than once
    multiplesFlag = False
    for x in A:
        if A.count(x) > 1:
            multiplesFlag = True
        
    for k in range(1, len(A)):
        #We test all subests wth k elements, against all subsets with len(A) - k elements
        
        combs1 = [y for y in itertools.combinations(A, k)]
        combs2 = [y for y in itertools.combinations(A, len(A) - k)]
        
        for i in range(len(combs1)):
            for j in range(len(combs2)):
                #Here we do our intersection trick to make sure we are not using values more than allowed
                t = set(combs1[i]).intersection(set(combs2[j]))
                flag = False
                if len(t) == 0:
                    #If intersection is empty we are fine and we can make combinations between 
                    #These 2 subsets
                    flag = True
                else:
                    if multiplesFlag:
                        #If intersection is non-zero and our set has been flagged as having multiples
                        #We do extra checks
                        flag = True
                        for x in t:
                            xcount = combs1[i].count(x) + combs2[j].count(x)
                            if xcount > A.count(x):
                                flag = False
                if flag:
                    #We finds all values that can be made from all subsets of our subsets
                    #Then we will apply the 4 operations on these values to create new values
                    t1 = recursiveGenerate(combs1[i])
                    t2 = recursiveGenerate(combs2[j])
                    for v1 in t1:
                        for v2 in t2:
                            values.add(v1 + v2)
                            values.add(v1 * v2)
                            if v1 - v2 > 0:
                                values.add(v1 - v2)
                            if v1 % v2 == 0:
                                values.add(v1 // v2)
    return values
    
def compute():
    data = ReadFile() #This functions just reads the txt file and delivers the information in a nice format
    #In my case each element of data is a tuple (g, A) where g is the goal number, A is the set of 6 numbers
    total = 0
    mod = 1005075251
    for n, (g, A) in enumerate(data):
        s = []
        for k in range(1, len(A) + 1):
            combs = itertools.combinations(A, k)
            #Generated all subsets with k values
            for x in combs:
                #Test if our goal value can be generated from this subset
                if g in recursiveGenerate(x):
                    s.append(sum(x))
        if len(s) == 0:
            s = 0
        else:
            s = min(s)
        print(n + 1, s)
        total += pow(3, n + 1, mod) * s
    return total % mod