OraQA

Oracle Question and Answer

  • Do you have a solution to a problem? Do you have an unanswered question? Login and share it with the Oracle community. More...

Oracle News


Entries RSS feed

Comments RSS feed

How to solve the No Average Spanned Puzzle in SQL

January 19th, 2008 By Frank Zhou

The following is an interesting puzzle posted by Jsoftware:

Arrange a list of distinct positive integers so that no two numbers have their average between them in the sequence.

COLUMN input  FORMAT A10
COLUMN reason FORMAT A60
variable input_data varchar2(20)
exec :input_data  := '1,2,3,4';

———Check if two number have their average between them in the sequence———

SELECT :input_data input,
PRIOR n||' is placed between '||CONNECT_BY_ROOT n||' and '||n as reason
FROM
(SELECT doc.extract('/l/text()').getNumberVal() n, ROWNUM rn
 FROM
 TABLE(xmlSequence(extract(XMLType('<doc><l>'||
      replace(:input_data,',','</l><l>')||'</l></doc>'),'/doc/l'))) doc
)
WHERE LEVEL = 3
CONNECT BY PRIOR rn <rn
AND CASE WHEN LEVEL = 3
                    THEN CASE WHEN PRIOR n * 2 = n + CONNECT_BY_ROOT n
                                           THEN 1
                                 END
                   ELSE 1 END = 1
AND LEVEL <=3;

INPUT      REASON
---------- -----------------------------
1,2,3,4    2 is placed between 1 and 3
1,2,3,4    3 is placed between 2 and 4

——————————————10G SQL Solution————————————————

SELECT trim(BOTH ',' FROM str) AS No_Avg_Spanned_str
FROM
( WITH input AS
 (SELECT doc.extract('/l/text()').getNumberVal() n, count(*) over () cnt
  FROM
  TABLE(xmlSequence(extract(XMLType('<doc><l>'||
  replace(:input_data,',','</l><l>')||'</l></doc>'),'/doc/l'))) doc
 ),
  data AS
 (SELECT sys_connect_by_path(n,',')||',' str
  FROM (SELECT n, cnt FROM input)
  WHERE LEVEL = cnt
  CONNECT BY NOCYCLE n != PRIOR n
  AND CASE WHEN LEVEL BETWEEN 3 AND cnt
                      THEN CASE WHEN PRIOR n * 2 != n + CONNECT_BY_ROOT n
                                             THEN 1 END
                      ELSE 1 END =1
  )
SELECT str FROM data
WHERE str NOT IN
(SELECT str
 FROM
 (SELECT str FROM data) a,
 (SELECT CONNECT_BY_ROOT n as head, PRIOR n as pre_num, n as num
   FROM (SELECT n FROM input)
   WHERE LEVEL = 3
   CONNECT BY NOCYCLE PRIOR n != n
   AND CASE WHEN LEVEL = 3
                       THEN CASE WHEN PRIOR n * 2 = n + CONNECT_BY_ROOT n
                                              THEN 1
                                    END
                        ELSE 1 END = 1
   AND LEVEL <=3
  ) b
 WHERE instr (str,','||pre_num||',') > instr(str, ','||b.head||',')
 AND   instr (str,','||num||',') > instr(str, ','||pre_num||',')
 )
);

NO_AVG_SPANNED_STR
--------------------
1,3,2,4
1,3,4,2
2,1,4,3
2,4,1,3
2,4,3,1
3,1,2,4
3,1,4,2
3,4,1,2
4,2,1,3
4,2,3,1

10 rows selected.

One Response to “How to solve the No Average Spanned Puzzle in SQL”

  1. newkid Says:

    Hi Frank, I finally understood your solution and rewrote it in 11GR2:

    WITH input AS
        (SELECT doc.extract('/l/text()').getNumberVal() n, count(*) over () cnt
         FROM
         TABLE(xmlSequence(extract(XMLType('<doc><l>'||
         replace(:input_data,',','</l><l>')||'</l></doc>'),'/doc/l'))) doc
        )
    ,t2(n1,n2,n3,lvl) AS (
        SELECT n,0,0,1 FROM input
        UNION ALL
        SELECT t2.n1
              ,DECODE(lvl,1,input.n,t2.n2)
              ,DECODE(lvl,2,input.n,t2.n3)
              ,lvl+1
          FROM t2,input
         WHERE lvl<3 AND input.n NOT IN (n1,n2)
        )
    ,b AS (SELECT n1,n2,n3 from t2 WHERE lvl=3 AND n2*2=n1+n3)
    ,t(n,str,cnt,lvl,root) AS
        (SELECT n,','||n||',',cnt,1,n
           FROM input
         UNION ALL
         SELECT input.n,t.str||input.n||',',input.cnt,lvl+1,t.root
           FROM t,input
          WHERE lvl<input.cnt
                AND INSTR(str,','||input.n||',')=0 --- nocycle
                AND (lvl<2 OR lvl>=2 AND t.n*2 != input.n + root)
                AND NOT EXISTS
                    (SELECT 1
                      FROM b
                     WHERE instr(t.str||input.n||',', ','||b.n2||',') > instr(t.str||input.n||',', ','||b.n1||',')
                       AND instr(t.str||input.n||',', ','||b.n3||',') > instr(t.str||input.n||',', ','||n2||',')
                       AND instr(t.str||input.n||',', ','||b.n1||',') > 0
                    )
        )
    SELECT trim(BOTH ',' FROM str) AS No_Avg_Spanned_str
      FROM t
     WHERE lvl=cnt;
    
    NO_AVG_SPANNED_STR
    -----------------------------
    4,2,3,1
    1,3,4,2
    1,3,2,4
    3,1,4,2
    3,1,2,4
    3,4,1,2
    2,1,4,3
    2,4,1,3
    2,4,3,1
    4,2,1,3
    
    10 rows selected.
    

Leave a Reply

You must be logged in to post a comment.

RSS feed for comments on this question