SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 

Solving Ken’s FizzBuzz 3D–#SQLNewBlogger

Another post for me that is simple and hopefully serves as an example for people trying to get blogging as #SQLNewBloggers.

I like the FizzBuzz test. It’s cute and fun, and I’ve had my kids solve it, just to think about what it means to structure a simple problem. It’s not a great test of whether you’re a good programmer, but if you can’t solve this, you probably aren’t.

Ken Fisher set up a challenge to solve FizzBuzz with SQL, but in a 3D manner. He added a few challenge to this, like no modulus operator. I don’t know why you’d deliberately avoid using this, but it’s a programming exercise, so why not. I took the challenges because, well, Ken asked me do.

SQLNewBlogger

I’m putting this part first, because this is a good exercise, and a great post for your blog. Solve this yourself first, and write about it. Then you can read my code.

The coding part of this probably took me 20-25 minutes to do. I worked on it in a few stages, pausing to do other work and let the solution simmer a bit. I realized a few times that I was making it harder, so the breaks were helpful.

Writing this up was about 30 minutes, but it made me think about what I’d done.

Building a Solution

My first thought with this is I need a tally table. Of course, I’m building a set of coordinates from 1 to 100. I started here.

WITH myTally (n)
AS
-- SQL Prompt formatting off
(SELECT n = ROW_NUMBER() OVER (ORDER BY (SELECT null))
  FROM (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) a(n)
   CROSS JOIN (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) b(n)
)
, cteCoordinates (x, y, z)
-- SQL Prompt formatting on
AS
(
SELECT a.n ,
        b.n ,
        c.n
FROM myTally AS a
     CROSS JOIN myTally AS b
     CROSS JOIN myTally AS c
)
SELECT x, y, z
FROM cteCoordinates;

This gave me my list of numbers.

2018-07-02 14_40_48-SQLQuery4.sql - (local)_SQL2016.sandbox (vstsbuild (53))_ - Microsoft SQL Server

My next step was to think about the FizzBuzz test. I can’t use Modulo, so how can I determine if I am evenly divisible by 3? I decided to look at the simple division operator. I got these results, but notice anything?

2018-07-02 14_42_55-SQLQuery4.sql - (local)_SQL2016.sandbox (vstsbuild (53))_ - Microsoft SQL Server

I get a new number every time the division changes. Immediately I think of window functions here. So I decided to do some checking here. Since I’m looking for a change, I went with a LAG function.

If the LAG isn’t equal to the current value, I’ve had a change. Therefore, a Fizz.

2018-07-02 14_45_44-SQLQuery4.sql - (local)_SQL2016.sandbox (vstsbuild (53))_ - Microsoft SQL Server

Let’s clean this up to show Fizz and add the Buzz with a 5.

2018-07-02 14_47_27-SQLQuery4.sql - (local)_SQL2016.sandbox (vstsbuild (53))_ - Microsoft SQL Server

I’m getting there, but what about FizzBuzz? Well, the CASE will execute in order, so let’s add that one at the top.

2018-07-02 14_49_00-SQLQuery4.sql - (local)_SQL2016.sandbox (vstsbuild (53))_ - Microsoft SQL Server

I’ve mostly solved this, so let’s put this in my query. I’ll substitute the CASE in for each item of the cross join. I get this:

WITH myTally (n)
AS
-- SQL Prompt formatting off
(SELECT n = ROW_NUMBER() OVER (ORDER BY (SELECT null))
  FROM (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) a(n)
   CROSS JOIN (VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)) b(n)
),
cteCoordinates (x, y, z)
AS
( SELECT
CASE
     WHEN ( a.n/3 != LAG(a.n/3, 1, 0) OVER (ORDER BY a.n)
       AND  a.n/5 != LAG(a.n/5, 1, 0) OVER (ORDER BY a.n)
         )THEN 'FizzBuzz'
     WHEN a.n/3 != LAG(a.n/3, 1, 0) OVER (ORDER BY a.n) THEN 'Fizz'
     WHEN a.n/5 != LAG(a.n/5, 1, 0) OVER (ORDER BY a.n) THEN 'Buzz'
     ELSE CAST(a.n AS VARCHAR(8)) END,
case WHEN ( b.n/3 != LAG(b.n/3, 1, 0) OVER (ORDER BY b.n)
       AND   b.n/5 != LAG(b.n/5, 1, 0) OVER (ORDER BY b.n)
         )THEN 'FizzBuzz'
     WHEN b.n/3 != LAG(b.n/3, 1, 0) OVER (ORDER BY b.n) THEN 'Fizz'
     WHEN b.n/5 != LAG(b.n/5, 1, 0) OVER (ORDER BY b.n) THEN 'Buzz'
     ELSE CAST(b.n AS VARCHAR(8)) END,
case WHEN ( c.n/3 != LAG(c.n/3, 1, 0) OVER (ORDER BY c.n)
       AND  c.n/5 != LAG(c.n/5, 1, 0) OVER (ORDER BY c.n)
         )THEN 'FizzBuzz'
     WHEN c.n/3 != LAG(c.n/3, 1, 0) OVER (ORDER BY c.n) THEN 'Fizz'
     WHEN c.n/5 != LAG(c.n/5, 1, 0) OVER (ORDER BY c.n) THEN 'Buzz'
     ELSE CAST(c.n AS VARCHAR(8)) END
    FROM mytally a
    CROSS JOIN mytally b
    CROSS JOIN mytally c
)
SELECT *
  FROM cteCoordinates
  ORDER BY cteCoordinates.x, cteCoordinates.y, cteCoordinates.z

