Number Filtration Algorithm bug

36 views Asked by At

So I wrote this algorithm where given a set of integers it will remove all integers except 0 and 7 and then it will check if the remaining integers are in a certain order and then will return a boolean. Code below:

def spy_game(nums):
  for i in nums:
    if i != 0:
      if i == 7:
        continue
      else:
        nums.remove(i)
    else:
      continue
  stringlist = [str(o) for o in nums]
  mystring = ''.join(stringlist)
  return '007' in mystring

spy_game([1,0,2,4,0,7,5])

Now the problem is that if I run (for example) spy_game([1,0,2,4,0,7,5]) it will not return True regardless of the fact that the sequence of interest is present. After I decided to return the list per se after the filtration process, I found that all numbers except the ones in the middle got filtered out. So in this example, if I return nums it will return [0, 4, 0, 7] although the 4 should've been removed. I am aware that there are more optimal alternatives to this algorithm but I just want to understand why it doesn't work. Thank you.

2

There are 2 answers

0
Jimmar On BEST ANSWER

Instead of modifying the list, use another list to keep track of the wanted numbers.

You should not modify the list while iterating on it.

Here's a cleaned up version

def spy_game(nums):
    ans = []
    for i in nums:
        if i == 0 or i == 7:
            ans.append(i)

    stringlist = [str(o) for o in ans]
    mystring = ''.join(stringlist)
    return '007' in mystring
0
jirassimok On

zenwraight's comment says what the problem is: in Python, you can't modify a list while iterating over it.

As for why, the Python documentation discusses this in a note on the for statement's section:

An internal counter is used to keep track of which item is used next, and this is incremented on each iteration. … This means that if the [loop body] deletes the current … item from the sequence, the next item will be skipped (since it gets the index of the current item which has already been treated).

The documentation also describes what happens when you insert an element during a loop, and suggests one possible solution (using a slice to copy the list: for i in nums[:]: ...). In your use case, that solution is likely to work fine, but it is considerably less efficient than options that don't copy the entire list.

A better solution might be to use another list comprehension:

nums = [i for i in nums if i == 0 or i == 7]