How to solve the 1000 $1 Bills in 10 Envelopes Puzzle in SQL
October 12th, 2008 By Frank Zhou
The following is an interesting problem posted by mathforum.org:
You are given 1000 one dollar bills and 10 envelopes. Put the bills
into the envelopes in such a way that someone can ask you for any
amount of money from $1 to $1000 (examples $532, $619, $88, etc.)
and you can give it to them through a combination of the envelopes.
The following SQL pattern can be used to solve this puzzle, it also proves
that the result is correct.
————————————————–10G SQL Solution————————————————
SELECT ROW_NUMBER () OVER (ORDER BY num) envelope_num,
num dollars,
MIN from_min,
MAX to_max,
cnt combo_cnt
FROM (WITH DATA AS
(SELECT num
FROM (SELECT CASE
WHEN SUM (num) OVER (ORDER BY num) > 1000
THEN num
- ( SUM (num) OVER (ORDER BY num)
- 1000
)
ELSE num
END AS num
FROM (SELECT POWER (2, LEVEL - 1) AS num
FROM DUAL
CONNECT BY POWER (2, LEVEL - 1) <= 1000))),
data_check AS
(SELECT MAX (num) MAX,
MIN (num) MIN,
COUNT (*) cnt
FROM (SELECT DISTINCT SUM
(TO_NUMBER (REGEXP_SUBSTR (str,
'[^,]+',
1,
LEVEL
)
)
) num
FROM (SELECT SYS_CONNECT_BY_PATH (num,
','
) str
FROM (SELECT num
FROM DATA)
CONNECT BY PRIOR num < num)
CONNECT BY PRIOR str = str
AND REGEXP_SUBSTR (str, '[^,]+', 1, LEVEL) IS NOT NULL
AND PRIOR DBMS_RANDOM.STRING ('p', 20) IS NOT NULL
GROUP BY str))
SELECT MAX,
MIN,
cnt,
num
FROM data_check FULL OUTER JOIN DATA ON (data_check.MIN = DATA.num
)
)
ORDER BY num NULLS FIRST;
SQL> /
ENVELOPE_NUM DOLLARS FROM_MIN TO_MAX COMBO_CNT
------------ ---------- ---------- ---------- ----------
1 1 1 1000 1000
2 2
3 4
4 8
5 16
6 32
7 64
8 128
9 256
10 489
10 rows selected.
Elapsed: 00:00:00.43
June 24th, 2010 at 12:39 pm
Your solution is brilliant. Here’s an easy way to verify it:
WITH DATA AS (SELECT num,MAX(num) OVER() m FROM (SELECT CASE WHEN SUM (num) OVER (ORDER BY num) > 1000 THEN num - ( SUM (num) OVER (ORDER BY num) - 1000 ) ELSE num END AS num FROM (SELECT POWER (2, LEVEL - 1) AS num FROM DUAL CONNECT BY POWER (2, LEVEL - 1) <= 1000 ) ) ) ,TO_CHECK AS (SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM <=1000) SELECT n FROM ( SELECT n,num FROM TO_CHECK, DATA WHERE (CASE WHEN n>m THEN n-m ELSE n END)>num-1 AND BITAND((CASE WHEN n>m THEN n-m ELSE n END),num)>0 AND num < m OR (n>m AND num=m) ) GROUP BY n HAVING SUM(num) != n Or: WITH DATA AS (SELECT num,MAX(num) OVER() m FROM (SELECT CASE WHEN SUM (num) OVER (ORDER BY num) > 1000 THEN num - ( SUM (num) OVER (ORDER BY num) - 1000 ) ELSE num END AS num FROM (SELECT POWER (2, LEVEL - 1) AS num FROM DUAL CONNECT BY POWER (2, LEVEL - 1) < = 1000 ) ) ) ,TO_CHECK AS (SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM <=1000) SELECT num FROM DATA WHERE NOT EXISTS ( SELECT n FROM ( SELECT n,num FROM TO_CHECK, DATA WHERE (CASE WHEN n>m THEN n-m ELSE n END)>num-1 AND BITAND((CASE WHEN n>m THEN n-m ELSE n END),num)>0 AND num < m OR (n>m AND num=m) ) GROUP BY n HAVING SUM(num) != n ) ;