5
\$\begingroup\$

I am writing a modified travelling salesman problem recursively in Python 3.7. It has to find the best path around breweries to find the most beer types and not to exceed the max_distance. The problem is the execution time. I left it to run for 10 hours and it still didn't calculate final answer. When max_distance is set to 1000 it executes in about 40ms. I am not sure there is a possibility to use dynamic programming to solve this problem. I tried using dask but got a lot of errors.

Is there any other way to improve this code to make it run faster?

import copy
from math import radians, cos, sin, asin, sqrt

from datetime import datetime

best_path = []
best_beer_count = 0
best_distance = 0


class Brewery:
    def __init__(self, _brewery, beer, distance=0, visited=False):
        self.beer = beer
        self.id = _brewery[0]
        self.name = _brewery[1]
        self.longitude = _brewery[2]
        self.latitude = _brewery[3]
        self.distance_to_home = distance
        self.visited = visited

    def __str__(self):
        return "[{}, '{}', {}, {}],".format(self.id, self.name, self.longitude, self.latitude)


def merge_breweries_with_beers(breweries, beers):
    breweries_list = []
    for i in range(len(breweries)):
        breweries_list.append(Brewery(breweries[i], beers[i]))

    return list(breweries_list)


def haversine(lat1, lon1, lat2, lon2):
    """Returns distance between given coordinates"""
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
    c = 2 * asin(sqrt(a))
    r = 6371
    return c * r


def get_breweries_within_1000(lat, lon, breweries):
    breweries_1000 = []

    for brewery in breweries:
        distance = haversine(lat, lon, brewery.latitude, brewery.longitude)
        brewery.distance_to_home = distance
        if distance <= 1000:
            breweries_1000.append(brewery)

    return breweries_1000


def get_breweries_within_specific_distance(brew: Brewery, breweries, given_distance):
    """Returns list of breweries within specified distance"""
    breweries_specific_distance = []

    for brewery in breweries:
        distance = haversine(brew.latitude, brew.longitude, brewery.latitude, brewery.longitude)
        if given_distance > distance:
            breweries_specific_distance.append(brewery)

    return breweries_specific_distance


def make_graph(breweries):
    x = [[None for i in range(len(breweries))] for j in range(len(breweries))]
    for i in range(len(x)):
        for j in range(len(x)):
            distance = haversine(breweries[i].latitude, breweries[i].longitude,
                                 breweries[j].latitude, breweries[j].longitude)
            x[i][j] = distance
    return x


def set_best_path(curr_path):
    global best_beer_count
    global best_distance
    global best_path
    curr_beer_count = get_distinct_beer(curr_path)
    curr_distance = get_total_distance(curr_path)

    if curr_beer_count > best_beer_count:
        best_beer_count = curr_beer_count
        best_distance = curr_distance
        best_path = curr_path.copy()
        print(str(curr_path[1].id) + curr_path[1].name)
        print('Breweries count: ' + str(len(curr_path) - 2))
        print('Beer count: ' + str(best_beer_count))
        print('Distance: ' + str(best_distance) + '\n')

    elif curr_beer_count == best_beer_count and curr_distance < best_distance:
        best_beer_count = curr_beer_count
        best_distance = curr_distance
        best_path = curr_path.copy()
        print('Distance was better')
        print(str(curr_path[1].id) + curr_path[1].name)
        print('Breweries count: ' + str(len(curr_path) - 2))
        print('Beer count: ' + str(best_beer_count))
        print('Distance: ' + str(best_distance) + '\n')


def tsp_rec(breweries: [Brewery], distance_traveled, curr_pos, path, graph_of_distances):
    max_distance = 2000
    if len(path) != 0:
        new_path = path.copy()
        home = breweries[0]

        new_path[:0] = [home]
        home_final = copy.deepcopy(home)
        home_final.distance_to_home = haversine(home_final.latitude, home_final.longitude,
                                                path[-1].latitude, path[-1].longitude)
        new_path.append(home_final)

        set_best_path(new_path)

    for i in range(len(breweries)):
        if not breweries[i].visited:
            distance = distance_traveled + graph_of_distances[curr_pos][i]

            if distance + breweries[i].distance_to_home > max_distance:
                continue

            breweries[i].visited = True
            path.append(breweries[i])

            tsp_rec(breweries, distance, i, path, graph_of_distances)

            path.remove(breweries[i])
            breweries[i].visited = False
    return


def get_distinct_beer(path):
    beer = []
    for i in path:
        for j in i.beer:
            beer.append(j)
    unique_beer = list(set(beer))
    return len(unique_beer)


def get_total_distance(path):
    distance = 0
    for i in range(len(path) - 1):
        distance += haversine(path[i].latitude, path[i].longitude, path[i + 1].latitude, path[i + 1].longitude)
    return distance


