Question:
The question asks you to find the most effective way to accommodate family members in an aircraft such that no one sits alone i.e. at least 2 members sit together.
In computational terms:
Your input consists of the number of rows in an aircraft, number of seats per row in the aircraft, the list of seats that have been occupied prior to booking the seats for the family members and the number of family members you need to accommodate.
Let each row be numbered from 1 to num_of_rows and each seat from left to right be labelled as A, B, C……
We need to find the seats allocated to the family members such that, at least 2 of them sit alone, all of them sit as close as possible and if the number of seats available is less than the number of family members then try to accommodate the maximum number of members if not all.
Input:
rows = 3
seats_per_row = 6
num_passengers = 7 # Number of passengers in the family
pre_booked_seats = [(1, 'B'), (1, 'C'), (2, 'B'), (2, 'D'), (3, 'A'), (3, 'C'), (3, 'F')]
Approach:
As we can clearly see, there is a lot of information provided to us about the airplane, hence it would be wise to create an Airplane class that helps us manage and access this information easily.
class Airplane:
def __init__(self, rows, seats_per_row):
self.rows = rows
self.seats_per_row = seats_per_row
self.seat_map = self._generate_seat_map()
In order to make it easier to visualise the seats, we can define the airplane as a 2-D array.
Row 1 : O B B X X X
Row 2 : O B O B X X
Row 3 : B O B X X B
In this representation, let
0 -> available
B -> occupied
X -> Seats allocated to family members.
This approach allows us to easily check a seats availability by indexing in the 2-D array instead of iterating each time and finding the seat.This 2-D array generation is done by the generate_seat_map() method in the airplane class:
def _generate_seat_map(self):
return [['O'] * self.seats_per_row for _ in range(self.rows)]Lets now define the methods to mark the seats accordingly and also define a method to check the seats status:
def _check_available(self, row, seat): #checks if seat is available
return self.seat_map[row][seat] == 'O'
def book_seats(self, seats): #books seats for family
for seat in seats:
row, seat_char = seat
self.seat_map[row - 1][ord(seat_char) - 65] = 'X'
def pre_book_seats(self, seats): #blocks the seats in the list of occupied seats
for seat in seats:
row, seat_char = seat
self.seat_map[row - 1][ord(seat_char) - 65] = 'B'
def print_seat_map(self):
print(' ', end = '')
for i in range(self.seats_per_row):
print(chr(65 + i), end = ' ')
print('\n', '----------------------------')
for row_num, row in enumerate(self.seat_map, start=1):
print("Row", row_num, ": ", " ".join(row))
Now of course, lets come to how to find the seats.Our best case scenario is that we find seats for all members together (either in the same row or in the next consecuitive seat fot eh next row). So lets define that function:
def allocate_seats(self, num_passengers):
allocated_seats = []
# Try to allocate seats together for the whole family
for row in range(self.rows):
for seat in range(self.seats_per_row - num_passengers + 1):
if all(self._check_available(row, seat + i) for i inrange(num_passengers)):
for i in range(num_passengers):
allocated_seats.append((row + 1, chr(65 + seat + i)))
return allocated_seats
This function takes in the number of passengers to be seated together, and find that many consexutive seats.
Of course not alwasy will we find cosecutive seats. So your logic to implement the function could be
if there are k family members. Try to seat k family members together.
If cannot, we know that at least two must sit togther, so try to accomodate (k-2) members in consecutive seats and the other 2 sit together elsewhere.
If you cannot accomodate (k-2) either, then try (k-4) and try to accomoadate the second detached pair else where.
With this method, there will be cases where lets say you have 3 seats consecutively available somewhere. While trying to accomodate the 2 people (the ones seperated from the k), you make them sit on 2 of the 3 seats. However, you may have people left with no seat at the end of the algorithm. In this case, you search the plane again to find another family member and make them sit with them.
def main():
airplane = Airplane(rows=3, seats_per_row=6) # Example airplane configuration
rows, col = airplane.rows, airplane.seats_per_row
num_passengers = 7# Number of passengers in the family
pre_booked_seats = [(1, 'B'), (1, 'C'), (2, 'B'), (2, 'D'), (3, 'A'), (3, 'C'), (3, 'F')]
airplane.pre_book_seats(pre_booked_seats)
# Allocate seats for the family
a = num_passengers
k = 0
count = 0
seated = 0
seat_array = []
while a > 2:
a = num_passengers - (2*k)
#print(a, k , seated)
seats = airplane.allocate_seats(a)
if seats and a >= 2: #give consecutive seats to max people possible
for allocated_seat in seats:
seat_array.append(allocated_seat)
count +=1
airplane.book_seats(seats)
rem_seats = airplane.allocate_seats(2*k - seated)
if rem_seats: #allocate seats to the detached pair
for allocated_seat in rem_seats:
seat_array.append(allocated_seat)
count +=1
airplane.book_seats((rem_seats))
k+=1
seated = count
if count == num_passengers:
break
#find seats next to their family members for the people left out in the end
def find_seats(rows, cols, blocked_seats, booked_seats, k):
available_seats = []
for row_num in range(1, rows + 1):
for col_label in range(ord('A'), ord('A') + cols):
seat = (row_num, chr(col_label))
if seat not in blocked_seats and seat not in booked_seats:
col_idx = col_label - ord('A')
if (col_idx > 0 and (row_num, chr(col_label - 1)) in booked_seats) or \
(col_idx < cols - 1 and (row_num, chr(col_label + 1)) in booked_seats):
available_seats.append(seat)
k -= 1
if k == 0:
return available_seats
return available_seats
if seated < num_passengers:
left_seats = find_seats(rows, col, pre_booked_seats, seat_array, num_passengers - seated)
for i in left_seats:
seat_array.append(i)
airplane.book_seats(left_seats)
seated += len(left_seats)
if seated != num_passengers:
print('could only accmomodate', seated, 'people')
print('List of seats:' , seat_array, '\n')
airplane.print_seat_map()
Output:
List of seats: [(1, 'D'), (1, 'E'), (2, 'E'), (2, 'F'), (3, 'D'), (3, 'E'), (1, 'F')]
A B C D E F
----------------------------
Row 1 : O B B X X X
Row 2 : O B O B X X
Row 3 : B O B X X B