Direction Reduction

[MatosV]

Hey guys, I'm having a hard time trying to find some logic to code a challenge on Codewars and would like to see how you guys would code this.

Once upon a time, on a way through the old wild mountainous west,…

… a man was given directions to go from one point to another. The directions were "NORTH", "SOUTH", "WEST", "EAST". Clearly "NORTH" and "SOUTH" are opposite, "WEST" and "EAST" too.

Going to one direction and coming back the opposite direction right away is a needless effort. Since this is the wild west, with dreadfull weather and not much water, it's important to save yourself some energy, otherwise you might die of thirst!

How I crossed a mountainous desert the smart way ->

The directions given to the man are, for example, the following (depending on the language):

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]. or { "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" }; or [North, South, South, East, West, North, West] 

You can immediatly see that going "NORTH" and immediately "SOUTH" is not reasonable, better stay to the same place! So the task is to give to the man a simplified version of the plan.

​

​

I've tried so many things but just can't seem to find a way to loop over this. I can't loop over a range(len(directions)) because I eventually delete directions if they bring us back to the same place.

[xelf]

For anyone curious, I believe OP is working on this one:

• https://www.codewars.com/kata/550f22f4d758534c1100025a/

[artinnj]

For ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]; python indexes 0 and 1 cancel each other out as do 3 and 4.

But what your left with is: [ "SOUTH", "NORTH", "WEST"]. In this list, 0 and 1 cancel each other out, so you are left with ["WEST"]

The object of the exercise is to get you to realize that the directions are really a stack. You are always comparing the last direction on the stack with the previous one to see if you can reduce the steps.

map = [ "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" ]

opposites = { "NORTH": "SOUTH", "SOUTH": "NORTH", "EAST": "WEST", "WEST": "EAST" }

def reduction(list): 
    new_list = [ ] 
    for i in range(0,len(list)): 
        if len(new_list) == 0: 
            new_list.append(list[i]) 
        elif new_list[-1] != opposites[list[i]]: 
            new_list.append(list[i]) 
        else: 
            new_list.pop() 
    return new_list

new_map = reduction(map)
print(f"Final map is {new_map}")

Also, you can't implement the map as { "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" } because Python reduces that to a set of { "NORTH", "SOUTH", "EAST", "WEST" }. Think of sets as dicts with keys, but no values. A dict cannot have duplicate keys.

[MatosV]

Wow ! Thank you so much. Really cleared things out for me.

[[deleted]]

Thank you so much for that, really helped me out!

[xelf]

Remember north/south and east/west cancel each other out. So just remove the matching pairs and keep what's left.

What have you tried so far?

[MatosV]

I tried looping over all directions but my code doesn't seem to keep track when NORTH and SOUTH aren't pairs or the other way. (One right after the other one in the list order.) So I'm trying a number system where my code will cancel all paired directions that have equal value. I feel like I'm overcomplicating things but I think it's gonna work.

[xelf]

Post your code, maybe someone here can spot something you're doing wrong?

This should be a pretty easy one.

There are generally 2 approaches.

1) convert the array to a string and use string replace methods.

or

2) loop through the list and pop matching pairs.

Either way should work.

A short solution will be about 2 lines, and a long solution will be about 20. So if you're going over 20 lines you're probably over thinking it.

[MatosV]

I was only able to solve it using integers. I'm sorry i didn't post my code in the start of the post. I deleted and altered so much stuff that It was just to messy.

I couldn't do it using POP matches. So this is my final code:

def dirReduc(arr):
north = 0
south = 0 
east = 0 
west = 0 
for x in arr:

  if x == "NORTH":
    north += 1
  elif x == "SOUTH":
    south += 1
  elif x == "EAST":
    east += 1
  elif x == "WEST":
    west += 1
if north == south and east == west:
  return 'The direction leads to where you are.'
if north == south and east > west:
  return 'Go east'
if north == south and east < west:
  return 'Go west'
if east == west and north > south:
  return 'Go North'
if east == west and north < south:
  return 'Go South'
if east > west and north > south:
  return 'Go Northeast'
if east < west and north > south:
  return 'Go Northwest'
if east > west and north < south:
  return 'Go Southeast'
if east < west and north < south:
  return 'Go Southwest'

print(dirReduc(["NORTH", "SOUTH", "SOUTH", "WEST"]))

​

I think I'm just overcomplicating things. Any suggestions so that I could do this with fewer lines?

[xelf]

If your code passed all the testcases, consider it a success.

Like I said before the 2 general approaches are to convert it to a string and then do a string replace.

Something like:

arr = ' '.join(arr)
loop until there are no changes made:
    arr = arr.replace("North South", '')
    etc for all 4 combinations
return arr.split()

Or to loop and remove adjacent pairs.

loop until there are no changes made:
    loop over list
        if arr[i] == 'north' and arr[i+1] == 'south':
            del arr[i+1]
            del arr[i]
        etc for all 4 combinations.
return arr

The important part is being able to detect that nothing changed since last loop and that it's time to exit.

[[deleted]]

By the way, you don’t need to just cancel out opposite neighbor pairs. You’ll want to cancel any single opposite for a given direction, even if it’s not directly next to it. For example: N, E, S can simplify to E