CODEWITHSUNDEEP
pythonpython-3.x
user2100672
user2100672

Reputation:

Array item numbers for consecutive items

I'm trying to create a seat booking system which links to a CSV file and checks whether seating is available based on user input (seats together required and row number).

The row specified by the user is then retrieved as line. B would return:

['0', '0', '0', '0', '0', '0', '0', '0', '1', '0', 'B']

Where 0 is a free seat and 1 is a taken seat. The letter identifies the row.

I'm using the below line to retrieve the largest amount of consecutive zeroes in the array giving the largest block of seats.

LargeBlock = max(sum(1 for _ in g) for k, g in groupby(line) if k == '0')

I'd also like to return seat numbers. So using the above example, if a user requested three seats on row B, it would output B1-B3 being available. Any ideas on how to retrieve the numbers of the items in the list based on both the user input and the LargeBlock variable?

Upvotes: 0

Views: 199

Answers (2)

Javier
Javier

Reputation: 742

Dynamic programming is your friend!

You can define a utility function that gives you a new row with each seat listing how many free sits are there to the left of the given sit:

def free_seats(row):
    seats = []
    seats.append(1 if row[0] == '0' else 0)
    for k in range(1, len(row)):
        seats.append(0 if row[k] == '1' else 1 + seats[k-1])
    return seats

Then you use the number of free sits to find the first possible placement with the row code:

def find_n_seats(n, line):
    row_code = line[-1]
    available_seats = free_seats(line[:-1]) # Remove the line code
    try:
        last_seat = available_seat.index(n)
        return [row_code + str(i+1) for i in range(last_seat + 1 - n, last_seat)]
    except ValueError:
        print('Not possible to find {0} seats in row {1}'.format(n, row_code))
        return None

The above function should be applied to each line until you find a match.

Upvotes: 0

poke
poke

Reputation: 387687

Usually, finding the largest free group of seats is not really that useful. For example, a two people could fit into a gap of two seats, and they might prefer those over having a spot in that other group of six consecutive seats. And as you want to get the machine full, you probably want to prefer filling those hard-to-fill slots early too before you start getting spots from those larger free group areas.

So instead of getting you the biggest group, my solution just gives you every combination of seats you can take in a row.

def getPossibleSeats (line, row, num):
    if row != line[-1]:
        raise ValueError('Invalid row')

    for k, g in groupby(enumerate(line[:-1], 1), lambda x: x[1]):
        g = list(g)
        if k != '0' or len(g) < num:
            continue

        for i in range(len(g) - num + 1):
            yield ['{}{}'.format(row, s) for s, _ in g[i:i+num]]

For your example line, it looks like this:

>>> line = ['0', '0', '0', '0', '0', '0', '0', '0', '1', '0', 'B']
>>> for seats in getPossibleSeats(line, 'B', 4):
        print(seats)

['B1', 'B2', 'B3', 'B4']
['B2', 'B3', 'B4', 'B5']
['B3', 'B4', 'B5', 'B6']
['B4', 'B5', 'B6', 'B7']

For another example, it may look like this:

>>> line = list('11000110000001C')
>>> for seats in getPossibleSeats(line, 'C', 2):
        print(seats)

['C3', 'C4']
['C4', 'C5']
['C8', 'C9']
['C9', 'C10']
['C10', 'C11']
['C11', 'C12']
['C12', 'C13']

Upvotes: 1

Related Questions