Thinking outside the box

Patron Saint of Lost Yaks
posts - 203, comments - 734, trackbacks - 4

My Links

Advertisement

News

Archives

Post Categories

Joe Celko's Puzzles and Answers - The Restaurant seat assignment Problem

This problem is designed to come up with a solution that uses the smallest amount of storage possible for a 1,000 seat restaurant.
I've come up with a solution that need only 125 bytes of storage. All other solutions covered in Mr Celko's book has at least 1,000 bytes of storage.

Here is my solution, complete with all procedures to assign and release seats, together with views to display current status of each and one seat.


-- Setup sample data
CREATE TABLE    dbo.Restaurant
                (
                    Seats BINARY(125) NOT NULL
                )

-- Initialize an empty restaurant
INSERT  dbo.Restaurant 
        (
            Seats
        )
SELECT  0x
GO

-- Create procedure for handling seat assignment
CREATE PROCEDURE dbo.spAssignSeat
(
    @Seat SMALLINT
)
AS

DECLARE @Block TINYINT,
        @Bit TINYINT

SELECT  @Block = SUBSTRING(Seats, 1 + (@Seat - 1) / 8, 1),
        @Bit = POWER(2, (@Seat - 1) % 8)
FROM    dbo.Restaurant

UPDATE  dbo.Restaurant
SET     Seats = SUBSTRING(Seats, 1, (@Seat - 1) / 8) + CAST(@Bit | @Block AS BINARY(1)) + SUBSTRING(Seats, 2 + (@Seat - 1) / 8, 124 - (@Seat - 1) / 8)
GO

-- Create procedure for handling seat clearance
CREATE PROCEDURE dbo.spClearSeat
(
    @Seat SMALLINT
)
AS

DECLARE @Block TINYINT,
        @Bit TINYINT

SELECT  @Block = SUBSTRING(Seats, 1 + @Seat / 8, 1),
        @Bit = CAST(255 AS TINYINT) ^ POWER(2, (@Seat - 1) % 8)
FROM    dbo.Restaurant

UPDATE  dbo.Restaurant
SET     Seats = SUBSTRING(Seats, 1, (@Seat - 1) / 8) + CAST(@Bit & @Block AS BINARY(1)) + SUBSTRING(Seats, 2 + (@Seat - 1) / 8, 124 - (@Seat - 1) / 8)
GO

-- Create tally view
CREATE VIEW dbo.vwNums
AS

WITH    L0   AS(SELECT 1 AS c UNION ALL SELECT 1),
        L1   AS(SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
        L2   AS(SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
        L3   AS(SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
        Nums AS(SELECT ROW_NUMBER() OVER(ORDER BY c) - 1 AS Number FROM L3)

SELECT      TOP(125)
            Number
FROM        Nums
ORDER BY    Number
GO

-- Create view CurrentSeatings
CREATE VIEW dbo.vwCurrentSeatings
AS

SELECT      8 * v.number + b.number + 1 AS Seat,
            SIGN(SUBSTRING(Seats, 1 + v.number, 1) & POWER(2, b.number)) AS Taken
FROM        dbo.Restaurant AS s
INNER JOIN  dbo.vwNums AS v ON v.Number BETWEEN 0 AND 124
INNER JOIN  dbo.vwNums AS b ON b.Number BETWEEN 0 AND 7
GO

-- Create the available seats sequence view
CREATE VIEW dbo.vwAvailableSeats
AS

WITH cteSource(Seat, Taken, grp)
AS (
        SELECT  Seat,
                Taken,
                Seat - ROW_NUMBER() OVER (PARTITION BY Taken ORDER BY Seat) AS grp
        FROM    dbo.vwCurrentSeatings
)
SELECT      ROW_NUMBER() OVER (ORDER BY grp) AS Sequence,
            MIN(Seat) AS FromSeat,
            MAX(Seat) AS ToSeat
FROM        cteSource
WHERE       Taken = 0
GROUP BY    grp
GO

-- Display the wanted result
SELECT      Sequence,
            FromSeat,
            ToSeat
FROM        dbo.vwAvailableSeats
ORDER BY    Sequence

Print | posted on Saturday, July 31, 2010 1:20 AM | Filed Under [ Optimization SQL Server 2008 Algorithms SQL Server 2005 Celko Puzzle ]

Feedback

Gravatar

# re: Joe Celko's Puzzles and Answers - The Restaurant seat assignment Problem

Hmm.. this smells of a classic computer science problem or perhaps discrete math.. nice implementation even though it brought back my college nightmares. Something about travelling salesman & shortest path as I recall..
8/3/2010 10:17 PM | Jim K
Gravatar

# re: Joe Celko's Puzzles and Answers - The Restaurant seat assignment Problem

What’s the number of puzzle and which edition are you mentioning?
8/8/2010 11:15 AM | Mohammad
Gravatar

# re: Joe Celko's Puzzles and Answers - The Restaurant seat assignment Problem

After one day I repeat my question in the previous post!
Can you tell us the answer??

8/9/2010 3:55 PM | Mohammad
Gravatar

# re: Joe Celko's Puzzles and Answers - The Restaurant seat assignment Problem

Or you could spend a few seconds finding the answer yourself.

http://www.google.co.uk/#q=celko+restaurant
first result: this page
second result: Google books: puzzle 9 (page 34) of "Joe Celko's SQL puzzles & answers."

Not difficult.
8/11/2010 9:56 PM | Arnold Fribble
Gravatar

# re: Joe Celko's Puzzles and Answers - The Restaurant seat assignment Problem

oops, forgot to mention that Google's scan of the book says "Second Edition" on the cover
8/11/2010 10:05 PM | Arnold Fribble
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET