Why is this python loop containing consecutive duplicate items breaking?

Question

I am attempting solve this problem. In the problem am required to iterate over a list of directions (NORTH, SOUTH, EAST, WEST) and discard any adjacent opposite directions (NORTH and SOUTH, EAST and WEST) to return a reduced array containing only non-redundant directions. When I iterate over a list that does not contain consecutive duplicates, such as ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"], my code works fine, but it breaks when I iterate over a list with consecutive duplicates, like ['EAST', 'EAST', 'WEST']. Why is my code doing this, and how can I fix it to handle consecutive duplicates?

def dirReduc(arr):
  for direction in arr[:-1]:
    try:
      gotdata = arr[arr.index(direction)+1] 
    except IndexError:
      gotdata = 'null'
    except ValueError:
      gotdata = 'null'
    if gotdata is 'null':
      if arr == dirReduc(arr):
        return arr
      else:
        return dirReduc(arr)
    elif cancel_pair(direction, arr[arr.index(direction)+1]):
      del arr[arr.index(direction):arr.index(direction)+2]
  return arr

def cancel_pair(dir1, dir2):
  if dir1 in ('NORTH') and dir2 in ('SOUTH') or dir1 in ('SOUTH') and dir2 in ('NORTH'):
    return True
  elif dir1 in ('WEST') and dir2 in ('EAST') or dir1 in ('EAST') and dir2 in ('WEST'):
    return True
  return False

Answer 1

A for loop is not a good match for this problem. If you delete a pair of items, you may need to backtrack to see if a new pair was created. A while loop is much more natural:

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

def dirReduc(arr):
    i = 0
    while i < len(arr) - 1:
        if arr[i] == opposite_directions[arr[i+1]]:
            del arr[i:i+2]
            if i > 0:
                i -= 1 # back up a step if we just deleted some moves from the middle
        else:
            i += 1
    return arr

I also replaced your cancel_pairs function with a simple dictionary lookup. Python's dictionaries are great, and they're often a better choice than a complicated if/else block.

Answer 2

EDIT

I'm leaving this here because I think the explanation and the recursive version are helpful, but @Blckknght's answer is superior in that it does less work (by backing up only one element rather than restarting with each iteration).

---

Here's some working code. I realize it's a bit of a departure from your code. (You can ignore the cancel_pair implementation; I wrote my own before I saw yours. Yours looks fine.)

def cancel_pair(dir1, dir2):
    return tuple(sorted((dir1, dir2))) in (("NORTH", "SOUTH"), ("EAST", "WEST"))

def dirReduc(directions):
    did_something = True
    while did_something:
        did_something = False
        for i in range(len(directions) - 1):
            if cancel_pair(directions[i], directions[i + 1]):
                did_something = True
                directions = directions[:i] + directions[i + 2:]
                break
    return directions

I think there are a couple issues with your code:

1. You're modifying the list of directions while you're iterating over it. This is generally a bad idea, and specifically here, I think it may cause you to skip over elements (because the length of the list is changing).
2. You're only taking one pass through the array. In the problem you linked to on Codewars, you need to repeat the process after removing a canceling pair.
3. You're using index to figure out the current index, but it will always tell you the index of the first occurrence of the value you're passing in. You need to instead keep track of the index yourself. I chose to just iterate over the indices, since I need to use the index + 1 anyway.

UPDATE

A recursive approach might be easier to understand, depending on your programming background:

def dirReduc(directions):
    for i in range(len(directions) - 1):
        if cancel_pair(directions[i], directions[i + 1]):
            return dirReduc(directions[:i] + directions[i + 2:])
    return directions

Answer 3

opp = {}
opp['NORTH'] = 'SOUTH'
opp['EAST'] = 'WEST'
opp['SOUTH'] = 'NORTH'
opp['WEST'] = 'EAST'

def red(lst):
  i = 0
  j = 1
  while j< len(lst):
    if(opp[lst[i]] == lst[j]):
      lst[i] = 0
      lst[j] = 0
      lst = [x for x in lst if x != 0] 
      i =0
      j =1
    else:
      i+=1 
      j+=1

  print(i,j)

this is a cleaner way to do it, I store the opposite directions and then iterate over the list making a new copy every time i 'pop' opposite elements.

keep in mind that the input list will be modified by this code so you might want to pass a copy of the input list if needed.

Answer 4

There are a lot of mistakes in this function. The most important two local mistakes are:

• arr.index(direction) will always find the first instance of direction in arr, even after you've gone on to the next one

• you have del arr[x:y] in the middle of a loop over arr, which will have unpredictable results.¹

But also, I don't think your algorithm does what it's supposed to do. I would write this like this:

import re
_rcd_removals = re.compile(
    r"\b(?:SOUTH NORTH|NORTH SOUTH|WEST EAST|EAST WEST)\b")

def remove_cancelling_directions(dirs):
    """DIRS is a list of uppercase cardinal directions as strings
       (NORTH, SOUTH, EAST, WEST).  Remove pairs of elements that
       cancel each others' motion, e.g. NORTH immediately followed
       by SOUTH.  Modifies DIRS in place and returns nothing."""

    dirs[:] = _rcd_removals.sub("", " ".join(dirs)).split()

Regexes are great at sliding-window edits to sequences of words. Working on this as an array is going to be a lot finickier.

If you need to collapse pairs that are only visible after other pairs have been collapsed (e.g. WEST SOUTH NORTH EAST should become the empty list), then you should iterate to a fixed point:

import re
_rcd_removals = re.compile(
    r"\b(?:SOUTH NORTH|NORTH SOUTH|WEST EAST|EAST WEST)\b")
_rcd_fixwhite = re.compile(" {2,}")

def remove_cancelling_directions_repeatedly(dirs):
    ds = " ".join(dirs)
    prev_ds = None
    while prev_ds != ds:
        prev_ds = ds
        ds = _rcd_removals.sub("", ds)
        ds = _rcd_fixwhite.sub(" ", ds)
   dirs[:] = ds.split()

---

¹ Can anyone point me at official Python documentation stating that the effect of mutating a list while iterating over it is unpredictable? I know that it is, but I can't find an official rule. (The spec for list goes out of its way to point out that mutating a list while sorting it has undefined behavior.)