def main():
    breweries = ([15, 'Aktienbrauerei Kaufbeuren', 10.616100311279297000, 47.878101348876950000],
                 [26, 'Allguer Brauhaus AG Kempten', 10.569399833679200000, 47.748699188232420000],
                 [30, 'Alpirsbacher Klosterbru', 8.403100013732910000, 48.345699310302734000],
                 [37, 'Amstel Brouwerij', 4.890900135040283000, 52.373798370361330000],
                 [40, 'Andechser Klosterbrauerei', 11.185000419616700000, 47.977500915527344000],
                 [70, 'Bamberger Mahrs-Bru', 10.906700134277344000, 49.890098571777344000],
                 [74, 'Barfer - das kleine Brauhaus', 9.989899635314941000, 48.397899627685550000],
                 [88, 'Bayerische Staatsbrauerei Weihenstephan', 11.728799819946289000, 48.395198822021484000],
                 [103, 'Berliner Kindl Brauerei AG', 13.429300308227539000, 52.479301452636720000],
                 [104, 'Berliner-Kindl-Schultheiss-Brauerei', 13.411399841308594000, 52.523399353027344000],
                 [109, 'Bierbrouwerij Bavaria', 5.597700119018555000, 51.516300201416016000],
                 [110, 'Bierbrouwerij De Koningshoeven', 5.128499984741211000, 51.543998718261720000],
                 [110, 'Bierbrouwerij De Koningshoeven', 5.128499984741211000, 51.543998718261720000],
                 [111, 'Bierbrouwerij St.Christoffel', 6.051499843597412000, 51.168399810791016000],
                 [125, 'Binding Brauerei AG', 8.691300392150879000, 50.094299316406250000],
                 [127, 'Birra Moretti', 13.226900100708008000, 46.059700012207030000],
                 [131, 'Bitburger Brauerei', 6.522699832916260000, 49.973999023437500000],
                 [156, 'BOSS Browar Witnica S.A.', 14.900400161743164000, 52.673900604248050000],
                 [167, 'Brasserie DAchouffe', 5.744200229644775000, 50.150699615478516000],
                 [175, 'Brasserie de lAbbaye Val-Dieu', 5.822000026702881000, 50.704601287841800000],
                 [192, 'Brasserie Fantme', 5.512700080871582000, 50.285999298095700000],
                 [203, 'Brasseries Kronenbourg', 7.714900016784668000, 48.592998504638670000],
                 [204, 'Brauerei & Gasthof zur Krone', 9.588800430297852000, 47.671501159667970000],
                 [205, 'Brauerei Aying Franz Inselkammer KG', 11.780799865722656000, 47.970600128173830000],
                 [206, 'Brauerei Beck', 8.790100097656250000, 53.078701019287110000],
                 [207, 'Brauerei C. & A. Veltins GmbH & Co.', 8.125900268554688000, 51.305500030517580000],
                 [208, 'Brauerei Fssla', 10.885499954223633000, 49.894199371337890000],
                 [209, 'Brauerei Gbr. Maisel KG', 11.565899848937988000, 49.947700500488280000],
                 [210, 'Brauerei Grieskirchen AG', 13.829199790954590000, 48.235099792480470000],
                 [211, 'Brauerei Gss', 15.094699859619140000, 47.362499237060550000],
                 [212, 'Brauerei Herrenhausen', 9.681400299072266000, 52.393501281738280000],
                 [213, 'Brauerei Hrle', 10.023900032043457000, 47.824298858642580000],
                 [214, 'Brauerei Hrlimann', 8.524499893188477000, 47.364200592041016000],
                 [216, 'Brauerei Leibinger', 9.621500015258789000, 47.781799316406250000],
                 [217, 'Brauerei Locher AG', 9.413499832153320000, 47.330101013183594000],
                 [218, 'Brauerei Reissdorf', 6.994400024414062500, 50.875301361083984000],
                 [219, 'Brauerei Schtzengarten', 9.379400253295898000, 47.430099487304690000],
                 [220, 'Brauerei Schumacher', 6.785299777984619000, 51.221599578857420000],
                 [221, 'Brauerei Schwelm', 7.293600082397461000, 51.284698486328125000],
                 [222, 'Brauerei Spezial', 10.885499954223633000, 49.894199371337890000],
                 [223, 'Brauerei und Altbierkche Pinkus Mller', 7.621399879455566000, 51.965698242187500000],
                 [225, 'Brauereigasthof Adler', 9.399600028991700000, 48.077800750732420000],
                 [228, 'Brauhaus Faust', 9.249199867248535000, 49.699298858642580000],
                 [229, 'Brauhaus Johann Albrecht - Dsseldorf', 6.751599788665771500, 51.240398406982420000],
                 [230, 'Brauhaus Johann Albrecht - Konstanz', 9.175000190734863000, 47.665100097656250000],
                 [232, 'Brauhaus Sion', 6.959400177001953000, 50.939399719238280000],
                 [233, 'Brauhaus Sternen', 8.900600433349610000, 47.558498382568360000],
                 [234, 'Brausttte der Steirerbrau Aktiengesellschaft', 15.441699981689453000, 47.067901611328125000],
                 [238, 'Brennerei-Distillerie Radermacher', 6.122000217437744000, 50.671798706054690000],
                 [245, 'Brewery Budweiser Budvar', 14.475000381469727000, 48.973899841308594000],
                 [246, 'Brewery Corsendonk', 4.988999843597412000, 51.314399719238280000],
                 [261, 'Brouwerij t IJ', 4.926300048828125000, 52.366600036621094000],
                 [270, 'Brouwerij De Achelse Kluis', 5.489600181579590000, 51.298599243164060000],
                 [280, 'Brouwerij der Sint-Benedictusabdij de Achelse Kluis', 5.546000003814697000,
              51.251499176025390000],
                 [286, 'Brouwerij Kerkom', 5.165999889373779000, 50.776298522949220000],
                 [293, 'Brouwerij Sint-Jozef', 5.646399974822998000, 51.116798400878906000],
                 [307, 'Browar Okocim', 20.600299835205078000, 49.962200164794920000],
                 [309, 'Browar Zywiec', 19.174200057983400000, 49.662200927734375000],
                 [312, 'Bryggeriet lfabrikken', 12.116100311279297000, 56.074600219726560000],
                 [344, 'Carlsberg Bryggerierne', 12.539299964904785000, 55.666698455810550000],
                 [345, 'Carlsberg Sverige AB', 12.540499687194824000, 56.900199890136720000],
                 [386, 'Clner Hofbrau Frh', 6.956999778747559000, 50.940101623535156000],
                 [429, 'De Friese Bierbrouwerij Us Heit', 5.534200191497803000, 53.060600280761720000],
                 [448, 'Diebels Privatbrauerei', 6.421299934387207000, 51.533100128173830000],
                 [460, 'Dortmunder Actien Brauerei  DAB', 7.469200134277344000, 51.529800415039060000],
                 [465, 'Dreher Srgyrak Zrt.', 19.142200469970703000, 47.492099761962890000],
                 [480, 'Eder & Heylands', 9.071499824523926000, 49.921100616455080000],
                 [484, 'Einbecker Brauhaus AG', 9.864299774169922000, 51.816200256347656000],
                 [511, 'Ettaler Klosterbetriebe Abteilung Brauerei & Destillerie', 11.094200134277344000,
              47.569000244140625000],
                 [534, 'Flensburger Brauerei', 9.435500144958496000, 54.778999328613280000],
                 [558, 'Friesisches Brauhaus zu Jever', 7.901599884033203000, 53.575500488281250000],
                 [561, 'Frstliche Brauerei Thurn Und Taxis Regensburg', 12.091300010681152000, 49.015598297119140000],
                 [567, 'Gasthaus & Gosebrauerei Bayerischer Bahnhof', 12.371399879455566000, 51.339698791503906000],
                 [568, 'Gasthaus-Brauerei Max & Moritz', 9.606100082397461000, 47.606399536132810000],
                 [569, 'Gasthof-Brauerei zum Frohsinn', 9.430000305175781000, 47.517101287841800000],
                 [570, 'Gatz Brauhaus', 6.775700092315674000, 51.224899291992190000],
                 [573, 'Gilde Brauerei', 9.753199577331543000, 52.354400634765625000],
                 [616, 'Grolsche Bierbrouwerij', 6.816299915313721000, 52.208099365234375000],
                 [619, 'Gulpener Bierbrouwerij', 5.921299934387207000, 50.810901641845700000],
                 [621, 'Hacker-Pschorr Bru', 11.580200195312500000, 48.139099121093750000],
                 [628, 'Hannen Brauerei', 6.442100048065185500, 51.191299438476560000],
                 [639, 'Hasserder Brauerei', 10.753299713134766000, 51.843898773193360000],
                 [640, 'Hausbrauerei Zum Schlssel', 6.774499893188477000, 51.226100921630860000],
                 [649, 'Heineken Switzerland', 8.730199813842773000, 47.507701873779300000],
                 [650, 'Heller Bru Trum', 10.885299682617188000, 49.891998291015625000],
                 [659, 'Hirschbru Privatbrauerei Hss', 10.279000282287598000, 47.513198852539060000],
                 [661, 'Hochstiftliches Brauhaus in Bayern', 9.772399902343750000, 50.394901275634766000])

    beers = ([('St. Martin Doppelbock',), ('Jubiläums German Pils',)],
             [('Cambonator Doppelbock',), ('Winterfestival'), ('BayrischHell',)],
             [('Spezial',), ('Pils',)],
             [('Amstel Light',)],
             [('Doppelbock Dunkel',), ('Weißbier Dunkel',), ('Hell',)],
             [('Der Weisse Bock',), ('Hell',), ('Pilsner',), ('Ungespundet Lager Hefetrub',), ('Christmas Bock',), ('Weisse',), ('Hefeweißbier',)],
             [('Schwarze',), ('Blonde',), ('Rotgold-Pils',)],
             [('Festbier',), ('Kristall Weissbier',), ('Hefeweissbier Dunkel',), ('Original Lager',), ('Korbinian',), ('Hefe Weissbier',)],
             [('Weisse',)],
             [('Original Berliner Weisse',)],
             [('De Horste Vermeer Traditional Dutch Ale',), ('Hollandia',), ('Holland Beer',)],
             [('Quadrupel',), ('Tripel',), ('Dubbel',), ('La Trappe Quadrupel 2000/2001',), ('La Trappe Tripel',),
              ('La Trappe Enkel / La Trappe Blond',), ('La Trappe Dubbel',), ("Tilburg's Dutch Brown Ale",)],
             [('Quadrupel',), ('Tripel',), ('Dubbel',), ('La Trappe Quadrupel 2000/2001',), ('La Trappe Tripel',),
              ('La Trappe Enkel / La Trappe Blond',), ('La Trappe Dubbel',), ("Tilburg's Dutch Brown Ale",)],
             [('Robertus',), ('Christoffel Blond',)],
             [('Lager',)],
             [('La Rossa',), ('Birra Moretti La Rossa',)],
             [('Premium Beer',)],
             [('Mocny BOSS / BOSS Beer',), ('Porter Czarny Boss / Black BOSS Porter',)],
             [('Houblon',), ('McChouffe',), ('La Chouffe Golden Ale',), ('Chouffe-Bok',), ('Bière de Mars',)],
             [('Winter',), ('Grand Cru',), ('Triple',), ('Blonde',), ('Brune / Brown',)],
             [('Strange Ghost',), ('Chocolat',), ('Dark White',), ('Speciale Noël',)],
             [('1664',)],
             [('Coronator Helle Doppelbock',), ('See-Weizen Bio-Hefeweizen',), ('Kellerpils',), ('Pils',), ('Kronenbier',)],
             [('Ur-Weisse',), ('Altbairisch Dunkel',), ('Oktober Fest - Märzen',), ('Bräu-Weisse',), ('Jahrhundert-Bier',), ('Celebrator',)],
             [('St.Pauli Girl Special Dark',), ('St.Pauli Girl Beer',), ('Beer',), ('Dark',), ('Haacke-Beck',), ('Oktoberfest',), ("Beck's Light",)],
             [('Pilsner',)],
             [('Lagerbier',), ('Zwergla',), ('Gold-Pils',), ('Weizla Hell',)],
             [("Maisel's Weisse Kristall",)],
             [('Jörger Weiße Hell',)],
             [('Dark Beer / Stiftsbräu',)],
             [('Weizen Bier',), ('Premium Pilsener',)],
             [('Dunkle Weisse',)],
             [('Hexen Bräu',)],
             [('Edel-Pils',), ('Hefe-Weizen',), ('Edel-Spezial',)],
             [('Leermond Bier',)],
             [('Kölsch',)],
             [('St. Galler Landbier',)],
             [('Alt',)],
             [('Pils',), ('Hefe-Weizen',)],
             [('Rauchbier Lager',), ('Rauchbier Weissbier',), ('Rauchbier Märzen',), ('Ungespundetes',)],
             [('Jubilate Special Reserve Anniversary Ale',), ('Organic Ur Pils',), ('Obergärig / Münster Alt',), ('Organic Hefewizen',)],
             [('Zwickelbier',), ('Pils',), ('Spezial',)],
             [('Kräusen Naturtrüb',)],
             [('Kupfer',), ('Messing',)],
             [('Nickelbier',), ('Herbstbeer',), ('Weizen',), ('Kupfer',), ('Messing',)],
             [('Kölsch',)],
             [('Huusbier Schwarz',), ('Oktoberfest',), ('Weizentrumpf',), ('Honey Brown Ale',), ('Huusbier Hell',)],
             [('Gösser',)],
             [('Rader Ambrée',), ('Rader Blonde',)],
             [('Budweiser Budvar (Czechvar)',)],
             [('Christmas Ale',), ('Abbey Brown Ale / Pater',), ('Monk Pale Ale / Agnus Dei',), ('Monk Brown Ale',)],
             [('Zatte Amsterdamse Tripel',)],
             [('Trappist Extra',), ('Trappist Bruin Bier / Bière Brune',), ('Trappist Blond',)],
             [('Achel Blond 5°',), ('Achel Bruin 5°',), ('Achel Blond 8°',), ('Achel Bruin 8°',), ('Achel Trappist Extra',)],
             [('Bloesem Bink',), ('Winterkoninkse',)],
             [('Limburgse Witte',)],
             [('Okocim Porter',), ('O.K. Beer',)],
             [('Porter',), ('Krakus',)],
             [('Porter',)],
             [('Elephant',), ('47 Bryg',), ('Jacobsen Dark Lager',)],
             [('Carnegie Stark-Porter',), ('Falcon Lagrad Gammelbrygd',)],
             [('Kölsch',)],
             [('Us Heit Dubbel Tarwe Bier',)],
             [('German Premium Dark',), ('Alt',)],
             [('Traditional',), ('Original',), ('Hansa Imported Dortmunder',), ('Hansa Pils',)],
             [('Bak',), ('Dreher Classic',)],
             [('Schlappeseppl Export',)],
             [('Schwarzbier / Dunkel',), ('Ur-Bock Hell',)],
             [('Curator Dunkler Doppelbock',), ('Kloster Dunkel',), ('Kloster Edel-Hell',)],
             [('Pilsener',), ('Flensburger Pilsner',)],
             [('Pilsener',)],
             [('Schierlinger Roggen',)],
             [('Gose',)],
             [('Hefeweizen',), ('Spezial',), ('Kellerpils',)],
             [('Maisbier',), ('Weizenbier',), ('Dunkel',), ('Hell',)],
             [('Pils',), ('Helles Naturtrub',), ('Alt',)],
             [('Ratskeller',), ('Lindener Spezial',), ('Pilsener',)],
             [('Grolsch Amber Ale',), ('Grolsch Premium Weizen',), ('Grolsch Dunkel Weizen',), ('Grolsch Pilsner Speciale',), ('Grolsch Premium Pilsner',)],
             [('Dort',), ('Mestreechs Aajt',)],
             [('Original Oktoberfest',), ('Alt Munich Dark',), ('Weisse',)],
             [('Alt',), ('Hannen Alt',)],
             [('Premium Pils',)],
             [('Altbier',)],
             [('Original Ittinger Klosterbräu',)],
             [('Schlenkerla Helles Lagerbier',), ('Aecht Schlenkerla Rauchbier Märzen',), ('Aecht Schlenkerla Rauchbier Weizen',), ('Aecht Schlenkerla Rauchbier Urbock',)],
             [('Neuschwansteiner Bavarian Lager',), ('Doppel-Hirsch Bavarian-Doppelbock',), ('Bavarian-Weissbier Hefeweisse / Weisser Hirsch',)],
             [('Will-Bräu Ur-Bock',)])

    breweries = merge_breweries_with_beers(list(breweries), list(beers))
    lat = 51.74250300
    lon = 19.43295600

    breweries = get_breweries_within_1000(lat, lon, breweries)
    home = Brewery([None, 'Home', lon, lat], [], 0, True)
    breweries[:0] = [home]

    graph = make_graph(breweries)

    started = datetime.now()

    path = []

    tsp_rec(breweries, 0, 0, path, graph)

    ended = datetime.now()

    for brew in best_path:
        print(brew)

    print(get_total_distance(best_path))

    print('\n')

    print('\ndone')

    print("Started =", started)
    print("Ended =", ended)