That doesn’t seem to work. Even forgetting the ordering, I have a mess.

2018-07-02 14_58_53-SQLQuery4.sql - (local)_SQL2016.sandbox (vstsbuild (53))_ - Microsoft SQL Server

At this point I took a break. Clearly I’m overlooking something in my five minutes of work.

Debugging

Let’s move the items around and get some ideas here. I’ll get the actual numbers and then the FizzBuzz results. When I print the coordinate values along with the decodes, I see this.

2018-07-02 15_04_06-SQLQuery4.sql - (local)_SQL2016.sandbox (vstsbuild (53))_ - Microsoft SQL Server

What’s my error? I’m not thinking of LAG() correctly. This is by row, and the lagging for the x and y coordinates (the first two columns), aren’t changing at the same rate.

Aha.

Let’s change this. I’ll setup a simpler CTE first, one that takes the values from 1-100 and returns the value as well as the FizzBuzz calculation. This gives me this code:

WITH myTally (n)
AS
(
SELECT n = ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM
-- SQL Prompt formatting off
(    VALUES (1) ,(2) ,(3) ,(4) ,(5) ,(6) ,(7) ,(8) ,(9) ,(10)) AS a (n)
     CROSS JOIN    ( VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10) ) AS b (n)
     CROSS JOIN    ( VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10) ) AS c (n)
-- SQL Prompt formatting on
) ,
      cteFizzBuzz (x, n)
AS
(
SELECT CASE
            WHEN (n / 3 != LAG(n / 3, 1, 0) OVER (ORDER BY n)) AND (n / 5 != LAG(n / 5, 1, 0) OVER (ORDER BY n))
               THEN 'FizzBuzz'
            WHEN n / 3 != LAG(n / 3, 1, 0) OVER (ORDER BY n) THEN
                'Fizz'
            WHEN n / 5 != LAG(n / 5, 1, 0) OVER (ORDER BY n) THEN
                'Buzz'
            ELSE
                CAST(n AS VARCHAR(8))
        END, n
FROM myTally
) ,    cteCoordinates (x, y, z)

Now that I have this, let’s build the coordinates now. I’ll use the first set of code above as an example, and cross join the cteFizzBuzz with itself. I’ll make this the third CTE.

) ,    cteFinal (x, y, z, a, b, c)
AS
(
SELECT a.n, b.n, c.n, a.x, b.x, c.x
FROM           cteFizzBuzz AS a
     CROSS JOIN cteFizzBuzz AS b
     CROSS JOIN cteFizzBuzz AS c
)

Note that I’m returning the original values (for sorting) and the calculated FizzBuzz values, which are characters. If I didn’t care about this, I could ignore the first few columns.

In my outer query, I display the words, but order by the numbers.

SELECT 
    c.a, c.b, c.c
  FROM cteFinal c
  ORDER BY c.x, c.y, c.z

This gives me the answer (scrolled down to show a few cases).

2018-07-02 15_12_18-SQLQuery5.sql - (local)_SQL2016.sandbox (vstsbuild (54))_ - Microsoft SQL Server

On my machine, this takes about 4s to run. Not bad, and probably not optimal. The query plan is a mess, but this is for fun in a quick run, so let’s leave this  for now.

2018-07-02 15_14_08-SQLQuery5.sql - (local)_SQL2016.sandbox (vstsbuild (54))_ - Microsoft SQL Server

There are likely better solutions. I’m not an optimization guy out of the box. I get things done first, then I’ll go back and evaluate some time to tune things. In this case, adding in 3 more values (to 300) takes 1:58s. Going to 500 rows caused an SSMS out of memory error.

If I send the results to a temp table, things are better:

  • 100x100x100 (1,000,000 rows) – 00:01
  • 300x300x300 (27,000,000 rows) – 00:06
  • 500 x 500 x 500 (125,000,000 rows)  – 00:29
  • 1000x1000x1000 (1,000,000,000 rows) – 6:48

Note, don’t send results to the client if you don’t need to.

The Voice of the DBA

Steve Jones is the editor of SQLServerCentral.com and visits a wide variety of data related topics in his daily editorial. Steve has spent years working as a DBA and general purpose Windows administrator, primarily working with SQL Server since it was ported from Sybase in 1990. You can follow Steve on Twitter at twitter.com/way0utwest

Comments

Leave a comment on the original post [voiceofthedba.com, opens in a new window]

Loading comments...