NoCOUG SQL Challenge Entry

Once again the great Wizards of Northern California have reached out to the community, pleading for help in the deciphering of one more challenging riddle. The second edition of the NoCOUG SQL Challenge has been published and is open for submissions! This time Iggy and his ensemble came up not only with a SQL challenge but also with a brain-bender riddle that must be resolved before you can start coding your solution. Very nice!

I’ve taken my stab at the problem and described my solution below. If you want to make a fresh attempt at the problem, stop here, otherwise scroll down for my solution.

              **************
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
              *            *
    ***********            ***********
     *                              *
      *                            *
       *                          *
        *                        *
         *                      *
          *                    *
           *                  *
            *                *
             *              *
              *            *
               *          *
                *        *
                 *      *
                  *    *
                   *  *
                    **

The riddle

The first hurdle to overcome was the riddle. At a first look, it seemed just a bunch of random words, organized as a random pattern. I started playing with it and shuffling words and rows, trying to find a logical order for them and solve that jigsaw.

Eventually, an eureka moment: a tree!!! More specifically, a binary tree. The words have been organized in a binary tree, their location in the tree indicating their position in the sentence that was to be discovered. A depth-first traversal of the tree should yield the answer for the riddle and the challenge.

The query

I started by using some elbow grease and writing a query based on many self joins of the riddle table to obtain the complete traversal of the tree. Soon it was obvious that this approach was going to require a lot more typing than I was willing to do. The alternative answer was quick: “recursion”, which reminded me of last year’s challenge. As well as in that occasion, I thought of using “Subquery Factoring” (or CTE, Common Table Expressions) to traverse the tree, but this time with recursiveness, available from 11gR2.

A few bugs and ORA-600’s later, and a few query modifications to work around those isses, the first version of the query was ready:

with
mystery (root, fragment) as (
  select word2, word1 || ' ' || word2 || ' ' || word3
  from riddle
  where word1 is null and word3 is null
  --
  union all
  --
  select
    r.word2,
    m1.fragment || ' ' || r.word2 || ' ' || m2.fragment
  from riddle r
    join mystery m1 on m1.root = r.word1
    join mystery m2 on m2.root = r.word3
)
select * from mystery

This query worked reasonably well, but had a few problems:

• The length of the FRAGMENT column was determined by the concatenation done in the anchor member of the CTE (32+1+32+1+32=98 characters). The recursive concatenation eventually go beyond that limit, causing the query to abort with an error.
• The query above works very well for a balanced tree. For an imbalanced tree, though, two problems arise:
• • Some parent nodes have only one child node instead of two. Since the query above has two INNER JOINS in the recursive part, that query culls some of the branches off. My first thought to solve that was to use OUTER JOINS instead. CTE’s, however, have a restriction that prevents the use of OUTER JOINS with the CTE on the right hand side.
  • Nodes in different levels of the three are processed at the same iterations of the CTE. This causes disjoint branches to appear and never come together for a final and complete solution.

To work around these problems I had to “pretzel-ize” the query a little bit more and it became the below:

with
mystery (root, fragment) as (
  select word2, cast(word1 || ' ' || word2 || ' ' || word3 as varchar2(300))
  from riddle
  where word1 is null and word3 is null
  --
  union all
  --
  select
    r.word2,
    case when r.word1 is null then '' else m1.fragment end || ' ' || r.word2 || ' ' || case when r.word3 is null then '' else m2.fragment end
  from riddle r
    join mystery m1 on m1.root = r.word1 or r.word1 is null
    join mystery m2 on m2.root = r.word3 or r.word3 is null
  where not (r.word1 is null and r.word3 is null)
)
,
mystery2(root, fragment) as (
  select root, fragment
  from mystery
  --
  union all
  --
  select
    r.word2,
    m1.fragment || ' ' || r.word2 || ' ' || m2.fragment
  from riddle r
    join mystery2 m1 on m1.root = r.word1
    join mystery2 m2 on m2.root = r.word3
)
select distinct fragment
from mystery2
where length(fragment) = (select max(length(fragment)) value from mystery2)
order by length(fragment) desc

The changes in the query were:

• Added a CAST in the anchor member to increase the size of the string column and avoid the error due to the result being too long.
• Added additional predicates to the recursive join to avoid ignoring nodes that have one NULL child. That required a new WHERE clause to avoid cycles.
• Repeated exactly the same processing, through the MYSTERY2 view, to connect together the disjoint branches created by the first set of iterations (MYSTERY view). This was enough for this three and yielded the complete result. For bigger or more imbalanced trees, though, I suspect that more iterations could be necessary.
• Finally, I added some cosmetical manipulation to show only one row with the desired result.

And the result is…

FRAGMENT
--------------------------------------------------------------------------
TRYING TO TYPE ONE HUNDRED DISTINCT WORDS IN A SINGLE PARAGRAPH IS REALLY
TOUGH IF I CANNOT REPEAT ANY OF THEM THEN PROBABLY THOSE WITH MANY LETTERS
SHOULD BE USED MAYBE SOME READERS WILL UTILIZE DICTIONARIES THESAURUSES
THESAURI OR POSSIBLY EVEN ENCYCLOPEDIAS BUT MY PREFERENCE HAS ALWAYS BEEN
THAT GRAY MATTER BETWEEN YOUR EARS SERIOUSLY MARILYN CHALLENGES SUCH AS
THIS REQUIRE SKILLS BEYOND MATH SCIENCE AND PHYSICS SO WHAT DO YOU ASK
READING COMPREHENSION WRITING ABILITY GOOD OLD FASHIONED ELBOW GREASE
SCIENTISTS DONT CARE ABOUT STRUCTURE THEY WANT RESULTS HEY LOOK ONLY
ELEVEN MORE LEFT FIVE FOUR THREE TWO DONE