Project Euler #33: Digit canceling fractions

  • + 0 comments

    Some points as also mentioned by other programmers
    1) You can't cancel any 0, irrespective of whatever position it is at.
    2) 0's at end are allowed as long as point 1 is followed.
    3) You have to 'cancel' common digits in numerator and denominator not reduce the fractions, and hence the order of digits can be any.
    4) Don't repeat count fractions

    100points/- python 3

    import itertools
    def list_adder(strings,number):
        '''Create all possible strings with number added at all indices in string in strings'''
        l=len(strings[0])+1 #+1, because I also have to add number at last position 
        lis=[string[:i]+str(number)+string[i:] for string in strings for i in range(l)]
        return lis
    
    def permuter(lis1,lis2):
        '''It creates all possible permutations with lis1 as unordered and lis2 as ordered'''
        while lis1:
            n=lis1.pop()
            lis2=list_adder(lis2,n)
        return set(lis2)
    
    def lis_to_str(list1):
        '''Take in a sequence of numbers and returns a str of them'''
        return ''.join([str(no) for no in list1])
    
    def lis_to_int(list1):
        '''Take in a sequence of numbers and return int formed by combining them'''
        return int(''.join([str(no) for no in list1]))
    
    item=input().split()
    n=int(item[0])
    k=int(item[1])
    
    li1=list(itertools.combinations_with_replacement(range(1,10),r=k)) #This is the list of possible combinations of numbers which are common in numerator and denominator
    
    li2=list(itertools.product(range(10),repeat=n-k)) #The ordered combinations of other digits in numerator or denominator
    li2.remove((0,)*(n-k)) # after cancelling common digits we should'nt be left with something like 00/00 or 00/12 etc
    
    answers=set() #so that I don't count repeated fractions
    li3=[] # it contains for a particular element in li all the possible casses of elements in li2 with the numerator or denominator as in the format (12,1234) all stored in a list
    for i in li1:
        li4=[]
        for j in li2:
            li4+=[(lis_to_int(j),int(i)) for i in permuter(list(i),[lis_to_str(j)]) if i[0]!='0'] # we should'nt get number like 0123 for n=4
        li3.append(li4)
    
    for i in li3:
        for item in itertools.combinations(i,r=2): # I just used combinations instead of permutations cause the left over numerator should be less than left over denominator and the storing order was lexicographical
            if item[0][0]<item[1][0] and item[0][0]*item[1][1]==item[1][0]*item[0][1]:
                answers.add((item[0][1],item[1][1]))
    
    print(sum([a[0] for a in answers]), sum([a[1] for a in answers]))    
    

    `