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.
June 29th, 2010 at 12:31 pm
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.