21
16

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

(別解) Pythonで川渡り問題「宣教師と人喰い」を解く 【探索的(発見的)プログラム・再帰】

Last updated at Posted at 2016-07-22

元ネタは @kansihoさんの 「Pythonで川渡り問題「宣教師と人喰い」を解く 【探索的(発見的)プログラム・再帰】」です。

懐かしいネタで面白そうだったので、自分でも実装してみました。
方針は同じです。手順がひとつ見つかっても終わらずに他の手順も探すようにしました。

宣教師と人喰いのグループをGroupクラスにして、ボートへの乗降計算処理を加減算でできるようにしました。
往路と復路で処理が異なりますが、if文で処理を分けると煩雑になって可読性が下がるので、forward関数とbackward関数に分けました。
往路と復路の処理で共通に必要な「ボートに乗って移動しても安全な(喰われない)乗客の組合せを選び出す処理」をsafe_passengers関数にしました。
passengers_combinationsは、「岸に乗客が残っているか」や「ボートに乗って移動しても安全か(喰われないか)」といった条件に関係なく、1人か2人の乗客の組合せ配列です。変化することのない固定データなのでタプルにしました。

実装する際には、
・コメントがなくてもプログラムを理解できる変数名や関数名を付ける
if文やfor文を多段にしない
ということを意識しました。

#!/usr/bin/env python3

from itertools import product


class Group:

    def __init__(self, missionaries, cannibals):
        self.missionaries = missionaries
        self.cannibals = cannibals

    def __str__(self):              # for "%s" % self
        return "({0.missionaries}, {0.cannibals})".format(self)

    def __add__(self, group):       # "+" operator
        return Group(self.missionaries + group.missionaries, self.cannibals + group.cannibals)

    def __sub__(self, group):       # "-" operator
        return Group(self.missionaries - group.missionaries, self.cannibals - group.cannibals)

    def __contains__(self, group):  # "in" operator
        return self.missionaries >= group.missionaries and self.cannibals >= group.cannibals

    def is_empty(self):
        return self.missionaries == self.cannibals == 0

    def is_safe(self):
        return self.missionaries == 0 or self.missionaries >= self.cannibals


passengers_combinations = tuple(Group(missionaries, cannibals)
                                for missionaries, cannibals in product((0, 1, 2), (0, 1, 2))
                                if missionaries + cannibals in (1, 2))


def safe_passengers(depature_bank, arrival_bank):
    return (passengers
            for passengers in passengers_combinations
            if passengers in depature_bank
            if (depature_bank - passengers).is_safe()
            if (arrival_bank + passengers).is_safe())


def backward(left_bank, right_bank, steps):
    step = 'bank: %s   <%s' % (left_bank, right_bank)
    if step in steps:
        return
    if left_bank.is_empty():  # Goal
        print('\n'.join(steps + (step,)))
        print('%s steps.\n' % (len(steps) // 2))
        return
    for passengers in safe_passengers(depature_bank=right_bank, arrival_bank=left_bank):
        forward(left_bank + passengers, right_bank - passengers,
                steps + (step, 'BOAT: %s<---%s' % (passengers, passengers)))


def forward(left_bank, right_bank, steps=()):
    step = 'bank: %s>   %s' % (left_bank, right_bank)
    if step in steps:
        return
    for passengers in safe_passengers(depature_bank=left_bank, arrival_bank=right_bank):
        backward(left_bank - passengers, right_bank + passengers,
                 steps + (step, 'BOAT: %s--->%s' % (passengers, passengers)))


if __name__ == '__main__':
    forward(Group(missionaries=3, cannibals=3), Group(missionaries=0, cannibals=0))

追記
@tanuk1647さん の指摘のおかげで、backwardでも重複チェックが必要なことがわかりました。
手順は、11ステップが4つになりました。
出力結果を横に並べ直した結果がこちら。

bank: (3, 3)>   (0, 0)   bank: (3, 3)>   (0, 0)   bank: (3, 3)>   (0, 0)   bank: (3, 3)>   (0, 0)
BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (1, 1)--->(1, 1)   BOAT: (1, 1)--->(1, 1)
bank: (3, 1)   <(0, 2)   bank: (3, 1)   <(0, 2)   bank: (2, 2)   <(1, 1)   bank: (2, 2)   <(1, 1)
BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (1, 0)<---(1, 0)   BOAT: (1, 0)<---(1, 0)
bank: (3, 2)>   (0, 1)   bank: (3, 2)>   (0, 1)   bank: (3, 2)>   (0, 1)   bank: (3, 2)>   (0, 1)
BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)
bank: (3, 0)   <(0, 3)   bank: (3, 0)   <(0, 3)   bank: (3, 0)   <(0, 3)   bank: (3, 0)   <(0, 3)
BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)
bank: (3, 1)>   (0, 2)   bank: (3, 1)>   (0, 2)   bank: (3, 1)>   (0, 2)   bank: (3, 1)>   (0, 2)
BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)
bank: (1, 1)   <(2, 2)   bank: (1, 1)   <(2, 2)   bank: (1, 1)   <(2, 2)   bank: (1, 1)   <(2, 2)
BOAT: (1, 1)<---(1, 1)   BOAT: (1, 1)<---(1, 1)   BOAT: (1, 1)<---(1, 1)   BOAT: (1, 1)<---(1, 1)
bank: (2, 2)>   (1, 1)   bank: (2, 2)>   (1, 1)   bank: (2, 2)>   (1, 1)   bank: (2, 2)>   (1, 1)
BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)   BOAT: (2, 0)--->(2, 0)
bank: (0, 2)   <(3, 1)   bank: (0, 2)   <(3, 1)   bank: (0, 2)   <(3, 1)   bank: (0, 2)   <(3, 1)
BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)   BOAT: (0, 1)<---(0, 1)
bank: (0, 3)>   (3, 0)   bank: (0, 3)>   (3, 0)   bank: (0, 3)>   (3, 0)   bank: (0, 3)>   (3, 0)
BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)   BOAT: (0, 2)--->(0, 2)
bank: (0, 1)   <(3, 2)   bank: (0, 1)   <(3, 2)   bank: (0, 1)   <(3, 2)   bank: (0, 1)   <(3, 2)
BOAT: (0, 1)<---(0, 1)   BOAT: (1, 0)<---(1, 0)   BOAT: (0, 1)<---(0, 1)   BOAT: (1, 0)<---(1, 0)
bank: (0, 2)>   (3, 1)   bank: (1, 1)>   (2, 2)   bank: (0, 2)>   (3, 1)   bank: (1, 1)>   (2, 2)
BOAT: (0, 2)--->(0, 2)   BOAT: (1, 1)--->(1, 1)   BOAT: (0, 2)--->(0, 2)   BOAT: (1, 1)--->(1, 1)
bank: (0, 0)   <(3, 3)   bank: (0, 0)   <(3, 3)   bank: (0, 0)   <(3, 3)   bank: (0, 0)   <(3, 3)
11 steps.                11 steps.                11 steps.                11 steps.
21
16
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
21
16

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?