Home » Other » General » Puzzle n°01 - Finding adjacent seats in theater **
Puzzle n°01 - Finding adjacent seats in theater ** [message #290787] Mon, 31 December 2007 14:56 Go to next message
Michel Cadot
Messages: 59427
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
I will start the puzzle posts with one already posted by Ross in http://www.orafaq.com/forum/mv/msg/74101/209776/102589/#msg_209776.
Quote:

This is the case where you are Ticketek, and you get a group of 4 people who
want to book seats together. You must find all the places in the theatre where
there are 4 or more vacant seats all next to each other.

For our purposes, assume that we have n people, so we need n or more vacant
seats in a row. Ignore the problem that in most theatres the seat numbers
aren't adjacent at the ends of rows. (Assume that we have a circular
amphitheatre with the seats in a continuous spiral.) Return a row with the
starting number for each set of n adjacent seats. It would be even better if
you could return a single row for each block of of available seats of n or
more, so if n=4, and 101-106 are available, then the row (101,6) would be
preferable to 101,102,103.

The input will be as follows. If there are 1000 seats in the theatre, then
there will be 1000 rows in the table, with an indicator for whether each seat
is booked or not.

Here's a script to create the table and fill it with random but deterministic data.
DROP TABLE seats
/
CREATE TABLE seats (
  seat   INTEGER PRIMARY KEY,
  booked INTEGER CHECK (booked IN (0,1))
  )
/
DECLARE
  -- Each PI decimal gives the number of adajacent seats 
  -- with the same booked/unbooked status
  s_pi CONSTANT VARCHAR2(510) := '3' ||
'14159265358979323846264338327950288419716939937510' || 
'58209749445923078164062862089986280348253421170679' || 
'82148086513282306647093844609550582231725359408128' || 
'48111745028410270193852110555964462294895493038196' || 
'44288109756659334461284756482337867831652712019091' || 
'45648566923460348610454326648213393607260249141273' || 
'72458700660631558817488152092096282925409171536436' || 
'78925903600113305305488204665213841469519415116094' || 
'33057270365759591953092186117381932611793105118548' || 
'07446237996274956735188575272489122793818301194912';
  i_pi     PLS_INTEGER := 1; -- PI decimal
  i_seat   PLS_INTEGER := 0; -- seat number
  i_booked PLS_INTEGER := 1; -- 1=booked, 0=unbooked
  i_nb     PLS_INTEGER;      -- number of seats with same status
BEGIN
  LOOP
    EXIT WHEN i_seat >= 1000;
    i_nb := TO_NUMBER(SUBSTR(s_pi,i_pi,1)) + 1;
    FOR j in 1..i_nb LOOP
      EXIT WHEN i_seat+j > 1000;
      INSERT INTO seats VALUES (i_seat+j, i_booked);
    END LOOP;
    i_seat   := i_seat + i_nb;
    i_pi     := i_pi + 1;
    i_booked := 1 - i_booked;
  END LOOP;
  COMMIT;
END;
/

Enjoy!

Regards
Michel

[Updated on: Tue, 01 January 2008 01:07]

Report message to a moderator

Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #295747 is a reply to message #290787] Wed, 23 January 2008 04:48 Go to previous messageGo to next message
Michel Cadot
Messages: 59427
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
I will start with only the first 29 rows in the table to show how it works.
First, for each row I will add a flag column containing the seat number only if the previous seat is not in the same booked/unbooked state, this will give me the starting row of a new group of seats with the same status, each other row will have a null value in this column:
SQL>     select seat, booked,
  2             case 
  3               when nvl(lag(booked) over (order by seat),1-booked) != booked
  4               then seat
  5             end flag
  6      from seats
  7  order by seat
  8  /
      SEAT     BOOKED       FLAG
---------- ---------- ----------
         1          1          1
         2          1
         3          1
         4          1
         5          0          5
         6          0
         7          1          7
         8          1
         9          1
        10          1
        11          1
        12          0         12
        13          0
        14          1         14
        15          1
        16          1
        17          1
        18          1
        19          1
        20          0         20
        21          0
        22          0
        23          0
        24          0
        25          0
        26          0
        27          0
        28          0
        29          0

