Given n coins and a pan balance,find the only counterfeit 3

In the 1-ball case, if the status flag is already set, then we don't need to weight anymore. Otherwise, we need to find a good ball to compare.

java 代码

package solve;

import scale.Ball;
import scale.Scale;

import java.util.Set;

/**
 * 1-ball case: we need a good reference ball and at most one trial
 */
public class OneBallCaseSolver
{
    private Scale scale;
    private Set originalBallSet;

    public void findWeight(Set ballSet)
    {
        if (ballSet.size() != 1)
            throw new IllegalArgumentException("scale.Ball set size is not 1: size=" + ballSet.size());

        Ball ball = (Ball)ballSet.iterator().next();

        if (!ball.getStatus().equals(Ball.UNKNOWN)) return;

        // in order to figure it's good or bad, we need a good reference ball.
        Ball goodBall = Utils.findGoodBall(originalBallSet);
        if (goodBall == null)
        {
            throw new RuntimeException("can't findBallBall a good reference ball to use for the judgement");
        }

        // flag conversion
        int result = scale.weigh(ball, goodBall);
        ball.setStatus(Utils.convertToBallStatus(result));
    }

    public void setScale(Scale scale) { this.scale = scale; }
    public void setOriginalBallSet(Set originalBallSet) { this.originalBallSet = originalBallSet; }
}

In the 2-ball case, we need to check whether the status flags for both are set. If not, then we need two weighings.

java 代码

package solve;

import scale.Scale;
import scale.Ball;

import java.util.Iterator;
import java.util.Set;

/**
 * 2-ball case: we need a good reference ball and one or two weighings.
 */
public class TwoBallCaseSolver
{
    private Scale scale;
    private Set originalBallSet;

    public void findWeight(Set ballSet)
    {
        if (ballSet.size() != 2)
            throw new IllegalArgumentException("scale.Ball set size is not 2: size=" + ballSet.size());

        Iterator it = ballSet.iterator();
        Ball balla = (Ball)it.next();
        Ball ballb = (Ball)it.next();

        Ball goodBall = Utils.findGoodBall(originalBallSet);
        int result = scale.weigh(balla, goodBall);
        balla.setStatus(Utils.convertToBallStatus(result));

        if (!balla.getStatus().equals(Ball.NORMAL))
        {
            ballb.setStatus(Ball.NORMAL);
        }
        else if (ballb.getStatus().equals(Ball.UNKNOWN))
        {
            result = scale.weigh(ballb, goodBall);
            ballb.setStatus(Utils.convertToBallStatus(result));
        }
    }

    public void setScale(Scale scale) { this.scale = scale; }
    public void setOriginalBallSet(Set originalBallSet) { this.originalBallSet = originalBallSet; }
}

In the above two cases, whenever we need to weigh, we need a good ball as the reference. In the 3-ball case, we don't need a good ball.

java 代码

package solve;

import scale.Scale;
import scale.Ball;

import java.util.Set;
import java.util.Iterator;

/**
 * 3-ball case: we need two trials if all of the balls are not marked, otherwise
 * we need only one trial.
 */
public class ThreeBallCaseSolver
{
    private Scale scale;

    public void findWeight(Set ballSet)
    {
        if (ballSet.size() != 3)
            throw new IllegalArgumentException("scale.Ball set size is not 3: size=" + ballSet.size());

        // In the 3-ball case, we can figure out which one is good.
        // Here, we assume there is only one bad ball.
        Iterator it = ballSet.iterator();
        Ball balla = (Ball)it.next();
        Ball ballb = (Ball)it.next();
        Ball ballc = (Ball)it.next();

        if (balla.getStatus().equals(Ball.UNKNOWN)) // This means we start with 3 balls
        {
            // In this case we need two trials
            int result = scale.weigh(balla, ballb);
            if (result == Scale.EVEN)
            {
                // This means balla and ballb are good, ballc is bad.
                balla.setStatus(Ball.NORMAL);
                ballb.setStatus(Ball.NORMAL);
                if (scale.weigh(balla, ballc) == Scale.HEAVIER)
                    ballc.setStatus(Ball.LIGHTER);
                else
                    ballc.setStatus(Ball.HEAVIER);
            }
            else //if (result == Scale.HEAVIER)
            {
                // This means ballc is good
                ballc.setStatus(Ball.NORMAL);
                int result1 = scale.weigh(balla, ballc);
                if (result1 == Scale.EVEN) // a is also good
                {
                    balla.setStatus(Ball.NORMAL);
                    if (result == Scale.HEAVIER)
                        ballb.setStatus(Ball.LIGHTER);
                    else
                        ballb.setStatus(Ball.HEAVIER);
                }
                else if (result1 == Scale.HEAVIER) // b is good, a is heavier
                {
                    balla.setStatus(Ball.HEAVIER);
                    ballb.setStatus(Ball.NORMAL);
                }
                else
                {
                    balla.setStatus(Ball.LIGHTER);
                    ballb.setStatus(Ball.NORMAL);
                }
            }
        }
        else // This means we start with more than 3 balls and markWeight is marked.
        {
            // In this case we need only 1 trial with the marked info.
            // At this stage, all 3 balls are marked with either lighter or heavier.
            // From the Pigeon Principle, we can choose two balls with the same mark.
            Ball w1;
            Ball w2;
            Ball w3;

            if (balla.getStatus().equals(ballb.getStatus()))
            {
                w1 = balla;
                w2 = ballb;
                w3 = ballc;
            }
            else if (balla.getStatus().equals(ballc.getStatus()))
            {
                w1 = balla;
                w2 = ballc;
                w3 = ballb;
            }
            else if (ballb.getStatus().equals(ballc.getStatus()))
            {
                w1 = ballb;
                w2 = ballc;
                w3 = balla;
            }
            else
            {
                throw new RuntimeException("The balls are not marked properly");
            }

            int result = scale.weigh(w1, w2);
            if (result == Scale.EVEN)
            {
                w1.setStatus(Ball.NORMAL);
                w2.setStatus(Ball.NORMAL);
            }
            else if (result == Scale.HEAVIER)
            {
                w3.setStatus(Ball.NORMAL);
                if (w1.getStatus().equals(Ball.HEAVIER)) // heavier is bad
                {
                    w2.setStatus(Ball.NORMAL);
                }
                else // lighter is bad
                {
                    w1.setStatus(Ball.NORMAL);
                }
            }
            else
            {
                w3.setStatus(Ball.NORMAL);
                if (w1.getStatus().equals(Ball.HEAVIER))
                {
                    w1.setStatus(Ball.NORMAL);
                }
                else
                {
                    w2.setStatus(Ball.NORMAL);
                }
            }
        }
    }

    public void setScale(Scale scale) { this.scale = scale; }
}