Recursive Subqueries for FizzBuzz

So in yesterday’s post I mentioned that I wasn’t happy with my solution. Among several reasons were the limit on the first 100 numbers, and the lack of using what I think to be a more elegant solution with recursive sub-queries.

Also, I received a comment about problems with the MarkDown plugin — which was also affecting my code posting, so I disabled MarkDown and can now handle code posting much, much better.

I couldn’t let it rest, so I dug into the recursive sub-queries with a vengeance and wrote up something more elegant.

with
fb0 (input) as (
select      'buzz,fizz,fizzbuzz,fizz,buzz,fizz,fizz' input
from        dual
),
fb2 (n,pos,n_start,n_str) as 
(
select      /* Anchor query of root nodes for recursion */
            fb1.column_value n, 
            1 pos,
            fb1.column_value n_start,
            to_char(fb1.column_value) n_str
from        fb0,
            table(sys.odcinumberlist(3,5,6,9,10,12,15)) fb1
where       /* Limit root nodes to ones that match the first word of input */
            case regexp_substr(fb0.input,'\w+')
              when 'fizz' then mod(fb1.column_value,3)
              when 'buzz' then mod(fb1.column_value,5)
              when 'fizzbuzz' them mod(fb1.column_value,15)
            end = 0
union all
select      /* Build "child" nodes by walking fizzbuzz matching to input string */
            case 
              when mod(fb2.n,15) in (5,9) then n+1
              when mod(fb2.n,15) in (3,10) then n+2
              when mod(fb2.n,15) in (0,6,12) then n+3
            end,
            fb2.pos + 1,
            fb2.n_start,
            fb2.n_str || ',' ||
            case 
              when mod(fb2.n,15) in (5,9) then n+1
              when mod(fb2.n,15) in (3,10) then n+2
              when mod(fb2.n,15) in (0,6,12) then n+3
            end
from        fb2,
            fb0
where       case 
              when mod(fb2.n,15) in (0,5,6,10) then 'fizz'
              when mod(fb2.n,15) in (3,9) then 'buzz'
              when mod(fb2.n,15) in (12) then 'fizzbuzz'
            end =
            regexp_substr(fb0.input,'\w+',1,fb2.pos + 1)
),
fb3 (input, n_str, n_length, n_start, min_length, min_start) as 
(
select      /* Measure lengths of resulting matches, discard ones that are not long enough */
            fb0.input,
            fb2.n_str,
            fb2.n - fb2.n_start n_length,
            fb2.n_start,
            min(fb2.n - fb2.n_start) over () min_length,
            min(fb2.n_start) over (partition by fb2.n - fb2.n_start) min_start
from        fb2,
            fb0
where       fb2.pos = nvl(length(regexp_replace(fb0.input,'\w')),0)+1
),
fb4 (input, n_str) as 
(
select      /* Retain the matches which are shortest and start at the smallest value */
            fb3.input,
            fb3.n_str
from        fb3
where       fb3.n_length = fb3.min_length
and         fb3.n_start = fb3.min_start
)
select      /* Display output */
            input,
            n_str
from        fb4;

7 Responses to “Recursive Subqueries for FizzBuzz”

  1. Todd Barry Says:

    I guess I’m destined to not ever run this. There’s a “them” instead of a “then” in your first CASE, but even after correcting that I end up with an ORA-00600 on 11.2.0.3.

    ORA-00600: internal error code, arguments: [qctchr : bfl], [365], [40], [1], [873], [3], [2], [], [], [], [], []

  2. ddelmoli Says:

    Interesting — after correcting the “them” I ran it on both 11.2.0.1 on Windows and 11.2.0.3 on an Exadata x2-2 quarter rack without any issues…

    What platform are you trying it on?

  3. Todd Barry Says:

    AIX 6.1. Same result on at least six 11.2.0.3 instances – some with the latest PSU, some without it.

  4. ddelmoli Says:

    Hmm… Wonder if it’s related to a NLS_LENGTH_SEMANTICS bug. Can you tell me if you’re set to CHAR or BYTES?

  5. ddelmoli Says:

    Ok, just tried it on Amazon RDS, Oracle SE One, 11.2.0.2 v3 engine, no issues. So far it’s run successfully on 11.2.0.1 / Windows 2008, 11.2.0.2 / Amazon RDS, and 11.2.0.3 Exadata… It’s got to be something specific to the way your instances are configured somehow. Now I’m curious.

  6. Todd Barry Says:

    Yep, it’s the NLS_LENGTH_SEMANTICS bug. We are running AL32UTF8 with CHAR. The query runs if the session is altered to use BYTE.

    I saw this bug on MOS yesterday when looking up “qctchr : bfl” but it said the NLS bug was fixed in 11.2 so I didn’t actually test changing the NLS value. Apparently there is still a problem there.

  7. Barun Says:

    I haven’t touched C in quite a few years, but here is what I came up with. This seg fatlus at line 24, so don’t quote me on it. But the algorithm should hold true. #include#include #include Node.h #ifndef max #define max( a, b ) ( ((a) > (b)) ? (a) : (b) )#endif#ifndef min #define min( a, b ) ( ((a) right, &rightmin, &rightmax); minmax_depth(root->left, &leftmin, &leftmax); *min = 1 + min(leftmin, rightmin); *max = 1 + max(leftmax, rightmax); return;}bool is_balanced( Node *root) { int min, max; min = max = 0; minmax_depth(root, &min, &max); return (max min) > 0;}void main() { printf( Initializing ); Node *head, *tmp = NULL; int i; printf( Initializing ); for (i = 0; i right = head; head = tmp; } if(is_balanced(head)) { printf( Shouldn’t be balanced but is ); }}

Leave a Reply

Posting code can be a pain. To make sure your code doesn't get eaten, you may want to pre-format it first by using HTML Encoder