J'ai cette méthode qui obtient tous les mouvements valides d'un damier.

def get_all_moves(self) -> list:
    moves = []
    pieces = self.__get_all_turn_pieces()

    for p in pieces:
        self.__jump_moves(p.coord, moves)
        self.__b.wipe()
        self.__simple_moves(p, moves)

    moves.sort(key=len, reverse=True)
    for i in range(len(moves)):
        for j in range(len(moves)):
            if moves[i][:len(moves[j])] == moves[j] and len(moves[i]) > len(moves[j]):
                moves.remove(moves[j])
    return moves

Le problème est le suivant: selon les règles des pions, le joueur doit exécuter le plus grand nombre de captures dans son mouvement. Par conséquent, je dois supprimer les mouvements invalides.

Permet d'analyser cette sortie:

[[3, 0, 5, 2, 3, 4], [5, 0, 3, 2, 5, 4], [1, 0, 2, 1], [1, 2, 2, 3], [1, 2, 2, 1], [1, 4, 2, 3], [2, 5, 3, 6], [2, 5, 3, 4], [2, 7, 3, 6], [3, 0, 5, 2], [5, 0, 3, 2]]

Les premier et deuxième éléments de la liste de sortie contiennent, respectivement, les deux derniers. Je dois donc les supprimer car ils sont une «sous-liste» des premiers.

Le problème est que ma boucle imbriquée ne peut pas résoudre ce problème. Le programme renverse cette erreur:

Traceback (most recent call last):
  File "damas.py", line 435, in <module>
    print(m.get_all_moves())
  File "damas.py", line 418, in get_all_moves
    if moves[i][:len(moves[j])] == moves[j] and len(moves[i]) > len(moves[j]):
IndexError: list index out of range

Après un certain temps, je me demande quelle est la manière la plus pythonique de résoudre ce problème.

0
Dagdeloo 20 nov. 2018 à 19:37

3 réponses

Meilleure réponse

Comme vous l'avez peut-être compris, le problème est que vous ne vérifiez la longueur de moves pour i qu'une seule fois au début. Lorsque vous en supprimez des éléments, vous le raccourcissez, ce qui fait que la variable de boucle i avance finalement au-delà de la taille de la liste.

Il existe plusieurs moyens d'y remédier. Mon approche habituelle pour ce genre de situation, où vous devez évaluer chaque élément d'une liste pour la suppression, est de commencer à la fin de la liste et de revenir au début.

for i in reversed(range(len(moves))):
    for j in range(len(moves)):
        if i != j and moves[i] == moves[j][:len(moves[i])]:
            del moves[i]
            break

Notez que j'évalue moves[i] pour la suppression, et non moves[j]. Si je trouve que je veux le supprimer, je le fais et je sors immédiatement de la boucle interne for. Cela n'affectera que la structure de la liste à et après position i (les éléments que nous avons déjà pris en compte et que nous avons décidé de conserver), pas avant (les éléments que nous n'avons pas encore pris en compte ). Par conséquent, nous ne rencontrerons aucun IndexErrors embêtants.

0
glibdud 20 nov. 2018 à 18:17

Je ne sais pas si c'est la façon la plus pythonique de faire les choses, mais c'est une variante de quelque chose que j'ai utilisé pour vérifier les sous-chaînes qui est assez concise:

def check_for_sublist(sub_list,longer_list): 
    return any(sub_list == longer_list[offset:offset+len(sub_list)] for offset in range(len(longer_list)))

Ou une version lambda, qu'il m'a été conseillé de ne pas utiliser dans les commentaires. Je l'ai laissé ici comme outil d'apprentissage car j'ai appris quelque chose du commentaire!

x_sublist_y = lambda x, y: any(x == y[offset:offset+len(x)] for offset in range(len(y)))

Et puis je pense que ça fera l'affaire. Il crée une liste d'entrées pour lesquelles arraycheck ne renvoie pas True (en veillant à exclure la vérification des termes par rapport à eux-mêmes).

moves = [[3, 0, 5, 2, 3, 4], [5, 0, 3, 2, 5, 4], [1, 0, 2, 1], [1, 2, 2, 3], [1, 2, 2, 1], [1, 4, 2, 3], [2, 5, 3, 6], [2, 5, 3, 4], [2, 7, 3, 6], [3, 0, 5, 2], [5, 0, 3, 2]]

filtered_moves = [move1 for move1 in moves if all([not check_for_sublist(move1, move2) for move2 in moves if move1 != move2])]
0
Andrew McDowell 20 nov. 2018 à 17:29

Voici une solution utilisant une compréhension de liste, qui est souvent une approche utile lorsque vous voulez rendre les choses aussi pythoniques que possible

def is_sublist( seq, lists ):
    for candidate in lists:
        if len( candidate ) > len( seq ) and candidate[ :len( seq ) ] == seq:
            return True
    return False

moves = [[3, 0, 5, 2, 3, 4], [5, 0, 3, 2, 5, 4], [1, 0, 2, 1], [1, 2, 2, 3], [1, 2, 2, 1], [1, 4, 2, 3], [2, 5, 3, 6], [2, 5, 3, 4], [2, 7, 3, 6], [3, 0, 5, 2], [5, 0, 3, 2]]

# here comes the list comprehension:
pruned = [ eachMove for eachMove in moves if not is_sublist( eachMove, moves ) ]

Pour modifier la séquence moves sur place, vous devez l'assigner à moves[:] au lieu d'une nouvelle variable pruned.

Cependant, la solution ci-dessus n'est pas la plus efficace, ce qui peut être un problème si le nombre de mouvements potentiels est important. Une approche moins élégante comme la suivante peut être souhaitable car, à mesure que les mouvements de candidats sont rejetés, nous réduisons le nombre de superlistes potentielles par rapport auxquelles chaque sous-liste potentielle future doit être vérifiée:

accepted = []
while moves:
    eachMove = moves.pop( 0 )
    if not is_sublist( eachMove, moves ) and not is_sublist( eachMove, accepted ):
        accepted.append( eachMove )

moves[:] = accepted

Si l'ordre de la liste des coups n'est pas important, exécuter moves.sort() en haut de cette routine la rendra plus efficace (en fait, alors nous pourrions optimiser encore plus le code, car chaque déplacement ne doit jamais être par rapport au coup suivant dans la liste).

0
jez 20 nov. 2018 à 17:43