橋を修理する方法、Advent of Code ay 7

永遠のように感じられた時間 (正確には 5 時間) を経て、20 日目パート 2 はついに協力することにしました。待っているのでまだ少しボーッとしていますが、任務が始まります。今日は Advent of Code の 7 日目に取り組み、先週の 6 日目から再開します。今日の私たちの任務は、橋を修復して橋を渡り、主任歴史家の捜索を続けることです。

Microsoft Copilot によって生成されたかわいいイラスト

今日のチャレンジでは、別の種類の問題が提示されます。特定の形式で配置された数字のリストが与えられます (幸いなことに、今日は 2D パズルではありません…)。各行は方程式を形成するように設計されていますが、演算子はありません。私たちのタスクは、さまざまな演算子をテストして、結果の方程式が当てはまるかどうかを判断することです。

入力を処理するために 2 つの解析関数を使用します。解析関数は、まず各行をコロン (:) 文字で分割します:

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

parse_line は、期待される文字列とオペランドの文字列を整数に変換し、期待される整数と整数オペランドのタプルを含むタプルを返します

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

私は関数型プログラミング スタイルを好みます。Python の命令型の性質にもかかわらず、toolz/cytoolz のようなライブラリは非常に便利です。今日は、toolz.functoolz の thread_first を使用します。 thread_first の動作方法は次のとおりです。初期値を取得し、関数と引数のペアのシーケンスを適用し、結果を各ステップに通します。

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

この例では、thread_first は 1 で開始し、次に 2 で add を適用し (結果は 3)、最後に 2 で mul を適用します (結果は 6)。これは mul(add(1, 2), 2) と同等です。

次に、演算を適用するための計算関数を定義します。関数のタプル (funcs) とオペランドのタプル (operands) を入力として受け取ります:

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

アサートは、関数よりもオペランドが 1 つ多いことを保証します。 operands[1:] は関数のオペランドを提供します。 zip と * は、連鎖計算を実行する thread_first の関数とオペランドのペアを作成します。

例:

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

ここで、check_can_calibrate 関数を使用して入力の各行を検証できます。この関数は、期待される結果、オペランド、および可能な関数のタプルを入力として受け取り、関数の組み合わせが期待される結果を生成する場合は True を返し、それ以外の場合は False を返します。

def check_can_calibrate(
    expected: int,
    operands: tuple[int, ...],
    funcs: tuple[Callable[[int, int], int], ...],
) -> bool:
    return next(
        filter(
            None,
            (
                calculate(funcs, operands) == expected
                for funcs in product(funcs, repeat=len(operands) - 1)
            ),
        ),
        False,
    )

itertools.product はすべての関数の組み合わせを生成します。ジェネレーター式は、予想される結果と一致する組み合わせがあるかどうかをチェックします。 filter(None, ...) と next(..., False) は、最初の True の結果を効率的に見つけます。見つからない場合は False を返します。

パート 1 では、乗算と加算の演算子のみが与えられています。このパズルでは、これらの演算子を使用して有効な方程式を形成できる、期待値の合計を求めます。この合計を計算するために評価関数を実装します。

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

解析された入力を反復処理し、check_can_calibrate が True を返す期待値を合計します。

最後に、これまでに構築したものからパート 1 を組み立てます

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

この関数は、parse を使用して入力を解析し、解析されたデータと乗算と加算をそれぞれ表す関数のタプル (operator.mul、operator.add) を使用して評価を呼び出します。

パート 2 では、2 つの数値を結合する連結演算子に遭遇します。 Python では、これは f-string を使用するのと同じです:

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

これにより、最初の数値の末尾に 2 番目の数値の桁が追加され、新しい数値が効果的に作成されます。

あるいは、数式を使用して連結を実行することもできます。正の整数 x の桁数は、次の式を使用して計算できます。

これが機能するのは、log₁₀(x) が x を得るために 10 を累乗する必要があるためです。 Floor 関数はこれを最も近い整数に切り捨て、1 を加算すると桁数が得られます。例として 123 を見てみましょう:

これを int_concat 関数として実装します:

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

整数の連結を実行すると、文字列変換のオーバーヘッドが数学的に回避されます。文字列の連結にはメモリの割り当てと操作が含まれるため、特に大きな数値や多数の連結の場合、直接の整数演算よりも効率が低くなります。したがって、この数学的アプローチは一般に高速でメモリ効率が高くなります。

最後に、パート 2 を実装します。パート 1 との唯一の違いは、int_concat 演算子の追加です。

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

タダ！ 7 日目をクリアしました。これは、特にその後の日に比べて、比較的簡単な課題でした (20 日目の最適化はまだ頭が痛くなっています?)。最高のパフォーマンスではないかもしれませんが、読みやすさを優先しました。

今日はここまでです。良い休日と良い新年を?!来年の雇用状況が改善されることを願ってやみません (まだ #OpenToWork です。コラボレーションについては私に連絡してください!)。また来週書きます。

以上が橋を修理する方法、Advent of Code ay 7の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。