TSQL Challenge 20 - Identify repeating digits in Fibonacci Series

This challenge has absolutely no relevance to a real-life problem, but it is very interesting because it tests your programming skills and abstract thinking.

The Fibonacci series is defined as 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 etc, where each number in the series is the sum of the two numbers before it. For example: 34 = 13+21, 55 = 21+34 etc. Some Fibonacci numbers have repeating digits, like 55 for example, which has a single repeating digit. The Fibonacci number 17711 has 2 (different) repeating digits.

Your job is to look through the first 92 Fibonacci numbers (since the 93rd number is beyond BIGINT range) and produce a result set showing the 5 lowest Fibonacci numbers for each quantity of (different) repeating digits.

Expected Output

NumRepeats  FiboNumber
----------- --------------------
1           55
1           144
1           233
1           377
1           317811
2           17711
2           102334155
2           433494437
2           32951280099
2           53316291173
3           27777890035288
3           117669030460994
3           5527939700884757
3           14472334024676221
3           1779979416004714189
4           1100087778366101931

Rules

1. The quantity of repeating digits has to refer to DIFFERENT repeating digits. For example, if there were a Fibonacci number of 344144, this would just have 1 repeating digit, not 2.
2. The repeating digits must be ADJACENT to each other. For example, if there were a Fibonacci number of 34532, the digit of 3 repeats itself, but the 3’s are not adjacent to each other.
3. The repeating digits consist of 2 or more adjacent digits. For example, if there were a Fibonacci number of 23333333, the digit of 3 is considered a single repeating digit. It doesn't matter how many times it repeats.
4. This should be done by a single query.
5. The output should look like the result given above (sorted by NumRepeats, FiboNumber)

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 #20 

We would like to welcome you to the SQL Server Challenge Idea Contest 2010-Q1. Submit an interesting challenge idea or details of a TSQL problem that you have seen, heard or solved. Authors of winning solutions will get a cash prize of $100 and 10 SQL Stars. Read More >>

Syntax Bookmark of the Day! – SQL Server Database Mail Syntax
	Quick and detailed reference for SQL Server Database Mail Feature http://syntaxhelp.com/sqlserver/dbmail

About the Author

TSQL Challenge 14 – Winning Solutions

We are just done with the evaluation of TSQL Challenge 14 and the results are published. We received a large number of solutions demonstrating different ways of solving the given problem.

And the top 3 winners are:

1. Aurelien Verla
2. Mark Cowne
3. Adam Machanic

Please join us to congratulate the winners! Their solutions will certainly help to learn better ways of writing TSQL code and solving real-world problems more efficiently.  You can see a list of all the winners here.

The Number Table (or Tally Table)

As I had mentioned a few times in the past, a Number Table (also called as a Tally Table) is an essential tool for every database developer. It helps to solve a number of common TSQL problems using a SET based approach. All the three winning solutions used a tally table to produce the expected output.

Creating and using a Tally Table

If you don’t have a Tally Table in your database, probably it is time to start thinking about building one. There are many ways to create and populate a Tally Table. Some times, for smaller operations, developers even generate a Tally Table on the fly to get a certain operation done. This article might give you some ideas by showing a few different ways of generating a Tally Table.

If you don’t have a tally table, and wants to write a query that uses a Tally Table, you could either generate a Tally Table on the fly using a CTE or Recursive CTE or use the system table master.dbo.spt_values. You can apply a filter for “type = ‘P’” on master.dbo.spt_values to get a sequence of numbers. You might find two issues when trying to use master.dbo.spt_values. First, there may be cases where you dont’t have access to master.dbo.spt_values and the other is that the number of rows in master.dbo.spt_values is limited.

Both Aurelien and Mark used master.dbo.spt_values to solve TSQL Challenge 14. Adam, on the other hand, decided to build a Tally Table on the fly and used it. You can find Aurelien’s solution here, Mark’s here and Adams solution here.

Tally Table for TSQL Challenges

If you wish to use a Tally Table in your solutions for TSQL Challenges, you can take one of the options given below.

