Solve Desert Crossing Problem using Stack in Python
The following is a step-by-step procedure for solving Desert Crossing Problem in Python:
- Create a list of directions: First of all, define a Python list of directions that we will take as input to solve the problem statement.
- Create an empty list: Next, create an empty Python list to hold the shortened instructions. This list will work as the Stack.
- Iterate through the list of directions: Then, use a Python for loop to iterate the list of directions of the ‘directions’ input list.
- Compare the two consecutive directions: Then use Python if statement to compare the current direction to the previous direction. Append the current direction to the simplified directions list i.e., the stack list if the two directions are not opposite each other. If the two directions are diametrically opposed, remove the prior direction (if it exists) from the stack.
- Return the Stack: Return the stack after iterating through all directions.
Code Implementation
Python3
directions = ["NORTH", "SOUTH", "EAST", "WEST", "NORTH"] stack = [] for direction in directions: if stack and ((direction == "NORTH" and stack[-1] == "SOUTH") or (direction == "SOUTH" and stack[-1] == "NORTH") or (direction == "EAST" and stack[-1] == "WEST") or (direction == "WEST" and stack[-1] == "EAST")): stack.pop() else: stack.append(direction) if not stack: print("[]") else: print("[" + ", ".join(stack) + "]") |
Output:
[NORTH]
Time complexity: O(n), as we have to transverse in the list which has size n.
Space Complexity: O(n), as we use extra space as a stack, which in the worst case may have n size.
Code Explanation:
Input list: [“NORTH”, “SOUTH”, “EAST”, “WEST”, “NORTH”].
We can process the directions as follows:
- Initialize an empty stack.
- Process each direction in the list:
- Process direction “NORTH”:
- Stack is empty, so push “NORTH” into the stack. Stack is now [“NORTH”].
- Process direction “SOUTH”:
- Top of stack is “NORTH”, which is opposite to “SOUTH”, so pop “NORTH” from the stack. Stack is now empty.
- Process direction “EAST”:
- Stack is empty, so push “EAST” into the stack. Stack is now [“EAST”].
- Process direction “WEST”:
- Top of stack is “EAST”, which is opposite to “WEST”, so pop “EAST” from the stack. Stack is now empty.
- Process direction “NORTH”:
- Stack is empty, so push “NORTH” into the stack. Stack is now [“NORTH”].
- All directions have been processed, so the simplified directions are the directions left in the stack, which is [“NORTH”].
Using Stacks to solve Desert Crossing Problem in Python
A man is using a compass to cross a desert, and he has been given specific directions for his task. Following directions is only permitted: “NORTH”, “EAST”, “WEST”, and “SOUTH”. However, the desert has very hot weather, and it would be advantageous if man could save energy. Thus, your task is to simplify the directions and eliminate those that cancel each other out, i.e., eliminate those consecutive directions that are opposite to each other end.
Direction Map
Note: We can only eliminate the directions which are opposite to each other. For example, if the west is our first direction then the second direction must be east then only we can eliminate both directions otherwise we will not be able to eliminate it. Let us see how we can solve this problem in Python.