Friday, November 6, 2009

The 8 balls puzzle

Here is an interesting puzzle about selecting the heaviest ball among 7 other equally weighted balls. For example a collection of the 8 balls would look like this [2,1,1,1,1,1,1,1].

The goal is to choose the heaviest ball by performing only two weighings.
Fact: You know that all 7 other balls are equally weighted but you could not figure out the heaviest ball.
Solution: In order to do so, you are using the weighing machine but as a challenge you can only use the weighing machine at most twice

import java.util.Random;

public class TheHeaviestBall {

private int count = 0;
private int indexHeaviestBall = 0;
private Random myRand = new Random();
private int[] balls = {1,1,1,1,1,1,1,1};
private int[] arrangeBalls(){
balls[myRand.nextInt(8)] = 2;
for (int aBall : balls) {
System.out.print(aBall + " ");
}
return balls;
}

public void weighingCount(){
count++;
if (count > 2) {
System.out.println("Your algorithm fails");
}
}

public int theBALL(){
int myBalls[] = arrangeBalls();
weighingCount();
if ((myBalls[0]+myBalls[1]+myBalls[2]) > (myBalls[3]+myBalls[4]+myBalls[5])) {
weighingCount();
if (myBalls[1] == myBalls[2]) {
indexHeaviestBall = 0;
return myBalls[0];
} else {
if (myBalls[1] >= myBalls[2]) {
indexHeaviestBall = 1;
return myBalls[1];
} else {
indexHeaviestBall = 2;
return myBalls[2];
}
}
}
else if ((myBalls[3]+myBalls[4]+myBalls[5]) > (myBalls[0]+myBalls[1]+myBalls[2])) {
weighingCount();
if (myBalls[4] == myBalls[5]) {
return myBalls[3];
} else {
if (myBalls[4] >= myBalls[5]) {
indexHeaviestBall = 4;
return myBalls[4];
}
else {
indexHeaviestBall = 5;
return myBalls[5];
}
}
}
else {
weighingCount();
if (myBalls[6] >= myBalls[7]) {
indexHeaviestBall = 6;
return myBalls[6];
}
else {
indexHeaviestBall = 7;
return myBalls[7];
}
}
}

public static void getMyHeaviestBall(){
TheHeaviestBall hb = new TheHeaviestBall();
//Algorithm validation
if (hb.count > 2) {
System.out.println("You can do better");
} else {
System.out.println("\nThe heaviest ball [ " + hb.theBALL() + " ] is the " + (hb.indexHeaviestBall + 1) + "th ball from the left");
}
}

public static void main(String[] args) {
getMyHeaviestBall();
}
}
Update: Click here to view the solution to solve the 12 balls puzzle

0 comments:

Post a Comment