0

I have this grid array which contains numbers from 0 to 7. A slot can be considered free on the grid only if it is a 0 and there's no different number before it:

[0, 0, 0, 0, 1, 0, 0, 0]           # every 0 before the 1 is a free slot

I want to make it so that the program can find the first slot that contains a number from 1 to 7, so that it knows that all the previous slots are free. I can make it work using a loop, like:

array = [0, 0, 0, 0, 1, 0, 0, 0]
freeslot = len(array)-1               # initializing in case it does not find a match
for n in range(1, 8):
   if (n in array) and (array.index(n)-1 < freeslot):
         freeslot = array.index(n)-1

The thing is, whenever I'm running this to check the grid, I check for 15 different arrays, so I feel that a loop makes it too slow. Is there a way to make it not using loops, or at least make it more efficient?

Jason Aller
  • 3,541
  • 28
  • 38
  • 38
Robson Luan
  • 51
  • 5
  • 1
    The whole body of the loop is extremely inefficient. `n in array` will potentially iterate the entire list, then `index` may as well, and then you're calling `index` a second time if the condition was true. If you need to know the index, call `index` once. If it doesn't throw, you know `n` is in the list so you don't need to do a `in` check. Then once you have that index, you don't need to call `index` a second time. I'd fix that then re-evaluate if performance is still an issue. – Carcigenicate Nov 02 '21 at 00:24
  • Not possible with arrays, but if you represent your array using bits, then log base 2 of the value will give you a number representing the index. Example, `00101000` (which is `40` in base 10). Taking the `log2(40)` gives 5 which corresponds to the index of the first `1`, so now you know that indices `6` and `7` are free – smac89 Nov 02 '21 at 00:25

2 Answers2

1

A possible solution is to use a numpy array and have a look at this solution: Numpy first occurrence of value greater than existing value

Tarik
  • 10,810
  • 2
  • 26
  • 40
1

This should work. freeslot = list(map(lambda x: True if 7 >= x > 0 else False, array)).index(True). Basically what it does is replace everything in a array list copy that is less than 7 but over 1 and replaces it with True. Then it indexes the first case of True in the new copy.

random
  • 62
  • 1
  • 7