Food Truck Problem by IEEEXtreme

Hello All..Today I am here with my solution for a Coding contest problem.

Problem begins now...

Madhu has a food-truck called "The Yummy Goods" that goes to a different business Hotspot everyday at lunch! Madhu wants to perform location-based advertising to folks in offices near her halt. To do this she uses the GPS location as a longitude and a latitude at the Stop and decides on radius (r) value. She wants to broadcast advertisement SMSes, to customers within this radius, advertising her food-truck.

She needs your help to generate the list of Phone numbers of such folks. She has access to big file of telecom data, which among other details, contains the phone number, longitude, and latitude of active cell-phone users in the city at that moment.




In order to calculate the distance between her stops and her subscribers, she wants you to use the most recent location available for each subscriber, To calculate the distance, you should use the Haversine Formula:

d = 2 x r x arcsin(sqrt(sin² ((lat1 - lat2)/2) + cos(lat1) x cos(lat2) x sin² ((long1 - long2)/2)))

where d is the difference between two points on the surface of the earth, in KM's

r is the radius of the earth (6378.137 km for this problem )

lat1, long1 are the latitude and longitude respectively of point1

lat2, long2 are the latitude and longitude respectively of point2

Input Format:

The first line contains Madhu's latitude and longitude in degrees seperated by Comma

The second line contains the radius r in KMs within which she wants to broadcast her advertisement

The third line is a header for the data in the subsequent lines.

The remaining lines have rows of telecom data of active cellphone users, Each line contains the following comma-seperated fields

• A time stamp in MM/DD/YYYY  hh:mm format, MM is a two digit months, eg: 01 for January, DD is two-digit day of month ( 01 through 31 ), YYYY is a four digit year, hh is the two digits of hour ( 00 through 23 ), and mm is the two digits of minute ( 00 through 59 )
• The latitude of subscriber in degrees
• The subscriber's phone number, as a 10 digit number

Notes:

• Some subscribers may appear, multiple times. You should use the most recent entry to determine the location of a subscriber, If a subscriber appears multiple times, the date/time stamps will differ
• None of the field values will contain commas

Constraints:

In order to eliminate rounding and approximation errors, no subscribers will be at a distance d from Madhu, such that 0.99 x r <=  d <= 1.01 x r

1 <= r <= 100

There will be at most 50,000 lines in the subscriber list

Output Format: 

A comma separated list of phone numbers for subscribers within a radius r of the stop, sorted in ascending order.

Sample Input:

18.9778972,72.8321983

1.0

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

10/21/2016 15:23,18.9513048,72.8343388,9020357980

10/21/2016 15:23,18.9513048,72.8343388,9020357962

10/21/2016 15:28,18.9548652,72.8332443,9020320027

10/21/2016 14:03,18.9179784,72.8279306,9020357972

10/21/2016 14:03,18.9179784,72.8279306,9020357959

10/21/2016 09:52,18.97523123,72.83494895,9020320007

10/21/2016 09:44,18.9715932,72.8383992,9020357607

10/21/2016 09:44,18.9715932,72.8383992,9020357593

10/21/2016 09:44,18.9715932,72.8383992,9020357584

10/21/2016 14:57,18.93438826,72.82704499,9020320011

10/21/2016 09:56,18.97596514,72.8327072,9020320045

10/21/2016 08:33,18.9811929,72.8353202,9020320084

10/21/2016 13:27,18.9159265,72.8245989,9020357896

10/21/2016 13:09,18.9077347,72.8076201,9020320094

10/21/2016 10:52,18.97523003,72.83494865,9020320007

Sample Output:

9020320045,9020320007,9020320084,9020357584,9020357593,9020357607

So till now we discussed what  the problem is.! So now lets have our solution with Code.

Here I wrote my Java Code for this problem.

