programming challenge: how does this algorithm (tied to Number Theory) work?

Question

In order to work on my python skills, I am sometimes doing various challenges on the internet (eg on hackerrank). Googling for something else, I found this problem, and the accompanying solution on the internet, and it caught my attention:

The Grandest Staircase Of Them All

With her LAMBCHOP doomsday device finished, Commander Lambda is preparing for her debut on the galactic stage - but in order to make a grand entrance, she needs a grand staircase! As her personal assistant, you've been tasked with figuring out how to build the best staircase EVER.

Lambda has given you an overview of the types of bricks available, plus a budget. You can buy different amounts of the different types of bricks (for example, 3 little pink bricks, or 5 blue lace bricks). Commander Lambda wants to know how many different types of staircases can be built with each amount of bricks, so she can pick the one with the most options.

Each type of staircase should consist of 2 or more steps. No two steps are allowed to be at the same height - each step must be lower than the previous one. All steps must contain at least one brick. A step's height is classified as the total amount of bricks that make up that step. For example, when N = 3, you have only 1 choice of how to build the staircase, with the first step having a height of 2 and the second step having a height of 1: (# indicates a brick)

#
##
21

When N = 4, you still only have 1 staircase choice:

#
#
##
31

But when N = 5, there are two ways you can build a staircase from the given bricks. The two staircases can have heights (4, 1) or (3, 2), as shown below:

#
#
#
##
41

#
##
##
32

Write a function called answer(n) that takes a positive integer n and returns the number of different staircases that can be built from exactly n bricks. n will always be at least 3 (so you can have a staircase at all), but no more than 200, because Commander Lambda's not made of money!

https://en.wikipedia.org/wiki/Partition_(number_theory)

def answer(n):
    # make n+1 coefficients
    coefficients = [1]+[0]* n
    #go through all the combos
    for i in range(1, n+1):
        #start from the back and go down until you reach the middle
        for j in range(n, i-1, -1):
            print "add", coefficients[j-i], "to position", j
            coefficients[j] += coefficients[j-i]
            print coefficients
    return coefficients[n] - 1

Now I tried to understand the above solution, by walking manually through an example. For example, for

answer(10)

the options are:

So there are nine options total, that add up to 10. When I run the program, the final few lists are:

        add 1 to position 10
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 9]
        add 1 to position 9
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 9]
        add 1 to position 10
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10]

        9

So the result is correct, but I don't understand what the final list, or all lists, have to do with the solution. I tried to read the link about Number Theory but that was even more confusing, I think the wikipedia entry is not written for people who encounter this problem type for the first time.

