Numbered triangles (Electronic Station) - 三角形のチップを並べる

どんな問題？

Numbered triangles
http://www.checkio.org/mission/numbered-triangles/

正三角形のチップ6個には、各辺に数字が書いてある。
6つを組み合わせて正六角形を作るが、同じ数字が書いてある辺のみを合わせることができる。
六角形の外側の数字の合計ができるだけ大きくなるような組み合わせを見つけて、その合計値を返せ。

文章で読むより、説明の画像を見た方がわかりやすい。
組み合わせが不可能なら0を返す。

三角形のチップは回転するだけでなく裏返すこともできるので注意。
[1,4,20]というチップは、[1,4,20],[4,20,1],[20,1,4]だけでなく、[1,20,4],[4,1,20],[20,4,1]にもなる。

どうやって解く？

全然わからない。
アルゴリズムを知っていれば簡単に解けてしまう感じはするのだが、アルゴリズムの勉強って今まで避けてきたからなぁ。だって、ソートのアルゴリズム知らなくても、sort()って書けばソートできるじゃん。

とりあえず、何も調べずに自力でやってみよう。
三角形を6つ並べるだけなので、全ての組み合わせを試してもしれてるんじゃないか？何通りぐらいあるんだろう。順列、組み合わせとか、記憶がおぼろげ・・・。

アルゴリズムはおいといて、三角形の隣り合う辺の数字をチェックする、というあたりを書いてみる。
問題は、チップの並び順が入れ替わることと、各チップが回転（＆フリップ）するということ。

チップの並び順は、0～5の順列でいいのかな？チップの並び順が、[0,3,2,5,1,4] であれば、
chips[0],chips[3],chips[2],chips[5],chips[1],chips[4]
と並んでいる状態とする。

各チップが回転するところは、チップの辺の並び順を
[ 前のチップと接する辺 , 次のチップと接する辺 , 外側の辺 ]
という形で指定する。辺の並び順が [2,0,1] であれば、
chips[n][2] が前のチップと接する辺
chips[n][0] が次のチップと接する辺
chips[n][1] が外側の辺
となる。

隣り合う辺をチェック

チップ6枚が「隣り合う辺が同じ数字」という条件を満たしているか、満たしているなら外側の数字の合計を返す、という関数を書いた。
チップの並び順(chip_order)と、辺の並び順(rotation_order)を指定すれば、引数のchipsから必要な辺の数字を取得できる。

def check(chips, chip_order, rotation_order):
    total = 0
    for i in range(len(chips)):
        chip = chips[chip_order[i]]
        rotation = rotation_order[i]
        prev_chip = chips[chip_order[i - 1]]
        prev_rotation = rotation_order[i - 1]
        # 前のチップと接する辺の数字が同じかどうかチェック
        if chip[rotation[0]] != prev_chip[prev_rotation[1]]:
            return 0
        total += chip[rotation[2]]  # 外側の数字を足していく
    return total

よし、あとは、チップの並び順と、辺の並び順をリストアップして、全ての組み合わせをチェックすればいい。

チップの並び順

チップはリング状に並ぶので、先頭は0で固定できる。その後は1～5の順列だ。
さらに、1～5が反転した並び順は除外できる。[0,1,2,3,4,5]と[0,5,4,3,2,1]は裏返しただけで同じものなので、どちらか1つでよい。
順列は、itertools.permutations() という、そのものずばりの関数が用意されていた。

itertools.permutations(range(1, 6), 5)

で、1～5を5個並べる順列が得られる。5!=120通り。
裏返したものを除去すると半分になるので、60通り。

perm = set(r if r[0] < r[-1] else r[::-1] for r in itertools.permutations(range(1, 6), 5))

まず [5,4,3,2,1] などは [1,2,3,4,5] に反転させる。それからset()を使って重複を削除する。

辺の並び順（回転の組み合わせ）

上にも書いたが、[1,4,20]というチップは、[1,4,20],[4,20,1],[20,1,4],[1,20,4],[4,1,20],[20,4,1]という6通りのパターンがある。これは、itertools.permutations()で書ける。
さらに、チップは6枚あるから、組み合わせはこの6乗となる。これは itertools.product() で作成できる。6^6=46656通り。そろそろ危険な匂いがしてきた。

rotation = itertools.permutations(range(3), 3)  # (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)
rotation_orders = list(itertools.product(rotation, repeat=6))

まとめ

チップの並び順と、辺の並び順とを合わせると、ループ数が非常に多くなってしまったが、とにかく全部の組み合わせを試して、最大値を求める。こちらがそのコード。

import itertools

def check(chips, chip_order, rotation_order):
    total = 0
    for i in range(len(chips)):
        chip = chips[chip_order[i]]
        rotation = rotation_order[i]
        prev_chip = chips[chip_order[i - 1]]
        prev_rotation = rotation_order[i - 1]
        # 前のチップと接する辺の数字が同じかどうかチェック
        if chip[rotation[0]] != prev_chip[prev_rotation[1]]:
        total += chip[rotation[2]]  # 外側の数字を足していく
    return total

def checkio(chips):
    # チップの並び順 60通り
    perm = set(r if r[0] < r[-1] else r[::-1] for r in itertools.permutations(range(1, 6), 5))
    chip_orders = [[0] + list(r) for r in perm]

    # チップの回転の組み合わせ 6^6=46656通り 
    rotation = itertools.permutations(range(3), 3)
    rotation_orders = list(itertools.product(rotation, repeat=6))

    # 合計 2,799,360 回！
    return max(check(chips, chip_order, rotation_order) for chip_order in chip_orders for rotation_order in rotation_orders)

ローカルマシンでも1つの問題の答えがでるのに3秒ほどかかってしまった。
CheckiOのサーバーにかなりの負荷を与えてしまうかもしれない。

とりあえず Run & Check!
なかなか終わらない・・・。冷や汗。
2分ほどかかったが、なんとかクリア。

う～ん、クリアはしたけど、全く納得はしていない。
昨日、図書館でアルゴリズムの本を借りてきたので、ちょっと読んでみたのだが、この問題にどのアルゴリズムを使えばいいのかもわからない。

悔しいけど、今の私には難しすぎるので、ちゃんとアルゴリズムを勉強してから再挑戦しよう。