How to solve the Impossible Combination Puzzle in SQL
February 5th, 2008 By Frank Zhou
The following is an interesting puzzle posted by Usenet rec-puzzles.org archive:
What is the smallest number of coins that you can’t make a dollar with? i.e., for what N does there not exist a set of N coins adding up to a dollar? It is possible to make a dollar with 1 current U.S. coin (a Susan B. Anthony),
2 coins (2 fifty cent pieces), 3 coins (2 quarters and a fifty cent piece), etc. It is not possible to make exactly a dollar with 101 coins.
———————————————-10G SQL Solution——————————————————
SELECT MIN (num) Min_Impossible_Combinations
FROM
(SELECT LEVEL num FROM DUAL CONNECT BY LEVEL <=101
MINUS
SELECT
SUM(TO_NUMBER(SUBSTR(num,
INSTR(num,',', 1, LEVEL) + 1,
INSTR(num,',', 1, LEVEL+1) -
INSTR(num,',', 1, LEVEL) -1))) num
FROM
(SELECT sys_connect_by_path(num,',')||',' num, rownum rn,
regexp_replace(sys_connect_by_path(str_num,','),'[[:alpha:]]') ||',' AS str_num
FROM
(SELECT str_num, num, to_number(substr(str_num,0,length(str_num)-1)) n,
substr(str_num,length(str_num)) coin_type
FROM
(SELECT LEVEL||'A' str_num , LEVEL AS num
FROM dual CONNECT BY LEVEL <=100
UNION ALL
SELECT LEVEL*5||'B' str_num, LEVEL
FROM dual CONNECT BY LEVEL*5 <=100
UNION ALL
SELECT LEVEL*10||'C' str_num, LEVEL
FROM dual CONNECT BY LEVEL*10 <=100
UNION ALL
SELECT LEVEL*25||'D' str_num, LEVEL
FROM dual CONNECT BY LEVEL*25 <=100
UNION ALL
SELECT LEVEL*50||'E' str_num, LEVEL
FROM dual CONNECT BY LEVEL*50<=100
UNION ALL
SELECT LEVEL*100||'F' str_num, LEVEL
FROM dual CONNECT BY LEVEL*100<=100
)
)
WHERE
CASE LEVEL
WHEN 1 THEN CASE WHEN n = 100 THEN 1 END
WHEN 2 THEN CASE WHEN n + PRIOR n =100 THEN 1 END
WHEN 3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n =100 THEN 1 END
ELSE 1 END =1
CONNECT BY PRIOR coin_type < coin_type
AND
CASE LEVEL
WHEN 2 THEN CASE WHEN n + PRIOR n <=100 THEN 1 END
WHEN 3 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=100 THEN 1 END
WHEN 4 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <96 THEN 1 END
WHEN 5 THEN CASE WHEN CONNECT_BY_ROOT n + PRIOR n + n <=85 THEN 1 END
ELSE 1 END =1
AND LEVEL <6
)
CONNECT BY PRIOR rn = rn
AND INSTR (str_num,',', 1,LEVEL+1) > 0
AND PRIOR dbms_random.string('p',10) IS NOT NULL
GROUP BY rn
HAVING SUM(TO_NUMBER(SUBSTR(str_num,
INSTR(str_num,',', 1, LEVEL) + 1,
INSTR(str_num,',', 1, LEVEL+1) -
INSTR(str_num,',', 1, LEVEL) -1))) = 100
);
MIN_IMPOSSIBLE_COMBINATIONS
---------------------------
77
Elapsed: 00:00:08.06
June 25th, 2010 at 6:50 am
11GR2:
WITH coins AS ( SELECT 1 cents FROM DUAL UNION ALL SELECT 5 cents FROM DUAL UNION ALL SELECT 10 cents FROM DUAL UNION ALL SELECT 25 cents FROM DUAL UNION ALL SELECT 50 cents FROM DUAL ) ,t(c1,c5,c10,c25,c50,cents,total_val) AS ( SELECT DECODE(c.cents,1,1,0) ,DECODE(c.cents,5,1,0) ,DECODE(c.cents,10,1,0) ,DECODE(c.cents,25,1,0) ,DECODE(c.cents,50,1,0) ,cents ,cents FROM coins c UNION ALL SELECT c1 + DECODE(c.cents,1,1,0) ,c5 + DECODE(c.cents,5,1,0) ,c10+ DECODE(c.cents,10,1,0) ,c25+ DECODE(c.cents,25,1,0) ,c50+ DECODE(c.cents,50,1,0) ,c.cents ,t.total_val + c.cents FROM t, coins c WHERE t.total_val + c.cents<=100 AND t.cents<=c.cents ) ,t2 AS ( SELECT DISTINCT c1+c5+c10+c25+c50 cnt FROM t WHERE total_val=100 ) SELECT MIN(rn) FROM (SELECT ROWNUM+1 rn FROM DUAL CONNECT BY ROWNUM<100 ) WHERE NOT EXISTS (SELECT 1 FROM t2 WHERE cnt=rn);