Finding the Closest Valid Point Using Manhattan Distance in JavaScript and Python

Have you ever been faced with a scenario where you needed to find the nearest valid point on a grid or chessboard-like structure? Perhaps you’re a budding programmer looking to expand your problem-solving skills.

In this blog post, we’ll explore the concept of Manhattan Distance and demonstrate how to utilize it to find the closest valid point to a given position. We’ll provide solutions in both JavaScript and Python, ensuring accessibility for developers of all backgrounds.

Introduction to Manhattan Distance

Manhattan Distance, also known as the L1 distance or taxicab distance, is a fundamental concept in grid-based problem-solving.

It measures the distance between two points on a grid-like system, considering only horizontal and vertical movements.

This distance metric is named after the grid layout of streets in Manhattan, where you can travel only along these gridlines — horizontally and vertically.

Problem Statement

Imagine you’re positioned at a specific point on a grid, represented by coordinates (x, y). Your task is to find the valid point closest to your current location according to the Manhattan Distance.

A point is considered valid if it shares either the same x-coordinate or the same y-coordinate as your current position. If multiple valid points have the same minimum Manhattan Distance, we return the valid point with the smallest index. If no valid points are found, we return -1.

JavaScript Solution

Let’s start by examining the JavaScript solution to this problem:

// Define the current position (x, y) and an array of locations.
const x = 5;
const y = 1;
const locations = [[1, 1], [6, 2], [1, 5], [3, 1]];

// Function to find the closest valid point using Manhattan Distance.
function findClosestValidPoint(x, y, locations) {
  // Initialize variables to keep track of the minimum distance and index.
  let minDistance = Infinity;
  let minIndex = -1;

  // Iterate through the locations array.
  for (let i = 0; i < locations.length; i++) {
    // Extract the x and y coordinates of the current location.
    const [xi, yi] = locations[i];

    // Check if the current location shares the same x-coordinate or y-coordinate with the target position.
    if (xi === x || yi === y) {
      // Calculate the Manhattan Distance between the current location and the target position.
      const distance = Math.abs(x - xi) + Math.abs(y - yi);

      // Update the minimum distance and index if the current location is closer.
      if (distance < minDistance) {
        minDistance = distance;
        minIndex = i;
      }
    }
  }

  // Return the index of the closest valid point.
  return minIndex;
}

// Call the function to find the closest valid point and store the result in closestIndex.
const closestIndex = findClosestValidPoint(x, y, locations);

// Output the result.
console.log(closestIndex); // Output should be 3 (index of the closest valid point)

In JavaScript, we start by defining the current position (x, y) and an array of locations. We then iterate through the locations, calculating the Manhattan Distance for each valid point and keeping track of the minimum distance and index of the closest valid point.

Python Solution

Now, let’s explore the Python solution to the same problem:

# Define the current position (x, y) and an array of locations.
x = 5
y = 1
locations = [[1, 1], [6, 2], [1, 5], [3, 1]]

# Function to find the closest valid point using Manhattan Distance.
def find_closest_valid_point(x, y, locations):
    # Initialize variables to keep track of the minimum distance and index.
    min_distance = float('inf')
    min_index = -1

    # Iterate through the locations list using an index 'i'.
    for i in range(len(locations)):
        # Extract the x and y coordinates of the current location.
        xi, yi = locations[i]

        # Check if the current location shares the same x-coordinate or y-coordinate with the target position.
        if xi == x or yi == y:
            # Calculate the Manhattan Distance between the current location and the target position.
            distance = abs(x - xi) + abs(y - yi)

            # Update the minimum distance and index if the current location is closer.
            if distance < min_distance:
                min_distance = distance
                min_index = i

    # Return the index of the closest valid point.
    return min_index

# Call the function to find the closest valid point and store the result in closest_index.
closest_index = find_closest_valid_point(x, y, locations)

# Output the result.
print(closest_index)  # Output should be 3 (index of the closest valid point)

In Python, we use a similar approach, iterating through the locations and calculating the Manhattan Distance for each valid point. We also keep track of the minimum distance and index of the closest valid point.

Conclusion

As you explore more algorithms and concepts, remember that practice and persistence are key. The more you tackle problems and refine your skills, the more confident and capable you’ll become as a programmer. So, keep coding, keep exploring, and keep embracing new challenges. Happy coding!

👋 Hey there! If you have any burning questions or just want to say hi, don’t be shy — I’m only a message away. 💬 You can reach me at jamilkashem@zoho.com.

🤝 By the way, I think we share the same interest in software engineering — let’s connect on LinkedIn! 💻