7
\$\begingroup\$

I'd like feedback on my solution to the outlined programming challenge. Is numpy a good candidate module for this? What might be a more efficient or Pythonic solution?

Closest Enemy II

Have the function ClosestEnemyII(strArr) read the matrix of numbers stored in strArr which will be a 2D matrix that contains only the integers 1, 0, or 2. Then from the position in the matrix where a 1 is, return the number of spaces either left, right, down, or up you must move to reach an enemy which is represented by a 2. You are able to wrap around one side of the matrix to the other as well. For example: if strArr is ["0000", "1000", "0002", "0002"] then this looks like the following:

0 0 0 0
1 0 0 0
0 0 0 2
0 0 0 2

For this input your program should return 2 because the closest enemy (2) is 2 spaces away from the 1 by moving left to wrap to the other side and then moving down once. The array will contain any number of 0's and 2's, but only a single 1. It may not contain any 2's at all as well, where in that case your program should return a 0.

Examples
Input: ["000", "100", "200"]
Output: 1
Input: ["0000", "2010", "0000", "2002"]
Output: 2
import doctest
import numpy as np

from typing import List


def calc_closest_enemy(matrix: List[str]) -> int:
    """Calculate the minimum number of moves to reach an enemy

    Moves allowed: left, right, up, down. All count as +1
    Wrapping allowed: if current position is on an edge, a move
    can be made to the opposite edge for the cost of 1 move.

    >>> calc_closest_enemy(matrix=["000", "100", "200"])
    1
    >>> calc_closest_enemy(matrix=["0000", "2010", "0000", "2002"])
    2
    >>> calc_closest_enemy(matrix=["0000", "0010", "0000", "0000"])
    0
    >>> calc_closest_enemy(matrix=["0000", "0100", "0000", "0020"])
    3
    >>> calc_closest_enemy(matrix=["0000", "0100", "0000", "0000", "0020"])
    3
    >>> calc_closest_enemy(matrix=["0200", "0100", "0000", "0000", "0020"])
    1
    """
    grid = np.array([list(s) for s in matrix], dtype=np.int32)

    # In case of no enemies
    if 2 not in grid:
        return 0

    # format (y, x)
    friendly_coords = tuple(int(i) for i in np.where(grid == 1))
    assert len(friendly_coords) == 2, "Only one friendly is allowed"

    # Create wrapped grid
    # Wrap the y-axis then take the y-axis wrapped grid, transpose, and wrap the
    # former x-axis (now y-axis after transposition)
    for indx in friendly_coords:
        height, _ = grid.shape

        # These slices are appended to the appropriate grid ends to produce
        # the wrapped grid
        slice_to_friendly = grid[:indx]
        slice_from_friendly = grid[indx+1:]

        grid = np.insert(
            arr=grid, values=slice_to_friendly, obj=height, axis=0)
        grid = np.insert(
            arr=grid, values=slice_from_friendly, obj=0, axis=0)

        # Transpose to reuse code in for loop
        grid = grid.T

    # format (y, x)
    friendly_coords = tuple(int(i) for i in np.where(grid == 1))

    # Gather all enemy coords into a generator
    enemy_locations = np.where(grid == 2)
    enemy_locations = ((x, y) for y, x in zip(
        enemy_locations[0], enemy_locations[1]))

    # Calculate the moves required to travel from friendly to each enemy
    # and return lowest
    moves = [sum((abs(friendly_coords[1] - enemy[0]),
                    abs(friendly_coords[0] - enemy[1])))
                for enemy in enemy_locations]
    min_moves = min(moves)

    return min_moves


if __name__ == "__main__":
    doctest.testmod()
\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

Here

enemy_locations = np.where(grid == 2)
enemy_locations = ((x, y) for y, x in zip(
    enemy_locations[0], enemy_locations[1]))

the x/y-coordinates are swapped, and later the x-coordinate of each enemy is subtracted from the y-coordinate of the friend, and vice versa:

