OraQA

The following is an interesting puzzle posted by Usenet rec-puzzles.org archive:

Assuming you have enough coins of 1, 5, 10, 25 and 50 cents, how many ways are there to make change for a dollar?

———————-SQL Solution————————

COLUMN combinations FORMAT A50
COLUMN Sum FORMAT A15

SELECT ltrim(max(str),',') combinations,
       rtrim(ltrim(replace(max(str_num),',','+'),'+'),'+') Sum,
       count(*) over () as counter
FROM
(SELECT sys_connect_by_path(str,', ') str, rownum rn,
        translate(sys_connect_by_path(str_num,','),
                  chr(0)||'ABCDE',chr(0))||',' AS str_num
FROM
(SELECT str_num, str, 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||' Penny' AS str
   FROM dual CONNECT BY LEVEL <=100
 UNION ALL
 SELECT LEVEL*5||'B' str_num,  LEVEL||' Nickel'
   FROM dual CONNECT BY LEVEL*5 <=100
 UNION ALL
 SELECT LEVEL*10||'C' str_num, LEVEL||' Dime'
   FROM dual CONNECT BY LEVEL*10 <=100
 UNION ALL
 SELECT LEVEL*25||'D' str_num, LEVEL||' Quarter'
   FROM dual CONNECT BY LEVEL*25 <=100
 UNION ALL
 SELECT LEVEL*50||'E' str_num, LEVEL||' Half D$'
   FROM dual CONNECT BY LEVEL*50<=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
)
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 ;

COMBINATIONS                                       SUM        COUNTER
----------------------------------------------- ------------ -------
 5 Penny, 1 Nickel, 4 Dime, 2 Quarter            5+5+40+50      292
 5 Penny, 1 Nickel, 4 Dime, 1 Half D$             5+5+40+50      292
 5 Penny, 1 Nickel, 9 Dime                               5+5+90             292
 5 Penny, 2 Nickel, 1 Dime, 1 Quarter, 1 Half D$ 5+10+10+25+50  292
...................
...................
...................
...................
 100 Penny                                                         100                     292
 1 Nickel, 2 Dime, 1 Quarter, 1 Half D$          5+20+25+50     292
 1 Nickel, 2 Dime, 3 Quarter                            5+20+75            292
....................
....................
....................
...................
 5 Dime, 2 Quarter                                             50+50               292
 5 Dime, 1 Half D$                                              50+50               292
 10 Dime                                                               100                   292
 2 Quarter, 1 Half D$                                         50+50               292
 4 Quarter                                                            100                   292
 2 Half D$                                                             100                   292  

292 rows selected.

Filed under SQL. Follow any responses to this entry through this RSS 2.0 feed.