[philiptellis] /bb|[^b]{2}/
Never stop Grokking


Sunday, November 21, 2010

Counterfeit coins solution

This is a solution to the Weighing piles of coins problem listed on Microsoft Research. It was fun solving it, and the basic idea of the solution could be applied to many other kinds of elimination problems.

Here's my algorithm. If you don't understand it, well, spend some time figuring it out.
Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 4 4 4 3 3 3 2 2 2 1 1 1 0 => 30 coins
// This is the first weighing

expected weight = 30X
actual weight = W

X1 = W div 30
D1 = W mod 30    // D1 <= 20 since |D| <= 5 and counterfeit coins in pile <= 4

if D1 == 0 then
        weigh all 52 coins (W)    // this is the second weighing
        X = W div 52
        D = (W mod 52) / 4
        pile = 13
else if D1 <= 5 then
        possible piles = 1-12
else if D1 >= 25 then
        X1 = X1 + 1,
        D1 = 30 - D1
        possible piles = 1-12
else if 5 < D1 < 10 then
        possible piles = 1-9
else if 10 <= D1 <= 20
        X11 = X1 + 1,
        D11 = 30 - D1
        possible piles = 1-6
end if


if 0 < D1 < 10 then

Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 1 3 4 1 2 4 0 1 3 2 3 4 4 => 32 coins
// This is the second weighing

        expected weight = 32X
        actual weight = W

        X2 = W div 32
        D2 = W mod 32    // D2 <= 20 since |D| <= 5 and counterfeit coins in pile <= 4

        if 12 <= D2 <= 20 and X1 != X2 then
                X2 = X2 + 1
                D2 = 32 - D2
        end if

        X = X2

        if      D2 == D1*0 then
                pile = 7
                D = D1/2
        else if D2 == D1*1 then
                pile = 3
                D = D1/4
        else if D2 == D1*2 then
                pile = 10
                D = D1
        else if D2 == D1*3 then
                pile = 11
                D = D1
        else if D2 == D1*4 then
                pile = 12
                D = D1
        else if D2 == D1*1/2 then
                pile = 8
                D = D1/2
        else if D2 == D1*3/2 then
                pile = 9
                D = D1/2
        else if D2 == D1*1/3 then
                pile = 4
                D = D1/3
        else if D2 == D1*2/3 then
                pile = 5
                D = D1/3
        else if D2 == D1*4/3 then
                pile = 6
                D = D1/3
        else if D2 == D1*1/4 then
                pile = 1
                D = D1/4
        else if D2 == D1*3/4 then
                pile = 2
                D = D1/4
        end if
else

Pile#:    1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 1 2 3 0 1 2 4 4 4 4 4 4 4 => 37 coins
// This is the second weighing

        expected weight = 37X
        actual weight = W

        X2 = W div 37
        D2 = W mod 37    // D2 <= 15 since |D| <= 5 and counterfeit coins in pile <= 3

        X = X2

        if X11 == X2 then
                D1 = D11
        end if

        if      D2 == D1*1/4 then
                pile = 1
                D = D1/4
        else if D2 == D1*2/4 then
                pile = 2
                D = D1/4
        else if D2 == D1*3/4 then
                pile = 3
                D = D1/4
        else if D2 == D1*0/3 then
                pile = 4
                D = D1/3
        else if D2 == D1*1/3 then
                pile = 5
                D = D1/3
        else if D2 == D1*2/3 then
                pile = 6
                D = D1/3
        end if
end if

0 comments :

Post a Comment

...===...