4
\$\begingroup\$

I took a code test for acme transport company and was rejected. That's ok. I'm still learning how to code. I didn't get much feedback so that's a bit frustrating. Can anyone here provide tips on how to optimize this python code? I thought that I had done a pretty good job with it, had the correct answers, etc. But apparently there are some fatal flaws, at least according to acme transport co!

Here's the challenge:

Parse a text file so that we know the following:

  • how many cars were dropped in total?
  • which car had the longest single trip? How long was the trip?
  • what car had the longest cumulative distance? How long was that.

The text file is formatted like this:

  • timestamp, Integer, The time in seconds since the start of the simulation

  • id, String, The id of the associated vehicle, e.g. JK5T

  • event_type, String The type of the event is one of START_RIDE, END_RIDE, DROP

  • x, Double, The x coordinate of the location of where the event happened in the simulation

  • y, Double, The y coordinate of the location of where the event happened in the simulation

  • user_id, Integer, The id of the associated user or NULL if the event does not have an associated user

The first few lines of the file look like this:

302,OPN1,DROP,33.28280226855614,-87.88162047789511,NULL
305,OPN1,START_RIDE,33.28280226855614,-87.88162047789511,4204
419,G2I0,DROP,-28.367411419413685,23.567421582328606,NULL
426,OPN1,END_RIDE,7.563016232237587,91.97004351346015,4204
428,LQBF,DROP,-50.50579634246066,-54.53980771216895,NULL
441,5HQH,DROP,-70.05156581770649,36.8358644984674,NULL

For my code I import a library called shapely that helps determine distances:

import csv
from shapely.geometry import Point
from collections import defaultdict



def main():
        myDict = defaultdict(dict)
        aDict = {}
        totalDrops = 0
        maxCar = None
        with open('events.txt') as f:
            reader = csv.reader(f)
            for row in reader:
                if row[2] == 'DROP':
                    totalDrops += 1 
                    myDict[row[1]]['drop'] = Point(float(row[3]), float(row[4]))
                if row[2] == 'START_RIDE':
                    myDict[row[1]]['start_ride'] = Point(float(row[3]), float(row[4]))
                if row[2] == 'END_RIDE':
                    singleTripDistance = myDict[row[1]]['drop'].distance(Point(float(row[3]), float(row[4])))
                    distanceTraveled = myDict[row[1]]['start_ride'].distance(Point(float(row[3]), float(row[4])))
                    aDict[row[1]] = singleTripDistance
                    if not maxCar:
                        maxCar = row[1]
                    if 'allDistances' not in myDict[row[1]]:
                        myDict[row[1]]['allDistances'] = distanceTraveled
                    else:
                        myDict[row[1]]['allDistances'] += distanceTraveled
                    if  myDict[row[1]]['allDistances'] > myDict[maxCar]['allDistances']:
                        maxCar = row[1]
            maxSingleTrip = max(zip(aDict.values(), aDict.keys()))
            print('There are ' + '' + str(totalDrops) + ' ' + 'total Drops.' + '\n' + 'The Car that ends up furthest away from its drop is:' + ' ' + str(maxSingleTrip[1]) + ' ' + 'and the distance is:' + ' ' + str(maxSingleTrip[0]) + '\n' + 'The Car with the highest total distance traveled is:' + ' ' + maxCar + ', ' + 'and the total distance is:' + ' ' +  str(myDict[maxCar]['allDistances']))
main()
\$\endgroup\$
3
\$\begingroup\$

What you did well

You used the csv module for parsing the CSV file, and you processed it in one pass. Your code is therefore reasonably efficient, and I wouldn't worry much about its performance.

Bugs

Your code reports "The Car that ends up furthest away from its drop is: …", but that is, in my interpretation, not the same as the longest single trip, which is what you were asked to calculate.

Concerns

Your data analysis code is mingled with the CSV parsing. That makes the code hard to read and hard to maintain.

The deeply nested dictionaries are hard to understand. What does myDict store? Its purpose is not apparent from its name. It's a two-level dictionary, where the first-level key is a vehicle_id, the second-level key is some attribute of that vehicle (the 'drop' coordinate, the 'start_ride' coordinate, or the 'allDistances' running total). You would be better off with three independent dictionaries. Better yet, as I've done below, define an Itinerary class instead.

What's aDict? It keeps track of the distance from each car's drop point to the endpoint of its last trip. Again, the variable name does not help.

