TSQL Challenge 22 - Filling balls into boxes based on rules and preferences

Who among us wouldn't want to go back to our childhood and enjoy those lovely playful time once again? Well, here is a challenge that might take you back to your childhood and might keep you busy sorting and filling colorful balls into different boxes. Here is an interesting challenge submitted by our new contributor RamiReddy.

As I have mentioned a few times in the past, we are working very hard on improving 'TSQL Challenges' and a number of people from the SQL Server community have been helping us to come up with some improvements.

We were getting a large number of comments against the 'all-in-one-query' requirement that we put on the challenges. They argue that not all real-world problems are solved with the 'single-query' approach. There are also times when a 'multi-step' query performs better than a 'single-query' approach. They are right.

On the other side, we do get a lot of feedback from people who say that they like the 'one-query' requirement because that is the real 'fun' in these challenges. The 'single-query' requirment makes them think beyond the regular problem solving methods and they find it very interesting. They are right too.

We are still working on setting up a plan that makes both the groups happy. Till then we will allow 'multi-statement' solutions selectively. It means that some challenges will allow multi-statement solutions and some will not. If the challenge allows multi-statement solutions, we will specifically mention it along with the challenge description.

To improve the quality of the challenges and the clarity of the rules of the challenges, we started inviting volunteers to do an 'early challenge review' where they get a chance to review the challenge description and rules and give us some suggestions to improve the quality of the challenges. I am very glad that a few people already came forward to help us and if any of you would like to volunteer, please contact me privately.

Starting with this challenge, we will be providing sample data in physical tables instead of table variables. Your solution should not include the code to populate the sample tables. You can assume that the sample tables with data exist in the current database.

Starting with this challenge, we are also introducing a 'Challenge Moderator'. The moderator of a challenge will be helping you with your questions in the forums and everything else that you would need related to a certain challenge. RamiReddy is the Moderator for this challenge and he will be available to help you with any questions related to this challenge.

We have got some boxes and balls. Our job is to put balls into those boxes. But, wait a second! The balls should be filled into the boxes based on some rules and preferences configured by the user. Here are the rules.

• A box can have only one ball
• A ball can be placed only in one box
• Number of balls and number of boxes will always be the same.
• All boxes should be filled and all balls should be used
• There will be a configuration table where the preferences of the user will be stored. The preference setting should be followed when putting a ball into a box.

In addition to this, there will be a configuration table where the preferences of the user will be stored. The preference setting should be followed when putting a ball into a box.

Here is the sample data for this challenge.

Table: TC22_Boxes

This is the table that stores the boxes. Each row in this table represents a box. Boxes in this table will always be unique.

BoxId       BoxName
----------- --------------------
1           Box 1
2           Box 2
3           Box 3
4           Box 4
5           Box 5
6           Box 6

Table: TC22_Balls

This table stores the balls. Each row in this table represents a ball. Balls in this table will always be unique.

BallId      BallName
----------- --------------------
1           Ball 1
2           Ball 2
3           Ball 3
4           Ball 4
5           Ball 5
6           Ball 6

Table: TC22_Preferences

This table stores the preferences set by the user. There may be multiple preferences configured for each box or ball. For example, the second and third rows indicate that you can put ball #1 or ball #3 into box #2. You can take any one of the preferences but need to make sure that all boxes will be filled and all balls will be used.

PreferenceId BoxId       BallId
------------ ----------- -----------
1            1           1
2            2           1
3            2           3
4            3           2
5            3           3
6            4           1
7            4           2
8            4           3
9            4           4
10           4           5
11           4           6
12           5           4
13           5           5
14           6           5

Here is the expected results based on the above sample data.

Box         Ball      
----------- ----------- 
Box 1       Ball 1           
Box 2       Ball 3           
Box 3       Ball 2           
Box 4       Ball 6           
Box 5       Ball 4           
Box 6       Ball 5           

User the following scripts to generate the sample data for this challenge

-- --------------------------------------------------
-- Create the 'Boxes' table
-- --------------------------------------------------
IF OBJECT_ID('TC22_Boxes','U') IS NOT NULL 
BEGIN
	DROP TABLE TC22_Boxes
END
GO

CREATE TABLE TC22_Boxes
(
    BoxId INT IDENTITY PRIMARY KEY,
    BoxName VARCHAR(20)
)
GO

INSERT INTO TC22_Boxes (BoxName)
SELECT 'Box 1' UNION all
SELECT 'Box 2' UNION all
SELECT 'Box 3' UNION all
SELECT 'Box 4' UNION all
SELECT 'Box 5' UNION all
SELECT 'Box 6' 


