Finding consecutive values in a multidimensional array - python

Question

I'm completely new to python really. I need some help with multidimensional arrays. I am making a seat booking system for a theatre. (just practice). I have set up a 5 row by 10 seat matrix. And all I really need to be able to do is assign 'available' or 'unavailable' to each seat. I can do this obviously, but what I have no idea how to do is be able to search or loop through a row to see if there are 6 seats available next to each other. Any help would be great. Bear in mind I am completely new to python.

In Python a multidimensional array is just a sequence of sequences, for example a `list` of `list`s. To access individual elements of one just use two indices. For example `seating[row_num][seat_num] = 'available'`. — martineau, Mar 26 '13 at 18:07
Thanks. That's pretty much what I had in mind. The one bit I can't syntactly write, is how to define the row_num and seat_num for each item in the lists. — user2212774, Mar 26 '13 at 19:12

Adam · Accepted Answer · 2013-03-27T10:55:35.817

3

The simplest way I can think of is to iterate over the rows, keeping track of the row number as index.

Then, we count available seats until we find six in a row or until we encounter an unavailable seat (we reset the count if this happens).

seats = [[True, True, True, False, True, True, True, False, False, True],
         [True, True, True, True, True, True, True, False, False, True],
         [True, True, True, False, True, True, True, False, False, True],
         [True, True, True, False, True, True, True, False, False, True],
         [True, True, True, True, True, True, True, False, False, True]]

for index, row in enumerate(seats):
    consecutive_seats = 0
    for seat in row:
        if seat:
            consecutive_seats += 1
            if consecutive_seats >= 6:
                print('There are at least six seats available on row', index)
                break
        else:
            consecutive_seats = 0

Further explanation