The print() call is hard to read, in an excessively long line of code, with lots of str() casts and unnecessary string concatenations. In this situation, I would recommend f-strings (introduced in Python 3.6), or str.format().

Suggested solution

This solution reports the car that ends up the furthest from its drop point, as you did, rather than the longest single trip as requested.

The Shapely library is overkill; subclassing namedtuple with a .distance() method is all I need for a handy Point class. Euclidean distances can be calculated using math.hypot.

If you look at the data, you'll see that each car acts as a state machine. It is initialized with a DROP event. Thereafter, it alternates between START_RIDE and END_RIDE events. No traveling is allowed when a START_RIDE occurs; the car is always the same place as its preceding DROP or END_RIDE coordinates. In my Itinerary class, I've kept track of the .state of the car so that I can perform certain assertions, but it's only essential to keep track of the coordinates at each DROP and END_RIDE event.

The itineraries() function parses the CSV into one simple data structure: a dictionary mapping vehicle IDs to their itineraries. I've chosen to use fileinput.input() to accept the file on the command line or through sys.stdin without hard-coding the filename.

The data analysis is accomplished using built-in functions len() and max() with generator expressions. That is more expressive and less cumbersome than maintaining several intermediate results each time an END_RIDE event occurs.

from collections import namedtuple
import csv
import fileinput
from math import hypot
from operator import attrgetter

class Point(namedtuple('Point', 'x y')):
    def distance(self, other):
        """Euclidean distance between two points."""
        return hypot(self.x - other.x, self.y - other.y)

class Itinerary:
    def __init__(self, car, x, y):
        self.car = car
        self.coords = [Point(x, y)]
        self.state = 'DROP'
        self.cumul_dist = 0

    def start_ride(self, x, y):
        assert self.state in ('DROP', 'END_RIDE'), "Restarting unfinished ride"
        assert Point(x, y) == self.coords[-1], "Teleportation occurred"
        self.state = 'START_RIDE'

    def end_ride(self, x, y):
        assert self.state == 'START_RIDE', "Ending a ride that hasn't started"
        self.coords.append(Point(x, y))
        self.state = 'END_RIDE'
        self.cumul_dist += self.coords[-1].distance(self.coords[-2])

    @property
    def final_dist(self):
        return self.coords[-1].distance(self.coords[0])

def itineraries(f):
    cars = {}
    for timestamp, car, event_id, x, y, user_id in csv.reader(f):
        if event_id == 'DROP':
            assert car not in cars, "Dropping the same car twice"
            cars[car] = Itinerary(car, float(x), float(y))
        elif event_id == 'START_RIDE':
            cars[car].start_ride(float(x), float(y))
        elif event_id == 'END_RIDE':
            cars[car].end_ride(float(x), float(y))
    return cars

def main():
    cars = itineraries(fileinput.input()).values()
    drops = len(cars)
    furthest = max(cars, key=attrgetter('final_dist'))
    most_traveled = max(cars, key=attrgetter('cumul_dist'))
    print(f"""There are {drops} total drops.
The car that ends up furthest from its drop is {furthest.car}, at distance {furthest.final_dist}.
Car {most_traveled.car} travels the longest cumulative distance: {most_traveled.cumul_dist}.""")

if __name__ == '__main__':
    main()
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hm, fair enough. Apparently I can't even read today... \$\endgroup\$ – Graipher Aug 30 '18 at 14:01
2
\$\begingroup\$

Making the code easier to read with variables

Having all the accesses to row[something] everywhere makes the code hard to read and to update. A good idea could be to introduce variables with meaningful names. You'd get for instance x = row[3].

Also Python offers a concise way to do this: iterable unpacking.

In your case, you could write something like:

        timestamp, vehicle_id, event, x, y, user_id = row

And by using these variables instead of accessing row, your code is already much prettier (and may be slighly faster as well).

We could go further and also define:

        coord = Point(float(x), float(y))

Use if/else for mutually exclusive conditions

You check if event == 'DROP' then if event == 'START_RIDE'. Of course, at most one of these can be true. I can be a good habit to use elif in this case. Also, you can take this chance to add a case to handle unknown events.

