Solution to Joe Celko's SQL puzzles & answers‎ - PUZZLE 9 AVAILABLE SEATS, Page 34

The Problem : You have a restaurant with 1,000 seats. Whenever a waiter puts someone at a seat, he logs it in a table of seats. Likewise, when a guest finishes a meal, you remove the guest’s seat number. You want to write a query to produce a list of the available seats in the restaurant, set up in blocks by their starting and ending seat numbers. Oh yes, the gimmick is that the database resides on a personal digital assistant and not a mainframe computer. As part of the exercise, you must do this with the smallest amount of storage possible. Assume each seat number is an integer. (extract from Joe Celko's SQL puzzles & answers‎ - PUZZLE 9 AVAILABLE SEATS, Page 34).

My set based solution with no procedural constructs like while loops or cursors)  goes like this:

/* Start by creating a new blank database, will name it [Puzzle] */
USE [Puzzle]

/* creating the table, will occupy 1000 char X 1 byte each = 1000 bytes */
   CREATE
     TABLE dbo.Seats
                  ( Seats char(1000) )

/* then insert all seats as empty */
INSERT INTO dbo.Seats VALUES ( REPLICATE('0',1000))

/* Then we need a way of set each seat as free/occupied */
CREATE PROCEDURE [dbo].[Set_Seat]
   @seatNum smallint,
   @occupied bit
AS
BEGIN
SET NOCOUNT ON;
  
/* This statetement will split the char string in two parts, setting the middle with the occupied value, concat them all together again, taking care of any weird case as well. */
UPDATE dbo.Seats
     SET Seats = CASE
                            WHEN @seatNum BETWEEN 0 AND 1000
                                THEN LEFT(Seats,@seatNum-1)
                                  + CAST(@occupied as char(1))
                                  + RIGHT(Seats,(LEN(Seats)
                                  - @seatNum))
                            ELSE Seats
                        END
END
/* then use this stored procedure to update the table, i.e. the following statement will update the the seats no 1,5,10 as occupied. */
EXECUTE [Puzzle].[dbo].[Set_Seat] @seatNum = 1, @occupied = 1
EXECUTE [Puzzle].[dbo].[Set_Seat] @seatNum = 5, @occupied = 1
EXECUTE [Puzzle].[dbo].[Set_Seat] @seatNum = 10, @occupied = 1

/* after executing this the table will look like this */

Seats

10001000010000000....

/* then we will need to have a way to see which seats are free and which are occupied.
To achieve this will need a helper number table, which is obtained by cross join the sys.objects table of the   [Puzzle] db. Because the db doesn't contain many user created objects, will double cross join to it self so as to achieve a cartesian product. This will give us at least a 1000 rows containing system information. By applying the funtion ROW_NUMBER() we can get the amount of numbered rows we want. */

/* the free seats */
CREATE VIEW [dbo].[vFreeSeats]
AS
SELECT a.Seat
  FROM ( SELECT n as Seat
                   FROM ( SELECT row_number() over (order by n.object_id) as ID
                                    FROM sys.objects n
                                       CROSS JOIN sys.objects v
                                   ) D ( n )
               WHERE n <= 1000
               ) a
 WHERE SUBSTRING((select * from dbo.Seats),a.Seat,1) = '0'
GO

/* and the occupied */
CREATE VIEW [dbo].[vOccupiedSeats]
AS
SELECT a.Seat
  FROM ( SELECT n as Seat
                   FROM ( SELECT row_number() over (order by n.object_id ) as ID
                                    FROM sys.objects n
                                        CROSS JOIN sys.objects v
                                 ) D ( n )
                WHERE n <= 1000
               ) a
 WHERE SUBSTRING((select * from dbo.Seats),a.Seat,1) = '1'
GO

/* Obtaining a plan of the restaurant using the same patern with row_number() to get a numbering from 1 to 1000, and then LEFT JOIN to dbo.vOccupiedSeats and dbo.vFreeSeats */
CREATE VIEW [dbo].[vAllSeats]
AS
SELECT s.Seat,
                o.Seat as Occupied,
                f.Seat as Free
       FROM ( SELECT n as Seat
                        FROM
                         ( SELECT row_number() over (order by n.object_id) as ID
                             FROM sys.objects n
                                CROSS JOIN sys.objects v
                          ) D ( n )
      WHERE n <= 1000 ) s

       LEFT JOIN dbo.vOccupiedSeats o
          ON o.Seat = s.Seat
           LEFT JOIN dbo.vFreeSeats f
               ON f.Seat = s.Seat
GO

/* Showing the start and end number of continous availabel blocks of seats, taking care for special cases as well. */
CREATE VIEW [dbo].[vFirstLastSeat]
AS
SELECT  f.[First] as FirstInBlock,
                l.[Last] as LastInBlock
  FROM (  /* get the first seat number of
                    each available continous block of seats */
               SELECT row_number() over (order by current_timestamp) as ID,
                             [First]
                   FROM ( /*  use this in case the first free seat is no 1 */
                                 SELECT 1 as [First]
                                   FROM dbo.vFreeSeats f
                                 WHERE f.Seat = 1
                                  UNION ALL
                                 /* this will return the first seats on a  
                                    continuous block,  except when
                                     this is seat no1*/
                                 SELECT f.Seat as [First]
                                   FROM dbo.vFreeSeats f
                                     JOIN dbo.vOccupiedSeats o
                                        ON f.Seat = o.Seat + 1 ) f
                      ) f
     
     /* get the last seat number of each available continous block of seats */
     JOIN ( SELECT row_number() over ( order by  current_timestamp ) as ID,
                                l.Seat as [Last]
                 FROM
                   ( /* this will return the first seats on a continuus 
                         block, except when this is seat no 1000 */
                      SELECT f.Seat
                        FROM dbo.vFreeSeats f
                            JOIN dbo.vOccupiedSeats o
                               ON f.Seat = o.Seat - 1
                       UNION ALL                                                
                       /* use this in case the last free seat is no 1000 */
                       SELECT 1000 as [Last]
                          FROM dbo.vFreeSeats
                        WHERE Seat = 1000 ) l
                  ) l

           ON f.ID = l.ID

/* The output of the previous statement */

FirstInBlock	LastInBlock
2	4
6	9
11	1000

/* Finally, if we didn't want to use the sys.objects table, we could have create a @tempTable with 10 null rows of bit datatype, and use this to cross join 3 times to give a helper number table of a 1000 rows. */