OraQA

Oracle Question and Answer

  • Do you have a solution to a problem? Do you have an unanswered question? Login and share it with the Oracle community. More...

Oracle News


Entries RSS feed

Comments RSS feed

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

3 Responses to “How to solve the Stamp Combo Puzzle in SQL”

  1. newkid Says:
    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         70
    
    
  2. newkid Says:

    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=70
    
  3. newkid Says:
    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
    

Leave a Reply

You must be logged in to post a comment.

RSS feed for comments on this question