Click here to monitor SSC
A service from Red Gate

in
Home SQL .NET SysAdmin Opinion Blogs Forums Books
Sign in | Join | Help
Home Blogs Forums
Blogs Home > Lionel Clarke > Sql Puzzle 4

Lionel Clarke

Software Engineer - Red Gate Software

Sql Puzzle 4

Published Friday, December 16, 2005 11:35 AM

/*
Sorry for the delay putting up this puzzle but I was going to
post a different puzzle for this week but failed to get a solution
for it :)

When queuing for our food at the Christmas party, I noticed that several of us
had already overdone the alcoholic drinks. Whilst we waited, I wondered how
many drunk people were standing next to each other, and what was the longest
unbroken row of these inebriated people in the queue.

This, then is the puzzle. Below is a table that represents a queue of people. The
value in the Position field represents their position in the queue. The FirstName
Field holds the first name of the person. The IsDrunk
Field is 1 if the person is drunk and 0 otherwise. Using the table below,
construct a single query without using variables, other tables and ddl
that returns single rows resultset which holds the most number of drunk
people standing adjacent in a row within the queue. For the example data below
the results should be 4, as Simon, James, Tom and Lionel are standing next to each
other, drunk, in the queue.

Largest Number Of Drunk People In A Row
---------------------------------------
4

*/
SET NOCOUNT ON
DECLARE @Queue TABLE
(
    Position INT PRIMARY KEY,
    FirstName VARCHAR(50) NOT NULL,
    IsDrunk INT NOT NULL -- 0 is not Drunk 1 is drunk
)

INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 1, 'Nick', 1
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 2, 'John', 0
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 3, 'Simon', 1
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 4, 'James', 1
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 5, 'Tom', 1
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 6, 'Lionel', 1
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 7, 'Neil', 0
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 8, 'Andras', 1
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 9, 'Richard', 1
INSERT INTO @Queue(Position, FirstName, IsDrunk)
    SELECT 10, 'Helen', 0

SET NOCOUNT OFF
by Lionel

Comments

 

Phil Factor said:


/*-----------------------------------------------------
--at first inspection this looks like a simple correlated subquery
--which just measueres the size of the gaps between the sober people

Select max (gap) from
(
Select [gap]=sober.position -
(select coalesce(max(position),0)
from @queue nextsober
where isDrunk=0
and nextsober.position < sober.position
)-1
from @queue sober where isDrunk=0
)Gaps

--which will give the right answer but totally ignore the end of the queue
--if there is nobody sober at the end of the queue. Lionel would not
--allow anything so cheaty as popping someone sober on the end of the
--queue so.....
---------------------------------------------------------*/
--here is a version of the same technique that scans forward as well
--as backwards. Lionel forgot to ban UNIONS so this will work


select max (gap) from
(
Select --gaps from the last sober person downwards
[gap]=sober.position -
(select coalesce(max(position),0)
from @queue nextsober
where isDrunk=0
and nextsober.position < sober.position
)-1
from @queue sober where isDrunk=0
union all
Select --gaps from the first sober person upwards
[gap]=
(select coalesce(min(position),(SELECT MAX(position) from @queue))
from @queue nextsober
where isDrunk=0
and nextsober.position > sober.position
)- sober.position-1
from @queue sober where isDrunk=0
) rowlengths

December 16, 2005 1:47 PM
 

Lionel said:

Bonus points to anyone who can solve the puzzle WITHOUT using a corralated subquery.
December 16, 2005 2:12 PM
 

James said:

So a solution without a corralated subquery albeit slightly mad...

SELECT TOP 1 ((S4.b - S4.A) - 1) as Num
FROM
(SELECT a = (CASE WHEN MAX(S2.Pos) IS NULL THEN 0 ELSE MAX(S2.Pos) END),
b = (CASE WHEN S1.Position IS NULL THEN 0 ELSE S1.Position END)
FROM
(SELECT * FROM @Queue as Q1 WHERE IsDrunk = 0) S1
LEFT JOIN
(SELECT Q2.Position as Pos FROM @Queue AS Q2 WHERE IsDrunk = 0) S2
ON S1.Position > S2.Pos
GROUP BY S1.Position) S4
ORDER BY Num DESC
December 16, 2005 3:25 PM
 

Phil Factor said:

--nice algorithm, James
--Ooops I missed out a simple +1 to check for an unbroken chain at the end without a
sober person at the end of the queue
select max (gap) from
(
Select --gaps from the last sober person downwards
[gap]=sober.position -
(select coalesce(max(position),0)
from @queue nextsober
where isDrunk=0
and nextsober.position < sober.position
)-1
from @queue sober where isDrunk=0
union all
Select --gaps from the first sober person upwards
[gap]=
(select coalesce(min(position),(SELECT MAX(position) from @queue)+1)
from @queue nextsober
where isDrunk=0
and nextsober.position > sober.position
)- sober.position-1
from @queue sober where isDrunk=0
) rowlengths

--By the way, how on earth do we indent our code.
December 16, 2005 4:34 PM
 

Phil Factor said:

James's method fails if you add drunkards onto the end, the same way my original attempt failed

If Lionel wants a solution without a correlated subquery, how about

declare @ii int
select @ii=case when isdrunk=0 then 0 else @ii+1 end from @queue
Select @ii
December 16, 2005 4:47 PM
 

Phil Factor said:

--which doesn't work; BrainFade! But this, which I meant to add, does, I reckon

declare @ii int,@jj int
select @ii=case when isdrunk=0 then 0 else coalesce(@ii,0)+1 end ,
@jj=case when coalesce(@jj,0)<coalesce(@ii,0) then @ii else @jj end from @queue
order by position
Select [result]=@jj
December 16, 2005 5:27 PM
 

Lionel said:

I definatly rember saying no varables :)
December 17, 2005 8:29 PM
 

Amanda said:

This is a blatant copy of James' code; I just added the union line to "insert" an IsDrunk = 0 line at the end of the table. This works even if you add IsDrunk records to the end of the table:

SELECT TOP 1 ((S4.b - S4.A) - 1) as Num
FROM
(SELECT a = (CASE WHEN MAX(S2.Pos) IS NULL THEN 0 ELSE MAX(S2.Pos) END),
b = (CASE WHEN S1.Position IS NULL THEN 0 ELSE S1.Position END)
FROM
(SELECT * FROM @queue as Q1 WHERE IsDrunk = 0 Union select Max(Position) + 1, 'Dummy', 0 from @queue) S1
LEFT JOIN
(SELECT Q2.Position as Pos FROM @queue AS Q2 WHERE IsDrunk = 0) S2
ON S1.Position > S2.Pos
GROUP BY S1.Position) S4
ORDER BY Num DESC
December 19, 2005 6:46 PM
 

Pete said:

Heres my version (with no correlated subqueries nor unions!). I had to put the case statement at the top to handle alcohol free parties...

select top 1 count(case when total = 0 then null else total end) as result from
(
select q1.position, count(q2.position) as total
from @queue q1
left join @queue q2 on q2.position < q1.position and q2.isdrunk = 0
and q1.isdrunk = 1
group by q1.position
) tbl1
group by total
order by result desc
December 22, 2005 4:37 PM
 

Phil Factor said:

I thought Pete's solution immensely clever and neat, And I marvelled at how it worked. However, it doesn't. It fails for the same reason my initial solution fails.

All you need to do is to make John drunk and the routine says that the longest unbroken queue of drunks is two. You'd have to pinch Amanda's trick, but in this case, adding a sober person to the beginning of the queue. Come now, there must be an elegant and simple solution to this, that doesn't use variables!
December 23, 2005 3:16 PM
 

eoldre said:

I think this does the trick. Basically, find the max distance between where there are no sober people between them.

Eric

select max(h.position-l.position+1)
from @queue l
join @queue h on l.position < h.position
where not exists(
select * from @queue s
where s.isdrunk=0
and s.position>l.position
and s.position<h.position)
and l.isdrunk=1 and h.isdrunk=1
December 23, 2005 5:22 PM
 

