OraQA

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

———————-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.

Filed under SQL. Follow any responses to this entry through this RSS 2.0 feed.