if __name__ == '__main__':
    main()
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Have you profiled the code to see where the bottlenecks are? Have you tried writing it in a non-interpretive language such as C++ to see what the difference in speed is? \$\endgroup\$ – pacmaninbw May 24 '20 at 17:17
  • 1
    \$\begingroup\$ @pacmaninbw I tried to write this code in GO and it works more than 50 times faster. I wound a solution (it would be a solution if I could understand it). This a document \$\endgroup\$ – Sam May 28 '20 at 18:49
10
\$\begingroup\$

Criticisms

Datatypes

Your data types own data they should not own. A Brewery has an identity, a location, and a set of beer it brews. It should not have a "distance to home" parameter, or a "visited" flag. Distance to who's home? Visited by whom?

Usability

haversine() is not a very usable function; it requires 4 parameters. It would make more sense to pass in two Location objects, and get the distance between those locations. 2 parameters is easier to use than 4.

Configuration

max_distance is hard-coded in the tsp_rec function. But from the problem description, it sounds like you change this value between 1000 and 2000. If so, why is it hard-coded and not a parameter?

get_breweries_within_1000() is even more brittle. The function name, and local variables include the distance limit. If you want to change the limit, what do you change? Just the hard-coded number, or the variable names and/or the function name too?

Global Variables

Global variables are to be eschewed, assiduously. They increase code coupling, and decrease usability and testability of code. It becomes harder to reason about the extent of the effects of a function, because global variables may be changed by any function, so one must examine each and every function to determine if it affects or is affected by a change elsewhere.

    tsp_rec(breweries, 0, 0, path, graph)

    for brew in best_path:
        print(brew)

