Problem set 4-2:More Pour Problem

目次

---

• 問題の説明
• ポイント
• ソース

問題の説明

---

PouringProblemの拡張版を今回は作成する。 前回の(PouringProblem)jsakusan.hatenablog.comは、2つの容器を使用した場合で解決方法を探索した。 しかし、今回は容器の数をフレキシブルに変化可能にする。 容器の状態はtupleを用いて、羅列することで表現する。例えば、5個の容器を使用する場合は(0, 0, 0, 0, 2)のように表現する。 探索後、答えは、(state, action ,state2, action, …..)と表現する。具体的には、((0, 0, 0, 0), ('fill', 2), (0, 0, 4, 0)) 関数の引数として、startの状態、endの状態、それぞれ容器のcapacityを与える。

ポイント

---

1, 各状態の探索方法

前回は、2つの容器ないでの表現だったので

def successors(x, y, X, Y):
    assert x <= X and y <= Y
    return {(0, x + y) if x + y < Y else (x - (Y - y), y + (Y - y)) : 'x => y',
             (x + y, 0) if x + y < X else (x + (X - x), y - (X - x)) : 'x <= y',
             (x, Y): 'fill up y', (X, y): 'Fill up x',
             (0, y): 'empty y', (x, 0): 'empty x'}

x, y(現在の状態)からX, Y(各容器の容量)内での状態遷移をすべて表現することができた。 しかし、今回は任意の個数容器があるので別の実装方法を実現しなければいけない。

今回は、def successors(state)(state => (0, 0, 0, 0, 0))として、listのn番目を異なる状態に変化させる処理を行うことで pour, full, emptyを表現する。

コード

def more_pour_problem(capacities, goal, start=None):

    def is_goal(state): return goal in state

    def more_pour_successors(state):
        indices = range(len(state))
        succ = {}
        for i in indices:
            succ[replace(state, i, capacities[i])] = ('fill', i)
            succ[replace(state, i, 0)] = ('empty', i)

            for j in indices:
                amount = min(state[i], capacities[j] - state[j])
                state2 = replace(state, i, state[i] - amount)
                succ[replace(state2, j, state[j] + amount)] = ('pour', i, j)

        return succ

    if start is None: start = (0,) * len(capacities)
    return shortest_path_search(start, more_pour_successors, is_goal)


def replace(sequence, i, val):
    "Return copy of sequence, with sequence[i] replace by val"
    s = list(sequence)
    s[i] = val
    return type(sequence)(s)


def shortest_path_search(start, successors, is_goal):
    """Find the shortest path from start state to a state
    such that is_goal(state) is true."""
    if is_goal(start):
        return [start]
    explored = set()
    frontier = [[start]]
    while frontier:
        path = frontier.pop(0)
        s = path[-1]
        for (state, action) in successors(s).items():
            if state not in explored:
                explored.add(state)
                path2 = path + [action, state]
                if is_goal(state):
                    return path2
                else:
                    frontier.append(path2)
    return Fail


Fail = []


def test_more_pour():
    assert more_pour_problem((1, 2, 4, 8), 4) == [
        (0, 0, 0, 0), ('fill', 2), (0, 0, 4, 0)]
    assert more_pour_problem((1, 2, 4), 3) == [
        (0, 0, 0), ('fill', 2), (0, 0, 4), ('pour', 2, 0), (1, 0, 3)]
    starbucks = (8, 12, 16, 20, 24)
    assert not any(more_pour_problem(starbucks, odd) for odd in (3, 5, 7, 9))
    assert all(more_pour_problem((1, 3, 9, 27), n) for n in range(28))
    assert more_pour_problem((1, 3, 9, 27), 28) == []
    return 'test_more_pour passes'


print(test_more_pour())