#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    1
    Rep Power
    0

    Counting block combinations


    I am given the following problem : A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this.

    How many ways can a row measuring fifty units in length be filled?

    Here's what I've wrote so far in python:

    Code:
     cache = [0]*51
    def prob(blocksize,colorsize):
        solutions = 1
        if(colorsize>blocksize): return solutions
        if(cache[blocksize] != 0): return cache[blocksize]
        for position in range(0,blocksize-colorsize+1):
            #print('\n',"New position:",position)
            for blocklength in range(colorsize,blocksize-position+1):
                #print("P:",position,"S:",blocklength,"Res:",solutions)
                solutions+=prob(blocksize-position-blocklength-1,colorsize)
                #print("Blocksize:",blocksize-position-blocklength-1,"Colorsize:",colorsize)
        cache[blocksize] = solutions
        return solutions
    
    print(prob(50,3))
    Can someone please explain to me how this recursive function works please. I've been studying recursive function and I understood how it works.The problem is that I cannot understand how the speffic one works.
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,714
    Rep Power
    480

    Project Euler #114.


    I haven't yet solved #114. You've made interesting comments: "The program you wrote that you don't understand."


    The program would be easier for me to read if the variable names corresponded to the problem description, block and row. I could refactor to please myself...


    These conditions terminate the recursion. The second says "if this is already solved use the cached answer".

    if(colorsize>blocksize): return solutions
    if(cache[blocksize] != 0): return cache[blocksize]



    for position in range(0,blocksize-colorsize+1):

    describes all the places a block could be inserted (by "left edge")



    for blocklength in range(colorsize,blocksize-position+1):

    are the lengths of red blocks that would fit.



    solutions+=prob(blocksize-position-blocklength-1,colorsize)

    Note that the recursion depends on both iteration variables, position and blocklength. In other words, the number of solutions is the number of ways to get populate to here plus the number of ways to populate the remaining of the space after sticking in said red block at said position.



    I hope this didn't help.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo