Saturday, November 7, 2009

The 12 balls puzzle

A solution to solve the 12 ball puzzle.
Fact: you know that 11 balls are equally weighted and 1 of them is not
Constraint: you can only use the weighing machine at most 3 times to determine the heaviest ball

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,1,1,1,1};
private int[] arrangeBalls(){
balls[myRand.nextInt(12)] = 2;
for (int aBall : balls) {
System.out.print(aBall + " ");
}
return balls;
}

public void weighingCount(){
count++;
if (count > 3) {
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]+myBalls[6]+myBalls[7])) {
weighingCount();
if ((myBalls[0]+myBalls[1]) > (myBalls[2]+myBalls[3])) {
weighingCount();
if (myBalls[0] > myBalls[1]) {
indexHeaviestBall = 0;
return myBalls[0];
} else {
indexHeaviestBall = 1;
return myBalls[1];
}
} else {
weighingCount();
if (myBalls[2] > myBalls[3]) {
indexHeaviestBall = 2;
return myBalls[2];
} else {
indexHeaviestBall = 3;
return myBalls[3];
}
}
}
else if ((myBalls[4]+myBalls[5]+myBalls[6]+myBalls[7]) > (myBalls[0]+myBalls[1]+myBalls[2]+myBalls[3])) {
weighingCount();
if ((myBalls[4]+myBalls[5]) > (myBalls[6]+myBalls[7])) {
weighingCount();
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];
}
}
}
else {
weighingCount();
if ((myBalls[8]+myBalls[9]) > (myBalls[10]+myBalls[11])) {
weighingCount();
if (myBalls[8] > myBalls[9]) {
indexHeaviestBall = 8;
return myBalls[8];
} else {
indexHeaviestBall = 9;
return myBalls[9];
}
} else {
weighingCount();
if (myBalls[10] > myBalls[11]) {
indexHeaviestBall = 10;
return myBalls[10];
} else {
indexHeaviestBall = 11;
return myBalls[11];
}
}
}
}

public static void getMyHeaviestBall(){
TheHeaviestBall hb = new TheHeaviestBall();
//Algorithm validation
if (hb.count > 3) {
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 8 balls puzzle

0 comments:

Post a Comment