It was time to climb the steps to the third level of the Foobar challenge. Google took that literally by serving up the following problem:
The Grandest Staircase Of Them All
==================================
With the LAMBCHOP doomsday device finished, Commander Lambda is preparing to debut on the galactic stage -- but in order to make a grand entrance, Lambda needs a grand staircase! As the Commander's 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 they 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 solution(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!
Languages
=========
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Java cases --
Input:
Solution.solution(3)
Output:
1
Input:
Solution.solution(200)
Output:
487067745
-- Python cases --
Input:
solution.solution(200)
Output:
487067745
Input:
solution.solution(3)
Output:
1
Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.
I was confused at first by the “You can buy different amounts of the different types of bricks (for example, 3 little pink bricks, or 5 blue lace bricks)“. I thought it meant the Commander was intending to combine different types of bricks in her staircase. It was only after I processed the examples a few times that I began to understand her requirements.
But even after I understood the goal, I struggled for quite some time to layout the problem in a way that would help me solve it. I kept drawing it out in different ways but it just wasn’t clicking. Changing the stairs to be increasing from left-to-right seemed to help. I eventually ended up with this visualization of a solution for an input of 6 bricks:
I could see a possible approach now. Start at ground level and then add the first step. The first step could be a height of anything from 1 to the number of available bricks, so long as there were still enough bricks to complete the next step. For each choice of first step height, the second step height then had to start at least one brick higher, but it could also be anything above that so long as there were still enough bricks available to complete the next step. This could continue on and I’d either reach a point where there were insufficient bricks to build the next step, or I’d use exactly the amount of bricks I had. Both scenarios would serve as recursive base cases, with the latter counting towards a final number of valid permutations.
Unfortunately not all test cases passed with that approach. I eventually considered that larger brick counts must be generating duplicate branches. Adding a dictionary keyed on the inputs of each branching allowed for that duplicate work to be cached and re-used. With that, the tests finally passed!
I wish I’d taken more time to review my comments with this one. I realized after submitting that I’d incorrectly translated my diagram to text. But the code itself got the job done:
# Author: Derek Moran, Level 3, Commander Lambda's Personal Assistant @ Commander Lambda Space Station
# Date: 25-NOV-2022
def solution(n):
# Your code here
return getNumberOfStaircasePermutations(n)
# Returns the number of permutations of staircases that can be built with the input number of bricks. Staircases follow these rules:
# - 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.
#
# The provided number of bricks must be an integer between 3 and 200 inclusive
#
# TODO: Since the possible input set is small, if the Commander is likely to run this frequently, it would probably make sense
# to run this for all inputs 3-to-200 and store the results in a lookup table, thus allowing for O(1) lookups from that result table.
def getNumberOfStaircasePermutations( numTotalBricks ):
if not type(numTotalBricks) is int:
raise TypeError("Number of bricks must be an integer")
if numTotalBricks < 3 or numTotalBricks > 200:
raise Exception("Number of bricks must be between 3 and 200 inclusive")
# Start with ( numBricksUsed, minNumBricksForNextStep ) = (0, 1)
# We can use 1 brick for the first step, and the remaining staircase permutations then must start at height 2
# Or we could use 2 bricks for the first step, and the remaining staircase permutations then must start at height 3
# Or we could use 3 bricks for the first step, and the remaining staircase permutations then must start at height 4
# And so on for as long as we have available bricks
#
# ie Starting from (0,1) we can add (1,2)+(2,3)+(3,4)+ ...
# (1,2) can then have added to it (3,3)+(4,4)+(5,5)+ ...
# (2,3) could then have added to it (5,4)+(6,5)+(7,6)+ ...
#
# This tree of calls can carry on until:
# - numBricksUsed reaches numTotalBricks, then that leaf ends the call chain and adds as a suitable permutation
# - numBricksUsed exceeds numTotalBricks, then that leaf ends the call chain and dismisses the permutation
#
# This may result in multiple calls with the same input ( numBricksUsed, minNumBricksForNextStep ),
# so we'll cache on this key so we can re-use that work in such cases
cache = {}
def numStaircasePermutationsFromNumTotalBricks( numBricksUsed, minNumBricksForNextStep ):
cacheKey = ( numBricksUsed, minNumBricksForNextStep )
if cacheKey in cache: return cache[cacheKey]
totalStaircasePermutations = 0
for numBricksToTryForNextStep in range( minNumBricksForNextStep, numTotalBricks ):
next_numBricksUsed = numBricksUsed + numBricksToTryForNextStep
if next_numBricksUsed == numTotalBricks:
totalStaircasePermutations += 1
break
if next_numBricksUsed > numTotalBricks:
break
next_minNumBricksForNextStep = numBricksToTryForNextStep + 1
numAdditionalStaircasePermutations = numStaircasePermutationsFromNumTotalBricks( next_numBricksUsed, next_minNumBricksForNextStep )
cache[ ( next_numBricksUsed, next_minNumBricksForNextStep ) ] = numAdditionalStaircasePermutations
totalStaircasePermutations += numAdditionalStaircasePermutations
cache[cacheKey] = totalStaircasePermutations
return totalStaircasePermutations
return numStaircasePermutationsFromNumTotalBricks( numBricksUsed = 0, minNumBricksForNextStep = 1 )
Leave a Reply