CODEWITHSUNDEEP
python
Jacob Pimental
Jacob Pimental

Reputation: 33

Brick Tower Building Puzzle

I've been given a little brainteaser to solve.

The task is to make a function with a single integer parameter. You have to figure out how many different combination of tower patterns you can make with that given amount of bricks (each proceeding tower must be less in height than one previous, kind of like). There must be 2 or more towers, one right next to the other.

For example, if you were given 3 blocks you can only produce 1 combination of towers, one with a height of 2 and its neighbor having a height of 1:

|
| |
2 1

Given 4 you can only still produce one combination since the next tower must be shorter than the previous:

|
|
| |
3 1

Given 5 you can produce 2 combinations:

|
|
|
| |
4 1

|
| |
| |
3 2

I have a function that can do all of this, however they give the example that 200 blocks should produce 487067745. Which my function simply does not do. I don't know what I am doing wrong. A push in the right direction would be very much appreciated. My function now looks like this:

def answer(num):
    # divide the blocks so we have two towers, one with a height of n-1 and 
    # the other with a height of one
    l1 = num-1
    l2 = 1
    combinations = 0
    while True:
        if l1 > l2:
            # add 1 to the combinations along with how many combinations we 
            # can make using the blocks from tower two
            combinations += 1 + answer(l2)
        elif l1 == l2:
            # see if we can make additional towers out of the rightmost tower
            # and add that to the combinations
            combinations += answer( l2 )
        else:
            # if the first tower is smaller than or equal to the other tower 
            # then we stop trying to make combinations
            return combinations
        l1 -= 1
        l2 += 1

While this method does work for smaller numbers of bricks (returning 2 combinations for 5 blocks and 1 combination for 3 or 4 blocks), it does not work for much larger numbers that would be impossible to do on sheets of paper.

Upvotes: 0

Views: 2964

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58409

Wikipedia gives the generating function for the number of partitions of n with distinct parts as q(n) = product (1+x^k) for k=1..infinity. Given that you exclude the possibility of a single tower, the number of different valid tower arrangements is q(n)-1.

This gives this neat O(n^2) time and O(n) space program for counting tower arrangements.

def towers(n):
    A = [1] + [0] * n
    for k in xrange(1, n+1):
        for i in xrange(n, k-1, -1):
            A[i] += A[i-k]
    return A[n] - 1

print towers(200)

The output is as required:

487067745

To understand the code, one can observe that A stores the first n+1 coefficients of the generating function product(1+x^k) for k=1...infinity. Each time through the k loop we add one more term to the product. We can stop at n rather than infinity, because subsequent terms of the product do not affect the first n+1 coefficients.

Another, more direct, way to think about the code is to define T(i, k) to be the number of tower combinations (including the single tower) with i blocks, and where the maximum height of any tower is k. Then:

T(0, 0) = 1
T(i, 0) = 0 if i > 0

T(i, k) = T(i, k-1)               if i < k
        = T(i, k-1) + T(i-k, k-1) if i >= k

Then one can observe that after j iterations of the for k loop, A contains the values of T(j, i) for i from 0 to n. The update is done somewhat carefully, updating the array from the end backwards so that results are changed only after they are used.

Upvotes: 6

Wso
Wso

Reputation: 302

Imagine calling the function answer(6). Your code returns 2, the correct answer however is 3 (5, 1; 4, 2; 3, 2, 1). Why is this? your code stops when the amount of blocks above the bottom tower is greater than the length of the bottom tower, so it sees 3, 3 and stops, it therefor never considers the combination 3, 2, 1.

My advice would be to rethink the function, try to take into account the idea that you can stack a number of blocks N on top of a tower that is less than N high.

Upvotes: 1

Related Questions