Chaker Benhamed

Home | |

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)])