DEV Community: Joao Vitor Veras

Python mro

Joao Vitor Veras — Mon, 10 Jan 2022 20:17:29 +0000

Method Resolution Order ou (MRO) é um que atributo define a ordem em que classes são organizadas, para que os métodos sejam procurados e executados. Em linguagens que não permitem herdar múltiplas classes o MRO não é tão necessário, mas nas que permitem (como Python) ele tem um papel importante.

Quando herdamos uma classe a classe herdada pode ser chamada de Parent ou Superclass e a classe que esta herdando Child ou Subclass, o papel do MRO é definir a ordem das Superclasses em que, será procurado por (e caso encontrado, executado) algum método.

class Grandparent():
    def method(self):
        return 'grandparent'

class Parent(Grandparent):
    def method(self):
        return 'parent'

class Child(Parent):
    pass

child = Child()

print(child.method()) # > 'parent'

um exemplo bem simples (sem fazer o uso de múltiplas heranças) é o código acima, temos 3 classes que possuem o mesmo método, o MRO primeiro procura pelo método na classe instanciada que estamos e caso não seja encontrado procura nas Superclasses, dessa forma: Child -> Parent -> Grandparent.

é possível visualizar essa ordem acessando o __mro__ na classe Child

child = Child()

# (<class '__main__.Child'>, <class '__main__.Parent'>, <class '__main__.Grandparent'>, <class 'object'>)

python object class

podemos ver uma classe que não criamos no final <class 'object'>. essa é uma classe built-in do python, ela está presente para ser a Superclass de classes que não tenham explicitamente definido classes para herdar. Por isso a vimos no final do __mro__ pois a classe Grandparent não herda nenhuma outra classe.

agora utilizando múltiplas heranças vamos ver o MRO cumprindo o seu papel.

class Grandparent():
    def method(self):
        return 'grandparent'

class Parent(Grandparent):
    def method(self):
        return 'parent'

class Parent2(Grandparent):
    def method(self):
        return 'parent2'

class Child(Parent, Parent2):
    pass

child = Child()

print(child.method()) # > 'parent'
print(Child.__mro__)
# (<class '__main__.Child'>, <class '__main__.Parent'>, <class '__main__.Parent2'>, <class '__main__.Grandparent'>, <class 'object'>)

como você pode na classe child temos o controle da ordem em que as Superclasses serão posicionadasChild(Parent, Parent2)

essa ordem fica disponível no atributo __bases__ de sua respectiva classe, por exemplo a classe Child acima:
print(Child.__bases__)
# (<class '__main__.Parent'>, <class '__main__.Parent2'>)

no exemplo do código acima já começa a ficar interessante, pois o esperado seria que o código tivesse o seguinte MRO

Child -> Parent -> Grandparent -> Parent2 -> Grandparent
mas isso não acontece porque como estamos lidando com herança a precedência importa, isso é, a classe Parent2 tem prioridade sobre a Grandparent, então o MRO define a seguinte ordem

Child -> Parent -> Parent2 -> GrandParent

então podemos concluir que Subclasses precedem Superclasses (como já dito ali em cima Subclasses, Superclasses = Child, Parent) e o nosso MRO se baseia na ordem do atributo __bases__

Exemplo 2

Se por acaso você tentar criar uma ordem que o MRO não consiga resolver você recebera um TypeError:

"TypeError: Cannot create a consistent method resolution
order (MRO) for bases"

no código acima não é possivel criar um Method Resolution Order consistente porque estamos tentando passar uma Superclass na frente de uma Subclass.

um workaround para esse erro seria invertendo o __bases__ da classe Child Child(Parent3, Parent), por mais que funcione existe uma maneira melhor de resolver isso e que vai deixar o seu MRO mais organizado e bem definido e você não terá erros inesperados no futuro.

class Grandparent():
    def method(self):
        return 'grandparent'

class Parent():
    def method(self):
        return 'parent'

    def parent(self):
        return 'parent hierarquicamente'

class Parent2(Parent, Grandparent):
    def method(self):
        return 'parent2'

class Parent3(Parent2):
    pass

class Child(Parent3):
    pass

child = Child()

print(child.parent()) # parent hierarquicamente

como temos a acesso a todos os métodos e atributos por hierarquia podemos remover a classe Parent da classe Child.

