# Find the maximum number of 4-passengers contiguous clusters

Problem Statement

1. An airline wants to allocate seats in their aircrafts such that each group of four passengers travelling together are to be seated next to each other in clusters of 4. A contiguous cluster can have an isle running through it - for example, you can sit one passenger on one side of the isle, and three on the other side, as long as there are no passengers from other parties in that cluster. Clusters must be on the same row.
2. There are 10 seats in each row, arranged in a 2 - 6 - 2 pattern (i.e. 2 seats, then an isle, then 6 seats, then an isle, then two seats). Rows range from 1 .. 40 and seats from A - K, skipping I
3. You are given an integer number of rows (N) and a space-delimited string (S) representing occupied seats. For example, "1A 2A 3B 5C 40F" would indicate occupied seats in rows 1 - 40. Similarly, "1A 2A 3B 5C" would indicated occupied seats in rows 1 - 5.
4. You are required to write a function seat(N,S), representing the number of rows and occupied seats respectively, and have to return the maximum number of 4-passenger contiguous clusters.

Solution Approach

1. Check for the trivial case of S = '' and N = 1 and return 2
2. Parse the occupied seats string into a list of strings using S.split(' ') to get individual seat allocation
3. Map the letters A - K into numbers 0 - 9
4. Create a 2D matrix map of seats
5. Parse the matrix row by row, looking for a patterns of 4 seats and return their count

Code

Fully documented code as follows:

import re

def printMatrix (M):

print('\n'.join([''.join(['{:4}'.format(item) for item in row])
for row in M]))

def sliceMatrix (M, C):
counter = 0;
clusters = 0;

# the approach here is to keep a count of where we checked last in the variable counter
# if we fail, we increment the counter by 1 and slice the next cluster of 4
# if we succeed in finding a cluster of 4 available seats, then we increment the number of
# clusters by 1 and the counter by 4.
# we then return the total number of clusters found in a row

for i in range (counter, len(M)):
# loop over array taking a slice of 4 spaces from where the current counter is
fourSlice = M[counter:counter+4];
print(fourSlice)
# check for the number of 0s in that slice
numZeros = fourSlice.count(0);
print("numZeros: ", numZeros);
# success: there are 4 zeros, then this is a cluster
if (numZeros == 4):
print("Found cluster. Clusters now: ", clusters + 1)
# increment the number of clusters found by 1
clusters += 1;
# move the counter 4 spaces
counter += 4;
# skip the rest of the loop iteration
continue;
# failure: increment the counter by 1 and loop
else:
counter += 1;
print ("i: ", i, " counter: ", counter)
print("total clusters found in this row: ", clusters)
# return the total number of clusters found in this row
return (clusters);

def solution(N, S):

# a dictionary to map column labels to numbers.
# this is necessary to obtain numerical values for the 2D matrix seat map.  Is there a better way?
columnDict  = {'A' : 0, 'B' : 1, 'C' : 2, 'D' : 3, 'E' : 4, 'F' : 5, 'G' : 6, 'H' : 7, 'J' : 8, 'K' : 9}

# check the trivial case whereby only one empty row exists and return 2
if (N == 1 and S==''):
return 2;

# construct an empty 2D matrix map of the aircraft seating of the format N x 10
seatMap = [[0 for n in range(10)] for y in range(N)];

# convert the occupied string list into a list of individual seat strings
S = S.split(' ');

# iterate over the array, and populate 2D map

for seat in S:
# search for one or more digits, followed by a single letter, placing each in a group
# digits are row numbers, letters are seat labels
m = re.search ("(\s*[\d]+)([abcdefghjkABCDEFGHJK]\s*)", seat)
if m:
# grab the first group from the match object, representing row number
occupiedRow = m.group(1);

# grab the second group from the match object, representing column label
occupiedColumn = m.group(2);
# convert the row number into a matrix index by decrementing it by 1. this is to account for
# machine representation of indexes, which start at 0
MR = int(occupiedRow) - 1;
# map the seat label to a number so that it can also be used as a matrix index.
# this is done as a dictionary lookup from the columnDict hash defined earlier
MC = columnDict[occupiedColumn];
# now we have a [row][column] matrix number, populate that entry as occupied
seatMap[MR][MC] = seat;
# just be helpful, and print the seat map
printMatrix(seatMap);

# next, iterate over seat map row by row, and extract each row to a 1d array
# but first, we initialise a total cluster counter, to keep cumulative track
# of how many clusters we get from the seat map matrix
totalClusters = 0;