Is it obvious that tsp_rec(...) has changed the value of best_path? If the function were instead written to return the results directly, it would improve understandability and minimize side effects.

Don't pass in unnecessary arguments

Consider again the tsp_rec(...) function:

    path = []
    tsp_rec(breweries, 0, 0, path, graph)

At the top level, it must be called with a distance_traveled, a curr_pos and a path. But is that a "friendly" interface design? Why require the user of the function to lookup the calling requirements and pass in the appropriate initial conditions when every caller of the top level would have to do exactly the same thing? It would make more sense to provide a clean top-level function, and use a recursive helper function. The top-level function would set up the initial top level call environment. Eg)

def _tsp_rec(...):
    # Verbatim copy of original tsp_rec() function

def tsp_rec(breweries: List[Brewery], graph_of_distances):
    path = []
    return _tsp_rec(breweries, 0, 0, path, graph_of_distances)

Also note: [Brewery] was not the correct type-hint; List[Brewery] is.


Improvements

Locations

A location is a nice data type to start with. It should contain immutable data; if you want a different location, you create a different location object.

from dataclasses import dataclass

@dataclass(frozen=True)
class Location:
    latitude: float
    longitude: float

Pretty straight forward object, but we can make it prettier with some extra class members:

    @staticmethod
    def deg_min_sec(degrees: float, positive: str, negative: str) -> str:
        suffix = positive if degrees >= 0 else negative
        degrees, minutes = divmod(abs(degrees), 1)
        minutes, seconds = divmod(minutes * 60, 1)
        return f"{degrees:.0f}\u00B0{minutes:.0f}\u2032{seconds*60:.3f}\u2033 {suffix}"

    def __str__(self):
        return self.deg_min_sec(self.latitude, "N", "S") + ", " + self.deg_min_sec(self.longitude, "E", "W")

