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