29 rows selected.

At second step, I repeat/propagate this flag to all subsequent seats with the same status:
SQL> with 
  2    step1 as (
  3      select seat, booked,
  4             case 
  5               when nvl(lag(booked) over (order by seat),1-booked) != booked
  6               then seat
  7             end flag
  8      from seats
  9    )
 10      select seat, booked, max (flag) over (order by seat) grp
 11      from step1
 12  order by seat
 13  /
      SEAT     BOOKED        GRP
---------- ---------- ----------
         1          1          1
         2          1          1
         3          1          1
         4          1          1
         5          0          5
         6          0          5
         7          1          7
         8          1          7
         9          1          7
        10          1          7
        11          1          7
        12          0         12
        13          0         12
        14          1         14
        15          1         14
        16          1         14
        17          1         14
        18          1         14
        19          1         14
        20          0         20
        21          0         20
        22          0         20
        23          0         20
        24          0         20
        25          0         20
        26          0         20
        27          0         20
        28          0         20
        29          0         20

29 rows selected.

Now, "flag" (which has been renamed to "grp") gives me each successive groups with same status.
Group 1 is booked, group 5 is free, group 7 is booked, group 12 is free, group 14 is booked and group 20 is free.
The next step is to get the minimal and maximal seat numbers and the number of seats in each group, limiting to the groups that are unbooked:
SQL> with 
  2    step1 as (
  3      select seat, booked,
  4             case 
  5               when nvl(lag(booked) over (order by seat),1-booked) != booked
  6               then seat
  7             end flag
  8      from seats
  9    ),
 10    step2 as ( 
 11      select seat, booked, max (flag) over (order by seat) grp
 12      from step1
 13    )
 14      select min(seat) first_seat, max(seat) last_seat, count(*) nb_seat
 15      from step2
 16      where booked = 0
 17      group by grp
 18  order by 1
 19  /
FIRST_SEAT  LAST_SEAT    NB_SEAT
---------- ---------- ----------
         5          6          2
        12         13          2
        20         29         10

3 rows selected.

Now, we just have to search for the rows/groups that satisfy the condition: a number of successive unbooked seats greater or equal the resqueted number.
With the full table, this gives:
SQL> def nb=6
SQL> with 
  2    step1 as (
  3      select seat, booked,
  4             case 
  5               when nvl(lag(booked) over (order by seat),1-booked) != booked
  6               then seat
  7             end flag
  8      from seats
  9    ),
 10    step2 as ( 
 11      select seat, booked, max (flag) over (order by seat) grp
 12      from step1
 13    ),
 14    step3 as (
 15      select min(seat) first_seat, max(seat) last_seat, count(*) nb_seat
 16      from step2
 17      where booked = 0
 18      group by grp
 19    )
 20  select first_seat||'-'||last_seat seats
 21  from step3
 22  where nb_seat >= &nb
 23  order by first_seat
 24  /
SEATS
---------------------------------------------------------------------------------
20-29
33-39
56-64
75-82
164-171
182-187
201-209
227-234
237-243
268-277
282-289
299-304
318-327
361-366
393-401
404-410
436-442
456-465
476-484

19 rows selected.

SQL> def nb=9
SQL> /
SEATS
--------------------
20-29
56-64
201-209
268-277
318-327
393-401
456-465
476-484

8 rows selected.


Regards
Michel

[Updated on: Fri, 25 January 2008 07:05]

Report message to a moderator

Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #296266 is a reply to message #295747] Fri, 25 January 2008 07:08 Go to previous messageGo to next message
Michel Cadot
Messages: 59427
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator

Note on the previous query: the final step (main query) should easily be merged into the previous one (named step3), I separated these steps to explain the query and let you now merge them. Wink