/**     IEEEXtreme - Food Truck Solution     Author : PavanYekabote */ import java.io.*; import java.util.*; public class BroadCastData {   double r;   ArrayList<Userdata> users,sor;   double lat,lon;   public BroadCastData()throws Exception   {     users = new ArrayList<>();     BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));     String data = readData(reader);     parseData(data,users);     for(Userdata us : users)     {       us.setDistance(this.getDistance(lat, lon, us.getLat(), us.getLon(), r));     }     //9020320007,9020320045,9020320084,9020357584,9020357593,9020357607     users = this.noDuplicates(users);     this.sortUsers(users);     int i=0;     for(Userdata us : users){       if(i++>=6)         break;       System.out.print(us.getPhno());       if(i!=6)       System.out.print(",");     }      }      public static void main(String args[])throws Exception   {     new BroadCastData();   }      public double getDistance(double lat1,double long1,double lat2,double long2,double r)   {     //2*r*arcsin(sqrt(sinSQUARE((lat1-lat2)/2)+cos(lat1)*cos(lat2)*sinSQUARE((long1-long2)/2)));        double sinsqrlats = Math.sin((lat1-lat2)/2) * Math.sin((lat1-lat2)/2); //sinSQUARE of lats     double sinsqrlongs = Math.sin((long1-long2)/2) * Math.sin((long1-long2)/2);     double d = 2*r*Math.asin(             Math.sqrt(                 sinsqrlats + Math.cos(lat1) * Math.cos(lat2) * sinsqrlongs));     return d;   }         public String readData(File f) throws IOException   {     String data ="",line;     BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(f)));     while((line = reader.readLine())!=null)     {       data = data+line+"\n";     }     return data;   }         public String readData(BufferedReader in) throws IOException   {     String data="",line;     while((line=in.readLine())!=null)     {       data = data+line+"\n";     }          return data;        }   //Parse data to required format   public void parseData(String data,ArrayList<Userdata> user)   {          //Date&Time,Latitude,Longitude,PhoneNumber (Date as MM/DD/YYYY HH:MM )     StringTokenizer linewise,commawise;          linewise = new StringTokenizer(data,"\n");     commawise = new StringTokenizer(linewise.nextToken(),",");     this.lat = Double.parseDouble(commawise.nextToken()); //Read Latitude     this.lon = Double.parseDouble(commawise.nextToken()); // Read Longitude     this.r  = Double.parseDouble(linewise.nextToken()); //Radius     linewise.nextToken();     while(linewise.hasMoreTokens())     {       putUserData(linewise.nextToken(),user);     }        }      public void putUserData(String data, ArrayList<Userdata> user)   {     StringTokenizer commawise = new StringTokenizer(data,",");          while(commawise.hasMoreTokens())     {       Userdata usd = new Userdata(                       parseDate(commawise.nextToken()),                     Double.parseDouble(commawise.nextToken()),                     Double.parseDouble(commawise.nextToken()),                     Long.parseLong(commawise.nextToken())                         );                  user.add(usd);     }   }      public Date parseDate(String date)   {     StringTokenizer str = new StringTokenizer(date," ");     String dayte = str.nextToken();     String time = str.nextToken();     StringTokenizer dividedate = new StringTokenizer(dayte,"/");     Date d = new Date();     d.setMonth(Integer.parseInt(dividedate.nextToken())-1);     d.setDate(Integer.parseInt(dividedate.nextToken()));     d.setYear(Integer.parseInt(dividedate.nextToken())-1900);     StringTokenizer divideTime = new StringTokenizer(time,":");     d.setHours(Integer.parseInt(divideTime.nextToken()));     d.setMinutes(Integer.parseInt(divideTime.nextToken()));     return d;   }      public void sortUsers(ArrayList<Userdata> user)   {     Userdata us;     for(int i=0;i<user.size();i++)       for(int j=0;j<user.size();j++)         if(user.get(i).getDistance()<=user.get(j).getDistance())         {           us = user.get(i);           user.set(i, user.get(j));           user.set(j, us);         }   }      public ArrayList<Userdata> noDuplicates(ArrayList<Userdata> user)   {     ArrayList<Userdata> data = new ArrayList<>();     int x=0;     for(int i=0;i<user.size();i++)       for(int j=0;j<user.size();j++)                if(user.get(i).getPhno() == user.get(j).getPhno())           if(user.get(i).getDate().before(user.get(j).getDate()))// Date of i after date of j             user.get(i).isAdded=true;                for(Userdata us : user)     {       if(!us.isAdded)         data.add(us);     }     return data;   }      //Userdata Class   class Userdata {     private Date date;     private double lat,lon,distance;     private long phno;     protected boolean isAdded;          public Userdata(Userdata usrdt)     {       this.date = usrdt.getDate();       this.lat = usrdt.getLat();       this.lon  = usrdt.getLon();       this.phno = usrdt.getPhno();     }     public Userdata(Date date, double lat, double lon, long phno)     {       this.date = date;       this.lat = lat;       this.lon  = lon;       this.phno = phno;     }     public double getDistance()     {       return this.distance;     }          public void setDistance(double distance)     {       this.distance = distance;     }               public Date getDate() {       return date;     }     public void setDate(Date date) {       this.date = date;     }     public double getLat() {       return lat;     }     public void setLat(double lat) {       this.lat = lat;     }     public double getLon() {       return lon;     }     public void setLon(double lon) {       this.lon = lon;     }     public long getPhno() {       return phno;     }     public void setPhno(long phno) {       this.phno = phno;     }      } }

Here is the output: