Algorithm for filling a matrix

Question

I need some help for solving this problem. I need to write a function that fills seats in a theater. For example we have this theater:

theater = [ [1, 1, 1, 0], # 1 row

            [1, 0, 1, 0], # 2 row

            [0, 0, 0, 0], # 3 row
          ]

We have to fill the seats from the beginning of the row.
First, we have to fill the row with least filled seats.
If we have 2 rows with equal number of filled seats we fill the one with lower row number (we have to fill row 2 if it has the same number of filled seats as row 3).
Finally, we have to fill till all the seats are filled. Empty seats are 0 and filled ones - 1. The result has to be list of tuples - first element will be row's number and the second one - column's number - (2,1) - row #2 and column #1 for example.

Example:

theater = [ [1, 1, 1],
           [1, 0, 0],
           [1, 0, 0],
           [1, 1, 0] ]

expected = [(4, 3), (2, 2), (2, 3), (3, 2), (3, 3)]

What have you done so far? Show your code here. Any particular issue you are facing in your code? — Shamas S, Apr 10 '15 at 13:37
I don't know where to start from? I'm learning Python for about a month and this problem is a bit difficult for me. Any ideas? — croorc, Apr 10 '15 at 14:42

score 0 · Answer 1 · edited May 23 '17 at 10:24

No one is going to tell you very preliminary things.

I can send you along the correct lines though. Look up how to define 2 dimensional arrays. Create 2 variables for rows and columns. Start rows and columns from 0,0. Keep increasing columns until it is equal to max seats in a row, set it to zero and increment row.

How to define two-dimensional array in pythonenter link description here

Sakib Ahammed · Answer 2 · 2015-04-11T06:42:23.237

The idea is :

firstly you identify empty seat in theater
then reverse empty list
then filtering empty list check upper row empty seat length are equal with
current row empty seat are same position with upper row empty seat position then add it in temporary list and repeat it for next upper row
then you get your final result

By this procedure this code:

theater = [ [1, 1, 1],
           [1, 0, 0],
           [1, 0, 0],
           [1, 1, 0] ]

empty = [[(i+1 ,j+1) for j in range(len(theater[i])) if theater[i][j] == 0]  for i in range(len(theater)) ]
empty = empty[::-1]
#print empty

final_result = []
for i in range(len(empty)):
    result = []
    if i != len(empty)-1 and empty[i] not in final_result:
        j = i+1
        while len(empty[i]) == len(empty[j]):
            flag = False
            for first, second in zip(empty[i], empty[j]):
                if first[1] != second[1]:
                    flag = True
                    break
            if flag:
                break
            else:
                result.insert(0, empty[j])
                j = j+1
                if j == len(empty):
                    break


        for rr in result:
            final_result.append(rr)
        final_result.append(empty[i])

    if empty[i] not in final_result:
        final_result.append(reversed(empty[i]))


expected = []
for i in final_result:
    expected.extend(i)

print expected

Output:

[(4, 3), (2, 2), (2, 3), (3, 2), (3, 3)]

Algorithm for filling a matrix

2 Answers2