How to solve the Stamp Combo Puzzle in SQL
March 27th, 2008 By Frank Zhou
The following is an interesting puzzle posted by Usenet rec-puzzles.org archive:
“Dad wants one-cent, two-cent, three-cent, five-cent, and ten-cent stamps.
He said to get four each of two sorts and three each of the others,
but I’ve forgotten which. He gave me exactly enough to buy them; just these dimes.”
How many stamps of each type does Dad want? A dime is worth ten cents.
------------------------------10G SQL Solution-----------------------------
SELECT max(fin_str) Stamp_combo
FROM
(SELECT ltrim(fin_str, ',') fin_str, rn, str_num
FROM
(SELECT sys_connect_by_path(str,', ') fin_str, rownum rn,
regexp_replace(sys_connect_by_path(str_num,','),'[[:alpha:]]') AS str_num
FROM
(SELECT str_num, str, substr(str_num,length(str_num)) stamp_type
FROM
(SELECT LEVEL||'A' str_num, LEVEL||' one_cent_stamp' AS str
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*2||'B' str_num, LEVEL||' two_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*3||'C' str_num, LEVEL||' three_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*5||'D' str_num, LEVEL||' five_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*10||'E' str_num, LEVEL||' ten_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
)
)
WHERE LEVEL = 5
CONNECT BY PRIOR stamp_type < stamp_type
)
WHERE length(regexp_replace(fin_str,'[^3]')) = 3
AND length(regexp_replace(fin_str,'[^4]')) = 2
)
CONNECT BY PRIOR rn = rn
AND regexp_substr(str_num,'[^,]+',1,LEVEL) IS NOT NULL
AND PRIOR dbms_random.string('p',20) IS NOT NULL
GROUP BY rn
HAVING SUM(TO_NUMBER(regexp_substr(str_num,'[^,]+',1,LEVEL))) IN
(SELECT LEVEL FROM dual
WHERE mod(LEVEL,10) = 0
AND LEVEL >= (SELECT (1+2)*4 + (3+5+10)*3 FROM dual)
CONNECT BY LEVEL <=(SELECT (1+2+3) * 3 + (5+10) * 4 FROM dual)
);
STAMP_COMBO
------------------------------------------------------------------------------
3 one_cent_stamp, 4 two_cent_stamp, 3 three_cent_stamp, 4 five_cent_stamp, 3 ten_cent_stamp
—————————————————11G SQL Solution———————————————————-
SELECT fin_str AS Stamp_combo
FROM
(SELECT ltrim(fin_str, ',') as fin_str, str_num
FROM
(SELECT sys_connect_by_path(str,', ') fin_str,
regexp_replace(sys_connect_by_path(str_num,'+'),'[[:alpha:]]') AS str_num
FROM
(SELECT str_num, str, substr(str_num,length(str_num)) stamp_type
FROM
(SELECT LEVEL||'A' str_num, LEVEL||' one_cent_stamp' AS str
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*2||'B' str_num, LEVEL||' two_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*3||'C' str_num, LEVEL||' three_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*5||'D' str_num, LEVEL||' five_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
UNION ALL
SELECT LEVEL*10||'E' str_num, LEVEL||' ten_cent_stamp'
FROM dual WHERE LEVEL BETWEEN 3 AND 4 CONNECT BY LEVEL <=4
)
)
WHERE LEVEL = 5
CONNECT BY PRIOR stamp_type < stamp_type
)
WHERE regexp_count(fin_str,'3') = 3
AND regexp_count(fin_str,'4') = 2
)
WHERE XMLQuery(str_num RETURNING CONTENT).getnumberval()
IN
(SELECT LEVEL FROM dual
WHERE mod(LEVEL,10) = 0
AND LEVEL >= XMLQuery('(1+2)*4 + (3+5+10)*3' RETURNING CONTENT).getnumberval()
CONNECT BY LEVEL <= XMLQuery('(1+2+3) * 3 + (5+10) * 4' RETURNING CONTENT).getnumberval()
);
STAMP_COMBO
——————————————————————————————————————————————
3 one_cent_stamp, 4 two_cent_stamp, 3 three_cent_stamp, 4 five_cent_stamp, 3 ten_cent_stamp
June 25th, 2010 at 11:18 am
WITH stamps AS ( SELECT ROWNUM n ,(CASE WHEN ROWNUM IN (1,2) THEN 4 ELSE 3 END) AS m ,DECODE(ROWNUM,4,5,5,10,ROWNUM) val FROM DUAL CONNECT BY ROWNUM<=5 ) ,t1 AS ( SELECT id,n,TO_NUMBER(SUBSTR(t.m,stamps.n,1)) m FROM (SELECT ROWNUM id, m FROM (SELECT DISTINCT REPLACE(SYS_CONNECT_BY_PATH(m,','),',') m FROM stamps WHERE LEVEL=5 CONNECT BY NOCYCLE n<>PRIOR n AND LEVEL<=5 ) ) t ,stamps ) SELECT * FROM ( SELECT t1.id,t1.m,s.val,SUM(t1.m*s.val) OVER(PARTITION BY t1.id) total FROM t1,stamps s WHERE t1.n = s.n ) WHERE MOD(total,10)=0 ORDER BY id,val; ID M VAL TOTAL ---------- ---------- ---------- ---------- 3 3 1 70 3 4 2 70 3 3 3 70 3 4 5 70 3 3 10 70June 28th, 2010 at 5:57 am
Recursive WITH in 11GR2:
WITH t(lvl,val,left_4,left_3,result) AS ( SELECT 0,0,2,3,'' FROM DUAL UNION ALL SELECT t.lvl+1 ,t.val+s.price*cnt ,left_4 - DECODE(cnt,4,1,0) ,left_3 - DECODE(cnt,3,1,0) ,t.result||' '||s.price||'*'||cnt FROM t ,(SELECT ROWNUM price_id,DECODE(ROWNUM,4,5,5,10,ROWNUM) AS price FROM DUAL CONNECT BY ROWNUM<=5) s ,(SELECT 4 as cnt FROM DUAL UNION ALL SELECT 3 FROM DUAL) WHERE t.lvl+1=s.price_id AND (cnt=4 AND left_4>0 OR cnt=3 AND left_3>0) ) SELECT result||'='||val FROM t WHERE lvl=5 AND MOD(val,10)=0; RESULT||'='||VAL ---------------------------------- 1*3 2*4 3*3 5*4 10*3=70June 28th, 2010 at 11:53 am
WITH c AS (SELECT 3 cnt FROM DUAL UNION ALL SELECT 4 FROM DUAL) ,stamps AS (SELECT c1.cnt||c2.cnt||c3.cnt||c5.cnt||c10.cnt AS all_cnt ,c1.cnt+2*c2.cnt+3*c3.cnt+5*c5.cnt+10*c10.cnt AS val ,'1*'||c1.cnt||'+2*'||c2.cnt||'+3*'||c3.cnt||'+5*'||c5.cnt||'+10*'||c10.cnt AS result FROM c c1,c c2,c c3,c c5,c c10 ) SELECT result||'='||val from stamps WHERE MOD(val,10)=0 AND LENGTH(all_cnt)-LENGTH(REPLACE(all_cnt,'4'))=2 AND LENGTH(all_cnt)-LENGTH(REPLACE(all_cnt,'3'))=3 ; RESULT||'='||VAL ------------------------------------- 1*3+2*4+3*3+5*4+10*3=70