Another Google question - drop glassballs from a building 3

The next step is to find the actually path of floors that we are going through to find the breaking floor. Here is the code to do that.

java 代码

package glassball;

import java.util.List;
import java.util.ArrayList;

/**
 * For a given building and balls, find out the path of floors we go through
 * on the way to find the minimal floor where the ball is broken if thrown.
 */
public class PathFinder
{
    private Building building;

    private GlassBallPuzzle puzzle;

    public PathFinder(Building building, int numOfGlassballs)
    {
        this.building = building;

        int totalFloors = building.getNumOfFloors();
        this.puzzle = new GlassBallPuzzle(numOfGlassballs, totalFloors);
    }

    public GlassBallPuzzle getPuzzle() { return puzzle; }

    public List findPuzzlePath()
    {
        int totalFloors = building.getNumOfFloors();
        int[][] sums = puzzle.getRecursiveSums();

        // we don't need extra balls. If we don't want this optimization
        // we have to check whether a floor is higher than building's height,
        // and ignore them if it's true.
        int ballIndex = puzzle.getOptimalTrialsAndBalls()[1] - 1;
        List path = new ArrayList();
        int baseFloor = 1;
        generatePathForBallWithIndex(ballIndex, path, baseFloor, totalFloors, sums);

        return path;
    }

    // This is a recursive call
    private void generatePathForBallWithIndex(int ballIndex, List path,
            int baseFloor, int totalFloors, int[][] sums)
    {
        int[] floorArray = generateFloorArray(sums, ballIndex, totalFloors);

        for (int i=0; i<floorArray.length; i++)
        {
            // -1 here because baseFloor starts with 1.
            int currentFloor = baseFloor + Math.min(totalFloors, floorArray[i] - 1);

            boolean result;
            if (ballIndex == 0 &&  currentFloor == totalFloors)
            {
                result = true; // only one ball case
            }
            else if (currentFloor < baseFloor + totalFloors)
            {
                result = building.isBrokenIfThrowAt(currentFloor);
                path.add(new Trial(currentFloor, ballIndex, result, false));
            }
            else
            {
                result = true; // we have been here, no point to do it again.
            }

            if (result)
            {
                if (i > 0) baseFloor += floorArray[i-1];

                int floorsBetween = currentFloor - baseFloor;

                if (ballIndex - 1 <= 0) // 0 or 1
                {
                    // try from bottom, one floor at a time
                    for (int k=baseFloor; k<baseFloor+floorsBetween; k++)
                    {
                        if (k <= 0) continue; // this happens when floor 1 is broken.
                        boolean stepResult = building.isBrokenIfThrowAt(k);
                        path.add(new Trial(k, ballIndex - 1, stepResult, false));
                        if (stepResult) return;
                    }

                    // this indicate the last broken one is the floor
                    // if there is no broken one, then we need to add the last floor
                    boolean hasBroken = false;
                    boolean allBroken = true;
                    for (int j=0; j<path.size(); j++)
                    {
                        Trial trial = (Trial)path.get(j);
                        if (trial.isBroken()) hasBroken = true;
                        else allBroken = false;
                    }

                    if (!hasBroken) path.add(new Trial(currentFloor, ballIndex, true, true));
                    if (allBroken) path.add(new Trial(currentFloor, ballIndex, true, true));
                    return;
                }
                else
                {
                    // now try on ballIndex - 1 array.
                    if (floorsBetween > 0)
                    {
                        generatePathForBallWithIndex(ballIndex - 1, path,
                            baseFloor, floorsBetween, sums);
                        return;
                    }
                }
            }
            // continue
        }
    }

    // This method is similar to the one in GlassBallPuzzle, but is dynamic
    // since the underlying sum array varies - depends on totalFloors variable.
    private int[] generateFloorArray(int[][] sums, int ballIndex, int totalFloors)
    {
        if (ballIndex == 0)
        {
            return sums[0];
        }

        // find the end element not to exceed totalFloors
        int[] sumArray = sums[ballIndex];
        int index = 0;
        for (int j=0; j<sumArray.length; j++)
        {
            // The equal sign is corresponding to the last trial
            // when the ball is broken.
            if (sumArray[j] >= totalFloors)
            {
                index = j;
                break;
            }
        }

        // now start from the end element, sum up going to the beginning;
        sumArray = sums[ballIndex - 1];
        int[] floors = new int[index + 1];
        int total=0;
        for (int j=0; j<=index; j++)
        {
            total += sumArray[index - j];
            floors[j] = total;
        }

        return floors;
    }
}

The last method is to generate series (A), (B), ... dynamically. The main code is a recursion.

Here we use two other classes, Building and Trial. Building is to define the number of floors and the broken floor, which will be used for testing purpose. The Trial class is to record each trial, plus a flag to indicate whether this is a logic conclusion or not, as we discussed in the previous post listed in (i) and (ii).

java 代码

package glassball;

/**
 * To hold the state of each trial
 */
public class Trial
{
    private int floor;
    private int ballNum;
    private boolean broken;
    private boolean isDeducted = false;

    public Trial(int floor, int ballNum, boolean broken, boolean isDeducted)
    {
        this.floor = floor;
        this.ballNum = ballNum;
        this.broken = broken;
        this.isDeducted = isDeducted;
    }

    public int getFloor() { return floor; }

    public int getBallNum() { return ballNum; }

    public boolean isBroken() { return broken; }

    public boolean isDeducted() { return isDeducted; }

    public String toString()
    {
        return "(f=" + floor + ", b=" + ballNum + ", " + (broken ? "broken" : "whole")
                + ", " + (isDeducted ? "deducted" : "tried") +  ")"; }

    public boolean equals(Object obj)
    {
        if ( !(obj instanceof Trial) ) return false;

        Trial trial = (Trial)obj;

        return this.floor == trial.floor && this.ballNum == trial.ballNum &&
               this.broken == trial.broken && this.isDeducted == trial.isDeducted;
    }
}

and

java 代码

package glassball;
/**
 * Building with floors.
 */
public class Building
{
    private int numOfFloors;
    // the lowest floor where the ball is broken if thrown.
    // This field is sealed inside this class.
    private int ballbreakingfloor;

    public Building(int numOfFloors, int ballbreakingfloor)
    {
        this.numOfFloors = numOfFloors;
        this.ballbreakingfloor = ballbreakingfloor;
    }

    public int getNumOfFloors() { return numOfFloors; }

    public boolean isBrokenIfThrowAt(int floor) { return floor >= ballbreakingfloor; }
}

The test cases are a little complex, which is in the next post.