Food Truck IEEEXtreme 10.0

about 5 years ago.

As cited in the description this problem was proposed by Nokia so I thought it will be hard however it was one of the easiest problems in the IEEEXtreme 10.

The problem consist of finding subscribers in radius r of a given GPS coordinate.

The information about the subscribers are given in the form

Date&Time,Latitude,Longitude,PhoneNumber
10/21/2016 13:34,18.912875,72.822318,9020320100
10/21/2016 10:35,18.9582233,72.8275845,9020320024
10/21/2016 15:20,18.95169982,72.83525604,9020320047
......

First we need to read the data then parse the date&time. For that I used datetime library in python and with little help from strftime the job is done

In [132]: from datetime import datetime

In [133]: datetime.strptime("10/21/2016 13:34", "%m/%d/%Y %H:%M")
Out[133]: datetime.datetime(2016, 10, 21, 13, 34)

Then I used Haversine formula to calculate the distance between two GPS points. 

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

def haversine(lon1, lat1, lon2, lat2):
    """
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees)
    """
    # convert decimal degrees to radians 
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

    # haversine formula 
    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 = 6378.137 
    return c * r

Then I created a empty dictionary with the subscriber's phone as the key and for the value [date, distance] . Then read line by line if the line I found is a newer position of the subscriber replace the date and distance. 

d = {}
for line in sys.stdin:
    subscriber  = line.strip().split(",")

    dat = datetime.strptime(subscriber[0], "%m/%d/%Y %H:%M")
    h = haversine(lon, lat, float(subscriber[2]), float(subscriber[1]))
    if item[3] in d:
        if dat > d[subscriber[3]][0]:
            d[subscriber[3]] = [dat, h]
    else:
        d[item[3]] = [dat, h]

Finally all I need to do is to check if the distance is less than the given radius. then just print the sorted phone numbers .

res = []
for phone in d:
    if  d[phone][1]<=r:
        res.append(phone)

print ",".join([phone for phone in sorted(res)])

The complete code:

from datetime import datetime
from math import radians, cos, sin, asin, sqrt
import sys

def haversine(lon1, lat1, lon2, lat2):
    """
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees)
    """
    # convert decimal degrees to radians 
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])

    # haversine formula 
    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 = 6378.137
    return c * r

lat, lon = map(float, raw_input().split(","))
r = float(raw_input())
raw_input()
d = {}
for line in sys.stdin:
    subscriber  = line.strip().split(",")

    dat = datetime.strptime(subscriber[0], "%m/%d/%Y %H:%M")
    h = haversine(lon, lat, float(subscriber[2]), float(subscriber[1]))
    if subscriber[3] in d:
        if dat > d[subscriber[3]][0]:
            d[subscriber[3]] = [dat, h]
    else:
        d[subscriber[3]] = [dat, h]
res = []
for phone in d:
    if  d[phone][1]<=r:
        res.append(phone)

print ",".join([phone for phone in sorted(res)])