Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase ««12345»»»

Celko's SQL Stumper: The Class Scheduling Problem Expand / Collapse
Author
Message
Posted Tuesday, January 26, 2010 3:24 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Wednesday, July 23, 2014 3:35 PM
Points: 2,393, Visits: 3,399
David, your solution has the same limitations as Pierre's.
Add two new rooms {r8, r9} with {800, 900} seats, and add two new classes {c8, c9} with {5, 10} students and run your query again.



N 56°04'39.16"
E 12°55'05.25"
Post #854011
Posted Tuesday, January 26, 2010 3:28 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Wednesday, July 23, 2014 3:35 PM
Points: 2,393, Visits: 3,399
No, I am not just complaining. I have another suggestion here
http://weblogs.sqlteam.com/peterl/archive/2010/01/23/Celko-Stumper---The-Class-Scheduling-Problem.aspx

Or as a "one-query"-solution...
DECLARE  @HowManySeatsFree INT = 0 -- Set to zero for maximum seating, and to 1 for letting in late pupils.

;WITH cteSource(room_nbr, class_nbr, recID)
AS (
SELECT r.room_nbr,
c.class_nbr,
ROW_NUMBER() OVER (ORDER BY r.room_size DESC, c.class_size DESC) AS recID
FROM dbo.Rooms AS r
INNER JOIN dbo.Classes AS c ON c.class_size <= r.room_size - @HowManySeatsFree
), cteYak(recID, room_nbr, roomPath, class_nbr, classPath, isPresent)
AS (
SELECT recID,
room_nbr,
'/' + CAST(room_nbr AS VARCHAR(MAX)) + '/' AS roomPath, -- List of taken rooms
class_nbr,
'/' + CAST(class_nbr AS VARCHAR(MAX)) + '/' AS classPath, -- List of taken classes
CAST(0 AS BIGINT)
FROM cteSource
WHERE recID = 1

UNION ALL

SELECT recID,
room_nbr,
CASE isPresent -- If room never encountered before (isPresent=0), take it!
WHEN 0 THEN roompath + CAST(room_nbr AS VARCHAR(MAX)) + '/'
ELSE roompath
END AS roompath,
class_nbr,
CASE isPresent -- If class never encountered before (isPresent=0), take it!
WHEN 0 THEN classpath + CAST(class_nbr AS VARCHAR(MAX)) + '/'
ELSE classpath
END AS classpath,
isPresent
FROM (
SELECT s.recID,
s.room_nbr,
y.roomPath,
s.class_nbr,
y.classpath,
CHARINDEX('/' + CAST(s.room_nbr AS VARCHAR(MAX)) + '/', y.roompath)
+ CHARINDEX('/' + CAST(s.class_nbr AS VARCHAR(MAX)) + '/', y.classpath) AS isPresent -- See if room or class is already taken. If so, isPresent is greater than 0, otherwise it will be 0.
FROM cteSource AS s
INNER JOIN cteYak AS y ON y.recID + 1 = s.recID
) AS d
)
SELECT room_nbr,
class_nbr
FROM cteYak
WHERE isPresent = 0 -- Only present the combination never taken/found before
OPTION (MAXRECURSION 0) -- Allow up to 32767 possible combinations.




N 56°04'39.16"
E 12°55'05.25"
Post #854014
Posted Tuesday, January 26, 2010 3:50 PM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Today @ 2:44 PM
Points: 1,945, Visits: 2,862
I am surprised by two things here:

1) Nobody bothered to see if SUM(class_size) <= SUM(room_size) so we know if it is impossible to stuff the classrooms.

2) I was expecting the ROW_NUMBER() OVER() to be used more.

3) I was expecting someone to look up the solutoins in SQL FOR SMARTIES and re-wroite them with new features and CTEs.


Books in Celko Series for Morgan-Kaufmann Publishing
Analytics and OLAP in SQL
Data and Databases: Concepts in Practice
Data, Measurements and Standards in SQL
SQL for Smarties
SQL Programming Style
SQL Puzzles and Answers
Thinking in Sets
Trees and Hierarchies in SQL
Post #854024
Posted Tuesday, January 26, 2010 3:58 PM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Wednesday, July 23, 2014 3:35 PM
Points: 2,393, Visits: 3,399
Joe Celko (1/26/2010)
I am surprised by two things here:

1) Nobody bothered to see if SUM(class_size) <= SUM(room_size) so we know if it is impossible to stuff the classrooms.

2) I was expecting the ROW_NUMBER() OVER() to be used more.

