Supprimer les triplets de nombres adjacents de la liste

Question

Voici le problème. L'entrée est une liste d'entiers. Si trois nombres adjacents apparaissent les uns à côté des autres, ils doivent être supprimés et l'opération se poursuit. Application iPhone avec des balles de mêmes couleurs. Le résultat devrait être le nombre de balles qui seront détruites.

Exemple :

input = [3,3,4,4,4,3,4]

1ère itération

output: [3,3,3,4]

Résultat final :

6   

4,4,4 lors de la première itération, donc trois balles. et 3,3,3 à la deuxième. Au total six.

Mon code est ci-dessous. Il va supprimer les 4,4,4 mais échouera ensuite, car l'index de la liste dépassera rapidement la plage.

    def balls(a):

        curr_index = 0
        removed_count = 0
        while len(a) > 2:

            if (a[curr_index] == a[curr_index+1]) and (a[curr_index] == a[curr_index+2]):

                a.remove(a[curr_index])
                a.remove(a[curr_index+1])
                a.remove(a[curr_index+2])

            curr_index += 1
            removed_count += 3

        return removed_count

a = [3, 3, 4, 4, 4, 3, 4]

print(balls(a)) # devrait afficher 6

Des idées ?

Answer 1

Je suis un peu en retard, mais mon idée est de faire le traitement en une seule passe. L'idée est que lorsque vous déposez un triplet, revenez en arrière de deux positions pour vérifier si un nouveau triplet a été créé par ce changement.

Exemple:

3 3 4 4 4 3
    ^--- triplet trouvé ici, supprimez-le
3 3 3
^--- déplacez le curseur de 2 positions vers la gauche et continuez à vérifier

Le code:

def drop3(lst):
    # drop3 détruit le lst, faites une copie si vous voulez le conserver
    dropped = 0 
    cursor = 0 
    limit = len(lst) - 2 
    while cursor < limit:
        if lst[cursor] == lst[cursor+1] == lst[cursor+2]:
            del lst[cursor:cursor+3]
            cursor = max(0, cursor-2)
            limit -= 3
            dropped += 3
        else:
            cursor += 1
    return dropped

Answer 2

Une solution en temps linéaire:

def balls(a):
    b = []
    for x in a:
        b.append(x)
        if b[-3:] == [x] * 3:
            del b[-3:]
    return len(a) - len(b)