Using Stacks to solve Desert Crossing Problem in Python

In this tutorial, we are going to take a look at a Desert Crossing problem, how we can use stacks in order to solve that problem and simultaneously learn about stacks in Python. 

Let’s first take a look at what the problem says:

A man is crossing a desert using a compass and he has been given certain directions for his task. The directions can only include: “NORTH”, “EAST”, “WEST”, “SOUTH”. However, the desert has scorching hot weather, and it would be beneficial if the man could save some energy. Thus, your task is to simplify the directions and remove the directions which cancel each other out, i.e., remove those CONSECUT̛IVE directions which are OPPOSITE to each other and. 

We need to write a function reduceDir(direction_list) which returns the simplified version of directions given in the direction_list.

Here are some examples to better understand the problem:

  1. [“SOUTH”, ”NORTH”, ”WEST”] → returns [“WEST”] as SOUTH and NORTH are opposite and are consecutive to each other.
  2. [“SOUTH”, ”EAST”, ”WEST”, ”NORTH”] → returns [] (empty list) as EAST and WEST are consecutive opposites and removing them leaves [“SOUTH”, “NORTH”] which are also consecutive opposites and hence they are removed and leave an empty list [].
  3. [“SOUTH”, ”EAST”, ”NORTH”, ”WEST”] → returns [“SOUTH”, ”EAST”,” NORTH”, ”WEST”] which is the same list because the directions are already simplified and none of them are consecutive opposites.

 

Now let’s see what stacks are.

Stacks

A stack is a data structure where… 

  • We can only interact with the item at the ‘top’ (stack[-1]) 
  • We can ‘push’ something to put it on the top of the stack (stack.append(…)) 
  • We can ‘pop’ to take something from the top of the stack (stack.pop()) 
  • We can also check its size (len(stack)) 

This kind of behavior is commonly referred to as LIFO (Last in First Out)

You can think of stacks as a pile of plates. Only the top plate can be removed at a time and a new plate can only be added to the top of the pile.

How to use stacks in order to solve the desert crossing problem?

We will treat the given direction_list as a stack and use the following approach in order to solve this problem:

  1. We pop the last element from the direction_list and append it to a new empty stack, call it ‘new_stack’.
  2. We then pop again from both our stacks (direction_list and new_stack) and compare these two. 
  3. If they are NOT opposite directions we append the popped element from new_stack back to new_stack and also append the popped element from direction_list to new_stack. 
  4. Else (if they are opposite directions): we do nothing.
  5. We repeat steps 2-5 until the given direction_list is empty.

 

NOTE: We handle the empty list case separately.

Implementing the code in Python

Below is the Python code to solve the desert crossing problem Using Stacks:

def reduceDir(direction_list):
  """ 
  Input:  a list of directions out of "NORTH", "EAST", "WEST", "SOUTH".
  Output: a simplified version of directions of the input list.
  Complexity: O(len(direction_list))
  """
  # handling for direction_listay length 0
  if len(direction_list)==0:
    return direction_list
  
  # we treat the two lists: direction_list (given) and new_stack as stacks
  # in a stack we only have access to the last element, which can be popped using .pop() and a new element can only be inserted at the end of the stack using .append()
  # we pop from direction_list and append it to new_stack

  new_stack = []
  x = direction_list.pop()
  new_stack.append(x)
  while len(direction_list)!=0:
    if new_stack ==[]:
      # this executes when new_stack becomes empty
      if direction_list==[]:
        # this checks for the direction_list to have something to be popped
        break
      x = direction_list.pop()
      new_stack.append(x)
    
    if direction_list==[]:
      # this checks for the direction_list to have something to be popped
      break
    t = new_stack.pop()
    m = direction_list.pop()
    if isTheOppositeOf(t,m) == False:
      # this executes when the two popped elements are not opposite
      new_stack.append(t)
      new_stack.append(m)

  new_stack.reverse()
  return new_stack


def isTheOppositeOf(t,m):
  # this is a helper function which returns True if the two given directions are opposite and False otherwise
  if t=="NORTH" and m =="SOUTH":
    return True
  elif t=="SOUTH" and m =="NORTH":
    return True
  elif t=="EAST" and m =="WEST":
    return True
  elif t=="WEST" and m =="EAST":
    return True
  return False

Let’s run a few examples:

  1. a = ['SOUTH','NORTH','WEST']
    
    print(reduceDir(a))

    Output:

    ['WEST']

     

  2. a = ['SOUTH','EAST','WEST','NORTH']
    
    print(reduceDir(a))

    Output:

    []

     

  3. a = ['SOUTH','EAST','NORTH','WEST']
    
    print(reduceDir(a))

    Output:

    ['SOUTH','EAST','NORTH','WEST']
  4. a = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
    
    print(reduceDir(a))

    Output:

    ["WEST"]

     

Thank you for sparing your valuable time and reading this article. You can check out other articles as well:

 

Leave a Reply

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