Here's my solution.
#!/usr/bin/python2.7
from math import sqrt
def distance(driver, order):
'''each argument is a tuple indicating the position of the driver and the
order respectively. It returns a numerical value of the distance between
them'''
# I'm sure there's a square function defined somewehere.
sq = lambda x: x*x
return sqrt(sq(driver[0] - order[0]) +
sq(driver[1] - order[1]))
def calc_all_distances(drivers, orders):
'''drivers and order are lists of tuples.
This function will calculate all the distances between each driver and
each order.
It will then store the result in a dictionary where the keys are tuples
of the indexes of each element.
For instance: distances[(0, 2)] is the distance between driver[0] and
order[2].'''
return {(i, j): distance(drivers[i], orders[j]) for i in xrange(len(drivers))
for j in xrange(len(orders))}
def return_min_dist(distances):
'''the input is a dictionary return by calc_all_distances.
The function returns the key of the smallest of value.'''
min(distances, key=distances.get)
def move_driv(drivers, idx, newpos):
'''update position of drivers[idx]'''
drivers[idx] = newpos
return drivers
def deliv(drivers, orders, driv_ord):
'''The programs main loop.
It starts by calculating all the distances between drivers and orders.
then looks for the shortest distance.
Repeat until all orders are selected.'''
if len(orders) == 0:
return driv_ord
distances = calc_all_distances(drivers, orders)
shortest = return_min_dist(distances)
mvdriver = shortest[0]
mvposition = shortest[1]
newpos = orders[mvposition]
driv_ord[mvdriver].append(orders[mvposition])
orders.pop(mvposition)
return deliv(move_driv(drivers, mvdriver, newpos),
orders,
driv_ord)
def test (nbrdrivers, shop_location, orders):
'''nbrdrivers is an int.
shop_location is a tuple of coordiantes,
orders is a list of tuples.'''
drivers = [shop_location] * nbrdrivers
dr_ord = [[] for n in range(nbrdrivers)]
return deliv(drivers, orders, dr_ord)
print test(3,
(0, 0),
[(0, 1), (0, -1)])
print test(3,
(0, 0),
[(0, 1), (0, 2)])
Output:
[[(0, -1)], [], [(0, 1)]]
[[(0, 1), (0, 2)], [], []]
It simply consists of bruteforcing by calculating all the distances between orders and drivers and selecting the shortest one each time.
The code is valid for geek's examples, although I would be surprised if it is the definite general solution to the problem.
I commented the code so that I could get feedback. Don't hesitate to bash it.
