Warning

This page is located in archive.

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

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

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.

solve(weigh) | Identifies the different ball. |
---|---|

Input: | `weigh` : Function that realizes the weighings. It expects 2 lists of numbers from 1 to 12, i.e., the balls that shall be put to left and right sides of the scales. |

Output: | 2-tuple of values determining the number of the different ball (1,…,12) and the indicator whether the ball is heavier (`'+` ') or lighter (`'-` '). |

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:

- the more correctly identified configurations, the more points;
- the more weighings required, the less 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 vall 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.

courses/be5b33prg/homeworks/balls.txt · Last modified: 2016/11/09 17:00 by xposik