12A猫で学んだこと-Memoir-

...What are you learning now?

プログラム練習ノート

こんにちは。StudentSです。
4月になりました。季節は春ですね。おひさまがぽかぽかしていて気持ちいいですね。
最近読んだ本の中にいいなぁ、と思ったフレーズがありました。
原文とは違うけれど、下記のような文章でした。

思い出って、おひさまの光に似ているね。心をあったかくしてくれる。
でも、抱きしめようとしても、重みを感じられないんだよね。

わたしの青春はいつくるんだろうなぁ? と思いながら、今日も何とか生きています...

1月に1度は何かブログをかけるようにしようと思っています。
Studentは、宿題やレポートの提出を迫られたら、例えネタがなかったとしても、
提出しなくちゃいけないんです。

最近、Pythonの練習にCheckIOというサイトで問題を解いています。
そして、上手い方々の答えを見て、勉強させてもらっています。
その中の1問に
Numbered triangles
という問題がありました。
問題の要旨としては、

  • 6枚の正三角形があり、それぞれの辺に数字がかいてある。
  • 6枚の正三角形をくっつけて正六角形を作る。ただし、くっつけることができる辺は同じ数字を書いてある辺だけ。
  • 作ることができる正六角形の辺の6つの数字(くっつけるのに使っていない数字)の和の最大値を求める。

という問題です。 この問題に恋に恋する人狼PLらしく、アタックしてみたいと思います。

パズルを解いてみる

それじゃあ、考えていこー よろしくね!
パズルも人狼も初手考えることは、全探索 だよね。
人狼なら自分以外を死亡させたら、基本的には自分の勝ちだし、
パズルだって、全てのケースを調べたら、問題は解ける。
吊り数や噛みの回数に余裕があったり、計算量的に可能なパズルだったら、まずそれだよね! このパズルを全探索するなら、1つの三角形の位置だけ固定させて、他の順番と向きを考えて... 考えなきゃいけないパターンは \( 5! \times (3!)^5 \times 3 \) になるかな?

factorial = lambda n: (lambda g,i:g(g, i))(lambda f, a: a if a <= 1 else f(f, a -1) * a, n)

簡単に階乗関数を使って計算してみると933120。これなら、全探索できそうだよね。
ちょっと効率の悪いスクリプトでも押し切れそうだね! ということで、愚直やってみよー!
クラスの女の子も、素直な男の子の方が扱いやすくて可愛いって言ってたしね!

def checkio(chips_input):
    pass

chips_inputにリストのリストで入力が入ってくるから、まずは6枚の三角形の並びを決めた時、スコアを計算する関数を書くね!

def calc_score(chips):
    """
    chip[i][0]: the length of hexagonal.
    chip[i][1]: counterclock's direction.
    chip[i][2]: anti-counterclock's direction.
    """
    #  chips[0][2] == chips[1][1] == ... chips[5][2] == chips[0][1]
    legal = all(chips[i][2] == chips[(i+1) % 6][1] for i in range(6))
    number_sum = sum(chip[0] for chip in chips)
    return legal * number_sum

とりあえず、まずはこんな感じかな? ルール違反の時は0にすればいいもんね。
ルールがはっきりすれば、後は全部のパターンを作るだけ。
「運命の人を見つけたら、後は愛するだけでいい」って言っていたのは誰だっけ?
授業で聞いた気がするんだけど、忘れちゃったなぁ。
好きな人をずっと好きでいるのが難しいのと同じで、やることが分かっていても実際に行うのは大変だよね。
ちょっと頑張ると、下みたいな感じでいいかな?

from itertools import permutations, product, chain
def checkio(chips_input):
    fixed = chips_input[0] # fixed triangle.
    chips = chips_input[1:] # triangles to be permutated.

    # For fixed triangle, only the length of hexagonal is fixed. (3, not3!.)
    fixed_patterns = [[fixed[li]] + [fixed[i] for i in range(len(fixed)) if i != li] for li in range(len(fixed))]
    concatenate_patterns = lambda chips: list(map(lambda fixed: [fixed] + chips, fixed_patterns))

    ps = map(lambda p:permutations(p), chips)  # Triangle Direction's patterns.  (3!)
    s = product(*ps)  # The group of triangles (whose direction's are not considered.)
    cand = map(permutations, s)  # Consider the order of triangles.
    # Generate the all patterns and check the maximum.
    result = 0
    for q in chain.from_iterable(cand):
        cands = concatenate_patterns(map(list, q))
        result = max(result, max(map(calc_score, cands)))
    return result

