summer_tree_home

Check iOでPython3をマスターするぜっ

Loading Cargo (Scientific Expedition) - 荷物は左右均等に

Python CheckiO

どんな問題？

Loading Cargo
http://www.checkio.org/mission/loading-cargo/

複数の荷物を、できるだけ重さの差が少なくなるように2つのグループに分けよ。

引数は、荷物の重さ（整数値）のリスト。
戻り値は、2つのグループの重量差の絶対値を返す。

問題文にヒントが書いてある。

例題：

checkio([10, 10]) == 0
checkio([10]) == 10
checkio([5, 8, 13, 27, 14]) == 3
checkio([5, 5, 6, 5]) == 1
checkio([12, 30, 30, 32, 42, 49]) == 9
checkio([1, 1, 1, 3]) == 0

どうやって解く？

最初は、ヒントを気にせずに、自分で考えてみる。スーパーでたくさん買い物して、右と左2つの袋を同じぐらいの重さにしたいときってどうするかな？

重いものから順番に

荷物の重い品物から順番に、左右に分散させていけば、だいたい同じぐらいになりそうな気がする。これをコードにしてみた。

def checkio(data):
    data.sort(reverse=True)
    # 重い荷物から順番に、軽い方の袋に入れていく
    left, right = [], []
    for d in data:
        if sum(left) < sum(right):
            left.append(d)
        else:
            right.append(d)
    # 右と左の重さの差を計算
    return abs(sum(left) - sum(right))

実行してみる。

AssertionError: 5th example
    assert checkio([12, 30, 30, 32, 42, 49]) == 9, "5th example"

やっぱダメか。
正解は [30, 30, 42] と [12, 32, 49] で差は9だが、
上のコードだと、[42, 32, 30] と [49, 30, 12] で差は13になっている。


重いものから順番に、ではダメみたいだ。
ヒントに書いてあるように、すべての組み合わせを試してみよう。

総当たり（順列）

左と右の2つのグループに分けるのって、どうすればすべてのパターンを試せるだろう？
まず、すべての荷物を順列で並べて、さらに、それを左右に分割すればできそうだ。

荷物が A,B,C の3つなら順列で

[A,B,C], [A,C,B], [B,A,C], [B,C,A], [C,A,B], [C,B,A]

の6パターン。
さらにそれぞれについて左右に分割する。例えば、A,B,Cの並びなら、

左 右
なし A,B,C
A B,C
A,B C

の3パターン。
左右に分けたら、重量差を計算して、その最小値を求める。

import itertools

def checkio(data):
    return min(abs(sum(d[:i]) - sum(d[i:])) for d in itertools.permutations(data) for i in range(len(data)))

http://www.checkio.org/mission/loading-cargo/publications/natsuki/python-3/first/

なんか無駄なケースが多そうだが、まあいいや。Run&Checkをクリック
・
・
・
5分ぐらいかかった。途中で固まったかと思ったが、なんとかクリア。
サーバーに負担掛けて申し訳ない。

総当たり（組み合わせ）

さっきの方法は、明らかに無駄が多い。2つのグループに分割するという言葉に惑わされていたが、ようするに「荷物をn個取り出して1つのグループにする」と考えればいいのか？ 残りが自動的にもう一つのグループとなる。そう考えると、もっと無駄のないやり方ができそうだ。

dataからn個を取り出すには、順列ではなく組み合わせを使う。

itertools.combinations(data, r=n)

求める答えは、取り出した荷物の重量(sum(d))と、残りの重さ(sum(data) - sum(d))の差なので、

result = abs((sum(data) - sum(d)) - sum(d))
       = abs(sum(data) - sum(d) * 2)

となる。

すべての組み合わせを試して、最小の重量差を求める。コードはこちら。

def checkio(data):
    # 荷物からn個取り出して、残りの荷物との重量差が最小値を計算
    return min(abs(sum(data) - sum(d) * 2) for n in range(len(data)) for d in itertools.combinations(data, r=n))

http://www.checkio.org/mission/loading-cargo/publications/natsuki/python-3/second/

今回はそれほど時間がかからずに終わった。無事にクリア。
ヒントの「すべての組み合わせを試せばいい」って、こういうことだったのか。
順列じゃ多すぎるもんなぁ。


さて、いよいよ、ヒントに書いてある「パーティション問題(Partition problems)」とやらを調べてみることにする。

次回に続く。