print(Child.__mro__)
# (<class '__main__.Child'>, <class '__main__.Parent3'>, <class '__main__.Parent2'>, <class '__main__.Parent'>, <class '__main__.Grandparent'>, <class 'object'>)

Acima podemos ver como ficou o MRO, bem definido e não trara problemas no futuro.

Como resolver o Knight's Tour Problem com a Warnsdorff's Rule

Joao Vitor Veras — Tue, 16 Nov 2021 22:47:47 +0000

O Knight's Tour problem é um problema que se baseia em uma sequência de movimentos num tabuleiro de xadrez, os movimentos são feitos apenas pelo Cavalo (Knight) e seguindo as regras do xadrez o objetivo é fazer um "Tour", ou seja, visitar todas as casas do tabuleiro, porém, só é permitido passar pelas casas apenas uma ÚNICA vez.

Existem várias maneiras de resolver esse problema algumas delas são:

Brute Force
Divide-and-conquer Algorithms
Neural Network
Warnsdorff's Rule

Warnsdorff's Rule é uma heurística (procedimento que auto-descobre e aplica um método, sem a garantia de ser perfeito ou racional, mas que é suficiente para chegar a um resultado seja ele aproximado ou imediato).

Imagine o seguinte cenário: Um tabuleiro padrão 8x8 e a posição inicial do Cavalo atribuída randomicamente, partindo da posição inicial vamos olhar para todas as casas que o Cavalo pode se mover, partindo dessas casas disponíveis vamos olhar novamente ao redor do cavalo e contar quantas casas temos disponíveis. A casa que tiver o menor numero de futuras casas disponíveis (vamos chama-las de Neighbors) é a vencedora e o Cavalo se move até ela, faremos isso até o Tour ser finalizado;

O nosso tabuleiro será representado por um Array 2D, se quiséssemos posicionar o Cavalo igual na imagem acima (na casa B4) em um Array 2D, seria assim board[4][1]. Você pode ver que temos um Array board com 8 Arrays representando o eixo X e cada Array com 8 elementos representando o eixo Y.

    board = [[-1 for i in range(n)]for j in range(n)]

Iniciamos todas as casas do tabuleiro com o valor -1 assim fica fácil na hora de saber se o Cavalo ja passou ou por aquela casa.

No xadrez o Cavalo faz um movimento em L e para representar isso no nosso código vamos utilizar 2 arrays moves_x = [] e moves_y = [] neles teremos todos os possiveis movimentos que o Cavalo pode fazer

    moves_x = [-2, -2, -1, -1, 2, 2, 1, 1]
    moves_y = [-1, 1, -2, 2, -1, 1, -2, 2]

esses números parecem aleatórios e podem soar um pouco confuso, mas calma... tudo fará sentindo.

na ilustração acima fica bem fácil de entender nela temos todos os movimentos em L possiveis, também está destacado em verde o movimento do Cavalo para a casa C7. Todos os movimentos são formados pelo calculo dos valores moves_x e moves_y sobre o os valores X e Y da casa que o Cavalo estiver. Por exemplo para mover da casa D5 (board[3][3]) para a C7 teriamos: X = 3 - 2, Y = 3 - 1 pronto agora já temos nossa nova posição board[1][2].

O movimento que fizemos acima só foi válido porquê o cavalo está no centro do tabuleiro, se o Cavalo estiver nas bordas o tabuleiro "acaba" ou se já tivesse passado pela casa C7 não poderiamos passar por lá novamente, para verificar isso utilizaremos a seguinte função que recebe next_move como o resultado do cálculo dos moves sobre o valor X, Y da posição atual, sendo esse um possivel movimento valido e o tabuleiro board

def validMove(next_move_x, next_move_y, board):
    if (not next_move_x < 0 and not next_move_y < 0 and next_move_x < n and next_move_y < n and board[next_move_x][next_move_y] == -1):
        return True
    return False

Tanto no eixo X ou Y caso o Cavalo tente fazer um movimento que ultrapasse o limite do tabuleiro o resultado do calculo será negativo e falhara na verificação acima e se esse movimento for feito na borda da direita ou para baixo o resultado será maior que o tamanho do tabueleiro; n representa o tamanho do tabuleiro (8)

solveKnight() é a nossa função principal