def main():
    myDict = defaultdict(dict)
    aDict = {}
    totalDrops = 0
    maxCar = None
    with open('events.txt') as f:
        reader = csv.reader(f)
        for row in reader:
            timestamp, vehicle_id, event, x, y, user_id = row
            coord = Point(float(x), float(y))
            if event == 'DROP':
                totalDrops += 1 
                myDict[vehicle_id]['drop'] = coord 
            elif event == 'START_RIDE':
                myDict[vehicle_id]['start_ride'] = coord
            elif event == 'END_RIDE':
                singleTripDistance = myDict[vehicle_id]['drop'].distance(coord)
                distanceTraveled = myDict[vehicle_id]['start_ride'].distance(coord)
                aDict[vehicle_id] = singleTripDistance
                if not maxCar:
                    maxCar = vehicle_id
                if 'allDistances' not in myDict[vehicle_id]:
                    myDict[vehicle_id]['allDistances'] = distanceTraveled
                else:
                    myDict[vehicle_id]['allDistances'] += distanceTraveled
                if  myDict[vehicle_id]['allDistances'] > myDict[maxCar]['allDistances']:
                    maxCar = vehicle_id
            else:
                print("Unexpected event ", e)
        maxSingleTrip = max(zip(aDict.values(), aDict.keys()))
        print('There are ' + '' + str(totalDrops) + ' ' + 'total Drops.' + '\n' + 'The Car that ends up furthest away from its drop is:' + ' ' + str(maxSingleTrip[1]) + ' ' + 'and the distance is:' + ' ' + str(maxSingleTrip[0]) + '\n' + 'The Car with the highest total distance traveled is:' + ' ' + maxCar + ', ' + 'and the total distance is:' + ' ' +  str(myDict[maxCar]['allDistances']))
main()

Non-required dependency

You've used an external dependency to handle the logic computing the distance.

It is good to avoid the Not Invented Here syndrom and avoid re-inventing the wheel.

On the other hand, dependencies on external packages are sometimes undesirable because of the amount of code you are using/integrating with no or little knowledge about.

I do not know what was the point of view of the staff reviewing your code but maybe they'd have appreciated if you had defined a simple class like:

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def distance(self, other):
        dx = self.x - other.x
        dy = self.y - other.y
        return math.sqrt(dx*dx + dy*dy)

Add a bit of doc and/or tests and it makes for a first good impression.

Variable names

myDict is not a great variable names as it does not convey much meanings. Maybe vehicles would be better or vehicles_dict...

Also, there is a style guide in Python called PEP 8. It is a highly recommended read. Among other things, it advices to use snake_case for variable names (instead of camelCase).

More variables

It may be worth defining yet another variable to make the code more concise:

        vehicle = vehicles[vehicle_id]

Then, we'd have something like:

def main():
    vehicles = defaultdict(dict)
    aDict = {}
    total_drops = 0
    max_car = None
    with open('events.txt') as f:
        reader = csv.reader(f)
        for row in reader:
            timestamp, vehicle_id, event, x, y, user_id = row
            coord = Point(float(x), float(y))
            vehicle = vehicles[vehicle_id]
            if event == 'DROP':
                total_drops += 1 
                vehicle['drop'] = coord 
            elif event == 'START_RIDE':
                vehicle['start_ride'] = coord
            elif event == 'END_RIDE':
                singleTripDistance = vehicle['drop'].distance(coord)
                distanceTraveled = vehicle['start_ride'].distance(coord)
                aDict[vehicle_id] = singleTripDistance
                if not max_car:
                    max_car = vehicle_id
                if 'allDistances' not in vehicle:
                    vehicle['allDistances'] = distanceTraveled
                else:
                    vehicle['allDistances'] += distanceTraveled
                if  vehicle['allDistances'] > vehicles[max_car]['allDistances']:
                    max_car = vehicle_id
            else:
                print("Unexpected event ", e)
        maxSingleTrip = max(zip(aDict.values(), aDict.keys()))
        print('There are ' + '' + str(total_drops) + ' ' + 'total Drops.' + '\n' + 'The Car that ends up furthest away from its drop is:' + ' ' + str(maxSingleTrip[1]) + ' ' + 'and the distance is:' + ' ' + str(maxSingleTrip[0]) + '\n' + 'The Car with the highest total distance traveled is:' + ' ' + max_car + ', ' + 'and the total distance is:' + ' ' +  str(vehicles[max_car]['allDistances']))
main()

Data structure

From the way the problem is stated, it looks like the staff was interested in seeing which data structure you'd use and how.

Defining a dictionnary mapping vehicles identifiers to other data is definitly good into the right directions.

I may stop this review at any time. Don't be surprised if it looks unfinished, I may try to get back to this later.

| improve this answer | |
\$\endgroup\$

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.