for i in range(N):
# slice a row from the seat map into a 1d array
rowSlice = seatMap[i][0:9]

# pass that slice to the sliceMatrix function to get the number of clusters in that row
numClusters = sliceMatrix(rowSlice, 4)

# keep cumulative track of clusters we get
totalClusters += numClusters;

# return the total number of clusters found
return (totalClusters)

# this is a sample occupancy string of an aircraft with 7 rows (N = 7)
S = "1A 1B 1F 2A 2B 2C 2D 3A 3C 3D 4A 4B 4E 5A";
N = 7;

Clusters = solution(N, S);

print ("Total Clusters: ", Clusters);


Thoughts

Could this be done any more efficiently or better/faster/...etc? Could the splitting of string S be done without regex, remembering that row numbers can be single or double digits?

• Why can't I find a function seat(N,S)? Please edit into your problem statement: How is maximum number of 4-passenger contiguous clusters to be interpreted, especially maximum? If it is about allocated seats (if it was about free seats, it would read 4-seat clusters, wouldn't it?), how do "5-seat clusters not part of a 6-seat cluster" count: two (overlapping) 4-seat clusters, one, or none? Commented Feb 9, 2020 at 8:00
• Please properly attribute quoted contents if at all possible - you tagged this programming-challenge. The conventional MarkDown is a block quote (>  line prefix/" in the post editor tool-bar). Commented Feb 9, 2020 at 8:07
• ["thanks", everyone] have a look at some reviews with a score of at least two of code presented in questions with score at least one. Take a guess how much time you'd need to invest to present a review equally useful. Commented Feb 10, 2020 at 19:18

## 3 Answers

While this is Code Review@SE:

Do not start coding while not confident the task is well defined.

A good way to check is test first:
If you don't know how to test it, you don't know what to achieve.
(Your program (sort of) outputs

1A  1B   0   0   0  1F   0   0   0   0
2A  2B  2C  2D   0   0   0   0   0   0
3A   0  3C  3D   0   0   0   0   0   0
4A  4B   0   0  4E   0   0   0   0   0
5A   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   0   0   0   0   0


- how many clusters of 4 do you see? Your program: Total Clusters: 9)

Almost as helpful is to somehow record the approach envisioned (viability of updates and version handling as welcome as with code) -
well done, presenting it before going into detail.
I would have loved it if it was in the code.

Two things irritating about the problem statement:
• no indication what is maximum about the maximum number of clusters to return
• mention of isles, which seem to be dispensable

There are conventions, lowering the threshold to grasp someone else's work.
Many Python conventions a formalised as Python Enhancement Proposals. I put first:

1. PEP 8 -- Style Guide for Python Code
there is no just about style: it's about readability
2. PEP 257 -- Docstring Conventions
"If you violate these conventions, the worst you'll get is some dirty looks."
And not the best software for the given effort. I wish I found Fully documented code.

Going through the code top to bottom, not commenting deviations from PEP 8 (Everyone is using tool help) and referring to Sam Stafford's answer regarding useful code comments:

• printMatrix(M)
• flawless use of comprehensions.
• Lacks a docstring -
Print the matrix using no less than four characters per item.?
• Unified alignment: '{:<4}'.format(item)
• sliceMatrix(M, C)
• Not named for what it returns/computes/modifies.
• Lacks a docstring -
Return the count of contiguous clusters of size C in M.?
• Features not only the magic literal 4:
what could(/should?) be (is?!) a parameter leaks into the name of a variable.
• Contains "tracing-print()s" not easy to disable.
i used exclusively for trace printing
• (Misses the opportunity to advance four seats when num_zeros is 0
“Premature optimisation is the root of all evil (or at least most of it) in programming.”   - D.E. Knuth)
• Keeps going when n_columns < counter + cluster_size
• solution(N, S)
• Lacks a docstring -
Return the maximum number of 4-passenger contiguous clusters.?
• Is on the long side - consider factoring out taking reservations into account and counting clusters
• An alternative to columnDict[occupiedColumn] is    "ABCDEFGHJK".find(occupied_column)
• does not iterate seatMap "the pythonic way": for row in seat_map:
• creates a slice without striking need
• using explicit start and end instead of row_slice = row[:]
• not using a symbolic upper bound: row_slice = row[0:seats_per_row]
• using a literal of 9, which is the last valid index and one less than a tolerable upper bound leading to wrong (low) results when there is a block of unoccupied seats "on the right" with a length divisible by 4
• seat(N, S)
• Missing, but specified by the problem statement.
• put your "tinker test" after an
if __name__ == '__main__': - if more than a couple of lines, better define a main()

There are many ways to reach a solution -

• start at the problem
• design and code the way you think about problem and solution
giving others (including your later self (!)) a chance to follow your thinking:
Document your design.
Document your code. In the code.

My take of "the map approach", sans module docstring:

def seating(N, empty, S):
''' Return a seating of N rows initially <empty>,
with taken seats from S blanked out. '''
seats = [empty]*N
for taken in S.split():
row = int(taken[:-1]) - 1
seats[row] = seats[row].replace(taken[-1], ' ', 1)

return seats

def count_clusters(seating, cluster_size):
''' Return the count of contiguous cluster_size clusters in seating. '''
return sum(len(cluster) // cluster_size for row in seating
for cluster in row.split())

def seat(N, S):
''' Return the maximum number of 4-passenger contiguous clusters. '''
return count_clusters(seating(N, "ABCDEFGHJK", S), cluster_size=4)


Sketch of an "interval approach":

• start with one interval per row
• for each reservation
• split every interval at the seat specified
• discard all short intervals
• count intervals

food for thought:
• ordering reservations (say, by ascending row) allows handling row by row • manipulating some form of "dance card" is equivalent to bucket sorting reservations

• nice and simple. I do not like the reuse of the seating name in the count_clusters method, but for the rest this is very elegant. Commented Feb 10, 2020 at 16:38

Two comments on your comments:

1. Have the comment be at the same indentation level as the block that you're commenting. Having all the comments start at column 0 forces the eye to rapidly scan from left to right, and it makes it impossible to discern the overall structure of the program at a glance from the left-hand margin of the code. (It looks like not all the code has this problem, but enough of it does to be very distracting.)

2. Comments should describe and rephrase the purpose of a block (a logical chunk) of code, not describe what each individual line of code does. For example, this:

# pass that slice to the sliceMatrix function to get the number of clusters in that row
numClusters = sliceMatrix(rowSlice, 4)


is not a useful comment, because I can already see that you're calling the sliceMatrix function, I can see that you're passing rowSlice to it, and I can see that you're calling the result numClusters.

On the matter of how to parse a seat string, this is simple enough that you don't really need a regex or even the manually specified letter:number mapping. The fact that the column is always expressed as a single letter makes it easy to do by slicing:

# Seats are specified as a row number followed by a column letter, e.g. "22D".
# Our seat map is zero-indexed so row 1, column A corresponds to 0, 0.
row = int(seat[:-1]) - 1   # raises ValueError if the row isn't a number
col = ord(seat[-1:].upper()) - ord('A')
seat_map[row][col] = seat  # raises IndexError if seat is out of bounds

• OK,thanks for your stylistic comments, appreciated. Now the crucks of the question: is there anything which could be improved? how about feedback on writing the same answer without resorting to regular expression matching? Commented Feb 9, 2020 at 12:32
• The easier your code is to read, the more substantive feedback you'll get on code review; I focused on the commenting style first because it was distracting to the point that I was hindered from reading the code to be able to suggest improvements. :) I'll do a quick edit to add a non-regexy way to parse seats though. Commented Feb 9, 2020 at 20:23
• Using ord(seat[-1].upper()) - ord('A'), how do you suggest to handle no column capital i? Commented Feb 10, 2020 at 13:15
• I didn't even notice the omission of I. Assuming that wasn't a typo, I'd just do if col >= 8: col -= 1 # column I(8) doesn't exist to handle the "skipped" column. Commented Feb 10, 2020 at 15:22

# ;

why all the ;. Python is not JS. They don't do any harm to the program, but they are unnecessary and hamper the readability

# 1 letter variable names

I try to avoid those as much as possible, unless they are the standard jargon in for example mathematical formula's, i as counter or x and y as coordinate

# Comments

As already noted in the other answers. Comments should explain why you did something. What you do should be clear from the code, variable names, .... They should explain the edge cases, limitations, why you do the -1 to get to 0-based indexing.

Part of this can be helped by splitting the code into smaller functions with their doctstring

# reassigning variable names

Like you do in S = S.split(' '); is a practice that leads to simple errors. Better to give the parsed product another name

# split the work in functions

Your Solution method does a lot of work. It - translates the input string - assembles the plane - iterates over the rows - asks sliceMatrix the number of free clusters - sums the number for all rows

Better would be to split this into more functions

# translating the input string

A simple method that translates the coordinates to row and column indices can be as simple as:

def translate_seats(input_string):
"""
Translates the input string to 0-indexed seat, row, column tuples

skips the row "I".
case insensitive

example:
"1A 1B 1F 2A 2B 2C 2D 3A 3C 3D 4A 4B 4E 5A 6K"
--> [
("1A", 0, 0),
("1B", 0, 1),
("1F", 0, 5),
("2A", 1, 0),
("2B", 1, 1),
("2C", 1, 2),
("2D", 1, 3),
("3A", 2, 0),
("3C", 2, 2),
("3D", 2, 3),
("4A", 3, 0),
("4B", 3, 1),
("4E", 3, 4),
("5A", 4, 0),
('6K', 5, 9),
]
"""
if not input_string:
return
COLUMNS = {
"a": 0,
"b": 1,
"c": 2,
"d": 3,
"e": 4,
"f": 5,
"g": 6,
"h": 7,
"j": 8,
"k": 9,
}
for seat in input_string.split(" "):
row = int(seat[:-1]) - 1
column = COLUMNS[seat[-1].lower()]
yield seat, row, column


The docstring immediately makes clear what this method does, and it being separate enables easy testing

# 'Building' the plane

Instead of 0 as placeholder for an empty seat, I've use None, since I think this better describes the chair being empty

def assemble_plane(rows, seats, columns=10):
"""
< docstring >
"""
plane = [
[None] * columns
for _ in range(rows)
]
for seat, row, column in translate_seats(seats):
plane[row][column] = seat
return plane

rows = 7
seats = "1A 1B 1F 2A 2B 2C 2D 3A 3C 3D 4A 4B 4E 5A"
assemble_plane(rows, seats, columns=10)

[['1A', '1B', None, None, None, '1F', None, None, None, None],
['2A', '2B', '2C', '2D', None, None, None, None, None, None],
['3A', None, '3C', '3D', None, None, None, None, None, None],
['4A', '4B', None, None, '4E', None, None, None, None, None],
['5A', None, None, None, None, None, None, None, None, None],
[None, None, None, None, None, None, None, None, None, None],
[None, None, None, None, None, None, None, None, None, None]]


I've added columns as an optional argument, should you ever wish wider or narrower planes.

In the inner loop, [None] * columns works since a new list is generated for each row, but the outer loop needs the for _ in range(rows) instead of * rows

# sliceMatrix

Has a number of things wrong. C and i are not used. It prints and calculates. If you want to see what happens, you either use a debugger, or use the logging module.

Instead of counting the number of 0s, you can also use the any() builtin if you used a Falsey placeholder for empty seats to test whether any of the seats is occupied.

Instead of the for-loop, I would make this an explicit while-loop with your own indexer (location)

I changed the magic number 4 you had in your method to an optional argument.

import logging
def clusters_in_row(row, cluster_length=4):
"""
< docstring >
"""
counter = 0
location = 0

while location < len(row) - cluster_length + 1:
# no need to check the last 3 seats for a cluster of 4
my_slice = row[location : location + cluster_length]
if any(my_slice): # an occupied seat, move on
location += 1
continue
counter += 1
logging.debug(f"empty cluster found starting on {location}")
location += cluster_length
return counter


Yet again, this is a small function whose function is clear, and can be independently tested

# putting it together

def solution(rows: int, seats: str):
columns = 10 # plane is 10 seats wide
cluster_length = 4
plane = assemble_plane(rows, seats, columns=columns)
total = 0

for i, row in enumerate(plane, 1):
empty_clusters = clusters_in_row(row, cluster_length=cluster_length)
logging.debug(f"row {i} has {empty_clusters} empty clusters")
total += empty_clusters
return total


If you don't need the extra debug logging, you can even use the builtin sum

def solution(rows: int, seats: str):
columns = 10  # plane is 10 seats wide
cluster_length = 4
plane = assemble_plane(rows, seats, columns=columns)
total = 0

return sum(
clusters_in_row(row, cluster_length=cluster_length) for row in plane
)

• Many thanks for everyone's valuable feedback. I come from a C/C++/Assembly background, writing real-time code for safety-critical applications; hence the comment describing what each line does: you'd get slaughtered by the reviewers in these domains if your code is documented this way, however mundane the comments are. Still; this is really useful feedback for me to take on my journey towards acquiring Python as a dev tool. Commented Feb 11, 2020 at 17:12