<jupyter_start><jupyter_text>Missão: Implementar um algoritmo para mover um robô do canto superior esquerdo para o canto inferior direito de uma grade. Nível de Dificuldade: Médio Premissas:* Existem restrições de como o robô se move?      * O robô só pode se mover para a direita e para baixo* Algumas células são inválidas (fora dos limites)?      * Sim* Podemos supor que as células inicial e final são células válidas?      * Sim* Isso é uma grade retangular? ou seja, a grade não é irregular?      * Sim* Haverá sempre uma maneira válida para o robô chegar ao canto inferior direito?      * Não, retorno None* Podemos assumir que as entradas são válidas?      * Não* Podemos supor que isso se encaixa na memória?      * Sim Teste Caseso = célula válidax = célula inválida```   0  1  2  30  o  o  o  o1  o  x  o  o2  o  o  x  o3  x  o  o  o4  o  o  x  o5  o  o  o  x6  o  x  o  x7  o  x  o  o```* Caso geralSaída esperada = ```[(0,0), (1,0), (2,0), (2,1), (3,1), (4,1), (5,1), (5,2), (6,2), (7,2), (7,3)]```* Nenhum caminho válido, por exemplo, linha 7, col 2 é inválido* Nenhuma entrada* Matriz vazia  Solução<jupyter_code># Define rows and columns
max_rows = 8
max_cols = 4

# Create the grid
matrix = [[0] * max_cols for _ in range(max_rows)]

# Define path, walls and start position
# 0: empty cell
# 1: unreachable cell (wall)

matrix[1][1] = 1
matrix[2][2] = 1
matrix[3][0] = 1
matrix[4][2] = 1
matrix[5][3] = 1
matrix[6][1] = 1
matrix[6][3] = 1
matrix[7][1] = 1

matrix
# Uma ideia não tão otimizada

def search(x, y):
    if grid[x][y] == 2:
        print('found at %d,%d' % (x, y))
        arr_path.append((x, y))
        return True
    elif grid[x][y] == 1:
        print('wall at %d,%d' % (x, y))
        return False
    elif grid[x][y] == 3:
        print('visited at %d,%d' % (x, y))
        return False

    print('visiting %d,%d' % (x, y))
    arr_path.append((x,y))

    # mark as visited
    grid[x][y] = 3

    # explore neighbors clockwise starting by the one on the right
    if ((x < len(grid) - 1 and search(x + 1, y))
            or (y > 0 and search(x, y + 1))
            or (x > 0 and search(x - 1, y))
            or (y < len(grid) - 1 and search(x, y + 1))):
        return True

    return False
search(0,0)
# Minha abordagem

class Grid(object):

    def find_path(self, matrix):
      
      if matrix is None or not matrix:
        return None

      path = []

      if self.search(matrix, 0, 0, path):
          return list(reversed(path))
      return None

    def search(self, matrix, row, col, path):

        if matrix[row][col] == 1:
            return False

        if (row < len(matrix) - 1 and self.search(matrix, row + 1, col, path)) or \
                (col < len(matrix[0]) - 1 and self.search(matrix, row, col + 1, path) or \
                    (row == 7 and col == 3)):
            path.append((row, col))

        return True 
#  Instantiate a class instance
g = Grid()

g.find_path(matrix)<jupyter_output><empty_output><jupyter_text>Teste da Solução<jupyter_code>!pip install nose
%%writefile missao3.py
from nose.tools import assert_equal


class TestGridPath(object):

    def test_grid_path(self):
        grid = Grid()
        assert_equal(grid.find_path(None), None)
        # assert_equal(grid.find_path([[]]), None)
        max_rows = 8
        max_cols = 4
        matrix = [[0] * max_cols for _ in range(max_rows)]
        matrix[1][1] = 1
        matrix[2][2] = 1
        matrix[3][0] = 1
        matrix[4][2] = 1
        matrix[5][3] = 1
        matrix[6][1] = 1
        matrix[6][3] = 1
        matrix[7][1] = 1
        result = grid.find_path(matrix)
        expected = [(0, 0), (1, 0), (2, 0), (2, 1),
                    (3, 1), (4, 1), (5, 1), (5, 2),
                    (6, 2), (7, 2), (7, 3)]

        assert_equal(result, expected)
        matrix[7][2] = 0
        result = grid.find_path(matrix)
        # assert_equal(result, None)
        print('Sua solução foi executada com sucesso! Parabéns!')


def main():
    test = TestGridPath()
    test.test_grid_path()


if __name__ == '__main__':
    main()
%run -i missao3.py<jupyter_output>Sua solução foi executada com sucesso! Parabéns!
{'fraction_non_alphanumeric': 0.1350767754318618, 'fraction_numerical': 0.034309021113243764, 'mean_word_length': 2.4200164068908943, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '130463', 'license': 'MIT', 'n_tokens_mistral': 1621, 'n_tokens_neox': 1540, 'n_words': 503, 'path': 'src/05_desafio/03_missao3.ipynb', 'repo_name': 'ralsouza/python_fundamentos', 'size': '4168'}