Phil Factor said:

/* This is a different style of solution which is simply to ask each member of the queue how far away in front is the nearest sober person, or the front of the queue; and then picking the biggest answer. Not as clever as Eric's, though. We're all waiting for Lionel's elegant solution! */
select max([drunkards In Front Of Me])
from
(
--find out the maximum figure of the smallest gap to a sober person
Select [drunkards In Front Of Me]=min(me-[His Or Her Position]) from
--all the queue members in front of )and behind) each queue member
(
--add a marker in front of the queue
select [me]=position,[Am I Drunk]=isDrunk,[His Or Her Position]=0,[Is He Or She Drunk]=0 from @queue c
union all
--roll out the queue showing all the other queue members from each's perspective
select [me]=a.position,
[Am I Drunk]=a.isDrunk,
[His Or Her Position]=b.position,
[Is He Or She Drunk]=b.isDrunk
from @queue a cross join @queue b
)f
where [Am I Drunk]<>0 and [Is He Or She Drunk]=0
and [His Or Her Position]<me--chuck away data on those behind me
group by [me]
)g



December 25, 2005 7:26 PM
 

Pete said:

I decided to approach this problem by grouping the adjacent drunks together and counting them. My method was to group them based on the number of sober people in front of them. Drunks next to each other always havehe same number of sober people in front of them. Unfortunately my first attempt ignored drunks at the very beginning of the line (they have zero sober people in front of them.) This solution has overcome this problem by only counting a person if they are drunk. Hope you like it...


select top 1 count(case when isdrunk = 0 then null else total end) as result from
(
select count(q2.position) as total, q1.isdrunk
from @queue q1
left join @queue q2 on q2.position < q1.position and q2.isdrunk = 0
and q1.isdrunk = 1
group by q1.position , q1.isdrunk
) tbl1
group by total
order by result desc
December 28, 2005 4:00 PM
 

Lionel said:

Well I think it is time to post my solution up. I did this in a bit of a strange way as I was going to pose a differnt problem but couldn't think of a good way of explaining it so I changed the problem and adapted my solution this problem.

I would like to thank everybody who put their solutions up. It really is interesting to see different peoples aproaches. Sorry for not writing everybody a reply but it has been a really hectic year end. Not a good excuse I know. I will try and be a bit better about putting stuff in the comments with the next few.

SELECT MAX(GroupLength) AS [Largest Number Of Drunk People In A Row] FROM
(SELECT COUNT(*) AS GroupLength
FROM @Queue a
INNER JOIN @Queue b
on a.Position <= b.Position
CROSS JOIN @Queue c
WHERE c.Position > b.Position - a.Position
AND c.Position <= b.Position
GROUP BY a.Position, b.Position
HAVING MIN(c.IsDrunk) = 1) DrunkGroups
December 30, 2005 5:13 PM
 

Fun with SQL (games, painting, puzzles) « 1st blog, pre-beta version… said:

PingBack from http://rolldice.wordpress.com/2010/01/24/fun-with-sql-games-painting-puzzles/
January 24, 2010 2:04 AM
You need to sign in to comment on this blog
<December 2005>
SuMoTuWeThFrSa
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567
How to Kill a Company in One Step or Save it in Three
 The majority of companies that suffer a major data loss subsequently go out of business. Wesley David... Read more...

Migrating from OCS 2007 R2 to Lync: Part 4
 Having migrated the rest of our users and legacy resources across and started getting ready to... Read more...

Automated Script-generation with Powershell and SMO
 In the first of a series of articles on automating the process of building, modifying and copying SQL... Read more...

Seth Godin: Big in the IT Business
 Seth Godin has transformed our understanding of marketing in IT. He invented the concept of 'permission... Read more...

Using SQL Test Database Unit Testing with TeamCity Continuous Integration
 With database applications, the process of test and integration can be frustratingly slow because so... Read more...