Asteroid Mining - Dynamic Programming problem

Question

I was given the following assignment:

There is n gram of mineral to be dug up on a certain asteroid. At the beginning there is only one robot at our disposal. Each robot can do one of two activities in a day (which take up the whole day):

1. dig up 1 gram of mineral
2. clone itself (the clone can only take action the next day)

Write a function that returns the minimum number of days needed to dig up at least n grams of mineral.

Of course, I immediately realised that this was a dynamic programming problem, but I have no idea how to solve the problem this way.

The only thing I managed to do was the naive recursive solution, which doesn't pass all the tests, which doesn't surprise me, because n can be up to a million:

def mining_rec(n, r = 1, d = 0):
    if n <= 0:
        return d
    if r >= n:
        return d + 1

    if r == 1:
        return min(mining_rec(n - 1, r, d + 1), mining_rec(n, r + 1, d + 1))
    else:
        for i in range(r + 1):
            mining_robots = i
            cloning_robots = r - i
            return mining_rec(n - mining_robots, r + cloning_robots, d + 1) 

Do you have any ideas on how this could be done using dynamic programming?

Answer 1

First of all, your current code has a for loop that will always exit upon its first iteration. This happens to turn out fine (you're lucky), because the other iterations would never lead to a more optimal solution. In other words, when you don't have enough robots yet to mine the required minerals, it is never a bad idea to have all of them make clones.

Still, let's first fix the code to make it do what you initially intended:

In that case you should perform all iterations of the loop, and keep the minimum of the values you got from the recursive calls. Like so:

    return min(
        mining_rec(n - mining_robots, r + (r - mining_robots), d + 1)
        for mining_robots in range(r + 1)
    )

You don't actually need to deal with r==1 separately, as also in that case you can use the above code.

Then, to use memoization, use functools.cache:

@cache
def mining_rec(n, r = 1, d = 0):
    if n <= 0:
        return d
    if r >= n:
        return d + 1

    return min(
        mining_rec(n - mining_robots, r + (r - mining_robots), d + 1)
        for mining_robots in range(r + 1)
    )

Greedy solution

But as already hinted above, you don't really have to go through this tree of possible choices. You can take a greedy approach where you only dig up minerals in the last day, when you have enough robots. In all other cases you can choose to clone all available robots.

This means the number of robots you have will double each day until you have reached a number of robots that is not less than the number of grams you need of the mineral. In other words, you need to clone for a number of days that is approximately log₂𝑛. More precisely it is ⌈log₂𝑛⌉ and to that we have to add one day for the digging.

That leads to this code:

def mining_greedy(n):
    return 1 + (n - 1).bit_length() if n > 0 else 0