Robot in a Hallway Problem using Dynamic Programming in Python

What is Dynamic programming?

Dynamic programming is a powerful optimization technique in computer science. The dynamic approach is applicable to a lot of real-world problems.

The below problem is a very simple yet effective problem in order to gain a better understanding of dynamic programming and how it works in different kinds of problems.

The Problem

Following is the description of the problem:

There is a hallway which is n tiles long. The first tile is where the robot starts. Each tile has an item on it, with some worth (this worth can be negative). The robot will stroll along the hall, and at each tile, it can either get the item on that tile or not. After stepping off the last tile the robot’s problem comes to an end.

We wish to maximize the value of items the robot selects and list which items were really picked up by the robot for obtaining the maximum value, but there is an issue. Picking up items takes energy. The robot’s energy increases when it isn’t picking up items, however, it loses energy when it gets an item. It can always walk ahead (moving doesn’t consume energy) however in some cases, it may be unable to get the current item(when energy is 0).

The robot begins with 0 energy (as a result the first item will never be picked up by the robot). The robot is able to perform the following 2 actions:

  • Get the item on the current floor tile, move to the next tile, and lose 1 energy. This action can only be carried out when the robot has at least 1 energy
  • Don’t pick up the item and move ahead to the next tile which increases energy by 1.

Dynamic Programming Strategy for the above Problem

  1. Overlapping subproblems: Imagine that you have memoized the solutions to all the subproblems.

In this problem, we need to assume that we know the maximum value of items for each i<n and we know what items have been selected for reaching that maximum value.

 

  1. Optimal substructure: Think about how the original problem can be solved using these memoized solutions.

In this problem, in order to find maxValue(n), we need to check for the energy condition first:

If at maxValue(n-1): energy is > 0 then maxValue(n) = max(maxValue(n-1) + value[n], maxValue(n-1))

Else if at maxValue(n-1), energy = 0: then maxValue(n) = max(maxValue(n-1), maxValue(n-1) – value[i] + value[n]. 

NOTE: here ‘i’ is the index of the minimum value out of the selected values for maxValue(n-1).

 

  1. Build upon the solutions to the subproblems in order to solve the original problem.

In this problem, we simply build in the following manner: maxValue(0), maxValue(1), maxValue(2)……maxValue(n)

 

The following clearly illustrates the optimal substructure of the problem:

MaximumValue(n) = { 0, if n = 0

max( MaximumValue(n-1), MaximumValue(n-1) + value[n]), if energy > 0

max(MaximumValue(n-1), MaximumValue(n-1) – value[minSelectedIndex] + value[n]), if energy = 0

Let’s look at a very small and simple example to understand the solution better

Suppose the list of values of items is: [4,3,5]

Now, we know the item at index 0 (value = 4) can not be picked up as the energy is 0. 

So, we always start from index 1 (value = 3).

Now we have energy = 1 so we decide to pick up the item at index 1 because it does increase our maximum value to 3 which was 0 till now.

Then, we go to the item at index 2 (value = 5) but now energy  = 0. So, now we go through all the items that have been picked up for the previous maximum value and find the minimum out of these items. 

Then, we check that if subtracting this minimum value from the previous maximum value and adding to it the value at the current index is greater than the previous maximum value. 

If it is greater, we make the required changes to the solution of removing the index with the minimum value and adding the current index.

In this case, as there is only 1 selected item when we reach index 2 (value = 5), the minimum value out of the selected will be = 3 and thus subtracting this value and adding value = 5 will increase our maximum value to 5 (which was 3 till now). Thereafter, we make the required updates to the maximum value, selected list, and energy value.

 

Implementing the solution in Python

def optimise_single_pickup(hallway):
    """
        Input: a list of integers (hallway) with each element
        representing the value of the item at that index

        Output: a two-element tuple: the first element represents
        the maximum value. the second element is a binary list with
        0's representing an item NOT picked up at that index
        and 1's representing the item is picked up at that index

        Complexity: O(n^2)
    """

    n = len(hallway)
    selected_list = [0] * n  # stores selected items as 1's
    energy = 1  # we start at tile 2 so energy is 1
    # loop for finding correct list of tiles
    for i in range(1, n):
        if energy == 0:
            # when energy is 0, we find the minimum of the
            # already selected items and compare this one
            # and the minimum one
            x = minSelectedIndex(hallway[0:i], selected_list[0:i])
            if (hallway[x] < hallway[i]) & (hallway[i] > 0):
                selected_list[x] = 0
                selected_list[i] = 1
                energy += 1
            else:
                energy += 1
        elif energy > 0:
            # when energy is one or more we pick the item if greater than 0
            if hallway[i] > 0:
                selected_list[i] = 1
                energy -= 1
            else:
                energy += 1

    sum1 = 0

    # to find total value of selected items
    for i in range(n):
        if selected_list[i] == 1:
            sum1 += hallway[i]

    ouput = (sum1, selected_list)

    return ouput


# helper function for task 1
# finds index of minimum selected item
def minSelectedIndex(hall, sel_list):
    """ Input: 2 lists: hallway: represents the same hallway list as before and, selected_list: represents the selected items

        Output: for the selected items in corridor
        according to the given selected_list, return the index
        of the minimum item.

        Complexity: O(n)
        """
    selected_indexes = []
    # selected_indexes stores the indexes of selected items
    for j in range(len(sel_list)):
        if sel_list[j] == 1:
            selected_indexes.append(j)

    op2 = selected_indexes[0]
    # this loop finds index of the minimum item sel_list of the selected ones
    for i in range(1, len(selected_indexes)):
        if hall[selected_indexes[i]] < hall[op2]:
            op2 = selected_indexes[i]

    op = op2

    return op

 

Let’s run an example

optimise_single_pickup([4,0,4,5,-3,4,3,2])

Output:

15, [0, 0, 1, 1, 0, 1, 0, 1])

Thank you for sparing your valuable time for reading this article.

Leave a Reply

Your email address will not be published. Required fields are marked *