How to implement a way to remove pairs in array

user_12472062 0
Viewed 266

I'm working on a problem that requires me to remove "pairs" (north-south and east-west pairs) in an array of strings. I'm unsure of a way to approach this problem on Python.

Here's the problem:

Write a function dirReduc which will take an array of strings and returns an array of strings with the needless directions removed (W<->E or S<->N side by side). (link to problem: https://www.codewars.com/kata/550f22f4d758534c1100025a)

Some test inputs and outputs:

Input  : ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
Output : ["WEST"]

Input  : ["NORTH", "WEST", "SOUTH", "EAST"]
Output : ["NORTH", "WEST", "SOUTH", "EAST"]

The 2nd set of inputs and outputs don't make much sense in regards to the task. My initial thought was to use a stack, but now I'm unsure of how to do it.

list arrays algorithm python
1 Answers

A simple implementation could just use a dictionary to define the opposing directions. When processing the list, if the current direction opposes the last one, remove the last one from the output. Else, add the new direction to the list:

dirs = {'NORTH': 'SOUTH', 'SOUTH': 'NORTH', 'EAST': 'WEST', 'WEST': 'EAST'}

def dirReduc(input):
    output = []

    for dir in input:
        if output and output[-1] == dirs[dir]:
            output.pop()
        else:
            output.append(dir)

    return output

print(dirReduc(["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]))
print(dirReduc(["NORTH", "WEST", "SOUTH", "EAST"]))
user_35589600
Related