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.

About way0utwest

Editor, SQLServerCentral
This entry was posted in Blog and tagged , , . Bookmark the permalink.

2 Responses to Solving Ken’s FizzBuzz 3D–#SQLNewBlogger

  1. FYI Your LAG solution was exactly why I said no Modulo :). I’ve seen maybe half a dozen solutions and no two were the same. I was curious to see what different ways people would use. For example

    n/3.0 = floor(n/3.0)
    (val/3)*3 = val
    Left(Reverse(Cast(upToAThousand.counter AS VARCHAR(4))), 1) IN (‘5’ , ‘0’)
    IIF(x – ((x / 3) * 3) = 0
    parsename(x.num/3.0,1)=0

    Then there are all the different ways to do the tally part of the table etc. Needless to say, it was an interesting exercise.

  2. way0utwest says:

    it’s interesting how many different ways people look to solve things. I slightly considered /3*3, but none of the others. someone (you) should compare performance of all the solutions.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.