元ネタは @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.