moves = [sum((abs(friendly_coords[1] - enemy[0]),
                abs(friendly_coords[0] - enemy[1])))
            for enemy in enemy_locations]

I find that confusing. If you don't swap the coordinates then the computation of the locations becomes simpler

enemy_locations = zip(*np.where(grid == 2))

and the distance computation becomes more logical:

moves = [sum((abs(friendly_coords[0] - enemy[0]),
                abs(friendly_coords[1] - enemy[1])))
            for enemy in enemy_locations]

Making moves a generator instead of a list would be sufficient.


Here

friendly_coords = tuple(int(i) for i in np.where(grid == 1))
assert len(friendly_coords) == 2, "Only one friendly is allowed"

you check if exactly one friend is given. But that check does not work: If there is zero or more than two 1 elements in the array then the int(i) conversion already fails with a

TypeError: only size-1 arrays can be converted to Python scalars

The error message is not appropriate if there is no friend.

Also assertions are for finding programming errors. A grid with zero or more than 2 friends is a wrong parameter and a reason to raise a ValueError:

Raised when an operation or function receives an argument that has the right type but an inappropriate value, and the situation is not described by a more precise exception such as IndexError.

My suggestion for that part would be

friendly_locations = list(zip(*np.where(grid == 1)))
if len(friendly_locations) != 1:
    raise ValueError("There must be exactly one friend")
friendly_coord = friendly_locations[0]

In order to compute the “wrapped distances” you augment the array by additional rows and columns. The dimensions of the array increase from \$ (m, n) \$ to at most \$ (2m-1, 2n-1) \$, i.e. the number of elements is almost quadrupled if the friend is located at one of the corners.

This can be completely avoided if the computation of the distance takes the wrapping into account:

def wrapped_distance(p1: Tuple[int, int], p2: Tuple[int, int], shape: Tuple[int, int]):
    """Return the wrapped distance between two points.

    The Manhattan distance from p1 to p2 in a grid of the given shape
    is computed, taking wrapping around the edges of the grid into account.
    """
    deltax = abs(p1[0] - p2[0])
    deltay = abs(p1[1] - p2[1])
    return min(deltax, shape[0] - deltax) + min(deltay, shape[1] - deltay)

And if the array is not modified then there is no need anymore to re-compute the friends's location. Also the pre-scan for the existence of enemies

if 2 not in grid:
    return 0

can now be replaced by calling min() with a default argument.

The main function then becomes:

def calc_closest_enemy(matrix: List[str]) -> int:
    """Calculate the minimum number of moves to reach an enemy.

    (... rest of your docstring omitted ...)
    """
    grid = np.array([list(s) for s in matrix], dtype=np.int32)

    friendly_locations = list(zip(*np.where(grid == 1)))
    if len(friendly_locations) != 1:
        raise ValueError("There must be exactly one friend")
    friendly_coord = friendly_locations[0]

    enemy_locations = zip(*np.where(grid == 2))
    distances = (wrapped_distance(friendly_coord, enemy, grid.shape)
                for enemy in enemy_locations)
    return min(distances, default = 0)
\$\endgroup\$
3
\$\begingroup\$

Is numpy a good candidate module for this?

Using numpy is fine, but you can get by just fine without it.

Borrowing Martin R's wrapped_distance function, you could solve the problem without any external libraries as follows:

def coordinates(matrix: List[str], subject: str) -> Iterable[Tuple[int, int]]:
    return ((r, c)
            for r, row in enumerate(matrix)
            for c, ch in enumerate(row)
            if ch == subject)

def calc_closest_enemy(matrix: List[str]) -> int:
    """Calculate the minimum number of moves to reach an enemy

    (... rest of your docstring omitted ...)
    """

    friendly_coord = next(coordinates(matrix, "1"))
    enemy_locations = coordinates(matrix, "2")
    shape = len(matrix), len(matrix[0])
    distances = (wrapped_distance(friendly_coord, enemy, shape) for enemy in enemy_locations)
    return min(distances, default=0)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.