最適化系の問題を解いてみる。

自分はPythonが第一言語なので https://checkio.org/ でよく遊ぶ。
自分のプログラム力はお世辞にも高いとは言えないようなレベルだと思うけど
そもそも普段の仕事はUIKitとかReactとかのフレームワークやライブラリと仲良くすることであってあまり自分でアルゴリズムとかを考えたりしないし
それに胡座を書き続けてきた結果CodeIQ(の簡単なやつ)は解けるがPaizaは全くワカランみたいな状況になって死にたくなったりするのでまあ似たような思いをしている人がいることを信じて出来なかった問題を解くまでを書いてみたいと思う。

自分がこういうプログラミングクイズみたいな問題に取り組むと

• FizzBuzzに毛が生えたようなやつ→解ける
• FizzBuzzに手足が生えたようなやつ→頑張れば
• 経路探索くらいのやつ→ググりながらやればなんとか
• 最適化→ググってもわからん

みたいな感じになる。

この先も似たようなことはあるとは思うけどその都度こんな感じでクリアしていきたい、と思う。 前置き終わり。

問題: Break Rings

→ https://checkio.org/mission/break-rings/

問題は

• 繋がりあった複数のリングがある。
• リングには番号が振られている。
• 何回かリングを破壊してバラバラに(全てのリングがどれとも繋がっていない状態)にしたい。
• 破壊する回数で一番少なく済むものを求める。

入力として 整数のsetのtupleが与えられる。これは対応するリングとリングの繋がりを示す。

input_value = ({1,2},{2,3},{3,4},{4,5},{4,6},{6,5})

出力はリングを破壊する回数。
↑の画像は3つ壊せばバラバラになる。

break_rings(input_value) == 3

考えたこと

つながっているリングが多いもの優先して壊せばそれが一番回数が少なくなるのでは？

やってみた。結論から言うとダメだった。

from collections import Counter

def break_rings(rings):
    break_count = 0
    while True:
        counter = Counter()
        for ring in rings:
            # 二個揃っていないものは除外
            if len(ring) != 2:
                continue
            l, r = ring
            counter[l] += 1
            counter[r] += 1
        # 二個揃うものがない(=バラバラ)
        if len(counter) == 0:
            break
        common, _ = counter.most_common(1)[0]
        break_count += 1
        for ring in rings:
            if common in ring:
                ring.remove(common)
    return break_count

おおう...このくらい絡まり合ってるとどの手順で破壊すれば回答に辿り着けるのか手作業じゃ分からん。
これは8個目のテストなので途中までは、まあ...。
そもそも最適化問題ってFizzBuzzみたいな明瞭な答えがあるのか分からないな…。

続・考えたこと

更に眺めていると、この問題は入力を単なる「ペアの集合」と考えれば良くて
ペアのどちらかに該当する数字で、全てのペアを網羅するリングの数字を列挙すれば良いのでは？というように見えてきた。
うまく説明できないけど... 例えば入力が

input_value = ({1, 2}, {2, 3}, {3, 4})

だったら(2, 4) or (2, 3) or (1, 3)で網羅できる。
明瞭なアルゴリズムはあるのかも知れないが自分には思いつかないので、全パターンを試してみることにする。

from itertools import permutations


def break_rings(rings):
    ring_numbers = set()
    # 登場するリングを集める
    for l, r in rings:
        ring_numbers.add(l)
        ring_numbers.add(r)

    break_count = len(ring_numbers) - 1
    # 壊すリングの順番を生成
    for break_rings in permutations(ring_numbers):
        filtered_rings = rings
        for count, ring in enumerate(break_rings, 1):
            # ペアのどちらかに含まれるものを除外していく
            filtered_rings = [r for r in filtered_rings if ring not in r]
            # break_countを超えてしまったら以降の検証は打ち切る。
            if count > break_count:
                continue

            # 全てのリングを網羅した。
            if not filtered_rings:
                break_count = count
                continue
    return break_count

オーダー数は、リングの数の順列の数…か? 時間は掛かるが失敗のケースは通ってくれる。

最適化

checkio.orgの検証がまるで終わらないので最適化を考えてみる。
そもそも個数しか求められていないので、全パターン網羅する必要はない。
そして、壊す順番も実は関係ない。
なので、 繰り返しを許さない組合せでいいし、検証は、短いものから始めて成功したら終了で良い。

from itertools import combinations

def break_rings(rings):
    ring_numbers = set()
    # 登場するリングを集める
    for l, r in rings:
        ring_numbers.add(l)
        ring_numbers.add(r)

    for break_count in range(1, len(ring_numbers)):
        # 壊すリングを生成
        for break_rings in combinations(ring_numbers, break_count):
            filtered_rings = rings
            for count, ring in enumerate(break_rings, 1):
                # ペアのどちらかに含まれるものを除外していく
                filtered_rings = [r for r in filtered_rings if ring not in r]
                # 全てのリングを網羅できた
                if not filtered_rings:
                    return break_count

手元のケースでは一瞬で終わるがどうか。 もっと良い答えはいくらでもあるのかもしれないが、ひとまず。

他の人の解答を見る前の感想

やる前は、知ってるか知らないかで終わるような解答があるのではみたいな甘えた考えがあったが、まあ、ないよな...。
あと(まるで自分が本当に壊すかのように)ストーリーに引っ張られると良くなくて壊す順番とかが大事なんじゃないかみたいな本質的じゃない部分に目が行きがちだった。
入力見て欲しい出力を考えて、それをどうやれば導けるかを考えてどういう性質があるか考える。
書いてみると当たり前なんだけど…。

他の人の解答を見た後の感想

一位の得票(イケてるコードの人に投票する仕組みがある)の人は同じcombinationsで組んでいて、product(積集合)の人も多そうだった。コード自体がイケてるかは別にして、とりあえずこんなもんか…。
次も頑張ろう。