Regards
Michel
Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #345734 is a reply to message #290787] Thu, 04 September 2008 11:56 Go to previous messageGo to next message
chacham
Messages: 1
Registered: September 2008
Junior Member
Isn't this a job for CONNECT BY?
SELECT
	Seat - Amount + 1 Seat,
	Amount
FROM
	(
	 SELECT
		Seat,
		MAX(Level) Amount
	 FROM
		Seats
	 WHERE
		CONNECT_BY_ISLEAF = 1
	 START WITH
		Booked	= 0
	 CONNECT BY
		Seat	= PRIOR Seat + 1
	    AND	Booked	= 0
	 GROUP BY
		Seat
	)
WHERE
	Amount >= 4
ORDER BY
	Seat;
Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #345738 is a reply to message #345734] Thu, 04 September 2008 12:21 Go to previous messageGo to next message
Michel Cadot
Messages: 59427
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Nice one! ./fa/2115/0/

Could you explain it, the purpose of these SQL puzzles is to help to learn SQL tricks and features.

Regards
Michel
Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #345770 is a reply to message #345738] Thu, 04 September 2008 14:34 Go to previous messageGo to next message
Brian Tkatch
Messages: 6
Registered: September 2008
Location: Oak Park, MI USA
Junior Member

Sure. I'll give it a shot.

The base query is creating a set of seats where they are all empty, and we'll throw in Level to find the offset:

SELECT
	Seat,
	Level Amount
FROM
	Seats
START WITH
	Booked	= 0
CONNECT BY
	Seat	= PRIOR Seat + 1
    AND	Booked	= 0


The START BY applies the CONNECT BY restricted of unbooked seats to the first seat as well.

The problem is, this allows each member in the set to start its own string. That is, if 2 is a child of 1, it'll be in there twice, once with an offset of 0 (when it is the parent) and once with an offset of 1 (when it is a child of 1).

The solution is two-fold.

1) Find the last member in the set. That's CONNECT_BY_ISLEAF = 1.
2) Being there are many sets, as each member starts its own set, use GROUP BY and MAX(Level) to get the leaf with the highest offset.


SELECT
	Seat,
	MAX(Level) Amount
FROM
	Seats
WHERE
	CONNECT_BY_ISLEAF = 1
START WITH
	Booked	= 0
CONNECT BY
	Seat	= PRIOR Seat + 1
    AND	Booked	= 0
GROUP BY
	Seat;


So, now we have the sets we want, and how many seats in each set. The problem now is, the seat listed is the final member in the set. That is easily solved, just subtract the amount of members from the final member and add one.

SELECT
	Seat - MAX(Level) + 1,
	MAX(Level) Amount 
FROM
	Seats
WHERE
	CONNECT_BY_ISLEAF = 1
START WITH
	Booked	= 0
CONNECT BY
	Seat	= PRIOR Seat + 1
    AND	Booked	= 0
GROUP BY
	Seat;


Perfect. That lists all sets of seats more than 1 in a row.

Now we can add the simple requirement of the puizzle. That it be 4 or more.

SELECT
	Seat - MAX(Level) + 1,
	MAX(Level) Amount 
FROM
	Seats
WHERE
	CONNECT_BY_ISLEAF	= 1
  AND	Level			>= 4
START WITH
	Booked	= 0
CONNECT BY
	Seat	= PRIOR Seat + 1
    AND	Booked	= 0
GROUP BY
	Seat;
Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #345773 is a reply to message #345770] Thu, 04 September 2008 14:39 Go to previous messageGo to next message
Michel Cadot
Messages: 59427
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator

Thanks
Michel
Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #614728 is a reply to message #296266] Mon, 26 May 2014 10:13 Go to previous message
Lalit Kumar B
Messages: 2449
Registered: May 2013
Location: World Wide on the Web
Senior Member
Michel Cadot wrote on Fri, 25 January 2008 18:38

Note on the previous query: the final step (main query) should easily be merged into the previous one (named step3), I separated these steps to explain the query and let you now merge them. [/img]


Very nicely summarized Michel. As you said, step3 could be resolved into single step using LISTAGG(11g onwards) :

