つながりを作る

ウィークリーチャレンジ 285

Mohammad S. Anwar は毎週、毎週 2 つのタスクに対する解決策を全員が考え出すチャンスであるウィークリー チャレンジを送信します。私のソリューションは最初に Python で書かれ、次に Perl に変換されます。これは、私たち全員がコーディングを練習するのに最適な方法です。

挑戦、私の解決策

タスク 1: 接続がありません

タスク

ルートのリスト @routes が与えられます。

それ以上発信接続を行わずに宛先を見つけるスクリプトを作成します。

私の解決策

これは非常に簡単なので、多くの説明は必要ありません。 2 つのリストを計算します。起点にはルート リストの最初の値があり、宛先には 2 番目の値があります。

次に、リスト内包表記を使用して、起点リストにない宛先を見つけ、これを行き止まりとして保存します。このリストに項目が 1 つだけ存在しない場合は、エラーが発生します。

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]

例

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

$ ./ch-1.py A Z
Z

タスク 2: 変化を起こす

タスク

指定された金額をセント単位で変更する方法の数を計算します。コインを使用することで、例えばペニー、ニッケル、ダイム、クォーター、ハーフダラー、合計値が所定の金額と等しくなる方法は何通りありますか?コイン選択の順序は関係ありません。

• 1 ペニー (P) は 1 セントに相当します。
• ニッケル (N) は 5 セントに相当します。
• 1 ダイム (D) は 10 セントに相当します。
• 1 四半期 (Q) は 25 セントに相当します。
• 1 半ドル (HD) は 50 セントに相当します。

私の解決策

私のコードに (現在は修正されている) バグがあるため、これが完了するまでに予想よりも少し時間がかかりました。 Python と Perl の両方にデバッガがあることは知っていますが、場合によっては print ステートメントに勝てないことがあります :)

久しぶりに再帰関数の使用を必要とするタスクを実行しました。このタスクでは、残りの変更と最後に使用されたコインを取得する Making_change という再帰関数を使用します。最初の呼び出しでは、remaining_change 値を入力に設定し、last_coin 値を None (Perl では undef) に設定します。

各呼び出しは可能なコインを反復処理し、次の 3 つのいずれかを実行します。

1. コインの値が last_coin の値より大きい場合は、スキップします。これにより、可能な組み合わせが重複することがなくなります。
2. コインの価値が残りの小銭と同じであれば、有効な解があるので、組み合わせの価値に 1 を加えます。
3. コインの価値が残りの価値よりも少ない場合は、使用したコインを差し引いた残りの価値で関数を再度呼び出します。

組み合わせの値は上流に渡されるため、最終的な戻り値には正しい数の組み合わせが含まれます。

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

再帰には制限があります。 Perl は、再帰が (深さ 100) になると警告します [https://perldoc.perl.org/perldiag#Deep-recursion-on-subroutine-%22%25s%22]。この値は、Perl を再コンパイルすることによってのみ変更できます。デフォルトでは、Python は 995 回の再帰後に (ResursionError)[https://docs.python.org/3/library/Exceptions.html#RecursionError] を発生させますが、この値は実行時に変更できます。

例

$ ./ch-2.py 9
2

$ ./ch-2.py 15
6

$ ./ch-2.py 100
292

以上がつながりを作るの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。