Pillar jumpers in python

Question

I've been stuck on an assignment for a few days now. And I can't even start coding since I don't even fully understand the assignment. So if someone could help me and indicate me in the right direction, I would be really grateful!

Image of text of the exercise, the image reads:

Josefine and her friends has invented a new game called Pillar Jumpers. In this game, a sequence of N pillars of non-decreasing heights are placed next to each other. The player starts on the first pillar, and the target is to reach the last pillar in at most J jumps.

The player has a certain jump strength S that determines how far he can jump. Let hi be the height of the i'th pillar for i∈ [1…N] The player can jump from pillar i to j if i< j ≤ i+S and hj ≤ hi+S

Given the heights of the pillars and the maximum number of jumps J, determine the minimum required jump strength S such that the player can still finish the game.

Input format :

Line 1: The integers N and J  
Line 2: The heights of the N pillars in a list

Output format

Line 1: The minimum required strength S.

So my first approach was to try to consider an array made out of the difference of the different heights, but it didn't work :/

And then I tried to split my original height list into J sublists and then compute the difference between the first and last value of each sub list, and then return the smallest one, but it didn't work either :/

Answer 1

I'm not sure which part of the problem you're struggling with, but essentially, the problem limits how far and how high the player can jump by the same factor S. The first thing that came to my mind is an approximate solution. Starting with some large value of S, you could "simulate" the problem with a loop that finds the farthest pillar j that satisfies the jumping limit, go to that pillar, and repeat the loop. Once you've reached the end then you would have discovered the minimum jumps needed for that particular S value. this value is probably smaller than the given input J, so you would repeat the simulation with a smaller jump strength S until your minimum jumps needed reach J. At this point, your S should be very near the correct value.

Answer 2

I won't post any code since this is an assignment, but since you've been stuck for a few days, I will give you a bit more than a hint:

1. Can you simplify the array so it will be easier to work with. How about taking the difference in height between consecutive pillars. You say in your post that you've tried it, it was a great idea !
2. Once you have it, how do you know if the challenge is impossible for a given strength, what does it mean? Don't look bellow unless you're stuck.

Think of it as stairs, is the step so big that I haven't got the strength to climb it.
Is any of the steps of the stairs bigger than my strength?

3. Now that we know it is possible, we have to loop... How many loops ? Why ? What variables do we include ? What do we keep track of ?

We have to climb all the steps of the stairs, this is a loop...
We have to keep track of what step I am on so we know where we are.
We have to keep track of the number of jump I've made to climb to the current step.

4. How to jump ? How many pillars do we skip per jump ? What is the rule, what does that mean to jump ?

While I am jumping, I should go to the next pillar if NUMBER_OF_STEPS < STRENGTH AND SUM(STEPS) < STRENGTH. where NUMBER_OF_STEPS is the number of steps in this jump and SUM(STEPS) is the difference in height between the step we leave and the current step. Right ? That was given in your assignment, I've just rephrased it.

5. Now that we know how many jump it takes for a given strength. We can try with different strengths and answer the question.

Answer 3

Since a definitive answer has not yet been given, and the fact that you are absolutely over the assignment due date by now, here is a valid solution in Python3, that uses O(N) space for storing the pillars and O(n * log n) worst case time complexity for reporting the best possible jump strength S.

The idea is to start with a good estimated guess of S, and then binary search for the optimal value. If we can't reach the last pillar, it means S is too small, and we increase the lower bound. If we can reach the last pillar, S might be smaller, so we decrease the upper bound. We check if S is valid in O(N) time (iterating through the pillar array), and we do this a worst case of log n number of times (binary search for S).

def main():
    # Read input variables N = number of pillars, J = number of jumps
    N, J = input().split()

    # Convert to integers
    N = int(N)
    J = int(J)

    # Read in the pillars, and convert them to integers
    pillars = input().split()
    pillars = [int(x) for x in pillars]

    # We need an estimated guess of the starting strength for S.
    # A very good approximation could be the average jump height needed to go to the last pillar in J jumps,
    # since this value must be a minimum jump strength to succeed.
    max_pillar = pillars[-1]
    min_pillar = pillars[0]
    S = (max_pillar - min_pillar) // J

    # For cases of pillars such as [1, 1], we want a minimum jump strength of 1, as 0 doesn't count
    S = max(S, 1)

    # We then optimize S through a binary search algorithm.
    optimized_S = optimize_S(S, J, pillars)

    # Print the result
    print(optimized_S)


def optimize_S(S, J, pillars):
    # We define the lower bound and upper bound - this will initially between S and S^2.
    low = S
    high = S * 2
    
    # As long as our interval is at least length 1, we can keep searching
    while low < high:
        
        # We find the midpoint of the interval, and check if this value of S is a valid jump strength
        mid = (low + high) // 2

        if check_strength(mid, J, pillars):

            # If the jump strength is valid, we narrow down the search interval, by updating the upper bound to the midpoint
            high = mid
        else:
            # If it is not valid, we narrow down the search interval, by updating the lower bound to the value just larger than the midpoint.
            low = mid + 1
    
    # We return the lowest value of S that is valid.
    return low

# This function checks if a given jump strength is valid for a given set of pillars.

def check_strength(S, J, pillars):
    # We have J jumps.
    jumps = J

    # We start at the first pillar, and keep track of our current pillar as we go.
    current = pillars[0]

    for i in range(len(pillars)):

        # We only jump, whenever we need to. This is the case when we meet a pillar that is higher than our current pillar + our jump strength.
        # We decrement the number of jumps we have left, and update our current pillar.
        if current + S < pillars[i]:
            jumps -= 1
            current = pillars[i-1]

            # If we still can't jump to the next pillar OR we have no more jumps left, we didn't succeed.
            if current + S < pillars[i] or jumps == 0:
                return False

    # If we made it through the loop, it means we succeeded, and we made it to the final pillar.
    return True


if __name__ == "__main__":
    main()