challenge 2

# zavzav, 17th of may 2018
# the challenge nr. 2
# Educated exhaustive search works I guess...

"""
terminology:
string - ordered list of numbers, also a sequence
substring - a list of numbers within another list of numbers, subsequence
234 is a substring of 1234, for example
"""

def root_check(num): #checks the given substring of numbers, if it has a cube root, when multiplying digits
    two = 0
    three = 0
    five = 0
    seven = 0 #sets the counters that chount the amount of 2,3,5,7
    for i in num: #counts instances of the digits
        if i == 2:
            two += 1
        elif i == 3:
            three += 1
        elif i == 5:
            five += 1
        elif i == 7:
            seven += 1
    return (two % 3 == 0) and (three % 3 == 0) and (five % 3 == 0) and (seven % 3 == 0)
    #returns true if num is a perfect cube
    #because a perfect cube is a number that has the count of each prime factor mod 3 equal to 0

def iterate_over(x):
    i = 0 #start index of the substring
    while i < len(x): #checks every possible substring of the number supplied
        j = i+3 #end index of the substring
        while j <= len(x):
            if (root_check(x[i:j])):
                return True, i # x has a perfect cube in it, try the next value (since we're searching for the
                #first without a cube)
                #returns True -> That a cube is found and i, the position of that cube
            j += 3 #+3 because the length of the substring must always be a multiple of 3
        i+= 1
    print ("no perfect cube for length of list n= ", len(x))
    return False, 0  #prepend an element to the list. We found a combination of digits that doesn't have
    #any perfect cubes (because if it had, the if statement would've activated and return stopped the function)

def end_check(x): #checks if we tried every possible number
    for i in x[-3:]: #every number starting with 3 7s will automatically have a cube, no need to check if
        if i != 7: #cont. every number starting with 777 has a cube - it automatically has it
            return False #it's not all 7's yet
    return True


#values = [2, 3, 5, 7] only primes needed because we're looking for the biggest number.
#when there would be a 6, we can turn it into 2*3, 4->2*2, 9->3*3
#0, 1, 8 are automatically excluded since already cubes themselves
#so we're only interested in checking numbers with those digits


def increment_list(number, i): # uses the index of that number that forms a cube (returned in iterate_over(x))
    #increments a value from that substring that forms a cube, so that it doesn't anymore. Therefore creating
    #a number that doesn't have that same sequence of cubes anymore. Difficult to understand maybe, but huge
    #performance boost.
    #for example transforms 23335 into 23355
    end = i
    #print(number, i)
    while number[i] == 7:
        #if the number we're incrementing is 7, make sure about carry digits. Similar to how
        #you have to carry digits from 999+1 -> 1000. Implementing this, with only numbers 2,3,5,7
        i += 1
    number[i] += 2 if number[i] != 2 else 1 # 2->3, 3->5, 5->7
    while i > end: #if we carried digits, set all preceding to the lowest value possible (like 000 in 1000)
        i -= 1
        number[i] = 2

number = [2] #starting value

while not end_check(number): #while we've yet to try every possible combination
    cond, pos = iterate_over(number)
    #try the current number. If that number has a cube, change it so that it might not anymore.
    #if it doesn't have a cube, prepend another digit to it
    #since we're searching for the first number which always has a cube, the answer will be when
    #we try all combinations, but not find any string which doesn't have a cube in it
    if cond: #if it has a cube in it
        increment_list(number, pos) #change the number
    else: #if it doesn't have a cube
        number.insert(0, 2) #prepend a 2 to list (to the lowest position, 4 in the number 1234)
        #we are also continuing from the previously obtained sequence without a cube since previous
        #sequences are substrings of the bigger one. If they already all have a cube, the bigger one
        #with the same starting digits will have a cube too. So continue from a sequence without cubes
        #a huge performance boost, compared to creating a new list of [2,2,...,2] a size 1 larger than before
print(len(number))
#since we've tried every combination (with optimizations to avoid factorial time complexity) and not found
#a combination, this is the answer. This wasn't the case with previous, smaller, numbers, so it must be the
#smallest such number