Code Day の到来 リネンのレイアウト

19日目: リネンのレイアウト

GitHub ソリューション

今日の課題は、通常の 2D パズルとダイクストラのアルゴリズムからの新鮮な変化でした。私のアプローチ方法は次のとおりです:

パート 1

目標は簡単です。利用可能なタオルを使用して、指定されたタオルの配置を作成できるかどうかを確認することです。

してはいけないこと:

最初に、itertools.combinations を使用して、考えられるすべてのタオルの組み合わせを生成しようとしました。これは実用的でも効率的でもないことがすぐに明らかになりました。

効果があったもの:

辞書 (メモ) と組み合わせた再帰を使用して、すでに処理されたデザインをキャッシュします。これにより、冗長な計算が防止され、ソリューションの効率が大幅に向上します。

仕組み:

各デザインの先頭をタオルのパターンの 1 つと合わせてみてください。
一致するものがあれば、一致した部分を削除し、残りを再帰的に処理します。
メモを使用して、すでにチェックしたデザインの結果をキャッシュし、重複した作業を避けます。
メモ化による再帰的アプローチにより、大規模な入力であっても複雑さが管理可能に保たれ、ソリューションが効率的に実行されます。

パート 2
2 番目の部分では、ハードルが上がりました。利用可能なパターンを使用して各タオルのデザインを作成する方法の数を数えます。

重要な洞察:
count_arrangements 関数はパート 1 の再帰ロジックを拡張していますが、デザインを構築するために考えられるすべての方法を計算するようになりました。

一致するタオルごとに、デザインの残りの部分を再帰的に実行します。
別の辞書 (memo_count) を使用して、以前に解決した部分問題の結果をキャッシュします。

例:
「brgr」が 2 つの方法で構築できる場合は、再計算するのではなく、単純にキャッシュから 2 を返します。

最適化:
パート 1 のおかげで、どのようなデザインが可能であるかはすでにわかりました。私たちはそれらの手配のみを計算します。

すべての有効な方法を合計すると、パート 2 の最終的な答えが得られます。これは非常に簡単です。

私が言ったように、今日のチャレンジはとても楽しくて、良い気分転換になりました。この記事が今後の課題やコーディングに役立つことを願っています。

いつものように、お気軽にフォローしたり、Twitter にご連絡ください

以上がCode Day の到来 リネンのレイアウトの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。