Immediate Food Delivery I: Finding the Closest Restaurant

Imagine you're building a food delivery app. A user has just placed an order and needs to find the closest restaurant that can fulfill it immediately. This challenge focuses on determining which restaurant is geographically closest to the user, given a list of restaurants and their locations.

Problem Description

You are given a list of restaurants, each represented by its name and coordinates (latitude and longitude). You are also given the user's coordinates (latitude and longitude). Your task is to determine the name of the restaurant that is closest to the user, based on the Haversine formula for calculating distances between two points on a sphere (Earth).

What needs to be achieved:

• Calculate the distance between the user's location and each restaurant's location using the Haversine formula.
• Identify the restaurant with the minimum calculated distance.
• Return the name of that closest restaurant.

Key Requirements:

• The Haversine formula must be used for distance calculation.
• The input will be a list of restaurants and the user's location.
• The output should be the name of the closest restaurant.
• Handle the case where the input list of restaurants is empty.

Expected Behavior:

The function should return the name of the restaurant with the shortest distance to the user. If multiple restaurants have the same shortest distance, return the name of the first one encountered in the list. If the restaurant list is empty, return "No restaurants available."

Edge Cases to Consider:

• Empty restaurant list.
• Restaurants located at the same coordinates.
• User located at the same coordinates as a restaurant.
• Large number of restaurants (performance considerations).

Examples

Example 1:

Input:
restaurants = [
    {"name": "Pizza Palace", "latitude": 34.0522, "longitude": -118.2437},
    {"name": "Burger Barn", "latitude": 34.0600, "longitude": -118.2500},
    {"name": "Sushi Spot", "latitude": 34.0450, "longitude": -118.2350}
]
user_latitude = 34.0500
user_longitude = -118.2400
Output: Pizza Palace
Explanation: Pizza Palace is the closest restaurant to the user based on the Haversine formula.

Example 2:

Input:
restaurants = []
user_latitude = 34.0522
user_longitude = -118.2437
Output: No restaurants available.
Explanation: The restaurant list is empty, so the function returns the specified message.

Example 3:

Input:
restaurants = [
    {"name": "Coffee Corner", "latitude": 34.0522, "longitude": -118.2437},
    {"name": "Tea Time", "latitude": 34.0522, "longitude": -118.2437}
]
user_latitude = 34.0522
user_longitude = -118.2437
Output: Coffee Corner
Explanation: Both Coffee Corner and Tea Time are at the same location as the user. The function returns the first one in the list.

Constraints

• The number of restaurants in the input list will be between 0 and 1000.
• Latitude and longitude values will be floating-point numbers between -90 and 90 for latitude, and -180 and 180 for longitude.
• The Haversine formula calculation should be reasonably efficient. While not a strict requirement, avoid excessively complex or inefficient implementations.
• Input data will always be well-formed (e.g., no missing fields in restaurant objects).

Notes

• The Haversine formula is a standard method for calculating distances between two points on a sphere given their latitudes and longitudes. You can find numerous resources online explaining the formula and its implementation.
• Consider using a helper function to encapsulate the Haversine formula calculation for better code organization and readability.
• Focus on clarity and correctness first. Performance optimization can be considered later if necessary.
• The Earth's radius is approximately 6371 kilometers (or 3959 miles). You can use either unit for your calculations, but be consistent.

Pseudocode:

FUNCTION find_closest_restaurant(restaurants, user_latitude, user_longitude):
  // Check if the restaurant list is empty
  IF restaurants is empty:
    RETURN "No restaurants available."

  // Initialize variables to store the minimum distance and the closest restaurant
  min_distance = Infinity
  closest_restaurant = null

  // Iterate through each restaurant in the list
  FOR EACH restaurant IN restaurants:
    // Calculate the distance between the user and the current restaurant using the Haversine formula
    distance = haversine(user_latitude, user_longitude, restaurant.latitude, restaurant.longitude)

    // Check if the calculated distance is less than the current minimum distance
    IF distance < min_distance:
      // Update the minimum distance and the closest restaurant
      min_distance = distance
      closest_restaurant = restaurant.name

  // Return the name of the closest restaurant
  RETURN closest_restaurant


FUNCTION haversine(lat1, lon1, lat2, lon2):
  // Earth radius in kilometers
  R = 6371

  // Convert latitude and longitude from degrees to radians
  lat1_rad = degrees_to_radians(lat1)
  lon1_rad = degrees_to_radians(lon1)
  lat2_rad = degrees_to_radians(lat2)
  lon2_rad = degrees_to_radians(lon2)

  // Calculate the differences in latitude and longitude
  dlat = lat2_rad - lat1_rad
  dlon = lon2_rad - lon1_rad

  // Apply the Haversine formula
  a = sin(dlat / 2)**2 + cos(lat1_rad) * cos(lat2_rad) * sin(dlon / 2)**2
  c = 2 * atan2(sqrt(a), sqrt(1 - a))

  // Calculate the distance
  distance = R * c

  RETURN distance

FUNCTION degrees_to_radians(degrees):
  RETURN degrees * PI / 180