Getting Started with Adobe After Effects - Part 6: Motion Blur
First Time? You can support us by signing up. It takes only 5 seconds. Click here to sign up. If you already have an account, click here to login.

View in another Language

Sponsored [Advertise Here]
Don't have a blog yet?
beyondrelational.com
Start writing a blog at beyondrelational.com, get recognized and build your brand

Syndicate your blog!
beyondrelational.com
Syndicate your blog with us to get wider reach into the technology community. Click here to get started.

Izenda Reports
izenda.com
Ad Hoc reporting for ASP.NET that actually works

TSQL Challenge 56 - Create a Sierpinski carpet using TSQL

This challenge invites you to generate a Sierpinsky carpet using TSQL. If you are new to Sierpinsky Carpet, see the details here (http://en.wikipedia.org/wiki/Sierpinski_carpet).

Your job is to read the input table and generate a Sierpinsky carpet of the specified level. The sample input data for this puzzle is given below.

Want to make SQL effortless?
With code-completion, SQL reformatting, script summaries and more, SQL Prompt 5 makes writing, editing, and exploring SQL effortless. Download a 14-day free trial now.

Sample Data

id level
-- -----
1      0
2      1
3      2

Expected Results

id row carpet
-- --- ---------
1    1 X
2    1 XXX
2    2 X X
2    3 XXX
3    1 XXXXXXXXX
3    2 X XX XX X
3    3 XXXXXXXXX
3    4 XXX   XXX
3    5 X X   X X
3    6 XXX   XXX
3    7 XXXXXXXXX
3    8 X XX XX X
3    9 XXXXXXXXX

Rules

  1. The output should be ordered by id, row column.
  2. The output should have three columns. The first column should contain the id,the second shopuld be row id of carpet and the third should contain the carpet.

Sample Script

Use the TSQL Script given below to generate the source tables and fill them with sample data.

IF OBJECT_ID('TC56','U') IS NOT NULL BEGIN
	DROP TABLE TC56
END
GO

CREATE TABLE TC56(
	id  INT,
	level INT
)
GO

INSERT INTO TC56(id,level)
SELECT 1, 0 UNION ALL
SELECT 2, 1 UNION ALL
SELECT 3, 2

SELECT * FROM TC56

Restrictions

  1. The solution should be a single query that starts with a "SELECT" or “;WITH”

Notes

  1. Read the Submission Guidelines and make sure that your solution follows them.
  2. If you would like to use a Tally Table, you can use the script given here. Your solution should not include the script to create and populate the tally table. You can assume that the tally table will be available in the database where the evaluation team will run your Code.
SQL Source Control - now with static data support
"By allowing static data to be versioned, SQL Source Control now becomes a complete source of truth for the application's data layer. I'm in." Troy Hunt, Software Architect.
More information and a free trial.

Leszek Gniadkowski
8 · 17.77% · 5729
Submit a Solution
View Solutions
View All Challenges Previous Challenge Next Challenge
2
Liked
14
Comments
48
Solutions



Submit

14   Comments   

Subscribe to Notifications
  • The input table always contains consecutive values in the level column, starting from 0?

    commented on May 17 2011 2:47AM  .  Report Abuse This post is not formatted correctly
    Razvan Socol
    178 · 1% · 278
  • Is there a maximum level to be dealt with - what data type are you expecting for the carpet output ?

    commented on May 17 2011 3:29AM  .  Report Abuse This post is not formatted correctly
    DaveR - UK
    112 · 1% · 463
  • The input table always contains consecutive values in the level column, starting from 0?

    No.

    Is there a maximum level to be dealt with - what data type are you expecting for the carpet output ?

    There is no maximum limit (output type - varchar(max))

    commented on May 18 2011 7:07AM  .  Report Abuse This post is not formatted correctly
    Leszek Gniadkowski
    8 · 18% · 5729
  • I would assume that 20 is logical possible maximum - carpet grows 3 times every iteration and 3^19 is 1 162 261 467 and it's the biggest power of 3 lower than 2^31 - 1, which is varchar(max)'s limit. I don't expect, however, anyone trying to output over a billion of rows, each of them over 1 GB in size :)

    My laptop is slow generating carpets of level 7 - takes 7 seconds to accomplish that, but it's not the strongest machine in the universe (Pentium Dual Core T2370, 2 GB RAM, 200 GB HDD). Level 8 runs over a minute, I'll have to review it.

    commented on May 18 2011 7:25AM  .  Report Abuse This post is not formatted correctly
    Szymon Wojcik
    67 · 3% · 877
  • My stats here

    (13 row(s) affected) Table 'TC56'. Scan count 28, logical reads 28, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. Table 'tsqlc_Tally'. Scan count 316, logical reads 1503, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

    SQL Server Execution Times: CPU time = 77 ms, elapsed time = 76 ms.

    commented on May 19 2011 6:12PM  .  Report Abuse This post is not formatted correctly
    Peso
    100 · 2% · 527
  • Lets make stats more interesting:

    INSERT INTO TC56(id,level) SELECT 1, 0 UNION ALL SELECT 2, 7 UNION ALL SELECT 3, 9 UNION ALL SELECT 4, 8 UNION ALL SELECT 5, 7

    So my stats here:

    (30619 row(s) affected) Table 'Worktable'. Scan count 6, logical reads 616417, physical reads 0, read-ahead reads 0, lob logical reads 126667, lob physical reads 0, lob read-ahead reads 0. Table 'TC56'. Scan count 30548, logical reads 30548, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

    SQL Server Execution Times: CPU time = 14531 ms, elapsed time = 44659 ms.

    commented on May 26 2011 5:16AM  .  Report Abuse This post is not formatted correctly
    Mario Puskaric
    154 · 1% · 321
  • Standard input:

    Table 'Worktable'. Scan count 2, logical reads 79, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. Table 'TC56'. Scan count 15, logical reads 15, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

    SQL Server Execution Times: CPU time = 15 ms, elapsed time = 13 ms.

    Mario's data:

    Table 'Worktable'. Scan count 2, logical reads 177145, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. Table 'TC56'. Scan count 29526, logical reads 29526, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

    SQL Server Execution Times: CPU time = 147187 ms, elapsed time = 186991 ms.

    Mario, what's the machine you're testing on? :)

    commented on May 26 2011 5:33AM  .  Report Abuse This post is not formatted correctly
    Szymon Wojcik
    67 · 3% · 877
  • I tested this on virtual machine with 8 Processors (cores) and 32GB RAM, but behind is 4 x 4core x 2.7GHz, 40GB. Well, maybe I should test it on laptop (but I don't have it with me now) to get more ‘realistic’ stats.

    Nevertheless, these stats are from my improved algorithm that deliberately uses more scans, but less memory (can become bottleneck on high levels).

    commented on May 30 2011 1:43AM  .  Report Abuse This post is not formatted correctly
    Mario Puskaric
    154 · 1% · 321
  • Hello,

    I've been checking my failed solutions and I'm surprised to see that the only reason for my submission (ID:4722) to fail was obvious problem with generating the basic sandbox. It looks like something went really wrong during the generation of that script.

    Could somebody have a look on that for me please?

    Thanks

    commented on Jul 29 2011 6:22AM  .  Report Abuse This post is not formatted correctly
    lof
    224 · 1% · 201
  • @lof,

    I will shortly send you the online URL to your sandbox which will allow you to test it 'exactly' the way the evaluation software does. That will help to figure out why it fails.

    commented on Jul 29 2011 6:51AM  .  Report Abuse This post is not formatted correctly
    Jacob Sebastian
    1 · 100% · 32235
Previous 1 | 2 Next

Your Comment


Sign Up or Login to post a comment.


Managed Windows Shared Hosting by OrcsWeb

Copyright © Rivera Informatic Private Ltd.