CODEWITHSUNDEEP
pythonmatrixchartsdepth-first-search
Wadhah Sky
Wadhah Sky

Reputation: 198

How to solve boat movements using Graph algorithm?

Appreciate your help to solve the following issue:

A game grid represents water and land masses. The grid contains a True value where it's water and False where it's land. A boat can go to the next tile in the left or right directions, or move twice in the top and bottom directions. All the tiles in the path must be inside the grid and contain water. Implement the can_travel_to function, which accepts a grid matrix, starting and destination coordinates (row and column), and returns a boolean indicating whether a boat can travel between the two points in one step.

For example, the following code:

game matrix = [
    [False, False, True, True, False],
    [False, False, True, False, False],
    [False, False, True, True, False],
    [False, True, False, True, False],
    [False, False, True, False, False]
]

print(can_travel_to (game_matrix, 2, 2, 0, 2))
print(can_travel_to (game_matrix, 2, 2, 2, 1))
print(can_travel_to (game_matrix, 2, 2, 2, 3))
print(can_travel_to(game_matrix, 2, 2, 4, 2))

Should print:

True
False
True
False

I pass one case of tests but I can't with the other two which in case all coordinates inside the grid and some coordinates are outside the grid.

Check this link to test your solution TestDome

Current solution:


class BoatMovements:
    def __init__(self, matrix, to_row, to_column):
        self.row = to_row
        self.column = to_column
        self.matrix = matrix
        self.visited = [
            [False for _ in range(len(matrix[0]))]
            for _ in range(len(matrix))
        ]

    def valid_move(self, row, column):

        if 0 <= row < len(self.matrix) and 0 <= column < len(self.matrix[0]):
            if self.matrix[row][column] and not self.visited[row][column]:
                return True

        return False

    def dfs_search(self, row, column):

        if not self.valid_move(row, column):
            return False

        if self.row == row and self.column == column:
            return True

        self.visited[row][column] = True

        return (self.dfs_search(row - 1, column) or
                self.dfs_search(row, column - 1) or
                self.dfs_search(row + 1, column) or
                self.dfs_search(row, column + 1))


def can_travel_to(game_matrix, from_row, from_column, to_row, to_column):

    try:
        # Check that:
        # 1- the given coordinates within the grid.
        # 2- the start and end coordinates is True.
        # 3- restrict the moves (two top/down and one left/right).
        if (to_row > len(game_matrix) - 1) or \
           (to_column > len(game_matrix) - 1) or \
           not game_matrix[from_row][from_column] or \
           not game_matrix[to_row][to_column] or \
           abs(to_row - from_row) > 2 or \
           abs(to_column - from_column) > 1:
            return False
    except IndexError:
        raise IndexError("The indexes must be valid indexes!")

    boat_movements = BoatMovements(game_matrix, to_row, to_column)
    return boat_movements.dfs_search(from_row, from_column)

Upvotes: 1

Views: 920

Answers (2)

Joseph Bijumon
Joseph Bijumon

Reputation: 1

You will get the wrong answer if you use DFS. The question doesn't say this, but you should assume that the boat only moves once. This solution passed all the tests:

def can_travel_to(game_matrix, from_row, from_column, to_row, to_column):
    # Get rows and columns in matrix
    ROWS = len(game_matrix)
    COLS = len(game_matrix[0])

    # Check if both coords are out of bound or if they are False in game_matrix
    if (from_row<0 or from_column<0 or to_row<0 or to_column<0 or
       from_row>=ROWS or from_column>=COLS or to_row>=ROWS or to_column>=COLS or
       not game_matrix[from_row][from_column] or not game_matrix[to_row][to_column]):
        return False

    # Check if the "to" coords is above or below the "from" coords
    if (from_column == to_column):
        if (from_row+1 == to_row or from_row-1 == to_row):
            return True

    # Check if the "to" coords is left or right of the "from" coords
    if (from_row == to_row):
        if (from_column+1 == to_column or from_column-1 == to_column):
            return True

        # If the cell to the right is water, we can also check the next cell to the right
        if (from_column < COLS and game_matrix[to_row][from_column+1]):
            if (from_column < COLS and from_column+2 == to_column):
                return True

    return False

Upvotes: -1

Wadhah Sky
Wadhah Sky

Reputation: 198

The issue was in the method can_travel_to() and the new update is:


def can_travel_to(game_matrix, from_row, from_column, to_row, to_column):
    """Method to check if boatMovements instance is able to travel to given
    coordinates depending on starting point"""

    # Check that:
    # 1- The given coordinates within the grid.
    # 2- Restrict the steps (two when moving top/down and one left/right).
    if (to_row > len(game_matrix) - 1) or \
       (to_column > len(game_matrix[0]) - 1) or \
       (from_row != to_row and abs(to_row - from_row) != 2) or \
       (from_column != to_column and abs(to_column - from_column) != 1):

        return False

    # Check that The start and end coordinates are True, otherwise return False
    if not game_matrix[from_row][from_column] or \
       not game_matrix[to_row][to_column]:
        return False

    # Create a BoatMovements instance and set coordination of the end
    # destination.
    boat_movements = BoatMovements(game_matrix, to_row, to_column)

    # Call dfs method and return its response.
    return boat_movements.dfs_search(from_row, from_column)

Note: You can find the full code on Github

Upvotes: 1

Related Questions