Problem 546306 · easy · Level 05 Advanced Algorithms & Graphs

Every Row Books the Same Seat

py-debugging · mutable default arguments · aliasing · py-lists

A theatre's booking helper has two bug reports. Here is the function:

def book_seats(rows, cols, bookings, refused=[]):
    """Seat map after the bookings: 'X' booked, '.' free, one string per row.
    Bookings for a seat that is already booked are refused and added to `refused`."""
    grid = [["."] * cols] * rows
    for r, c in bookings:
        if grid[r][c] == "X":
            refused.append((r, c))
        else:
            grid[r][c] = "X"
    return ["".join(row) for row in grid], refused
  • Report 1: "I booked seat 1 in row 0 of an empty 3 x 3 hall and the map shows seat 1 booked in every row."
  • Report 2: "The first concert refused one booking. For the second concert, in a fresh hall with no repeated seat, the refused list still contained the first concert's refusal."

Write a corrected book_seats(rows, cols, bookings, refused=None). Setup helpers available with Run: season(n, seed) (several concerts in a row) and shared_list() (a caller collecting refusals in its own list). It returns (seat map, refused list). When the caller passes a list as refused, the refusals are appended to that list and that same list is returned; when the caller passes nothing, every call starts with a new empty list.

Examples

Input:  book_seats(3, 3, [(0, 1)])
Output: ([".X.", "...", "..."], [])

Input:  (book_seats(2, 2, [(0, 0), (0, 0)]), book_seats(2, 2, [(1, 1)]))
Output: ((["X.", ".."], [(0, 0)]), (["..", ".X"], []))

Constraints

  • 1 <= rows, cols <= 300, up to 10**5 bookings, all inside the hall.

Goals

  • Recognise the shared-mutable-default trap from its symptom
  • Recognise a grid whose rows are one and the same list
  • Fix a bug at its cause and keep the documented interface
Starting Python…