A few weeks ago I posted an article about solving a combinatorics puzzle using SQL. In comments that followed, Iudith Mentzel mentioned another interesting puzzle involving combinations: the Four Weights puzzle. At the time I thought it might be an interesting problem to tackle with SQL. Last night I was up monitoring systems during some maintenance work and thought I’d use the idle time to work up a solution.
Simply stated, the Four Weights puzzle goes something like this… Given a balance scale with four distinct weights. Using only those weights, balance any integer target from 1kg to 40kg. Weights may be placed on either side of the scale. The puzzle then is finding the values of those four weights.
For example if I have a 1kg weight and a 3kg weight I can balance targets from 1kg to 4kg. Putting my target weight on the left side of a scale I can balance it in the following ways…
- If my target weighs 1kg, put the 1kg weight on the right.
- If my target weighs 2kg, put the 1kg weight on the left with the target and the 3kg on the right.
- If my target weighs 3kg, put the 3kg weight on the right.
- If my target weighs 4kg, put both the 1kg and 3kg weight on the right
Tackling this with SQL I first envisioned a trivial puzzle with 40 weights of values 1kg-40kg. The solution here would be to balance any target by using just one weight. To assemble a 4-Weight solution, I would select combinations of four from that full set.
To weigh any given target, each weight in my combination would either be on the left, on the right, or not used. I represented these usages as factors of -1, 0, or 1. Where -1 means the weight is placed with the target on the left, 1 meaning the weight is on the right, and 0 meaning unused.
Building my SQL from these components I created views using the WITH clause for my full collection of weights, my factors, and then joining those to create a set of usages.
WITH
weights
AS
( SELECT LEVEL w
FROM DUAL
CONNECT BY LEVEL <= 40),
factors
AS
( SELECT -1 f FROM DUAL UNION ALL
SELECT 0 f FROM DUAL UNION ALL
SELECT 1 f FROM DUAL),
usage
AS
(SELECT w, w * f u
FROM weights CROSS JOIN factors)
To solve the puzzle I use a 4-way join of the various usages. Since the usage table has 3 values for each weight (left, right, unused) and I can only use a weight once for each target I join them with the condition that the second weight is heavier than the first, the third heavier than the second, and the fourth is heavier than the third. This guarantees my join will yield every combination of usages where each weight is only used once. Furthermore, I’m only interested in combinations that yield a weight between 1 and 40.
SELECT u1.w w1, u2.w w2, u3.w w3, u4.w w4,
u1.u u1, u2.u u2, u3.u u3, u4.u u4,
u1.u + u2.u + u3.u + u4.u total,
COUNT(DISTINCT u1.u + u2.u + u3.u + u4.u)
OVER(PARTITION BY u1.w, u2.w, u3.w, u4.w) cnt
FROM usage u1,
usage u2,
usage u3,
usage u4
WHERE u1.w < u2.w
AND u2.w < u3.w
AND u3.w < u4.w
AND u1.u + u2.u + u3.u + u4.u BETWEEN 1 AND 40
Adding a count of the distinct totals for each combination of the 4 weights (irrespective of the factored usages in each combination) lets me filter weight-sets to find only those that produce exactly 40 different combinations. That is, in a range of 1kg to 40kg targets, if I have 40 distinct totals then I must have a combination of usages for each target.
SELECT w1,w2,w3,w4,
u1,u2,u3,u4,
total
FROM (SELECT u1.w w1, u2.w w2, u3.w w3, u4.w w4,
u1.u u1, u2.u u2, u3.u u3, u4.u u4,
u1.u + u2.u + u3.u + u4.u total,
COUNT(DISTINCT u1.u + u2.u + u3.u + u4.u)
OVER(PARTITION BY u1.w,
u2.w,
u3.w,
u4.w) cnt
FROM usage u1,
usage u2,
usage u3,
usage u4
WHERE u1.w < u2.w AND u2.w < u3.w AND u3.w < u4.w
AND u1.u + u2.u + u3.u + u4.u BETWEEN 1 AND 40)
WHERE cnt = 40
ORDER BY total;
Now that I have all the pieces, I can put them all together…
WITH
weights
AS
( SELECT LEVEL w
FROM DUAL
CONNECT BY LEVEL <= 40),
factors
AS
( SELECT -1 f FROM DUAL UNION ALL
SELECT 0 f FROM DUAL UNION ALL
SELECT 1 f FROM DUAL),
usage
AS
(SELECT w, w * f u
FROM weights CROSS JOIN factors)
SELECT w1,w2,w3,w4,
u1,u2,u3,u4,
total
FROM (SELECT u1.w w1, u2.w w2, u3.w w3, u4.w w4,
u1.u u1, u2.u u2, u3.u u3, u4.u u4,
u1.u + u2.u + u3.u + u4.u total,
COUNT(DISTINCT u1.u + u2.u + u3.u + u4.u)
OVER(PARTITION BY u1.w,
u2.w,
u3.w,
u4.w) cnt
FROM usage u1,
usage u2,
usage u3,
usage u4
WHERE u1.w < u2.w AND u2.w < u3.w AND u3.w < u4.w
AND u1.u + u2.u + u3.u + u4.u BETWEEN 1 AND 40)
WHERE cnt = 40
ORDER BY total;
W1 W2 W3 W4 U1 U2 U3 U4 TOTAL
1 3 9 27 1 0 0 0 1
1 3 9 27 -1 3 0 0 2
1 3 9 27 0 3 0 0 3
1 3 9 27 1 3 0 0 4
1 3 9 27 -1 -3 9 0 5
1 3 9 27 0 -3 9 0 6
1 3 9 27 1 -3 9 0 7
1 3 9 27 -1 0 9 0 8
1 3 9 27 0 0 9 0 9
1 3 9 27 1 0 9 0 10
1 3 9 27 -1 3 9 0 11
1 3 9 27 0 3 9 0 12
1 3 9 27 1 3 9 0 13
1 3 9 27 -1 -3 -9 27 14
1 3 9 27 0 -3 -9 27 15
1 3 9 27 1 -3 -9 27 16
1 3 9 27 -1 0 -9 27 17
1 3 9 27 0 0 -9 27 18
1 3 9 27 1 0 -9 27 19
1 3 9 27 -1 3 -9 27 20
1 3 9 27 0 3 -9 27 21
1 3 9 27 1 3 -9 27 22
1 3 9 27 -1 -3 0 27 23
1 3 9 27 0 -3 0 27 24
1 3 9 27 1 -3 0 27 25
1 3 9 27 -1 0 0 27 26
1 3 9 27 0 0 0 27 27
1 3 9 27 1 0 0 27 28
1 3 9 27 -1 3 0 27 29
1 3 9 27 0 3 0 27 30
1 3 9 27 1 3 0 27 31
1 3 9 27 -1 -3 9 27 32
1 3 9 27 0 -3 9 27 33
1 3 9 27 1 -3 9 27 34
1 3 9 27 -1 0 9 27 35
1 3 9 27 0 0 9 27 36
1 3 9 27 1 0 9 27 37
1 3 9 27 -1 3 9 27 38
1 3 9 27 0 3 9 27 39
1 3 9 27 1 3 9 27 40
Thus the solution is to use weights of 1, 3, 9, and 27 kilograms and the query shows how to use them to balance each target weight.
Now that we have the solution, we can see the pattern that each greater weight grows by a factor of 3. Using that knowledge to our advantage we can make the query more efficient by eliminating the unneeded weights and use the query to show the combinations for higher levels. For example, expanding to 5 weights (1, 3, 9, 27, 81) we can balance up to 121. Using the same structure above but swapping the weights and factors for pre-constructed nested tables yields all 121 combinations quickly.
WITH
weights
AS
(SELECT COLUMN_VALUE w
FROM ora_mining_number_nt(1,
3,
9,
27,
81)),
factors
AS
(SELECT COLUMN_VALUE f
FROM ora_mining_number_nt(-1,
0,
1)),
usage
AS
(SELECT w, w * f u
FROM weights CROSS JOIN factors)
SELECT w1,w2,w3,w4,w5,
u1,u2,u3,u4,u5,
total
FROM (SELECT u1.w w1, u2.w w2, u3.w w3, u4.w w4, u5.w w5,
u1.u u1, u2.u u2, u3.u u3, u4.u u4, u5.u u5,
u1.u + u2.u + u3.u + u4.u + u5.u total,
COUNT(DISTINCT u1.u + u2.u + u3.u + u4.u + u5.u)
OVER(PARTITION BY u1.w,
u2.w,
u3.w,
u4.w,
u5.w) cnt
FROM usage u1,
usage u2,
usage u3,
usage u4,
usage u5
WHERE u1.w < u2.w AND u2.w < u3.w AND u3.w < u4.w AND u4.w < u5.w
AND u1.u + u2.u + u3.u + u4.u + u5.u BETWEEN 1 AND 121)
WHERE cnt = 121
ORDER BY total;
We could continue to extend this to greater weight totals and arbitrarily large combinations.
This was a fun exercise to do in idle time between other activities. I hope you enjoyed it as much as I did. I’m sure it could be made even more efficient. I welcome alternate solutions.
Nicely done, Sean. I believe that instincts would have had me starting the recursion by testing the largest value (27) first but we’d have gotten to the same place, and the same solution. Recursion intimidates a lot of people. For them, the pattern that you show provides a road map for solving this Algebraically, without recursion. The pattern is, for each column, that once the target value is large enough to require the value in the column (value / 2 + .5), the value occurs repeated as the positive of the value, the negative of the value, and 0. The repeat count is a function of the column number relative 0. 3^0, 3^1, 3^2, …3^x.
Instinctively, if one were to search for a solution for a given value (say 49?) one knows to first consider the heaviest weight on one side of the scale, and refine the search moving through the weights in (descending) order. With only 4 weights the clerk in the butcher shop could likely figure it out. But I doubt he’d fare as well weighing cattle where 7 weights could be required, or large trucks using 10 weights. And whether the clerk realizes it or not, he’s solving it recursively.
Solving this without recursion is quite a chore.
Again, well done!
Hi Sean,
Great and extremely elegant solution, I am really impressed 🙂 🙂
Cheers & Happy Holidays,
Iudith