-- --------------------------------------------------
-- Create the 'Balls' table
-- --------------------------------------------------
IF OBJECT_ID('TC22_Balls','U') IS NOT NULL 
BEGIN
	DROP TABLE TC22_Balls
END
GO

CREATE TABLE TC22_Balls(
    BallId INT IDENTITY PRIMARY KEY,
    BallName VARCHAR(20)
)
GO

INSERT INTO TC22_Balls (BallName)
SELECT 'Ball 1' UNION all
SELECT 'Ball 2' UNION all
SELECT 'Ball 3' UNION all
SELECT 'Ball 4' UNION all
SELECT 'Ball 5' UNION all
SELECT 'Ball 6' 

-- --------------------------------------------------
-- Create the 'Preferences' table
-- --------------------------------------------------
IF OBJECT_ID('TC22_Preferences','U') IS NOT NULL 
BEGIN
	DROP TABLE TC22_Preferences
END
GO

CREATE TABLE TC22_Preferences(
    PreferenceId INT IDENTITY PRIMARY KEY,
    BoxId INT,
    BallId INT
)
GO

INSERT INTO TC22_Preferences (BoxID, BallID) 
SELECT 1,1 UNION all
SELECT 2,1 UNION all
SELECT 2,3 UNION all
SELECT 3,2 UNION all
SELECT 3,3 UNION all
SELECT 4,1 UNION all
SELECT 4,2 UNION all
SELECT 4,3 UNION all
SELECT 4,4 UNION all
SELECT 4,5 UNION all
SELECT 4,6 UNION all
SELECT 5,4 UNION all
SELECT 5,5 UNION all
SELECT 6,5

Notes

1. Read the Submission Guidelines and make sure that your solution follows them.
2. The solution should work on SQL Server 2005, 2008 or later versions
3. Use this forum for any questions related to TSQL Challenge #22 

Unlike the previous challenges, this one allows multi-statement solutions. Your solution does not need to be a single-query solution. You can use RBAR, cursors, loops etc in your solution. However, we need to apply some restrictions on your code so that your solution can be evaluated using our automated evaluation script.

Your code should not create objects like views, functions or stored procedures. Your solution should be a single batch. There should not be any 'GO' statements between your solution. We will put the entire content of your solution to the body of a stored procedure and if we do that, your code should not produce an error. For example, you need to make sure that the following works:

CREATE PROCEDURE TC_Eval
AS
BEGIN
SET NOCOUNT ON
-- your code here
END
GO

Your code should not include the code to create the sample data. You can assume that the sample tables already exist in the current database.

We will close this challenge for evaluation on 8 February 2010 Midnight GMT. All the solutions we receive till that date will be processed and the results will be announced in the format given here. However, you can continue to send us your solutions till the day we announce the evaluation results.

1. Are Boxid, BallID and PreferenceId  sequential with no gaps ?
• The column is an identity column and identity columns are not expected to be sequential. There can be gaps/missing-ids.
2. Is there a maximum number of balls and boxes?
• No, there is no maximum number of balls and boxes. The number of balls and boxes will always be the same so that if you fill the boxes correctly, all boxes will be filled and all balls will be used.
3. What sort order is the final result set ?
• Sort the output by Box ID
4. Is there any priority order if there are 2 Balls going into 1 box ?
• No, there is no priority order, because there is only one ‘correct’ box for each ball.
5. Will there be a case in which two balls are preferenced only to one box? For example, can ball3 and ball5 be referenced only to box7 ?
• No, two balls can't be preferenced ONLY to one box. It can happen that ball 3 and 5 are referenced to box 7. But in such a case, either or both of them will also have another preference to another box.
6. Is it guaranteed that the sample data have one and only one valid solution?
• Yes, There will be only on ‘correct’ solution for a given set of sample data. If you assign a ball to an incorrect box, you will end up with another box that does not have any ball to fill in.
7. Can we create indexes on the sample tables?
• No, No modifications should be done to the sample tables.
8. Can I create and use a tally/number table in my queries?
• No, you are not allowed to create and use your own tally tables. However if you need a tally table, you can use the script given here to create a tally table. When you send us your solution, do not include the script to create the tally table. Your query can assume that the tally table already exists on the database where we will run your queries.
9. Can I use a CLR procedure/function
• No, CLR code is not allowed.

• dave ballantyne
• Aurelien Verla
• lmu92
• Sergejack

The Early Review team did a great job by reviewing the challenge description, rules and helped to compile the FAQ list. We have made the required updates to the challenge based on the recommendations of the Early Review Team.

About the Author

Challenge Idea by

Related Posts

Comments