def solveKnight():
    moves_x = [-2, -2, -1, -1, 2, 2, 1, 1]
    moves_y = [-1, 1, -2, 2, -1, 1, -2, 2]

    board = [[-1 for i in range(n)]for j in range(n)]

    # posição inicial aleatoria
    starting_pos_x = random.randint(0, 7)
    starting_pos_y = random.randint(0, 7)

    # começar a contagem de tours 
    # e definir que já passamos por essa posição
    tour = 1
    board[starting_pos_x][starting_pos_y] = 1

    # procurar os proximos movimentos
    findNextMove(moves_x, moves_y, starting_pos_x, starting_pos_y, tour, board, 8)
    return printBoard(n, board)

aqui chamamos a função findNextMove()

def findNextMove(moves_x, moves_y, curr_pos_x, curr_pos_y, tour, board, neighbors_availability):
    if (tour == 8 ** 2):
        return True

    next_move_x = None
    next_move_y = None

    # andar pelo board  
    for i in range(8):
        new_move_x = curr_pos_x + moves_x[i]
        new_move_y = curr_pos_y + moves_y[i]

        if (validMove(new_move_x, new_move_y, board)):
            # contar quantos neighbors estão disponíveis
            neighbors_available = countNeighbors(new_move_x, new_move_y, moves_x, moves_y, board)
            if (neighbors_available < neighbors_availability):
                neighbors_availability = neighbors_available
                next_move_x = new_move_x
                next_move_y = new_move_y

    tour += 1
    board[next_move_x][next_move_y] = tour

    return findNextMove(moves_x, moves_y, next_move_x, next_move_y, tour, board, 8)

Para encontrar a próxima casa vamos definir temporariamente um new_move que será um possivel movimento válido, a partir deste new_move vamos contar quantas outras possiveis casa diponíveis (neighbors) existem, o new_move que tiver o menor numero de neighbors passa a ser o next_move

Precisamos fazer isso até o Cavalo visitar todas as casas, para isso o retorno da nossa função será ela mesma, tornando-a recursiva. A cada movimento válido que o Cavalo faz estamos adicionando +1 na variável tour, quando o seu total for igual a 8 ** 2 (64) que é o total de casas que existem no nosso tabuleiro saberemos que o Tour foi completo

para contar os neighbors faremos o seguinte

def countNeighbors(new_move_x, new_move_y, moves_x, moves_y, board):
    neighbors = 0

    for i in range(8):
        neighbor_x = new_move_x + moves_x[i]
        neighbor_y = new_move_y + moves_y[i]

        if (validMove(neighbor_x, neighbor_y, board)):
            if (validNeighbor(neighbor_x, neighbor_y, new_move_x, new_move_y)):
                neighbors += 1

    return neighbors

Iteramos por todos os moves válidos, como estamos manipulando o new_move que é uma posição temporaria apenas para contar quantas casas disponíveis existem não podemos contar a casa que o cavalo realmente está, e esse é o papel do validNeighbor()

def validNeighbor(neighbor_x, neighbor_y, new_move_x, new_move_y):
    if (neighbor_x != new_move_x and neighbor_y != new_move_y):
        return True 
    return False

Todos os movimentos que passarem são contados e retornados pela função countNeighbors().

Agora que o Cavalo já passou por todas as 64 casas precisamos printar na tela todo o caminho feito por ele

def printBoard(n, board):
    for i in range(n):
        for j in range(n):
            print(board[i][j], end=' ')
        print()

Para printar tudo isso iteramos pelo board e para cada elemento do eixo X printamos com o parametro end=' ', porquê o python por padrão cria uma nova linha e o resultado que esperamos é que fiquem um ao lado do outro, assim:

5 20 3 26 7 22 31 36 
2 27 6 21 30 37 8 23 
19 4 29 50 25 32 35 38 
28 1 48 33 56 51 24 9 
45 18 57 62 49 34 39 52 
60 63 44 47 42 55 10 13 
17 46 61 58 15 12 53 40 
64 59 16 43 54 41 14 11

esse é o caminho feito pelo Cavalo em um tabuleiro de 8x8.

você pode acessar o código completo neste gist

DEV Community: Joao Vitor Veras

Python __mro__

python object class

Exemplo 2

Como resolver o Knight's Tour Problem com a Warnsdorff's Rule

Python mro