1. Use master.dbo.spt_values, if the number of rows in spt_values is sufficient for solving the given problem. However, you need to make sure that your code will not break when we test it with a much larger set of data during our evaluation process.
2. Create and use a Tally Table on the fly. Note that you are not allowed to create table variables, temporary tables or table valued functions in your solutions.
3. The next and probably the best option is to create a Tally Table using the script given here. If you decide to go with this option, you need to take care of the following:
   1. The table should be created exactly as per the script given here.
   2. The name of the table should be “dbo.tsqlc_Tally”
   3. You should not include the code to build this table as part of your solution. You can assume that this table is present in the target system where we evaluate your solutions.

TSQL Challenge 14 – Evaluation Summary

We received 128 submissions for TSQL Challenge 14. Out of that, 41 solutions were rejected due to one or more of the following reasons.

• Using Temp Tables
• Using Table Variables
• Using Local Variables
• Using WHILE Loops
• Using Cursors
• Using UDFs

Note that the challenges are 'always ON', which means that you can submit a solution at any time. You can submit a new solution even after the results are published. If your solution is disqualified, you can re-submit a new version of the challenge at any time.

87 Solutions went through the Basic Testing using the sample data given along with the challenge and only 62 of them passed the test. Those solutions were put through the Logic Testing and only 49 of them passed the test.

The solutions that passed the Logic Test were send to a Load Test with a large table having 100,000 rows. Here is the script that we used to generate the test data for Load Testing. The Load Testing was done with a timeout value of 5 minutes per solution. Solutions that took more than 5 minutes to execute were rejected. Only 20 solutions passed the Load Test and the performance statistics of those solutions are posted here.

Winning Solutions

Solutions that pass the Load Testing will be assigned a rank based on their performance. Based on the rank of each solution, we will consider the top 10 solutions as winning solutions. You can find the Winning Solutions of TSQL Challenge 14 here.

Resubmitting a new solution

Though the results of this challenge is published, you can still submit a new solution. We will evaluate your submissions periodically and will refresh the final results if one of those solutions are better than the solutions already published.

We would like to welcome you to the SQL Server Challenge Idea Contest 2010-Q1. Submit an interesting challenge idea or details of a TSQL problem that you have seen, heard or solved. Authors of winning solutions will get a cash prize of $100 and 10 SQL Stars. Read More >>

TSQL Challenge 14 – Results of Basic Testing

As many of you have already mentioned, it is a bit frustrating that it takes us almost 8-10 weeks to publish the results of a challenge. We are working very hard on this and you will see a significant improvement in the speed of the evaluation process from now onwards. We are just done with the basic testing of TSQL Challenge 14 and there are unpleasant results.

Results

We received a total of 128 submissions for this challenge, and unfortunately, 41 of them were disqualified because they did not follow the submission guide lines. The rejections fall into the categories given below.

1. Using temp tables
2. Using table variables
3. Using local variables
4. Using WHILE Loops
5. Using Cursors
6. Using UDFs

We completed the Basic Testing phase on the remaining 87 solutions using the data given here. 25 solutions failed the basic testing due to the following reasons.

1. Incorrect output data
2. Incorrect number of output columns
3. Incorrect order of output columns

Note that the evaluation is done by an automated script which will reject a submission if the columns (order and number of columns) do not follow the output structure given in the challenge description.

Resubmit your solutions

If your solution is disqualified due to one of the reasons given above, you don’t need to worry. You can resubmit your solution and after the evaluation is completed, we will review your submission and if it passes the tests will insert it at the right grade in the final results. TSQL Challenges do not close any more and you can always submit a better solution.

Questions

