Question $4$: shopAroundTown

The shopAroundTown$($orderList$,$ fruitTown, gasCost$)$ function takes as input a list of $($fruit$,$ numPounds$)$ pairs as in question $3,$ a town object, and a number representing the cost of gas per mile traveled, and determines the best route to take to fill the fruit order. A town object contains a list of shops and the distances between each pair of shops and from each shop to 'home' in miles. See the documentation in the file town.py for a more detailed description of the representation of a town object. A valid route must start and end at home, so function returns a list of shops such that the sum of the total gas cost accrued from starting at home, going to each shop in the list in order, and returning to home, plus the total cost of buying the necessary fruit at the stores on the list, is minimized.

This question has a few more working parts than the previous three. Fortunately, we've provided an implementation of the solution! Unfortunately, it doesn't work.

Our approach is simple: We start with our list of all shops in town. We get all subsets of this list of shops, and filter the list of subsets to only contain subsets of shops that are carrying all the fruit we are trying to purchase. We then make a list of all permutations of all of these subsets $($i$.$e$.$ all possible routes through all possible valid choices of stores$)$ and return the one which allows us to fill our order for the lowest cost. It's not the most clever algorithm $($it checks O$($n$!*2^$n$)$ routes where n is the number of shops$),$ but it gets the job done.

Using your newly acquired debugging skills $($using pdb or the debugging tool in vs code$),$ find the bugs in shopAroundTown.py$.$ You shouldn't have to make any major changes $($specifically$,$ there are four small changes, none of which require you to add or remove any lines$).$ Bugs may be in the functions shopAroundTown, getAllSubsets, and getAllPermutations.