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