The 12-Coins is a classic balance puzzle where the goal is find a fake coin from one of 12 using only 3 trials on the balance scale. Furthermore, once you find the fake coin you should be able to determine if it is lighter or heavier than the real coins.
The solution involves dividing the coins into piles that are then weighed against each other. Then using the results of those weighing to find candidate coins as well as identifying known good coins which can then be used in subsequent trials to reduce the number of unknowns.
For example. if you divide the initial set into 3 piles of 4 coins each and weigh 2 of the piles you have only 2 possible results. Either the scale balances because the 2 piles are of equal weight, or the scales will tip because one of the coins is heavier or lighter than the others. If the scale balances then you know all 8 of those coins must be good because they all weigh the same and the fake coin is in the remaining pile. If the scale does not balance then you know all 4 coins in the third pile must be good because the fake one must on the scale causing the piles to be unbalanced.
The package below will solve the puzzle. The twelve coins are lettered A through L. Using the SOLVE procedure you can pick one to be the fake and decide if it will be heavy or light. Alternately you have have the package assign the fake coin and weight difference randomly. A third parameter will determine if the solution will start with a fixed arrangement of coins A,B,C,D in the left pan of the scale and E,F,G,H in the right pan, with I,J,K,L left off the scale – or if the initial distribution of the 3 piles will be randomized. It makes no difference in the final outcome but randomizing may help assure the readers that the algorithm works in the general case and not just for a specific arrangement.
The DO_ALL procedure will iterate through all permutations of coin selection and choice of heavy or light.
It may seem like cheating to give the answer to the package and then ask it to solve the puzzle; but the choices of fake coin and weight difference are not referenced anywhere except in the WEIGH_COINS function which only returns a result of left-heavy, right-heavy, or balanced. The 3 steps of the solving algorithm never reference the answer values.
When weighing the coins, the function will use DBMS_OUTPUT to display a simple ASCII-art representation of the scale and balance result. The following block shows an example of a randomized solution for a heavy F-coin with the 3 weight trials used to solve it.
SQL> BEGIN
2 twelve_coins.solve(p_fake=>'F', p_heavy_fake=> true);
3 END;
4 /
--------------------------------
EJGI__-*-__CDKH
AB____
\
*
\
____FC
A_____-*-_____B
Fake coin: F is heavy
--------------------------------
You can see step 1 randomly assigned the coins to the pans but the first 8 were balanced. Therefore the fake must be within (A, B, F, L.)
For step 2 two of the unknown coins were put in the left pan (A, B) and one of them in the right along with a known good coin from the initial set (F, C). The result is the right pan is heavier but we don’t know yet if that is because one of (A, B) is light, or if F is heavy. We know C is good from the step 1 balance so those are the only options.
For step 3, the left pan coins were compared to each other. Since they are balanced, they must both be good coins, meaning the fake must have been in the right pan which was heavy. Since the only unknown coin in the right pan was F, we know F is the fake and that it must be heavy since its pan was heavier than the other.
And thus the puzzle was solved in 3 tries.
I found the 12-Coins puzzle a fun mental exercise and enjoyed coming up with a package to implement the solution. I hope you find it interesting and a helpful code example.
CREATE OR REPLACE PACKAGE twelve_coins
AS
PROCEDURE solve(p_fake IN CHAR DEFAULT NULL,
p_heavy_fake IN BOOLEAN DEFAULT NULL,
p_random IN BOOLEAN DEFAULT TRUE);
PROCEDURE do_all(p_random IN BOOLEAN DEFAULT FALSE);
END;
/
CREATE OR REPLACE PACKAGE BODY twelve_coins
AS
c_left_heavy_template CONSTANT VARCHAR2(100) := '
~RIGHT~
/
*
~LEFT~/
';
c_right_heavy_template CONSTANT VARCHAR2(100) := '
~LEFT~
\
*
\
~RIGHT~
';
c_balanced_template CONSTANT VARCHAR2(100) := '
~LEFT~-*-~RIGHT~
';
SUBTYPE scale_result IS PLS_INTEGER RANGE -1 .. 1;
c_left_heavy CONSTANT scale_result := -1;
c_right_heavy CONSTANT scale_result := 1;
c_balanced CONSTANT scale_result := 0;
TYPE coin_tab IS TABLE OF CHAR(1);
c_all_coins CONSTANT coin_tab
:= coin_tab('A',
'B',
'C',
'D',
'E',
'F',
'G',
'H',
'I',
'J',
'K',
'L') ;
g_fake CHAR(1);
g_heavy_fake BOOLEAN;
FUNCTION show_coins(p_coins IN coin_tab)
RETURN VARCHAR2
IS
-- Construct a text string of the coin pile
v_result VARCHAR2(12);
BEGIN
FOR i IN 1 .. p_coins.COUNT
LOOP
v_result := v_result || p_coins(i);
END LOOP;
RETURN v_result;
END show_coins;
FUNCTION weigh_coins(p_left IN coin_tab, p_right IN coin_tab)
RETURN INTEGER
IS
-- Given the left and right piles, check the result using the heavy pile
v_scales VARCHAR2(100);
v_balance INTEGER;
BEGIN
CASE
WHEN g_fake MEMBER OF p_left AND g_heavy_fake
THEN
v_scales := c_left_heavy_template;
v_balance := c_left_heavy;
WHEN g_fake MEMBER OF p_left AND NOT g_heavy_fake
THEN
v_scales := c_right_heavy_template;
v_balance := c_right_heavy;
WHEN g_fake MEMBER OF p_right AND g_heavy_fake
THEN
v_scales := c_right_heavy_template;
v_balance := c_right_heavy;
WHEN g_fake MEMBER OF p_right AND NOT g_heavy_fake
THEN
v_scales := c_left_heavy_template;
v_balance := c_left_heavy;
ELSE
v_scales := c_balanced_template;
v_balance := c_balanced;
END CASE;
-- Show an ASCII "drawing" of the scales
v_scales :=
REPLACE(v_scales,
'~LEFT~',
RPAD(show_coins(p_left),
6,
'_'));
v_scales :=
REPLACE(v_scales,
'~RIGHT~',
LPAD(show_coins(p_right),
6,
'_'));
DBMS_OUTPUT.put_line(v_scales);
RETURN v_balance;
END weigh_coins;
PROCEDURE randomize(p_left OUT coin_tab, p_right OUT coin_tab)
IS
-- distribute the coins randomly across
-- the initial left/right piles on the scale
BEGIN
p_left :=
coin_tab(NULL,
NULL,
NULL,
NULL);
p_right :=
coin_tab(NULL,
NULL,
NULL,
NULL);
FOR x IN (SELECT ROWNUM rn, n
FROM ( SELECT LEVEL n
FROM DUAL
CONNECT BY LEVEL <= 12
ORDER BY DBMS_RANDOM.VALUE)
WHERE ROWNUM <= 8)
LOOP
IF x.rn <= 4
THEN
p_left(x.rn) := c_all_coins(x.n);
ELSE
p_right(x.rn - 4) := c_all_coins(x.n);
END IF;
END LOOP;
END randomize;
PROCEDURE step_1(p_heavy OUT coin_tab,
p_light OUT coin_tab,
p_unknown OUT coin_tab,
p_balance OUT scale_result,
p_random IN BOOLEAN DEFAULT TRUE)
IS
v_left coin_tab;
v_right coin_tab;
BEGIN
-- Divide the coins into 3 piles, weigh 2 of them.
IF p_random
THEN
randomize(v_left, v_right);
ELSE
v_left :=
coin_tab('A',
'B',
'C',
'D');
v_right :=
coin_tab('E',
'F',
'G',
'H');
END IF;
p_balance := weigh_coins(v_left, v_right);
CASE p_balance
WHEN c_left_heavy
THEN
p_heavy := v_left;
p_light := v_right;
p_unknown := NULL; -- The remaining coins are all good, neither heavy nor light
WHEN c_right_heavy
THEN
p_heavy := v_right;
p_light := v_left;
p_unknown := NULL; -- The remaining coins are all good, neither heavy nor light
ELSE
p_heavy := NULL; -- Both pans are equal meaning the fake must be in the 3rd pile
p_light := NULL; -- Both pans are equal meaning the fake must be in the 3rd pile
p_unknown := c_all_coins MULTISET EXCEPT v_left MULTISET EXCEPT v_right;
END CASE;
END step_1;
PROCEDURE step_2(p_heavy IN coin_tab,
p_light IN coin_tab,
p_unknowns IN coin_tab,
p_balance OUT scale_result)
IS
v_left coin_tab;
v_right coin_tab;
v_allgood coin_tab;
v_onegood CHAR(1);
BEGIN
CASE
WHEN p_unknowns IS NOT NULL
THEN
-- If the unknowns are populated, then the fake is among them
v_allgood := c_all_coins MULTISET EXCEPT p_unknowns;
v_onegood := v_allgood(1);
v_left := coin_tab(p_unknowns(1), p_unknowns(2));
v_right := coin_tab(p_unknowns(3), v_onegood);
ELSE
v_allgood := c_all_coins MULTISET EXCEPT p_heavy MULTISET EXCEPT p_light;
v_onegood := v_allgood(1);
v_left :=
coin_tab(p_heavy(1),
p_heavy(2),
p_light(1));
v_right :=
coin_tab(p_heavy(3),
p_light(2),
v_onegood);
END CASE;
p_balance := weigh_coins(v_left, v_right);
END step_2;
FUNCTION step_3(p_heavy IN coin_tab,
p_light IN coin_tab,
p_unknowns IN coin_tab,
p_balance_1 IN scale_result,
p_balance_2 IN scale_result)
RETURN VARCHAR2
IS
v_result VARCHAR2(10);
v_allgood coin_tab;
v_onegood CHAR(1);
v_balance scale_result;
BEGIN
CASE
WHEN p_balance_1 = c_balanced
THEN
IF p_balance_2 = c_balanced
THEN
v_allgood := c_all_coins MULTISET EXCEPT p_unknowns;
v_onegood := v_allgood(1);
v_balance := weigh_coins(coin_tab(p_unknowns(4)), coin_tab(v_onegood));
v_result := p_unknowns(4) || CASE v_balance WHEN c_left_heavy THEN ' is heavy' ELSE ' is light' END;
ELSE
-- balance 2 uneven
v_balance := weigh_coins(coin_tab(p_unknowns(1)), coin_tab(p_unknowns(2)));
v_result :=
CASE
WHEN v_balance = c_balanced AND p_balance_2 = c_left_heavy
THEN
p_unknowns(3) || ' is light'
WHEN v_balance = c_balanced AND p_balance_2 = c_right_heavy
THEN
p_unknowns(3) || ' is heavy'
WHEN v_balance = p_balance_2 AND v_balance = c_left_heavy
THEN
p_unknowns(1) || ' is heavy'
WHEN v_balance = p_balance_2 AND v_balance = c_right_heavy
THEN
p_unknowns(1) || ' is light'
WHEN v_balance != p_balance_2 AND v_balance = c_left_heavy
THEN
p_unknowns(2) || ' is light'
WHEN v_balance != p_balance_2 AND v_balance = c_right_heavy
THEN
p_unknowns(2) || ' is heavy'
ELSE
NULL -- can't happen
END;
END IF;
ELSE
-- balance 1 uneven
v_allgood := c_all_coins MULTISET EXCEPT p_heavy MULTISET EXCEPT p_light;
v_onegood := v_allgood(1);
v_result :=
CASE p_balance_2
WHEN c_balanced
THEN
CASE weigh_coins(coin_tab(p_light(3)), coin_tab(p_light(4)))
WHEN c_balanced THEN p_heavy(4) || ' is heavy'
WHEN c_left_heavy THEN p_light(4) || ' is light'
ELSE p_light(3) || ' is light'
END
WHEN c_left_heavy
THEN
CASE weigh_coins(coin_tab(p_heavy(1)), coin_tab(p_heavy(2)))
WHEN c_left_heavy THEN p_heavy(1) || ' is heavy'
WHEN c_right_heavy THEN p_heavy(2) || ' is heavy'
ELSE p_light(2) || ' is light'
END
WHEN c_right_heavy
THEN
CASE weigh_coins(coin_tab(p_heavy(3)), coin_tab(v_onegood))
WHEN c_left_heavy THEN p_heavy(3) || ' is heavy'
ELSE p_light(1) || ' is light'
END
END;
END CASE;
RETURN v_result;
END step_3;
PROCEDURE solve(p_fake IN CHAR DEFAULT NULL,
p_heavy_fake IN BOOLEAN DEFAULT NULL,
p_random IN BOOLEAN DEFAULT TRUE)
IS
v_heavy coin_tab;
v_light coin_tab;
v_unknown coin_tab;
v_result VARCHAR2(10);
v_balance_1 scale_result;
v_balance_2 scale_result;
BEGIN
-- If the user selected a fake, use it, otherwise pick one at random
CASE
WHEN p_fake IS NULL
THEN
g_fake := CHR(ROUND(DBMS_RANDOM.VALUE(ASCII('A'), ASCII('L'))));
WHEN p_fake NOT MEMBER OF c_all_coins
THEN
RAISE VALUE_ERROR;
ELSE
g_fake := p_fake;
END CASE;
-- If the user chose heavy/light use it, otherwise pick at random
IF p_heavy_fake IS NULL
THEN
g_heavy_fake := DBMS_RANDOM.VALUE < 0.5;
ELSE
g_heavy_fake := p_heavy_fake;
END IF;
DBMS_OUTPUT.put_line(RPAD('-',
30,
'-'));
step_1(v_heavy,
v_light,
v_unknown,
v_balance_1,
p_random);
step_2(v_heavy,
v_light,
v_unknown,
v_balance_2);
v_result :=
step_3(v_heavy,
v_light,
v_unknown,
v_balance_1,
v_balance_2);
DBMS_OUTPUT.put_line('Fake coin: ' || v_result);
DBMS_OUTPUT.put_line(RPAD('-',
30,
'-'));
END solve;
PROCEDURE do_all(p_random IN BOOLEAN DEFAULT FALSE)
IS
-- Run trials for each of the 12 coins being the fake
-- Run each coin trial twice, once with the fake heavy and again light
BEGIN
FOR i IN 1 .. 12
LOOP
FOR j IN 1 .. 2
LOOP
solve(p_fake => c_all_coins(i),
p_heavy_fake => CASE j WHEN 1 THEN TRUE ELSE FALSE END,
p_random => p_random);
END LOOP;
END LOOP;
END do_all;
END;
/