Search
Your task is to write a function that solves the puzzle below. You shall
balls.zip: supplementary codes for this task.
We have 12 balls, all are exactly the same in all respects, with a single exception. One of the balls is either slightly lighter of slightly heavier that 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.
balls_solver.py
solve()
weigh
'+
'-
You can get up to 5 points for successful solution of this task.
Function solve() should return the correct result for any possible configuration of the different ball: (1,'+'), …, (12,'-'). During 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:
(1,'+')
(12,'-')
To be able to exercise and test your solution, we provide an implementation of class Balls which simulates the balance scale.
Balls
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:
weigh(left, right)
left
right
none
>>> 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 vall number 7 (and the number of balls on both sides is the same).
weigh()
'right
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:
n_balls
log
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, '-').
(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():
balls
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:
solve
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.