3) I was expecting someone to look up the solutoins in SQL FOR SMARTIES and re-wroite them with new features and CTEs.

So you came up with this stumper to sell more books?
Which two of the three things surprised you?



N 56°04'39.16"
E 12°55'05.25"
Post #854025
Posted Wednesday, January 27, 2010 2:28 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Friday, June 6, 2014 4:34 AM
Points: 38, Visits: 143
Attempt #2.1: Descending order algorithm

WITH AllocationOrder AS (
SELECT
class_nbr,
class_size,
class_alloc_order = DENSE_RANK() OVER (ORDER BY class_size DESC, class_nbr),
room_nbr,
room_size,
room_alloc_order = DENSE_RANK() OVER (ORDER BY room_size DESC, room_nbr)
FROM Classes, Rooms
WHERE class_size <= room_size
),
Priority AS (
SELECT
room_alloc_order,
class_room_priority = ROW_NUMBER() OVER (PARTITION BY room_alloc_order ORDER BY class_alloc_order),
class_nbr,
class_size,
room_nbr,
room_size
FROM AllocationOrder
WHERE room_alloc_order <= class_alloc_order
)
SELECT
c.class_nbr,
c.class_size,
p.room_nbr,
p.room_size
FROM Classes c
LEFT JOIN Priority p ON c.class_nbr = p.class_nbr AND p.class_room_priority = 1
ORDER BY c.class_size DESC


Post #854242
Posted Wednesday, January 27, 2010 3:54 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Wednesday, October 9, 2013 2:56 AM
Points: 25, Visits: 58
1. Always better to start with a blank sheet, then you really own the problem.
2. I understood lack of obscurity, portability and backward compatibility were important here.

Swe's comments are interesting. I didn't deal with temporal contention because it didn't appear to be an issue from the problem definition. If it is to be dealt with then the possibility that some classes will not get a room has to be dealt with.

I like the vacant thresholding idea that some of the contributors have included.

I will see can I take a look at this again before the deadline.
Post #854272
Posted Wednesday, January 27, 2010 4:40 AM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Wednesday, July 23, 2014 3:35 PM
Points: 2,393, Visits: 3,399
pierre-702284 (1/27/2010)
Attempt #2: Ascending order algorithm

Add a room r8 with 48 seats.

pierre-702284 (1/27/2010)
Attempt #2: Descending order algorithm

Add a class c9 with 75 students.



N 56°04'39.16"
E 12°55'05.25"
Post #854292
Posted Wednesday, January 27, 2010 4:47 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Friday, June 6, 2014 4:34 AM
Points: 38, Visits: 143
Yeah, sorry, I noticed that mistake and I've amended my code. Please try again!
Post #854295
Posted Wednesday, January 27, 2010 5:23 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Friday, June 6, 2014 4:34 AM
Points: 38, Visits: 143
Attempt #3 - Final version, I promise!!

Descending order algorithm

SELECT c.class_nbr, c.class_size, s3.room_nbr, s3.room_size
FROM Classes c
LEFT JOIN (
SELECT *, class_priority = ROW_NUMBER() OVER (PARTITION BY class_alloc_order ORDER BY room_size DESC, room_nbr)
FROM (
SELECT *, room_priority = ROW_NUMBER() OVER (PARTITION BY room_alloc_order ORDER BY class_alloc_order)
FROM (
SELECT
class_nbr,
class_alloc_order = DENSE_RANK() OVER (ORDER BY class_size DESC, class_nbr),
room_nbr,
room_size,
room_alloc_order = DENSE_RANK() OVER (ORDER BY room_size DESC, room_nbr)
FROM Classes, Rooms
WHERE class_size <= room_size
) s1
WHERE room_alloc_order <= class_alloc_order
) s2
WHERE room_priority = 1
) s3 ON c.class_nbr = s3.class_nbr AND s3.class_priority = 1
ORDER BY c.class_size DESC, c.class_nbr

Post #854303
Posted Wednesday, January 27, 2010 8:00 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Thursday, February 2, 2012 7:24 AM
Points: 30, Visits: 109
I was not aware that the definition of the problem intended to handle collisions. I assumed the reason for making the class and room sized unique was to avoid that in the solution. Obviously, a first fit solution will have collisions where the sizes are such that they meet the criteria.

That certainly would make for a more involved solution.

Is that actually the scope of this problem?
Post #854410
« Prev Topic | Next Topic »

Add to briefcase ««12345»»»

Permissions Expand / Collapse