Example:

>>> print(Location(51.74250300, 19.43295600))
51°44′33.011″ N, 19°25′58.642″ E

Now that we have Location objects, we can compute the distance between them. We could write a haversine(loc1, loc2) function, but normally to figure out distances, we take the end point and subtract the start point, so why not define a subtraction operator for Location objects, which returns the distance?

class Location:

    # ... other members ...

    def __sub__(self, other: Location) -> float:
        """
        Return the distance between two locations
        """

        lon1, lat1, lon2, lat2 = map(radians, [self.longitude, self.latitude, other.longitude, other.latitude])

        dlon = lon2 - lon1
        dlat = lat2 - lat1
        a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
        c = 2 * asin(sqrt(a))
        r = 6371
        return c * r

Breweries

Like a Location, a Brewery should be immutable data, describing the identity, the location, and the types of brews it produces:

from typing import Set

@dataclass(frozen=True)
class Brewery:
    brewery_id: int
    name: str
    location: Location
    brews: Set[str]

    def __str__(self):
        return f"{self.name} ({self.location})"

    def __hash__(self):
        return self.brewery_id

Note: I'm using a set for the types of brews a brewery produces. Since you want the most unique beer types from the tour, it is useful to collect the brews on the tour into a set, which naturally and efficiently eliminates duplicates. Starting with a set in each brewery makes this even easier.

Also note: I'm using the brewery_id as a hash value. Since the data is immutable (frozen=True), it can be used as key in dictionaries. But hashing all the data together to generate a hash is overkill, when the brewery_id is already a unique integer.

To create your list of breweries, I used your original data (with a comma added after 'Winterfestival' to make it into a tuple like the rest of the data)

breweries = ([15, 'Aktienbrauerei Kaufbeuren', 10.616100311279297000, 47.878101348876950000],
             [26, 'Allguer Brauhaus AG Kempten', 10.569399833679200000, 47.748699188232420000],
             ...)

