自分は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]
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(積集合)の人も多そうだった。コード自体がイケてるかは別にして、とりあえずこんなもんか…。
次も頑張ろう。
