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