beers = ([('St. Martin Doppelbock',), ('Jubiläums German Pils',)],
         [('Cambonator Doppelbock',), ('Winterfestival',), ('BayrischHell',)],
         ...)

And this code:

breweries = [Brewery(id_, name, Location(latitude, longitude), set(brew for brew, in brews))
             for (id_, name, longitude, latitude), brews in zip(breweries, beers)]

Example:

>>> breweries[0]
Brewery(brewery_id=15, name='Aktienbrauerei Kaufbeuren', location=Location(latitude=47.87810134887695, longitude=10.616100311279297), brews={'St. Martin Doppelbock', 'Jubiläums German Pils'})

Main

To drive the program, I used this code:

if __name__ == '__main__':
    breweries = (... omitted ...)
    beers = (... omitted ...)

    breweries = [Brewery(id_, name, Location(latitude, longitude), set(brew for brew, in brews))
                 for (id_, name, longitude, latitude), brews in zip(breweries, beers)]

    path, brews, distance = travelling_brewmaster(breweries, Location(51.74250300, 19.43295600), 1750)

    print("Path:    ", len(path), "breweries")
    for location in path:
        print("         ", location)
    print("Distance:", distance)
    print("# brews: ", brews)

Notice how I am passing the home location and the maximum travel distance as arguments to travelling_brewmaster(), instead of having these hard-coded in the program.

Travelling Brew Master

Let's begin writing our travelling_brewmaster function:

def travelling_brewmaster(breweries: List[Brewery], home: Location,
                          max_distance: float) -> Tuple[List[Brewery], int, float]:

    def track_best(path: List[Brewery], brews: Set[str], distance:float) -> None:
        nonlocal best_path, best_brews, best_distance

        num_brews = len(brews)
        if num_brews > best_brews or num_brews == best_brews and distance < best_distance:
            best_path = path
            best_brews = num_brews
            best_distance = distance

    best_path = []
    best_brews = 0
    best_distance = inf

    # ... more code here ...

    return best_path, best_brews, best_distance

We can immediately see several of the points raised above taking shape. First, travelling_brewmaster(...) takes in only the list of breweries, a home location, and a maximum distance to travel. No extra initial values the caller needs to supply.

Second, it will be returning the best_path, best_distance, and best_brews, so the function should not be affecting any global state. How does it achieve that? It declares those as local variables, and then uses a track_best() inner function with nonlocal variable references to update those variables as better paths are found.

A Bridge Too Far

Again, your get_breweries_within_1000 function was oddly specific; but it was doing the right thing. Any brewery beyond max_distance/2 from the home location cannot be visited and returned from within the distance limitation. We just need to shorten it, and make it more general.

First, we want the distances from home to every brewery. We'll need this more than once, so let's store it:

    distance_to_home = { brewery: brewery.location - home for brewery in breweries }

Since I've added a __hash__ method to the immutable Brewery class, the breweries make perfect dictionary keys; we don't have to look up distances by indices. This allows us to ...

    breweries = [brewery for brewery in breweries if distance_to_home[brewery] * 2 <= max_distance]

... remove any brewery which is clearly too far away to visit from breweries, which can/will change each brewery's index number. If we don't find any breweries within that limit, there is no solution.

    if len(breweries) == 0:
        raise ValueError("No solution")

Once we have our list of candidate breweries, we can compute the distance between any brewery pair, as a dictionary of dictionaries:

    distances = { brewery1: {brewery2: brewery1.location - brewery2.location for brewery2 in breweries}
                  for brewery1 in breweries }

Halving Your Work Load

Your travelling brewmaster exhaustively travels each brewery path combination. This means your brewmaster will travel both:

home -> brewery #1 -> brewery #7 -> brewery #4 -> brewery #3 -> home

and

home -> brewery #3 -> brewery #4 -> brewery #7 -> brewery #1 -> home

but conclude that both routes result in the same number of brews, and the second path is the same length as the first. Clearly, this is a waste of time. If you can avoid testing the reverse routes, you can eliminate half of the work and speed the search up be a factor of two.

How can we ensure we don't look at the reverse loops? One way is to pick pairs of breweries for the first and last brewery to visit, without selecting the reverse pair. If we choose brewery i (0 < i < n) for the first brewery, then choosing brewery j, where j > i, is sufficient to ensure no reverse pairs are chosen.

    for i, last in enumerate(breweries):

        # ... more code here ...

        for j, first in enumerate(breweries[i+1:], i+1)

            # ... more code here ...

I said we don't need the index numbers above, but I'm looping over the breweries and keeping track of the index numbers. Why? So we can simply determine what the "rest" of the breweries are:

            rest = breweries[:i] + breweries[i+1:j] + breweries[j+1:]

These are the candidates for visiting between the first and the last.

Searching

A simplistic recursive inner search helper might look like this:

    # Recursive helper
    def helper(path, distance, beers, breweries):

        last = path[0]
        prev = path[-1]

        for i, brewery in enumerate(breweries):
            distance2 = distance + distances[prev][brewery]
            loop_distance = distance2 + distances[last][brewery]

            if loop_distance <= max_distance:
                brews = beers | brewery.brews
                path2 = path + [brewery]

                track_best(path2, brews, loop_distance)

                rest = breweries[:i] + breweries[i+1:]
                if rest:
                    helper(path2, distance2, brews, rest)

Since it is an inner function, like track_best, it has access to the outer function variables, like the distances dictionary and max_distance.

