Cinema Seats

Computer Science Level 4

Unlike the traditional cinemas, Alice's cinema has only one row, and each seat has a colour of either red, blue or green:

$RRBRGGRBB$

Every day, she encounters customers requesting for consecutive seats with a particular sequence of colours. To verify if the request is possible, she uses the following matching algorithm :

def match(customerColor, rowColor):
    if len(customerColor) > len(rowColor):
        return False
    elif customerColor == rowColor[:len(customerColor)]:
        return True
    else:
        for i in range(len(customerColor)):
            if customerColor[i] != rowColor[i]:
                return match(customerColor, rowColor[i+1:])

Which of the customer request will return false according to the algorithm but is actually true?

None of the requests More than one of the requests

RRBR

RB

RGG

RBR

1 solution

Ved Pradhan
Jun 14, 2020

The main problem with the code is in the last line:

return match(customerColor, rowColor[i+1:])

What the for loop essentially does is go through the row, seeing if each color matches with the customer's request. Once one of the colors do not match, we know that this cannot be a valid seating, and it will start at the next index. The problem is that it doesn't account for overlaps !

To further illustrate idea, let's use indices. Our for loop starts from the start of the string. Let's say:

Index 0 matches
Index 1 matches
Index 2 does not match

Here, this program will now start looking for a new string at Index 3. However, this is a problem, because the requested string could have started at Index 1 or Index 2 , and it would never be caught! The solution to this is to store our starting index. Then, once we get a character that doesn't match, we restart not from the current index + 1, but the starting index + 1.

However, that's not what this problem is asking. We just need to find which string doesn't work. The answer is $RBR$ . Let's see why. Keep in mind that our row string is $RRBRGGRBB$ .

Index 0 matches.
Index 1 does not match, because $R \neq B$ .
Start again from Index 2.

We missed a seating! $RBR$ does occur, and it starts at Index 1. However, we never compared Index 1 of our row to Index 0 of the customer string, because it skipped that to go directly to Index 2. Thus, our answer is $\boxed{RBR}$ .

A side note: Similarly, the string $RB$ would have been missed here for the same reason. However, this is not the answer, because $RB$ is caught later on in the string.

Cinema Seats

1 solution

0 pending reports