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  |
Michel Cadot
Messages: 17697
Registered: March 2007
Location: Nanterre, France, http://... |
Senior Member |
|
|
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]
|
|
|
| Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #295747 is a reply to message #290787 ] |
Wed, 23 January 2008 04:48  |
Michel Cadot
Messages: 17697
Registered: March 2007
Location: Nanterre, France, http://... |
Senior Member |
|
|
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]
|
|
|
| Re: Puzzle n°01 - Finding adjacent seats in theater ** [message #296266 is a reply to message #295747 ] |
Fri, 25 January 2008 07:08 |
Michel Cadot
Messages: 17697
Registered: March 2007
Location: Nanterre, France, http://... |
Senior Member |
|
|
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. 
Regards
Michel
|
|
|
Goto Forum:
Current Time: Fri Jul 25 17:39:57 CDT 2008
Total time taken to generate the page: 0.02113 seconds |
]
Members
Search
Help
Register
Login
Home