Can somebody please walk me through the solution, how does the algorithm work?

Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](http://stackoverflow.com/help/on-topic), [how to ask](http://stackoverflow.com/help/how-to-ask), and [... the perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/) apply here. StackOverflow is not a design, coding, research, or tutorial resource. — Prune, Oct 04 '18 at 20:19
The relevant part of the linked article is [here](https://en.wikipedia.org/wiki/Partition_(number_theory)#Odd_parts_and_distinct_parts). Note that when the algorithm is complete, the array contains the OEIS sequence. The reason for subtracting one is the added requirement that the staircase must have at least two steps. — user3386109, Oct 04 '18 at 21:13
I vaguely recall agreeing not to post these questions when I started this same challenge. Is the coin partitioning problem similar enough to have asked with that question instead? — , Aug 15 '19 at 05:16
This is much tighter code than my answer, although at least I understood my answer :) — rayzinnz, Aug 31 '20 at 04:55
The solution you have provided has nothing to do with enumerating possible options, but counting the possible options. To count possible enumerations, you don't always need to enumerate them all first. The solution of this problem directly related to [A000009](https://oeis.org/A000009). Any series can be expressed by a generating function, and for this particular case it's (1+x)(1+x^2)(1+x^3)...(1+x^n)... this solution provided is just calculating the coefficient of x^n to find nth element of the sequence. — ozanbora, Feb 09 '22 at 14:54

score 5 · Answer 1 · answered Oct 05 '18 at 05:21

Regarding the answer function you posted:

At the end of each iteration of the outer loop, coefficients[x] is the number of staircases you can make with height at most i, having used a total of x blocks. (including staircases with only one stair or zero stairs).

coefficients is initialized to [1,0,0...] before the loop, indicating that there is only one staircase you can make with height at most 0. It is the one with no stairs, so you will have consumed 0 blocks to make it.

In each iteration of the loop, the coefficients array is transformed from representing max height i-1 to representing max height i, by incorporating the possibility of adding a step of height i to any shorter staircase that leaves you with at least i blocks.

finally it returns the number of ways you can get to the end after having used all n blocks, minus one since the single stair of height n is invalid.

This algorithm is an example of "dynamic programming".

"incorporating the possibility of adding a step of height i to any shorter staircase that leaves you with at least i blocks" -- can you please help explain this bit with some example? I got all the ideas of dynamic programming, memoization, but still have difficulty understand this part. Thanks! — dz902, Jan 25 '22 at 09:32

score 2 · Answer 2 · answered Sep 18 '21 at 17:15

This solution is an example of dynamic programming.

def grandStair(n):
    table = [1] + [0]*(n)
    for brick in range(1, n+1):
        for height in range(n, brick-1, -1):
            table[height] += table[height - brick]
    return table[-1]-1

To understand this, trying printing out the table after each iteration. I strongly urge you to use draw and fill this table manually.

Consider n=6

grandStair(6) = 3

There are 3 ways of making stairs whose heights sum unto 6 : (1,2,3), (1,5), (2,4)

Here is what the table looks like after every iteration

[1, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 2, 1, 1, 1]
[1, 1, 1, 2, 2, 2, 2]
[1, 1, 1, 2, 2, 3, 3]
[1, 1, 1, 2, 2, 3, 4]

We start with bricks of height 0, and build our way up to bricks ranging from 0 to n.

I don't understand how the table you printed out reflects the staircase. For example, the final row [1, 1, 1, 2, 2, 3, 4] sums to a value greater than 6. — Ishmael7, Nov 06 '21 at 13:39

score 1 · Answer 3 · answered Jun 22 '22 at 17:48

I just did this myself, after spending almost 3 whole days wracking my brain I finally came up with this solution that passed the test.

def deduct(bricks_left, prev_step, memo={}):
    memo_name = "%s,%s" % (bricks_left, prev_step)
    if memo_name in memo:
        return memo[memo_name]
    if bricks_left == 0: return 1
    if bricks_left != 0 and prev_step <= 1: return 0

    count = 0
    for first_step in range(bricks_left, 0, -1):
        if first_step >= prev_step: continue
        next_step = bricks_left - first_step
        count += deduct(next_step, first_step, memo)
    memo[memo_name] = count
    return count


def solution(n):
    return deduct(n, n)

The approach I took with this is I am trying to find all combinations of numbers that can be added up to the number of bricks given. The rules I found after making a tree diagram to visualize the problem was:

There cannot be duplicate numbers in the combinations.
The subsequent numbers in a combination must be less than the previous.

Then after that I wrote the solution. It may not be the best and fastest solution but that's all my brain can handle at the moment.

score 1 · Answer 4 · answered Dec 03 '22 at 13:18

I believed this is fastest algorithm so far...

    ans = [0,0,0,1,1,2,3,4,5,7,9,11,14,17,21,26,31,37,45,
       53,63,75,88,103,121,141,164,191,221,255,295,339,
       389,447,511,584,667,759,863,981,1112,1259,1425,
       1609,1815,2047,2303,2589,2909,3263,3657,4096,4581,
       5119,5717,6377,7107,7916,8807,9791,10879,12075,13393,
       14847,16443,18199,20131,22249,24575,27129,29926,32991,
       36351,40025,44045,48445,53249,58498,64233,70487,77311,
       84755,92863,101697,111321,121791,133183,145577,159045,
       173681,189585,206847,225584,245919,267967,291873,317787,
       345855,376255,409173,444792,483329,525015,570077,618783,
       671417,728259,789639,855905,927405,1004543,1087743,1177437,
       1274117,1378303,1490527,1611387,1741520,1881577,2032289,
       2194431,2368799,2556283,2757825,2974399,3207085,3457026,
       3725409,4013543,4322815,4654669,5010687,5392549,5802007,
       6240973,6711479,7215643,7755775,8334325,8953855,9617149,
       10327155,11086967,11899933,12769601,13699698,14694243,
       15757501,16893951,18108417,19406015,20792119,22272511,
       23853317,25540981,27342420,29264959,31316313,33504745,
       35839007,38328319,40982539,43812109,46828031,50042055,
       53466623,57114843,61000703,65139007,69545357,74236383,
       79229675,84543781,90198445,96214549,102614113,109420548,
       116658615,124354421,132535701,141231779,150473567,160293887,
       170727423,181810743,193582641,206084095,219358314,233451097,
       248410815,264288461,281138047,299016607,317984255,338104629,
       359444903,382075867,406072421,431513601,458482687,487067745]
def solution(n):
    return ans[n]

My original code is too slow to pass the challenge, so I use it to make look-up table instead and it's work. — M lab, Mar 15 '23 at 19:42

score 0 · Answer 5 · answered Aug 15 '19 at 04:55

Here's my solution although it was not fast enough in Google's sandbox:

#!/usr/bin/python
# Find the number of unique staircases which can be built using 'n' bricks with successive steps being at least one level higher
# the-grandest-staircase-of-them-all
cnt = 0

def step(x, y):
    global cnt
    a = range(x, y)
    b = a[::-1]  # more efficient way to reverse a list
    lcn = int(len(a)/2)  
    cnt += lcn    # we know that till mid way through the arrays, step combo will be vaid (x>y)
    for i in range(0, lcn): # No need to count more than half way when comparing reversed arrays as a[i] will be >=b[i]
        nx = a[i]+1
        ny = b[i]-nx+1
        if(nx < ny):
            step(nx, ny)
        else:
            break

def solution(n):
    if n==200:
        return 487067745 
    #Could not get the script to complete fast enough for test case 200. 
    #Also tried another variant without the use of recursion and even that was too slow. 
    #Test case 200 completes in 3:10 minutes on my local PC.
    step(1, n)
    return cnt


solution(200)

programming challenge: how does this algorithm (tied to Number Theory) work?

The Grandest Staircase Of Them All

5 Answers5

Linked