CheckIO - Home Challenge 10 : Golden Pyramid (algorithm A)

checkio.1.10a.goldenPyramid.py

# CheckIO - Home Challenge 10 : Golden Pyramid (algorithm A)
# http://checkio.org

# Consider a tuple of tuples in which the first tuple has one integer 
# and each consecutive tuple has one more integer then the last. 
# Such a tuple of tuples would look like a triangle. 
# You should write a program that will help Stephan find the highest possible sum 
# on the most profitable route down the pyramid. 
# All routes down the pyramid involve stepping down and to the left or down and to the right.
# Input: A pyramid as a tuple of tuples. Each tuple contains integers.
# Output: The maximum possible sum as an integer.
# Precondition:
#     0 < len(pyramid) ≤ 20
#     all(all(0 < x < 10 for x in row) for row in pyramid)
            
# Running the path...
def getGold(pyramid, path): 
    gold=pyramid[0][0]
    idx=0
    for leap in range(1,len(pyramid)):    # Through the levels...
        idx+=int(path[leap-1])            # Setting next target 
        gold+=pyramid[leap][idx]          # Collecting gold!
    return gold
     
def count_gold(pyramid):  
    levels=len(pyramid)  # number of levels of pyramid
    nPaths=2**(levels-1) # number of possible paths
    print("Pyramid[" + str(nPaths) + "paths]: " + str(pyramid))
    maxGold=0
    for x in range(0,nPaths):
        path=str(bin(x)[2:]).zfill(levels-1) # Converting number of path to binary
        gold=getGold(pyramid,path) # Running the path
        maxGold=max(maxGold,gold)  # Looking for MAX
    print("Max Path: " + path + " - Max Gold: " + str(maxGold))
    return maxGold

if __name__ == '__main__':
    assert count_gold((
        (1,),
        (2, 3),
        (3, 3, 1),
        (3, 1, 5, 4),
        (3, 1, 3, 1, 3),
        (2, 2, 2, 2, 2, 2),
        (5, 6, 4, 5, 6, 4, 3)
    )) == 23, "First example"