The twelve-balls problem is a famous problem where you are given twelve balls, one of which is a different weight, but you don't know whether it is heavier or lighter than the other balls. Using only three weighings of a two-sided scale, it is possible to find the differently weighted ball, and determine whether it is heavier or lighter.
Your task is to build a program that does the following:
Accept a number of balls
Nto be compared, from
100. (In the traditional problem,
N = 12.)
Produce two lists of numbers, representing the balls to be placed on each side of the balance. An equal number of balls must be placed on each side.
Accept an input signifying whether the left side of the scale is heavier, the right side is heavier, or the two sides are equal (this can be represented any way you want to: e.g.
1for right, or
2for right, and
3for equal), and in response, either produce another pair of lists of balls to be weighed, or a guess as to which ball is the different one and whether it is heavier or lighter.
Your score is the sum of the maximum number of weighings for each value of
100 that it took to figure out the right answer for
N balls using your algorithm (each case of "ball
x is heavier/lighter" must be tested). Lowest score wins.
For example, if for
N = 12, your algorithm managed to get 3 weighings for every case except "ball 8 is heavy" where it took 4 weighings, your score for
N = 12 is 4. If your maximum score was 10 weighings for each
N from 8 to 100, your final score would be
Your algorithm must return the correct answer for all possible test cases (for any
N, there are
2N possible test cases, which is a total of 10,044). In addition, the source code of your solution may not exceed 51,200 bytes (50 KB) in size.