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

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

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

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

みたいな感じになる。

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

問題: Break Rings

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

問題は

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

f:id:ssuwam:20160606204816p:plain

入力として 整数の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

f:id:ssuwam:20160606204951p:plainf:id:ssuwam:20160606204956p:plainf:id:ssuwam:20160606204959p:plain おおう...このくらい絡まり合ってるとどの手順で破壊すれば回答に辿り着けるのか手作業じゃ分からん。
これは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

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

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

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

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

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

try! Swiftに参加していた。

短いインターバルで内容を咀嚼していくのはなかなかハードだったけど、内容がそれぞれ極まっていた。

同時通訳のレシーバーが足らないという話が気掛かりだったけど戻っていたようで、よかった。

とりあえず、個々のテクニックは別にして今回感じたことは大きく2つ

Swiftのプログラミングスタイル

Objective-Cは、誰が書いても同じようなコードになる。
Objective-Cnilへのメソッド呼び出しが無視されたり
評価するとデフォルト値を返すなどして、簡単にヌルポを吐かない代わりに独特の意訳をする言語だ。
標準のNSArrayや、NSDictionaryに値を詰めると型が消えるという仕様、ダイナミックなメソッド呼び出しは完全に動的言語のそれで、主な使命がFoundationやUIKitのAPIの利用ということを差し引いても`There's Only One Way To Do It`だ。

Swiftはどうか、というとSwift2からProtocol Oriented Programingが提唱されており、メタプログラミングが追加されRxをはじめとしたFunctionalなプログラミングスタイルが既に人気を集めている。
そして、恐ろしいことにそれらは日々増え続ける状態の管理を幾分か、簡明にする優れた答えの一つでもある。
まあだいたい、言いたいことはakisuteさんが仰っておられた通り。 

try! Swift SwiftらしいTable View Controllerの使い方

try! Swift Protocol-Oriented Programming in Networking

try! Swift パーサーコンビネーター in Swift

自分も見習ってキラッキラしたSwiftコードを書きてえと思う一方で、エクストリームな世界に対しては、身構えるところもある...。

Swift Package Managerとswiftenv

今回は基本的にiOSに向けたセッションだったが

try! Swift Swiftでサーバを書いてみよう #tryswiftconf Day3-2 - niwatakoのはてなブログ

try! Swift ライブラリの開発 #tryswiftconf Day2-8 - niwatakoのはてなブログ

 はLinux環境での利用について言及していた。

これらは今後一年で主流になっていくと思われるので、試す。(cocoapodsはコマンド一発で使える、cartageもビルドの速さなど、過去の資産も含め一日の長があるのでそれなりに使われていくと思う)
来年は上から下まで全部swiftで書いたとかraspi動かしたみたいなセッションが出るんだろうか。

Party

英語使えないのにお酒を飲んで外国の参加者の方に意味不明な絡みをしてしまった。

とても申し訳ない、勉強させていただきます。

棚上げテキスト 1.0.0

自分用のメモアプリをリリースした

棚上げテキスト

棚上げテキスト

  • Fumiya Kubota
  • Productivity
  • Free

どんなアプリか

棚上げ機能が付いている機能に乏しいメモアプリ。

棚上げ機能

編集中のテキストにリンクの定型文を登録して埋め込むことができる。
棚上げした文は、リンクをタップした先で後から変えることと
それについてのdescriptionを書くことができる。

f:id:ssuwam:20160109105820p:plain  f:id:ssuwam:20160109110033p:plain

何を目指したのか

考えをまとめようとしている時「まだ決まっていない概念」が思考の邪魔をすることが自分はよくある。
ただ、それをまとめるためだけに別のメモを作るなどするとたぶん一番重要な全体の流れからは遠ざかってしまう。
全体の流れを考える上で障害となるものを全て棚上げして、今考えていることの最後まで辿り着くことの助けとなるようなメモアプリを目指して作った。

なんで作ったのか

理由1

灯台下暗しというか

「そらそうよ」のフリック入力は気持ちいい [転載禁止]©2ch.net

http://orpheus.2ch.net/test/read.cgi/livejupiter/1431911650/l50

最近こういうスレが立つことが多くてハッとしたんだけど
片手の入力方式としてのフリック入力は暫定最強(日本語限定だし他は英語環境くらいしか知らないが)だと気付かされたので
もう少し片手間のアウトプットとして使っていきたいと思った。
何か作れば、自分くらいは使うだろうと。

理由2

RPGツクールMV発売に向けてそれに役に立つようなやつが欲しかった。
試しにライトノベルのあらすじだけ書いてみたらそこそこ便利だった。

作ってみてどうだったか

  • 仕事で使うには割と慎重派なんだけど、まあ単純すぎるアプリだしrealm便利だった。アプリの知能指数があがった。
  • 「棚上げ」は棚上げした名前というか気分的には「棚上げ(仮)」みたいな感じなんだけど最後まで思い浮かばないまま出てしまった。

TODO:

  • 棚上げ画面のUI改善
  • エクスポート
  • フォルダ分け(棚上げした定型文の名前空間的なものが欲しい)