01 - Which ball is different?

Your task is to write a function that solves the puzzle below. You shall

1. design an algorithm that solves the puzzle,
2. implement the algorithm as a Python function, and
3. test the algorithm thoroughly to see whether it works.

We have 12 balls, all are exactly the same in all respects, with a single exception. One of the balls is either slightly lighter or slightly heavier than the other 11. (And we do not know whether it is lighter or heavier). “Slightly” means that the difference is very small and you need to use an accurate weighing instrument, balance scales (see the picture), to see the difference. Your task is to learn which ball is different from the others and whether it is lighter or heavier using the least possible number of weighings.

Note that you can only weigh the balls against other balls; no weighing of balls vs anything else is possible.

In module balls_solver.py, create function solve() which shall implement your algorithm of successive weighings.

You can get up to 5 points for a successful solution for this task.

Function solve() should return the correct result for any possible configuration of the different ball: (1,'+'), …, (12,'-'). During the evaluation, all these configurations will be tested. Your score will be based on the number of correctly identified configurations, and on the maximum number of weighings you needed across all configurations. In general:

• the more correctly identified configurations, the more points;
• the more weighings required, the fewer points.

To be able to exercise and test your solution, we provide an implementation of class Balls which simulates the balance scale.

Assume that among the 12 balls, ball number 7 is heavier. You shall create and instance of Balls as follows:

>>> balls = Balls(12, (7, '+'))

Class Balls has a method weigh(left, right). This method is the interface to the balance scale. It takes 2 arguments: list of balls on the left-hand side, and list of balls on the right-hand side. The method returns which side is the heavier one (left or right), or returns none when both sides are equally heavy. You can call the method like this:

>>> balls.weigh([1,2,3,4], [5,6,7,8])
'right'

After the initialization above, this call to method weigh() shall return the value 'right', because the right-hand side of the scales contains the heavier ball number 7 (and the number of balls on both sides is the same).

You can also use Balls to analyze which weighings were actually carried out. The member variable n_balls contains the number of calls to method weigh() from the instance creation. The member variable log contains a list of strings describing the weighing events performed from the class initialization. If we, e.g., perform 3 measurements with the object like this:

balls = Balls(12, (7,'+'))
balls.weigh([1], [2])
balls.weigh([1,2], [5,6])
balls.weigh([7,8,9], [10,11,12])
print('The sequence of ball events was:')
print('\n'.join(balls.log))
print('Function weigh() was called {} times.'.format(balls.n_calls))

we shall get the following output:

The sequence of ball events was:
Init: different ball set to (7, '+').
Call 1: [1] vs [2] --> heavier is none
Call 2: [1, 2] vs [5, 6] --> heavier is none
Call 3: [7, 8, 9] vs [10, 11, 12] --> heavier is left
Function weigh() was called 3 times.

Function solve(), which shall be implemented by you, will get a reference to method weigh as an argument. Inside function solve() you can use weigh() as many times as you want, but you should keep the number of calls as small as possible. Function solve() shall eventually return the number of the different ball and the sign of the mass difference, e.g. (8, '-').

A possible, but INCORRECT implementation of function solve() can look like this:

def solve(weigh):
    heavier = weigh([1], [2])
    if heavier == 'left':
        return (1,'+')
    elif heavier == 'right':
        return (2, '+')
    else:
        return (12, '-')

How your implementation of function solve() works for a single configuration can be tested by the following code. Note how method weigh of object balls is passed to function solve():

from balls import Balls
from balls_solver import solve
 
different = (7, '+')                        
balls = Balls(12, different)
result = solve(balls.weigh)
print('\n'.join(balls.log))
print('After these events, my solve() function thinks '
      'that the different ball is {}.'.format(result))
print('It required {} weighings.'.format(balls.n_calls))

If you run this script then - using function solve listed above - we shall get the following output:

Init: different ball set to (7, '+').
Call 1: [1] vs [2] --> heavier is none
After these events, my solve() function thinks that the different ball is (12, '-').
It required 1 weighings.

One of your goals should be to test all possible configurations, check that for all of them the correct result is returned, and find out what is the number of required weighings in the worst case.