Jumping Frog with Energy - Difficult Dynamic Programming/Greedy Problem

Question

Given a set of n stones, arranged in a row at equal distances from each other. The stones are numbered from 0 to n-1. A frog that is on stone number 0 has to get to stone number n-1.

A jump is a move from stone i to stone j ( i<j ). Such a jump has length equal to j-i. The maximum jump length of the frog depends on its energy level (which cannot drop below 0). A jump of length j-i costs the frog j-i energy. For example, with an initial energy of 3, a frog on stone 0 can jump to stone 3 at most.

On some stones, there may be worms, which add energy to the frog. If the frog jumps on a stone with a worm on it, it MUST eat the worm. The list T[0...n-1] contains the energy values of the worms on the corresponding stones. If there is no worm on the stone, this is equivalent to a value of 0.

The frog starts with 0 Energy, but it is guaranteed that there is a worm on stone number 0.

Given a list T, the task is to return a list of the indexes of the stones on which the frog has been, before getting to stone n-1. However, this must be the shortest possible list. In some cases there may be more than one solution, whichever is accepted. It is guaranteed that always the frog will be able to get to stone n-1.

Example no. 1: For T = [3, 0, 2, 1, 0, 2, 5, 0] the answer is [0, 2, 5].

Example no. 2: For T = [7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0] the answer is [0, 3, 7] or [0, 5, 7].

I have no idea how to approach this problem, all I know is that I probably need to use some dynamic programming or greedy algorithm here, but how? Anyone have any ideas?

Answer 1

You can solve this in O(n log n) time using a greedy algorithm and a priority queue.

It is quite helpful to re-frame the problem away from jumps of variable length.

New problem framing:

• Suppose you're at the 0th stone, and must walk on every stone from 0 to n-1.
• You have T[0] current energy-units initially, and every step costs 1 energy unit.
• At each stone T[i] you pass, you get an option to pay one jump-dollar and receive T[i] energy-units, at most once. Your goal is to minimize the cost in jump-dollars.
• Your energy units are not allowed to be at zero when you take a step.

The key observation is that we don't have to decide which stones we've landed on (bought energy from) until we actually need that energy for our next step.

So, keep a max-heap (priority-queue) of all the T[i] (energy-units sales) that we've passed but haven't purchased. If our current energy is 0, greedily remove the largest T[i] (energy-unit sale), add it to our current energy, and append i to the list of stones we've bought energy from.

This is akin to retroactively having decided to stop at the ith stone, which is OK since nothing is affected apart from our current energy and the list of available energy choices. This greedy algorithm works because we only ever visit a stone when it is unavoidable, and choosing any other stone to visit (instead of the highest energy unused one) can never increase our current energy.

---

Python code (using the heapq module)

def min_jump_path(stones: list[int]) -> list[int]:
    """Return a shortest valid path to end of the array.
    We must walk from index 0 to n-1, at a cost of 1 energy unit per step.
    Energy cannot be 0 when taking a step.
    Runtime: O(n log n). Space: O(n)"""

    used_stones: list[int] = [0]
    current_energy: int = stones[0]

    available_energy_choices: list[tuple[int, int]] = []

    for idx, energy_offered in enumerate(stones[1:], 1):
        current_energy -= 1

        # If we need to use some stone's energy to continue
        if current_energy < 0:

            # Return some 'error-value' if impossible
            if len(available_energy_choices) == 0:
                return []

            energy_gain, stone_used = heapq.heappop(available_energy_choices)
            energy_gain = -energy_gain  # Negated for max-heap
            current_energy += energy_gain
            used_stones.append(stone_used)

        if energy_offered > 0:
            heapq.heappush(available_energy_choices,
                           (-energy_offered, idx))  # Negated for max-heap

    # Used stone list may be out of order initially
    return sorted(used_stones)

Usage:

print(min_jump_path([3, 0, 2, 1, 0, 2, 5, 0]))
# [0, 2, 5]

print(min_jump_path([7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]))
# [0, 5, 7]

Answer 2

Note that an optimal solution never jumps backwards: remove the jump immediately before turning backwards to make it more optimal, thus disproving the initial solution's optimality. This gives us a natural order in which to consider positions.

---

Consider the state of the problem's world:

• the frog is at position p,
• has e energy,
• and used k jumps to get there.

So, the trivial form of a solution is: given p, e, and k, is it possible to arrive at such a state?

Now, we can just ask f(p,e,k), which is either true or false, for every possible set of parameters, consider the previous or next jump to arrive at such a state, and perhaps get an inefficient but working solution, recursive or iterative. The base is f(0,T[0],0) = true, and the desired states are f(n-1,?,?).

To make it more efficient, perhaps we can make some of the parameters (p, e, or k) the target function.

• For example, consider g(p,e) = min k: for given position and energy, calculate the minimum number of jumps to have such position and energy. For convenience, define k as plus-infinity if such state (p,e) is not reachable with any number of jumps.

• Or consider h(p,k) = max e: if we reached position p in exactly k jumps, how much energy can we have left as surplus? Again, define as minus-infinity if (p,k) is not reachable at all.

• Finally, we may even be able to do a(p) = best pair (k,e): for a given position p, what is the minimum number of jumps k to arrive there, and with this exact number of jumps, what is the maximum amount of surplus energy e the frog can still have? (Perhaps this won't work, but it's still educative to think why exactly it won't.)

---

Consider this list, or expand on it, to decide which approach would work for you -- or at all.

Answer 3

I can think of 2 heuristics when it comes to deciding which stone to jump to: "the farthest stone possible" and "the most rewarding stone possible".

---

The Farthest Stone Possible

1. Calculate the minimum energy required to reach the end, say M, at each stone.
2. Jump to the farthest stone where you would keep at least the minimum energy required at the stone.
3. Repeat step 2 until you reach the last stone.

---

The Most Rewarding Stone Possible

1. Calculate the minimum energy required to reach the end, say M, at each stone.
2. At each jump, work out the reward function:

Reward of the jump (R) = Energy to be earned by the jump - Energy to be spent by the jump

3. Jump to the most rewarding stone among the possible next stones while satisfying the minimum energy requirement at the next stone. Choose the farthest one if multiple stones are equally rewarding. Also, always choose the last stone if that is possible.

4. Repeat step 2-3 until you reach the last stone.

---

Example 2 with The Farthest Stone Possible heuristic:

Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
  T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
  M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]

Steps

1. At Idx 0 - energy 7

-> jump to 5 since that is the farthest stone you can get while satisfying the minimum energy requirement.

2. At Idx 5 - energy 5

-> jump to 7 for the same reason as in the step 1.

3. At Idx 7 - energy 9

-> jump to the last stone for the same reason as in the step 1.

---

Example 2 with The Most Rewarding Stone Possible heuristic:

Idx: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14]
  T: [ 7, 0, 0, 1, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0, 0]
  M: [-3, 3, 2, 1, 1, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0]

Steps

1. At Idx 0 - energy 7

Next Idx Possible	Reward
1	-1
2	-2
3	-2
4	-4
5	-2

-> choose 5

2. At Idx 5 - energy 5

Next Idx Possible	Reward
6	-1
7	4
8	-3
9	-4
10	-5

-> choose 7

3. At Idx 7 - energy 9

-> choose the last stone since it's possible