The python enumerate function allows you to iterate over the sequence of seats, giving you back an index and the current item at that index. Optionally, you can pass it a parameter to set the starting index (so if you want your seat rows to start from one, you could use the following instead:
```
for index, row in enumerate(seats, start=1): ...
```
In fact, the details of what's happening here are interesting: enumerate returns a two-item Tuple (think of it as an immutable – unchangeable – list) which you are unpacking to index and row. You can then use these two variables just like any others.
For each pair of index and row, you iterate over the row and check if seat is True (you can, but shouldn't, write seat == True – it's redundant information). If it is True, you consider it available and increase the counter for available consecutive seats by one.
Immediately thereafter, you need to check if you've found enough free seats, in which case you can break out of the loop, in other words, you're skipping the rest of the seats in the row because you already know enough of them are free, and continuing with the next iteration of the outer loop, which will yield the next row index and row.
If, on the other hand, the seat is False (unavailable), you reset the count of consecutive available seats to zero but you continue checking the rest of the row.

Suggested improvements

Make a class Seat and give it an attribute is_available
Introduce constants to get rid of magic numbers

edited Mar 27 '13 at 10:55

answered Mar 26 '13 at 18:23

Adam

15,537
2
42
63

That's exactly whe I was going with my own example. I set up 'seats' just like that. Does for index, row in enumerate(seats) attach an index to each of the rows/nested list? Is it possible you could comment your code so I can understand the process? I want to know the method rather than just know how to replicate it. Thanks. I really do appreciate your help. – user2212774 Mar 26 '13 at 19:16
@user2212774 that's an excellent attitude. I've tried to explain as well as I could, and hope to have shown a bit of what is going on in the background. – Adam Mar 26 '13 at 21:22
Thank you very much. Really useful explanations. It was very nice of your to have taken your time to help me. – user2212774 Mar 26 '13 at 22:37
@user2212774 No worries. I see you've discovered how to upvote; additionally, it makes sense to mark the most helpful answer (in your own opinion) with the tick mark. Of course, you can reserve your judgment until more answers come in or change it any time. – Adam Mar 26 '13 at 22:41
what does the following do: **for seat in row: if seat:** where is the defination for seat coming from? how does python know what 'seat' is? also, I assume that 'row' refers to each nested list? does python just handle each new nested list as a new row, and thats why you can use 'row' to refer to each list? sorry i am a pain, i just want to understand everything about this method so i can use for other scenarios, rather than just replicate it for just this one example. If this is a hassle, please dont spend time on it. You have already been tremendous help. Thanks – user2212774 Mar 27 '13 at 13:04
The definition of `row` is `for index, row in enumerate(seats):`, in other words, *iterate over `seats`, giving each item the name `row`*. The type of `row` is `list`, so you can iterate over every one of those lists called `row`, again assigning each item a name, but this time calling it `seat`. `seat` is of type `bool`, so it can be either `True` or `False`. `if seat:` checks if seat evaluates to `True`. Note that `seat` and `row` are just names that you can change. Try changing these names to understand it better. – Adam Mar 27 '13 at 13:55
so where it is saying **for seat in row**, because python is expecting an index ref to follow the **'for'**, it will take the name of that index as whatever is written there? and **'if seat:...'** is simply saying: if the index 'seat' is **true**. I asumed i would have to actually write **if seat = true**. I noiced you used the += operator. Is that because you are adding the sum of all true seats? why wouldnt it simply be **consecutive_seats + 1** I think have have run out of annoying questions now. You are very patient. I cant tell you how much i appreciae your help!!!! – user2212774 Mar 27 '13 at 14:35
i did just think of something else, just to clarify, does index refer to each nested list, or each item (true/false) contained in that list? i think row refers to the individual nested list, and index refers to each item in that list?? – user2212774 Mar 27 '13 at 14:55

Abhijit · Answer 2 · 2013-03-26T19:18:15.523

Assuming you have a seat arrangement similar to below

seats=[   [1, 0, 0, 0, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 1, 1, 0, 1, 1, 1, 0],
    [0, 0, 1, 1, 1, 0, 1, 0, 0, 1],
    [0, 0, 1, 0, 0, 0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]]

Instead of maintaining as a nested list, my suggestion is to maintain a list of strings. Searching a pattern (here sequence of '0's or '1's or even something complex like middle seat or end seat) is faster and easier through string search. Even for complex searches you can employ regex

Suggested Data Structure

seats=[   '1000111010',
    '0001101110',
    '0011101001',
    '0010000011',
    '0000000100']

Now to search for consecutive 6 empty seats , you have to search '0'*6 something like

>>> any('0'*6 in row for row in seats)
True
>>> next((i,row.index('0'*6)) for i,row in enumerate(seats) if '0'*6 in row )
(4, 0)

Explanation

next((i,row.index('0'*6)) for i,row in enumerate(seats) if '0'*6 in row ) returns the first item from the generator expression. Assuming you know about the built-in

enumerate: Returns a list of tuples of (index , element)

The expression can be equivalently written as

for i,row in enumerate(seats):
    if '0'*6 in row
       print (i,row.index('0'*6)
       break

any('0'*6 in row for row in seats) can be equivalently written as

def search(seats):
    for row in seats:
        if '0'*6 in row:
            return True
    return False

This seems like a great idea. As I said, I am annoyingly new to this. So I'm not sure I fully understand the whole of the line that starts next. Hw exactly is it working? Thanks for your reply. I appreciate this help so much. — user2212774, Mar 26 '13 at 19:09
That's a really nice solution. Can you explain how 'any' at that start works? And if I a, honest, I'm not sure how next and onwards is working. Sorry, I did say I am very new. — user2212774, Mar 26 '13 at 19:18
@user2212774: I have added an explanation of how the generator expression and the any buitlt-in is working — Abhijit, Mar 26 '13 at 19:23

score 0 · Answer 3 · edited May 23 '17 at 12:13

0

you may consider to use sparse matrix.

and Iterate it like that: https://stackoverflow.com/a/4319159/1031417

edited May 23 '17 at 12:13

Community

1
1

answered Mar 26 '13 at 18:28

0x90

39,472
36
165
245

Finding consecutive values in a multidimensional array - python

3 Answers3

Further explanation

Suggested improvements