algoadvance

You are playing a simplified PAC-MAN game. You start at the point (0, 0) on an infinite 2D grid and your destination is at a specific point target. There are several ghosts on the same 2D grid, each of whom start at different points and you want to reach the target without any ghost reaching it before you or at the same time.

Given an array ghosts, where ghosts[i] is an array [x_i, y_i] representing the starting position of the i-th ghost, and given the array target of length 2 representing your destination:

You need to return True if you can escape all the ghosts, otherwise return False.

Example

Constraints

Clarifying Questions

  1. Do ghosts have any movement restrictions or patterns?
    • Ghosts move in the same way you do, meaning they can move one step in any of the four cardinal directions per turn.
  2. Can ghosts occupy the same position?
    • Yes, they can.
  3. What is the importance of the Euclidean distance versus Manhattan distance in this problem?
    • For grid-based problems like this, the Manhattan distance is more relevant since movement is restricted to horizontal and vertical steps.
  4. When does a player or ghost move in the game?
    • All entities (including ghosts and player) move simultaneously turn by turn.

Strategy

  1. Calculate the player’s Manhattan distance to the target:
    • This is computed as |target[0] - 0| + |target[1] - 0|.
  2. Calculate each ghost’s Manhattan distance to the target:
    • For each ghost, compute |target[0] - ghost[i][0]| + |target[1] - ghost[i][1]|.
  3. Compare the distances:
    • If at least one ghost can reach the target in the same or fewer moves than the player, return False.
    • Otherwise, return True.

Code

def escapeGhosts(ghosts, target):
    # Calculate player's distance to the target
    player_distance = abs(target[0]) + abs(target[1])
    
    # Check each ghost's distance to the target
    for ghost in ghosts:
        ghost_distance = abs(target[0] - ghost[0]) + abs(target[1] - ghost[1])
        if ghost_distance <= player_distance:
            return False
            
    return True

# Example usage
print(escapeGhosts([[1, 0], [0, 3]], [0, 1]))  # Expected output: True
print(escapeGhosts([[1, 0]], [2, 0]))          # Expected output: False

Time Complexity

The time complexity for this solution is (O(n)), where (n) is the number of ghosts. This is because for each ghost, we perform a constant time calculation to compute the Manhattan distance and compare it. Thus, the solution is efficient and scales linearly with the number of ghosts.

Try our interview co-pilot at AlgoAdvance.com