It could be driven by the last/first pair loop, above:

    for i, last in enumerate(breweries):

        path = [last]
        distance = distance_to_home[last]
        track_best(path, last.brews, distance * 2)

        for j, first in enumerate(breweries[i+1:], i+1):
            path2 = path + [first]
            distance2 = distance + distance_to_home[first]
            loop_distance = distance2 + distances[last][first]

            if loop_distance <= max_distance:

                brews = first.brews | last.brews
                track_best(path2, brews, loop_distance)
                rest = breweries[:i] + breweries[i+1:j] + breweries[j+1:]

                helper(path2, distance2, brews, rest)


    best_path.append(best_path.pop(0))
    return best_path, best_brews, best_distance

For convenience, we've added the last brewery as the first element of the path / best_path list, so when we return our best path, we need to move it back to the end of the list to compensate.

Unfortunately, this is very slow. We need to add some optimizations

Optimization

Every time we add a brewery to the path, the path distance gets longer. Travel to any remaining brewery from the most recently added brewery and back to the last brewery must not exceed max_distance. So the rest of the breweries can be filtered to exclude any candidate which cannot be reached within the max_distance constraint.

            rest = [candidate for candidate in rest
                     if distance2 + distances[first][candidate] + distances[last][candidate] <= max_distance]

We can also filter out any candidate which doesn't add any new brews to our mix:

            rest = [candidate for candidate in rest
                     if not candidate.brews <= brews]

And we can do both filter steps at once:

            rest = [candidate for candidate in rest
                     if distance2 + distances[first][candidate] + distances[last][candidate] <= max_distance
                     and not candidate.brews <= brews]

A similar filtering must be performed in the helper() method, using the brewery that was just added.

                rest = [candidate for candidate in rest
                        if distance2 + distances[brewery][candidate] + distances[last][candidate] <= max_distance
                        and not candidate.brews <= brews]

Performance Timing

datetime.now() is not the most accurate method to use for timing. time.perf_counter() is far superior. A decorator may be used to easily add (and later remove) time-profiling of a specific function:

from time import perf_counter

def timed(func):
    def wrapper(*argv, **kwargs):
        start = perf_counter()
        result = func(*argv, **kwargs)
        end = perf_counter()
        print(f"{func.__name__}: {end-start:.2f}")
        return result
    return wrapper

Usage:

@timed
def travelling_brewmaster(breweries: List[Brewery], home: Location, max_distance: float) -> Tuple[List[Brewery], int, float]:
    ...

Reworked Code

Here is my completely reworked travelling brewmaster code:

from math import radians, cos, sin, asin, sqrt, inf
from time import perf_counter
from dataclasses import dataclass
from typing import List, Set, Tuple

def timed(func):
    def wrapper(*argv, **kwargs):
        start = perf_counter()
        result = func(*argv, **kwargs)
        end = perf_counter()
        print(f"{func.__name__}: {end-start:.2f}")
        return result
    return wrapper

@dataclass(frozen=True)
class Location:
    latitude: float
    longitude: float

    @staticmethod
    def deg_min_sec(degrees: float, positive: str, negative: str) -> str:
        suffix = positive if degrees >= 0 else negative
        degrees, minutes = divmod(abs(degrees), 1)
        minutes, seconds = divmod(minutes * 60, 1)
        return f"{degrees:.0f}\u00B0{minutes:.0f}\u2032{seconds*60:.3f}\u2033 {suffix}"

    def __str__(self):
        return self.deg_min_sec(self.latitude, "N", "S") + ", " + self.deg_min_sec(self.longitude, "E", "W")

    def __sub__(self, other):
        lon1, lat1, lon2, lat2 = map(radians, [self.longitude, self.latitude, other.longitude, other.latitude])

        dlon = lon2 - lon1
        dlat = lat2 - lat1
        a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
        c = 2 * asin(sqrt(a))
        r = 6371
        return c * r

@dataclass(frozen=True)
class Brewery:
    brewery_id: int
    name: str
    location: Location
    brews: Set[str]

    def __str__(self):
        return f"{self.name} ({self.location})"

    def __hash__(self):
        return self.brewery_id

@timed
def travelling_brewmaster(breweries: List[Brewery], home: Location, max_distance: float) -> Tuple[List[Brewery], int, float]:

    def track_best(path: List[Brewery], brews: Set[str], distance:float) -> None:
        nonlocal best_path, best_brews, best_distance

        num_brews = len(brews)
        if num_brews > best_brews or num_brews == best_brews and distance < best_distance:
            best_brews = num_brews
            best_distance = distance
            best_path = path # + [last]


    def helper(path, distance, beers, breweries):

        last = path[0]
        prev = path[-1]

        for i, brewery in enumerate(breweries):
            distance2 = distance + distances[prev][brewery]
            loop_distance = distance2 + distances[last][brewery]     
            brews = beers | brewery.brews
            path2 = path + [brewery]

            track_best(path2, brews, loop_distance)

            rest = breweries[:i] + breweries[i+1:]
            rest = [candidate for candidate in rest
                    if distance2 + distances[brewery][candidate] + distances[last][candidate] <= max_distance
                    and not candidate.brews <= brews]
            if rest:
                helper(path2, distance2, brews, rest)

    distance_to_home = { brewery: brewery.location - home for brewery in breweries }
    breweries = [brewery for brewery in breweries if distance_to_home[brewery] * 2 <= max_distance]

    print(f"{len(breweries)} breweries within {max_distance} driving limit.")
    if len(breweries) == 0:
        raise ValueError("No solution")

    distances = { brewery1: {brewery2: brewery1.location - brewery2.location for brewery2 in breweries}
                  for brewery1 in breweries }

    best_path = []
    best_brews = 0
    best_distance = inf

    for i, last in enumerate(breweries):

        path = [last]
        distance = distance_to_home[last]
        track_best(path, last.brews, distance * 2)

        for j, first in enumerate(breweries[i+1:], i+1):
            distance2 = distance + distance_to_home[first]
            loop_distance = distance2 + distances[last][first]
            if loop_distance > max_distance or first.brews <= last.brews:
                continue

            path2 = path + [first]
            brews = first.brews | last.brews
            track_best(path2, brews, loop_distance)
            rest = breweries[:i] + breweries[i+1:j] + breweries[j+1:]
            rest = [candidate for candidate in rest
                     if distance2 + distances[first][candidate] + distances[last][candidate] <= max_distance
                     and not candidate.brews <= brews]
            if rest:
                helper(path2, distance2, brews, rest)

    best_path.append(best_path.pop(0))
    return best_path, best_brews, best_distance