SQL> WITH step1
  2       AS (SELECT seat,
  3                  booked,
  4                  CASE
  5                    WHEN Nvl(Lag(booked)
  6                               over (
  7                                 ORDER BY seat), 1 - booked) != booked THEN seat
  8                  END flag
  9           FROM   seats),
 10       step2
 11       AS (SELECT seat,
 12                  booked,
 13                  Max (flag)
 14                    over (
 15                      ORDER BY seat) grp
 16           FROM   step1
 17           WHERE  booked = 0
 18           ORDER  BY seat)
 19  SELECT *
 20  FROM  (SELECT Listagg(seat, ',')
 21                  within GROUP(ORDER BY grp) seat_range,
 22                Count(*)                     cnt
 23         FROM   step2
 24         GROUP  BY grp)
 25  WHERE  cnt > 4;
SEAT_RANGE                                                                              CNT
-------------------------------------------------------------------------------- ----------
20,21,22,23,24,25,26,27,28,29                                                            10
33,34,35,36,37,38,39                                                                      7
56,57,58,59,60,61,62,63,64                                                                9
75,76,77,78,79,80,81,82                                                                   8
113,114,115,116,117                                                                       5
135,136,137,138,139                                                                       5
164,165,166,167,168,169,170,171                                                           8
182,183,184,185,186,187                                                                   6
201,202,203,204,205,206,207,208,209                                                       9
227,228,229,230,231,232,233,234                                                           8
237,238,239,240,241,242,243                                                               7
268,269,270,271,272,273,274,275,276,277                                                  10
282,283,284,285,286,287,288,289                                                           8
299,300,301,302,303,304                                                                   6
318,319,320,321,322,323,324,325,326,327                                                  10
336,337,338,339,340                                                                       5
351,352,353,354,355                                                                       5
361,362,363,364,365,366                                                                   6
393,394,395,396,397,398,399,400,401                                                       9
404,405,406,407,408,409,410                                                               7
SEAT_RANGE                                                                              CNT
-------------------------------------------------------------------------------- ----------
436,437,438,439,440,441,442                                                               7
456,457,458,459,460,461,462,463,464,465                                                  10
476,477,478,479,480,481,482,483,484                                                       9
509,510,511,512,513                                                                       5
564,565,566,567,568,569,570,571                                                           8
582,583,584,585,586,587,588,589,590                                                       9
601,602,603,604,605,606,607,608,609                                                       9
611,612,613,614,615,616,617,618,619                                                       9
627,628,629,630,631,632                                                                   6
642,643,644,645,646,647,648,649,650                                                       9
659,660,661,662,663,664,665                                                               7
673,674,675,676,677                                                                       5
710,711,712,713,714                                                                       5
720,721,722,723,724,725,726                                                               7
728,729,730,731,732,733,734,735,736,737                                                  10
744,745,746,747,748,749                                                                   6
751,752,753,754,755,756                                                                   6
778,779,780,781,782,783,784,785                                                           8
789,790,791,792,793,794                                                                   6
799,800,801,802,803,804                                                                   6
815,816,817,818,819                                                                       5
SEAT_RANGE                                                                              CNT
-------------------------------------------------------------------------------- ----------
821,822,823,824,825,826,827,828,829                                                       9
844,845,846,847,848                                                                       5
872,873,874,875,876                                                                       5
887,888,889,890,891,892,893,894,895                                                       9
918,919,920,921,922,923,924,925,926,927                                                  10
932,933,934,935,936,937,938,939,940                                                       9
955,956,957,958,959,960                                                                   6
967,968,969,970,971,972                                                                   6
983,984,985,986,987,988,989                                                               7
995,996,997,998,999                                                                       5
51 rows selected


Looking for more such puzzles!
Thanks to you and Ross Smile
Previous Topic: Input and output channels
Next Topic: Puzzle n°- Traverse through 100 doors, find which are open/closed **
Goto Forum:
  


Current Time: Sat Oct 25 18:53:58 CDT 2014

Total time taken to generate the page: 0.04590 seconds