We are in the process of setting up the new website (http://databasechallenges.com/SQLServer/TSQL) with the right structure and would like to hear your ideas on the following:

1. With TSQL challenge 13, we made all the solutions publicly available (even the solutions that failed the tests - http://databasechallenges.com/SQLServer/TSQL/Challenge13/Submissions) Do you think it is a good idea? In TSQL Challenge 14, we only mentioned the number of submissions we received, we did not publish all the solutions we received. Is that a better option?
2. Do you like to see the list of solutions that passes each evaluation phase? (see an example here: http://databasechallenges.com/SQLServer/TSQL/Challenge13/logic_testing_results) Or is it advisable to publish only the count of solutions that passes the given test?
3. Any other suggestion you have, to make the evaluation process better and the challenges and their solutions re-usable?

Thanks for your continuous interest in TSQL Challenges

Jacob

TSQL Challenge 19 - Working with consolidated calculations on hierarchical structures

Working with hierarchies is almost always lot of fun for most of us. Traversing heirarchies and processing data from child or parent nodes is really interesting and such assignments are ideal opportunities to test your logic and query writing skills.

This challenge involves generating an organizational hierarchy and calculating the total orders created by each employee and his/her subordinates. It involves a number of challenges such as generating a resultset in the correct hierarchical form, calculating the orders created by each employee and his/her subordinates and finally calculating the total orders created by self and all the subordinates.

We have been working on making the evaluation process more efficient and transparent. As a result, we came up with a 4 step evaluation process which we have described in detail in this post. We are also working on speeding up the evaluation process and we hope to catch up with the evaluation in a few weeks.

There are a number of things you could do to help us make the evaluation process faster. The first of that is following all the guidelines and rules given in the challenge. If you follow the guidelines, it will help us to complete the evaluation process faster.

When you submit a solution, do not include the code to generate the sample data. So, ideally your query should start with a SELECT or WITH and nothing else. No SET statements, NO setup or clean-up code. Our evaluation process will inject the required code into your solution while processing your solution. Please note that by following these guidlines, you are helping us to complete the evaluation process sooner.

Please pay attention to the rules given at the end of the challenge and the submission guidelines. We currently accept only SET based soutions with a single TSQL query. CTEs are accepted but temp tables, table variables, WHILE loops or UDFs are currently not accepted. A large number of submissions in the previous challenges were rejected because of these reasons. We are working on the evaluation process to see if we can support NON-SET based solutions in the future and we are quite hopeful that we will do it in the future.

Sample Data for TSQL Challenge 19

Employee Table

EmployeeID  FirstName       LastName        ReportsTo
----------- --------------- --------------- -----------
2           Andrew          Fuller          NULL
1           Nancy           Davolio         2
3           Janet           Leverling       2
4           Margaret        Peacock         2
5           Steven          Buchanan        2
8           Laura           Callahan        2
6           Michael         Suyama          5
7           Robert          King            5
9           Anne            Dodsworth       5

Order Table

OrderID     EmployeeID
----------- -----------
10258       1
10270       1
10275       1
10265       2
10277       2
10251       3
10253       3
10256       3
10250       4
10252       4
10248       5
10254       5
10249       6
10289       7
10303       7
10308       7
10262       8
10268       8
10276       8
10278       8
10255       9
10263       9

Expected Output

Name                      Level by_self by_sub total
------------------------- ----- ------- ------ -----
Fuller, Andrew            0     2       20     22
    Buchanan, Steven      1     2       6      8
        Dodsworth, Anne   2     2       0      2
        King, Robert      2     3       0      3
        Suyama, Michael   2     1       0      1
    Callahan, Laura       1     4       0      4
    Davolio, Nancy        1     3       0      3
    Leverling, Janet      1     3       0      3
    Peacock, Margaret     1     2       0      2

Scripts

Use the following script to generate the sample data

DECLARE @emp TABLE (
	EmployeeID INT,
	FirstName VARCHAR(15),
	LastName VARCHAR(15),
	ReportsTo INT
)

DECLARE @ord TABLE (
	OrderID INT,
	EmployeeID INT
)

INSERT INTO @emp(EmployeeID, FirstName, LastName, ReportsTo)
SELECT 2,'Andrew','Fuller',NULL UNION ALL
SELECT 1,'Nancy','Davolio',2 UNION ALL
SELECT 3,'Janet','Leverling',2 UNION ALL
SELECT 4,'Margaret','Peacock',2 UNION ALL
SELECT 5,'Steven','Buchanan',2 UNION ALL
SELECT 8,'Laura','Callahan',2 UNION ALL
SELECT 6,'Michael','Suyama',5 UNION ALL
SELECT 7,'Robert','King',5 UNION ALL
SELECT 9,'Anne','Dodsworth',5
SELECT * FROM @emp

INSERT INTO @ord (OrderID, EmployeeID) 
SELECT 10258,1 UNION ALL
SELECT 10270,1 UNION ALL
SELECT 10275,1 UNION ALL
SELECT 10265,2 UNION ALL
SELECT 10277,2 UNION ALL
SELECT 10251,3 UNION ALL
SELECT 10253,3 UNION ALL
SELECT 10256,3 UNION ALL
SELECT 10250,4 UNION ALL
SELECT 10252,4 UNION ALL
SELECT 10248,5 UNION ALL
SELECT 10254,5 UNION ALL
SELECT 10249,6 UNION ALL
SELECT 10289,7 UNION ALL
SELECT 10303,7 UNION ALL
SELECT 10308,7 UNION ALL
SELECT 10262,8 UNION ALL
SELECT 10268,8 UNION ALL
SELECT 10276,8 UNION ALL
SELECT 10278,8 UNION ALL
SELECT 10255,9 UNION ALL
SELECT 10263,9 

SELECT * FROM @ord

Rules

1. The output should show the hierarchical relationship between the employees (as shown in the example above)
2. The column "by_self" should show all the orders created by the employee (directly)
3. The column "by_sub" should show the total of orders created by all the employees reporting to him/her
4. The column "total" should show the total of "by_self" and "by_sub"
5. The employees shoud be ordered by lastname, firstname

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 #19 

We will close this challenge for evaluation on 28 December 2009 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.

You can submit solutions for challenges even after we publish the results. However, there are a few things you should do before submitting your solutions.

• Do a basic testing of your solution using the sample data we post along with the results of the evaluation. See an example here.
• If your solution passes the basic testing, do a logic testing of your solution. We will publish the data to be used for the logic testing along with the challenge results. You can see an example here.
• If your solution passes the logic testing, do a load testing of your solution using the load testing data that we publish along with the challenge results. You can see an example here.
• After load testing, match your results with the results we have published for that challenge. (see an example here). If the results of your solution comes in the top 10 solutions listed on the results page, go ahead and send us your solution. Make sure that you send us the results of your load testing along with your submission.
• We will re-evalute your solution and if it comes in the top 10, we will list it in the results page and you will be added to the winners page (see an example here) and will get a certain number of SQL Stars based on the grade of your solution.

We would like to welcome you to the SQL Server Challenge Idea Contest 2010-Q1. Submit an interesting challenge idea or details of a TSQL problem that you have seen, heard or solved. Authors of winning solutions will get a cash prize of $100 and 10 SQL Stars. Read More >>

Syntax Bookmark of the Day! – SQL Server Backup Syntax
	Quick and detailed reference for SQL Server FULL BACKUP command http://syntaxhelp.com/sqlserver/backup/full

About the Author

SQL Server Challenge Idea Contest 2010-Q1

Welcome to the SQL Server Challenge Idea Contest 2010 Q1. SQL Server Challenge Idea Contest is a quarterly challenge from SQL Server Challenges team to recognize people with great SQL Server experience solving complex business problems using TSQL.

If you have a great SQL Server Challenge idea, send us your challenge idea and we will be very happy to review them.

What are challenge ideas?

Any business problem that requires above average SQL Server skills to solve may be qualified as an ideal candidate for the SQL Server Challenge Idea Contest. It could be one of the following:

1. Any problem that you came across and successfully solved.
2. Any problem that you have come across but was not able to solve.
3. Any difficult problem that you have seen, heard of can think of.

Challenge Guidelines

The challenge idea you submit should follow the guidelines given below.

1. It should be a problem that can be solved using TSQL.
2. It should be a data transformation challenge – taking data from one or more tables and producing the output in a certain format.
3. You should provide a description of the challenge.
4. You should provide detailed list of the rules, logic requirements and additional details such as sort order etc, along with your submission.
5. you should provide the sample data and expected results. The sample data should be simple, short and minimal and should focus on explaining the concept of the challenge
6. You should provide the scripts to create the sample data
7. Though not mandatory, it is recommended that you provide a more detailed data for performing the logic testing of the solutions. This data should contain a more detailed tricky set of data which has all sort of odd and exceptional value combinations.
8. Finally, though it is not mandatory, we will be very happy if you can provide the script for generating the load testing data. The load testing is done with a larger data set, which is usally 1 million rows.

And the Winners Get…..

The authors of winning solutions will receive a few exciting prizes. The challenge idea that comes first will receive a cash prize of $100 by Paypal. In addition, the winner will get 10 SQL Stars and the challenge will be published at www.tsqlchallenges.com.

The SQL Server Challenges team will also select top (up to) 10 challenge ideas from the submissions and the authors of those challenges will get a consolation cash prize of $25 each. They will also earn 5 SQL Stars each for their interesting challenge idea. Selected challenge ideas will be published at www.tsqlchallenges.com.

Submitting the challenge idea

Follow the guidelines given below for submitting your challenge idea.

1. Create a text file that explains your challenge idea. Name the file “firstname_lastname_SSCIC2010Q1.txt”. If your first name is “smith” and last name is “jones”, your file should be named “smith_jones_SSCIC2010Q1.txt”. Include the source data and expected output in the text description.
2. Create a sql file that contains the scripts to create the input data. Use table variables instead of physical/temp tables and provide the insert scripts. Include your version of the solution (if you were able to solve the problem) in the sql file. Name the file “firstname_lastname_SSCIC2010Q1.sql”. If your first name is “smith” and last name is “jones”, your file should be named “smith_jones_SSCIC2010Q1.sql”.
3. Send both the files by email to tc@beyondrelational.com. We will send a confirmation email when we receive the submission. If you do not receive a confirmation message in 24 hours, please resend your submission.
4. Last date for submitting your entries is 31 January 2010 Midnight GMT. The winners will be announced by the second week of February.

Questions

Use this forum to discuss your questions on this contest.

Good Luck

Best of luck all the participants and we look forward to see your submissions soon.

TSQL Challenges – Announcing the new improved evaluation process!

One of the areas we always knew that we need improvement, is the evaluation process. We had been constantly working on improving the evaluation process to improve the accuracy, quality and transparency of the process. While we were still working on getting into a better process, we faced a major glitch with the evaluation of TSQL Challenge 13. This mistake made us focus fully on the evaluation process, under ‘emergency mode’ and set the process right. As a result, I am very happy to announce the new evaluation process which makes the whole process very transparent and provides more accurate results. Many thanks to all the members of TSQL Challenges Team who spent quite a lot of time working on the evaluation process, especially Adam, David, Brad and Rui (and Jacob too??).

A more transparent Evaluation Process

We started doing a multi-step evaluation process starting from TSQL Challenge 13. The evaluation process includes:

1. Pre Process Validation
2. Basic Testing
3. Logic Testing
4. Load Testing

To make the evaluation process more transparent, we will be posting the solutions, data used for the testing, test results etc on a new website (http://sqlserverchallenges.com). Please take a look at the results of TSQL Challenge 13 and we are sure you will like it :-).

Pre Process Validation

The evaluation process starts with ‘Pre Process Validation’ where the solutions will be reviewed and verified whether they follow the submission guide lines. For example, solutions that use cursors or temp tables will be rejected at this stage. Once the invalid submissions are removed, the evaluation process moves ahead with the Accepted Solutions. We will publish the list of accepted solutions after the Pre Process Validation is completed. You can see an example here.

Basic Testing

During this stage, the solutions will be tested against the sample data we publish along with the challenge description. We will only test the accuracy of the solution at this stage. Performance statistics are not collected at this testing phase. Any solution that does not produce the EXACT output described in the challenge description will be rejected. Note that the number of columns and the values of every row should match 100% with the Expected Output listing given in the challenge description. We will publish the solutions that pass the Basic Testing once the testing is done. You can see an example here.

Logic Testing (tricky testing?)

Solutions that pass the Basic Testing will go through a tougher Logic Testing. This testing will be done on a set of ‘tricky’ data where the robustness and the strength of the logic applied in the solution will be tested. After the evaluation, we will publish the tricky data so that you can take a look at the data used for the testing. You can see an example here. Solutions that pass the Logic testing will be published as done with TSQL Challenges 13 here.

Load Testing

Finally, the solutions will go through the Load Testing phase. During Load Testing, we will test the solutions with a very large set of data. We will publish the data for your reference, after the evaluation is over. Note that this is the only testing where we collect the performance statistics of each solution. We will publish the performance details of each solution after the evaluation is over. You can find an example here.

Announcing the Winners

After the Load Testing, we will order the results based on the rank (which includes Reads, Writes, Duration and CPU) and will consider the top 10 solutions as winning solutions. Based on the rank, each winner will get 1 to 10 SQL Stars. We will also create a page where the total SQL Stars each person earned will be published. A higher number of SQL Stars indicates a higher level of query writing skills. Here are the winners of TSQL Challenge 13.

Comments and Questions

We will be very happy to hear your comments, feedback and questions on the evaluation process.