Établir des liens

Défi hebdomadaire 285

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 : Pas de connexion

Tâche

Vous recevez une liste d'itinéraires, @routes.

Écrivez un script pour trouver la destination sans autre connexion sortante.

Ma solution

C'est assez simple et ne nécessite donc pas trop d'explications. Je calcule deux listes, les origines ont les premières valeurs de la liste des itinéraires tandis que les destinations ont la deuxième valeur.

J'utilise ensuite la compréhension de liste pour trouver des destinations qui ne figurent pas dans la liste des origines, et je les stocke comme impasses. Je génère une erreur s'il n'y a pas exactement un élément dans cette liste.

def no_connection(routes: list) -> str:
    origins = [v[0] for v in routes]
    destinations = [v[1] for v in routes]
    dead_ends = [d for d in destinations if d not in origins]

    if len(dead_ends) > 1:
        raise ValueError(
            'There are multiple routes with no outgoing connection')

    if len(dead_ends) == 0:
        raise ValueError('All routes have an outgoing connection')

    return dead_ends[0]

Exemples

$ ./ch-1.py B C C D D A
A

$ ./ch-1.py A Z
Z

Tâche 2 : Apporter le changement

Tâche

Calculez le nombre de façons de rendre la monnaie pour un montant donné en centimes. En utilisant les pièces, par ex. Penny, Nickel, Dime, Quarter et Half-dollar, de combien de manières distinctes la valeur totale peut-elle être égale au montant donné ? L'ordre de sélection des pièces n'a pas d'importance.

• Un centime (P) est égal à 1 centime.
• Un nickel (N) équivaut à 5 cents.
• Un centime (D) équivaut à 10 centimes.
• Un quart (Q) est égal à 25 cents.
• Un demi-dollar (HD) équivaut à 50 cents.

Ma solution

En raison d'un bug (maintenant corrigé) dans mon code, cela a pris un peu plus de temps que je ne l'avais espéré. Je sais que Python et Perl ont un débogueur, mais parfois, vous ne pouvez pas battre les instructions print :)

Cela fait un moment que nous n'avons pas de tâche qui fait appel à l'utilisation d'une fonction récursive. Pour cette tâche, j'ai une fonction récursive appelée making_change qui prend la monnaie restante et la dernière pièce utilisée. Le premier appel définit la valeur left_change sur l'entrée et la valeur last_coin sur None (undef en Perl).

Chaque appel parcourt les pièces possibles et fait l'une des trois choses suivantes :

1. Si la valeur de la pièce est supérieure à la valeur last_coin, nous l'ignorons. Cela garantit que nous ne dupliquons pas les combinaisons possibles.
2. Si la valeur de la pièce est la même que la monnaie restante, nous avons une solution valide, j'en ajoute donc une à la valeur de la combinaison.
3. Si la valeur de la pièce est inférieure à la valeur restante, j'appelle à nouveau la fonction avec la valeur restante réduite de la pièce utilisée.

La valeur des combinaisons est transmise en amont afin que le retour final ait le nombre correct de combinaisons.

def making_change(remaining: int, last_coin: int | None = None) -> int:
    combinations = 0

    for coin in [1, 5, 10, 25, 50]:
        if last_coin and last_coin < coin:
            continue
        if coin == remaining:
            combinations += 1
        if coin < remaining:
            combinations += making_change(remaining-coin, coin)

    return combinations

Il y a des limites à la récursivité. Perl avertira lorsqu'une récursion est (100 de profondeur)[https://perldoc.perl.org/perldiag#Deep-recursion-on-subroutine-%22%25s%22]. Cette valeur ne peut être modifiée qu'en recompilant Perl. Par défaut, Python générera une (ResursionError)[https://docs.python.org/3/library/exceptions.html#RecursionError] après 995 récursions, bien que cette valeur puisse être modifiée au moment de l'exécution.

Exemples

$ ./ch-2.py 9
2

$ ./ch-2.py 15
6

$ ./ch-2.py 100
292

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!