Compression d'allumettes

Défi hebdomadaire 296

Chaque semaine, Mohammad S. Anwar envoie The Weekly Challenge, une chance pour nous tous de trouver des solutions à deux tâches hebdomadaires. Mes solutions sont d'abord écrites en Python, puis converties en Perl. C'est une excellente façon pour nous tous de pratiquer le codage.

Défi, Mes solutions

Tâche 1 : Compression de chaînes

Tâche

Vous recevez une chaîne de caractères alphabétiques, $chars.

Écrivez un script pour compresser la chaîne avec un encodage de longueur d'exécution, comme indiqué dans les exemples.

Une unité compressée peut être soit un seul caractère, soit un nombre suivi d'un caractère.

BONUS : Écrivez une fonction de décompression.

Ma solution

Grâce à la puissance des expressions régulières, c'est une tâche assez simple. Python et Perl permettent à la valeur de remplacement d'être une fonction. J'ai donc une fonction appelée sc qui convertira plusieurs lettres en un chiffre et en la lettre. Par exemple, si l'entrée était aaa, elle renverrait 3a.

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

Il s'agit ensuite d'appeler cette fonction selon les besoins.

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])+)', sc, s)

La fonction de décompression (Python uniquement) fonctionne de la même manière. Il prend un modèle d'un nombre suivi d'une lettre et le remplace par la lettre répétée le nombre d'occurrences spécifié.

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

Pour l'exécution depuis la ligne de commande, j'utilise le module argparse pour voir si l'option --decompress est spécifiée.

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("--decompress", help="decompress the input", action='store_true')
    parser.add_argument("str", help="the string to compress/decompress")
    args = parser.parse_args()

    if args.decompress:
        result = string_decompress(args.str)
    else:
        result = string_compress(args.str)
    print(result)

Exemples

$ ./ch-1.py abbc
a2bc

$ ./ch-1.py aaabccc
3ab3c

$ ./ch-1.py abcc
ab2c

$ ./ch-1.py --decompress a2bc
abbc

$ ./ch-1.py --decompress 3ab3c
aaabccc

$ ./ch-1.py --decompress ab2c
abcc

Tâche 2 : Carré d'allumettes

Tâche

Vous recevez un tableau d'entiers, @ints.

Écrivez un script pour savoir s'il est possible de créer un carré en utilisant les bâtons comme dans le tableau donné @ints où $ints[ì] est la longueur du i-ème bâton.

Ma solution

Ça va être un peu long, alors attachez-vous. La première chose que je vérifie, c'est que la somme des bâtons est divisible par quatre. Si ce n'est pas le cas, il n'y a pas de solution possible et je peux renvoyer false

Je peux également vérifier qu'aucun bâton n'est plus long qu'un côté. Si cela se produit, je renvoie également false.

Avec ces deux vérifications, tous les exemples donneraient le résultat correct. Cependant, cela indiquerait à tort que 4 3 3 3 3 est vrai alors qu'en fait ce n'est pas le cas.

Tentative deux

En regardant les exemples et ma propre réflexion, j'ai pensé que la solution serait de faire correspondre une paire de valeurs pour correspondre à chaque côté. Donc, pour l'exemple 3 4 1 4 3 1, nous avons deux paires de bâtons 3 et 1, ce qui fait quatre. Cela résoudrait le problème du 4 3 3 3 3, car trois n'a pas de correspondant.

Mais cela ne fonctionnerait pas si les bâtons étaient 4 4 3 1 2 1 1, car un côté utilise trois bâtons (un 2 et deux 1)

Tentative trois

Ma prochaine tentative a donc été un peu plus compliquée, et j'ai pensé que c'était une bonne solution... jusqu'à ce que ce ne soit pas le cas. Pour cette tentative, j'ai commencé avec le bâton le plus long. Si ce n'était pas la longueur du côté, j'ai ensuite pris le bâton le plus long nécessaire pour terminer le côté, et j'ai répété jusqu'à ce qu'il n'y ait plus de solution possible. En utilisant cette méthode, les solutions suivantes étaient vraies.

• 4 4 3 1 2 1 1
• 9 5 4 3 3 3 3 3 3
• 9 6 3 5 4 3 3 3
• 9 6 3 5 4 3 3 2 1

Je pensais que c'était la solution, jusqu'à ce que je réalise que 9 5 3 1 5 2 2 3 3 3 ne fonctionnerait pas. Le premier côté est 9, le côté suivant est 5 3 1, et le troisième côté échouerait avec 5 3 et non 1.

Tentative quatre

À ce stade, j'ai commencé à me demander s'il était même possible de trouver une solution qui n'impliquait pas la force brute. J'ai donc dormi dessus, griffonné plein de choses sur ma tablette (je suis en vacances donc je ne peux pas utiliser mon tableau blanc), et j'ai de nouveau dormi dessus. Ma conclusion est que l'utilisation d'une fonction récursive est la seule solution.

Peut-être que je réfléchis trop à tout cela, ou peut-être qu'il existe une solution très simple à laquelle je viens de penser (comme ce fut le cas la semaine dernière).

Le code final

Vous lisez toujours ? Bravo :)

Pour cette tâche, j'ai une fonction récursive appelée make_side. Il faut une liste (arrayref en Perl) des bâtons restants et la longueur requise. Il passe ensuite par les bâtons restants (le plus haut en premier). Ensuite, l'une des trois choses suivantes se produit :

• Si le bâton est plus long que la longueur requise, je le saute.
• Si c'est la longueur requise, je la retourne.
• S'il est court, je l'utilise et j'appelle à nouveau la fonction pour utiliser un autre stick. L'appel retire le bâton utilisé, et réduit la longueur requise de la longueur du bâton utilisé.

La fonction renverra une liste des sticks utilisés, ou None (undef en Perl) si aucune combinaison valide de sticks n'est trouvée.

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

La dernière pièce du puzzle, j'effectue les vérifications mentionnées dans la première partie (la somme est divisible par quatre, pas de bâton plus long qu'un côté), puis j'appelle la fonction ci-dessus. Si cela renvoie None, je renvoie false. Si tous les bâtons sont utilisés, je renvoie vrai.

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])+)', sc, s)

Exemples

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!