これで提出してみると、Task Solved!
でも、もう少し面白い感じにしたいよね...
このコードはエンターテイメントがないんだよね。
驚きやときめきあがないように感じる...
ボクなりにちょっと頑張るね!

from itertools import permutations, product, chain
checkio = lambda ci: max(max(map(lambda chs: all(chs[i][2] == chs[(i+1) % 6][1] for i in range(6)) * sum(ch[0] for ch in chs),
                            ([elem] + list(map(list, q)) for elem in ([ci[0][li]] + [ci[0][i] for i in range(3) if i != li] for li in range(3)))))
                         for q in chain.from_iterable(map(permutations, product(*map(permutations, ci[1:])))))

これが、ボクの答えだ! いつか運命の人に出会えることを祈った4-liner!

  • 2行目は答えを出す部分
  • 3行目は固定する三角形と他の三角形をくっつけるのを考える部分
  • 4行目は三角形の置き方を全て列挙する部分

これでどうかなぁ...ときめきがあるかな?
ちょっと細かいところで変なところもあるけれど、わくわくするようなそんなプログラムだといいなぁ。
少しずつ戸惑うかもしれないけれど、一緒にいて楽しい思い出をたくさん作れる...そんな素敵な人に出会いたいな。

速度改善について

これで正解はできたけれど...遅いんだよね...
短期村の人狼ゲームで人外の騙りとして大切なのは質の高い占い文を短時間で作り上げること
...速度が重要になるんだよね。  
遅い理由は、permutationsで、ルールに一致しない例を大量に作っているから。
permutationsで、例を作る時にルールに一致するかをチェックすれば、早くなるはず。
ということで、その関数を作ろうー!

from itertools import permutations, product, chain

predicator = lambda l, n: not l or l[2] == n[1]
def mperm(cands):
    def _inner(indices):
        if len(cands) == len(indices):
            yield tuple(cands[i] for i in indices)
        for i in range(len(cands)):
            if i not in indices and predicator(tuple(cands[indices[-1]]), tuple(cands[i])): 
                yield from _inner(indices + [i])
    for i in range(len(cands)):
        yield from _inner([i])


checkio = lambda ci: max(max(map(lambda chs: all(chs[i][2] == chs[(i+1) % 6][1] for i in range(6)) * sum(ch[0] for ch in chs),
                            ([elem] + list(map(list, q)) for elem in ([ci[0][li]] + [ci[0][i] for i in range(3) if i != li] for li in range(3)))))
                         for q in chain.from_iterable(map(mperm, product(*map(permutations, ci[1:])))))

ということで、itertools.permutations もどきを作って見たよ。
そして、要素を追加する時に、ルールをチェックするようにしたけれど、不格好だよね...
それに最悪計算量は変わらないし...
うーん、人狼も恋もプログラムも難しいね!

終わりに

ここまで読んでくれた人、ありがとー!
全探索の問題ってさ、人狼の詰み進行の時みたいに何も考えずにやっていくだけで頭をつかうことって少ないんだよね。
でも、人狼ゲームの結果が決まっているとしても、その中の過程がつまらないものになるか、面白いものになるかはプレイヤーたちの腕で決まると思っているよ!
このパズルの問題は全探索の問題だけど、その中の過程でなにかのときめきを作ることができていたら、ボクは嬉しいな!
また会うときがあったらよろしくね!

補足と反省

  • まずは問題作成者の方に感謝を。他の問題も含めてよい練習をさせていただいております。

  • 回答編にはすごい人達のコードがあるので、興味のある方は読まれることをおすすめします。先駆者の方々のコードをみたら、類似のアイデアはすでに上がっています。

  • 上記の回答は自分の中でかなり苦労して書いています...最初に正解にたどりついたコードは... (ときめきなんて、全然なかったよ!)

  • RPとネタのはさみ方が人狼と恋愛関係で半分ずつぐらいになっていて統一性がないなぁ。次はもう少し統一性を持たせないかな?

  • RPのキャラクターの幅をもう少し広くすることは今後の課題です。