L'avènement de la mise en page du linge Code Day

Jour 19 : Disposition du linge

Solution GitHub

Le défi d'aujourd'hui était un changement rafraîchissant par rapport aux puzzles 2D habituels et aux algorithmes de Dijkstra. Voici comment je l'ai abordé :

Partie 1

L'objectif était simple : vérifier si les arrangements de serviettes donnés peuvent être créés à l'aide des serviettes disponibles.

Ce qu'il ne faut PAS faire :

Au départ, j'ai essayé de générer toutes les combinaisons de serviettes possibles avec itertools.combinations. Il est rapidement devenu évident que ce n’était ni pratique ni efficace.

Ce qui a fonctionné :

Utilisation de la récursivité combinée à un dictionnaire (mémo) pour mettre en cache les conceptions déjà traitées. Cela évite les calculs redondants et rend la solution beaucoup plus efficace.

Comment ça marche :

Pour chaque motif, essayez de faire correspondre le début avec l'un des motifs de serviette.
S'il y a une correspondance, supprimez la partie correspondante et récurez sur le reste.
Utilisez Memo pour mettre en cache les résultats des conceptions que nous avons déjà vérifiées, évitant ainsi les travaux en double.
L'approche récursive avec mémorisation maintient la complexité gérable, même pour des entrées plus importantes, et permet à la solution de fonctionner efficacement.

Partie 2
La deuxième partie a fait monter la barre : comptez le nombre de façons de créer chaque motif de serviette en utilisant les modèles disponibles.

Information clé :
La fonction count_arrangements étend la logique récursive de la partie 1, mais calcule désormais toutes les manières possibles de construire une conception.

Pour chaque serviette assortie, répétez sur le reste du motif.
Utilisez un autre dictionnaire (memo_count) pour mettre en cache les résultats des sous-problèmes précédemment résolus.

Exemple :
Si "brgr" peut être construit de 2 manières, nous en renvoyons simplement 2 depuis le cache au lieu de le recalculer.

Optimisation :
Grâce à la première partie, nous savons déjà quelles conceptions sont possibles. Nous calculons uniquement les arrangements pour ceux-là.

for arrangement in arrangements:
    if arrangement in memo and memo[arrangement]:
        ways = count_arrangements(arrangement, towels, memo_count)
        total_arrangements += ways

En résumant toutes les méthodes valables, nous obtenons la réponse finale pour la partie 2, aussi simple que cela.

Comme je l'ai dit, j'ai trouvé le défi d'aujourd'hui assez amusant et c'était un bon changement. J'espère que cet article vous a aidé pour les futurs défis/codage.

Comme toujours, n'hésitez pas à me suivre ou à me contacter sur Twitter

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!