if __name__ == '__main__':

    breweries = ( ... omitted for brevity ...)
    beers = (... omitted for brevity ...)

    breweries = [Brewery(id_, name, Location(latitude, longitude), set(brew for brew, in brews))
                 for (id_, name, longitude, latitude), brews in zip(breweries, beers)]

    path, brews, distance = travelling_brewmaster(breweries, Location(51.74250300, 19.43295600), 1600)

    print("Path:    ", len(path), "breweries")
    for location in path:
        print("         ", location)
    print("Distance:", distance)
    print("# brews: ", brews)

And here is the output, which takes a half-second with a max_distance of 1600:

40 breweries within 1600 driving limit.
travelling_brewmaster: 0.49
Path:     10 breweries
          Brewery Budweiser Budvar (48°58′26.039″ N, 14°28′30.001″ E)
          Brauerei Grieskirchen AG (48°14′6.359″ N, 13°49′45.119″ E)
          Brauerei Aying Franz Inselkammer KG (47°58′14.160″ N, 11°46′50.880″ E)
          Hacker-Pschorr Bru (48°8′20.757″ N, 11°34′48.721″ E)
          Bayerische Staatsbrauerei Weihenstephan (48°23′42.716″ N, 11°43′43.679″ E)
          Heller Bru Trum (49°53′31.194″ N, 10°53′7.079″ E)
          Brauerei Fssla (49°53′39.118″ N, 10°53′7.800″ E)
          Brauerei Spezial (49°53′39.118″ N, 10°53′7.800″ E)
          Bamberger Mahrs-Bru (49°53′24.355″ N, 10°54′24.120″ E)
          Brauerei Gbr. Maisel KG (49°56′51.722″ N, 11°33′57.239″ E)
Distance: 1585.2867749820152
# brews:  36
\$\endgroup\$
6
  • \$\begingroup\$ Wow... Thanks for these tips. I will try to improve my code and update it in a original post! \$\endgroup\$ – Sam May 27 '20 at 11:43
  • 2
    \$\begingroup\$ Great answer! The Brewery dataclass should have an __eq__ method to compare such that same self.brewery_ids return equality, so that two breweries with the same hash also compare equal. But that is not required by the hash implementation; it only requires that objects which compare equal have the same hash, which they do in your code (breweries are only equal to themselves, which makes sense). \$\endgroup\$ – Alex Povel May 30 '20 at 19:45
  • 1
    \$\begingroup\$ You were very generous with your efforts. \$\endgroup\$ – Paulb May 30 '20 at 20:53
  • 2
    \$\begingroup\$ @AlexPovel dataclass defaults are (init=True, repr=True, eq=True, order=False, unsafe_hash=False, frozen=False), so by default will automatically define the __eq__ method, so two distinct objects with the same values will compare as equal. \$\endgroup\$ – AJNeufeld May 30 '20 at 21:33
  • \$\begingroup\$ @AJNeufeld Oh very nice, thank you for clarifying. \$\endgroup\$ – Alex Povel May 31 '20 at 10:53
2
\$\begingroup\$

Some of these are not performance improvements but are improvements nonetheless.

Brewery constructor

def __init__(self, _brewery, beer, distance=0, visited=False):
    self.beer = beer
    self.id = _brewery[0]
    self.name = _brewery[1]
    self.longitude = _brewery[2]
    self.latitude = _brewery[3]
    self.distance_to_home = distance
    self.visited = visited
...
    breweries_list.append(Brewery(breweries[i], beers[i]))

is problematic, particularly around the assumptions that _brewery makes. Unpack it elsewhere, i.e.

def __init__(
    self, 
    brewery_id: int, 
    name: str,
    longitude: float,
    latitude: float,
    beers: Sequence[str],
    distance: float=0, 
    visited: bool=False,
):
    self.brewery_id, self.name, self.longitude, self.latitude, self.beers, self.distance, self.visited = (
        brewery_id, name, longitude, latitude, beers, distance, visited,
    )
...
    breweries_list.append(Brewery(
        *breweries[i],
        beers=beers[i],
    ))

Other things to note:

  • Use type hints
  • Do not use id as that shadows a built-in
  • I'm unclear on why you don't just store beers as a tuple on brewery. You can do away with merge_breweries_with_beers altogether and just include the beer tuples in your main brewery database.

Database

Store it in a JSON file, not hard-coded into the source.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for your suggestions! I am using MariaDb for data, but I hardcoded it just for this question. \$\endgroup\$ – Sam May 24 '20 at 16:22
  • \$\begingroup\$ Fair enough. You should work on the current feedback, and then post a new question which shows the actual MariaDB calls. You will get better feedback on how to avoid that merge. \$\endgroup\$ – Reinderien May 24 '20 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.