3年半ぶりに川渡りクイズを解く

はじめに

なぜこれをやり始めたか？
こちらで構築したコーディングに対するAIアシストが実際に役に立つのか試したかったからです。
touch-sp.hatenablog.com
3年半前の記事はこちらです。
touch-sp.hatenablog.com

結論

う～ん、あんまり役に立たなかったです。
余計なおせっかいが入ったりする場面もありました。

実際にはClaude 3.7 Sonnetに少しアシストしてもらいました。

Pythonスクリプト

'''
３人の宣教師と３人の人先住民がが川岸にいます。
川には2人まで乗れるボートが一艘あります。
宣教師の数がそこにいる先住民の数より少なくなると殺されしまいます。
全員が無事に対岸に渡るには、どうしたら良いでしょうか？

宣教師 = a
先住民 = b
'''

moves =[
    (1, 0), #宣教師一人
    (2, 0), #宣教師二人
    (0, 1), #先住民一人
    (0, 2), #先住民二人
    (1, 1)  #宣教師一人と先住民一人
]

class State:
    def __init__(
            self,
            person_a: int,
            person_b: int,
            boat: int,
            depth: int
    ):
        self.person_a = person_a
        self.person_b = person_b
        self.boat = boat
        self.depth = depth

    def __str__(self):

        string_for_print = f"宣教師 {self.person_a}, 先住民 {self.person_b}"

        return string_for_print

    def move(self, move):
        direction = 1 if self.boat == 0 else -1
        return State(
            person_a = self.person_a + direction * move[0],
            person_b = self.person_b + direction * move[1],
            boat = 1 - self.boat,
            depth = self.depth + 1
       )

    def is_valid(self):
        if not (
            0 <= self.person_a <= 3 and
            0 <= self.person_b <= 3
        ):
            return False

        if self.person_a > 0 and (self.person_a < self.person_b):
            return False

        right_person_a = 3 - self.person_a
        right_person_b = 3 - self.person_b
        if right_person_a > 0 and (right_person_a < right_person_b):
            return False

        return True

    def availables_next_states(self):
        return [new_state for move in moves if (new_state := self.move(move)).is_valid()]

    def is_goal(self):
        return (
            self.person_a == 0 and
            self.person_b == 0
        )

    def __hash__(self):
        return hash((self.person_a, self.person_b, self.boat))

    def __eq__(self, other):
        if isinstance(other, State):
            return (
                self.person_a == other.person_a and
                self.person_b == other.person_b and
                self.boat == other.boat
            )
        else:
            return False

def solve():
    initial_state = State(3, 3 ,1, 0)

    queue: list[State] = [initial_state]

    visited_states: set[State] = set()
    visited_states.add(initial_state)
    
    parent_map: dict[State, list[State]] = {}
    parent_map[initial_state] = []

    found_one: bool = False

    while len(queue) > 0:
        current_state = queue.pop(0)

        if current_state.is_goal():
            found_one = True
        
        if not found_one:
            for next_state in current_state.availables_next_states():
                if next_state not in visited_states:
                    visited_states.add(next_state)
                    queue.append(next_state)
                    parent_map[next_state] = [current_state]
                else:
                    if len(parent_map[next_state]) > 0 and parent_map[next_state][0].depth == current_state.depth:
                        parent_map[next_state].append(current_state)

    if found_one:
        return parent_map
    else:
        return None

def get_all_path(parent_map) -> list[list[State]]:
    final_state = State(0, 0, 0, 100) # 100 is dummy number

    queue: list[list[State]] = [[final_state]]

    all_path: list[list[State]] = []

    while len(queue) > 0:
        current_path = queue.pop(0)

        if current_path[0].depth == 0:
            all_path.append(current_path)

        for next_state in parent_map[current_path[0]]:
            queue.append([next_state] + current_path)

    return all_path

def print_path(path) -> None:
    final_state = State(0, 0, 0, 100) # 100 is dummy number
    for i in range(len(path)-1):
        print(path[i])
        
        if path[i].boat == 1:
            print(
                "左 -> 右 "
                f"宣教師 {path[i].person_a - path[i+1].person_a} "
                f"先住民 {path[i].person_b - path[i+1].person_b}"
            )
        else:
            print(
                "右 -> 左 "
                f"宣教師 {path[i+1].person_a - path[i].person_a} "
                f"先住民 {path[i+1].person_b - path[i].person_b}"
            )
        
    print(final_state)
    print()
    
if __name__ == "__main__":
    parent_map = solve()
    if parent_map:
        all_path = get_all_path(parent_map)
        for i, path in enumerate(all_path):
            print(f"解法 {i+1}")
            print_path(path) 
    else:
        print("No solution found.")

出力された結果

解法 1
宣教師 3, 先住民 3
左 -> 右 宣教師 0 先住民 2
宣教師 3, 先住民 1
右 -> 左 宣教師 0 先住民 1
宣教師 3, 先住民 2
左 -> 右 宣教師 0 先住民 2
宣教師 3, 先住民 0
右 -> 左 宣教師 0 先住民 1
宣教師 3, 先住民 1
左 -> 右 宣教師 2 先住民 0
宣教師 1, 先住民 1
右 -> 左 宣教師 1 先住民 1
宣教師 2, 先住民 2
左 -> 右 宣教師 2 先住民 0
宣教師 0, 先住民 2
右 -> 左 宣教師 0 先住民 1
宣教師 0, 先住民 3
左 -> 右 宣教師 0 先住民 2
宣教師 0, 先住民 1
右 -> 左 宣教師 1 先住民 0
宣教師 1, 先住民 1
左 -> 右 宣教師 1 先住民 1
宣教師 0, 先住民 0

解法 2
宣教師 3, 先住民 3
左 -> 右 宣教師 1 先住民 1
宣教師 2, 先住民 2
右 -> 左 宣教師 1 先住民 0
宣教師 3, 先住民 2
左 -> 右 宣教師 0 先住民 2
宣教師 3, 先住民 0
右 -> 左 宣教師 0 先住民 1
宣教師 3, 先住民 1
左 -> 右 宣教師 2 先住民 0
宣教師 1, 先住民 1
右 -> 左 宣教師 1 先住民 1
宣教師 2, 先住民 2
左 -> 右 宣教師 2 先住民 0
宣教師 0, 先住民 2
右 -> 左 宣教師 0 先住民 1
宣教師 0, 先住民 3
左 -> 右 宣教師 0 先住民 2
宣教師 0, 先住民 1
右 -> 左 宣教師 1 先住民 0
宣教師 1, 先住民 1
左 -> 右 宣教師 1 先住民 1
宣教師 0, 先住民 0

解法 3
宣教師 3, 先住民 3
左 -> 右 宣教師 0 先住民 2
宣教師 3, 先住民 1
右 -> 左 宣教師 0 先住民 1
宣教師 3, 先住民 2
左 -> 右 宣教師 0 先住民 2
宣教師 3, 先住民 0
右 -> 左 宣教師 0 先住民 1
宣教師 3, 先住民 1
左 -> 右 宣教師 2 先住民 0
宣教師 1, 先住民 1
右 -> 左 宣教師 1 先住民 1
宣教師 2, 先住民 2
左 -> 右 宣教師 2 先住民 0
宣教師 0, 先住民 2
右 -> 左 宣教師 0 先住民 1
宣教師 0, 先住民 3
左 -> 右 宣教師 0 先住民 2
宣教師 0, 先住民 1
右 -> 左 宣教師 0 先住民 1
宣教師 0, 先住民 2
左 -> 右 宣教師 0 先住民 2
宣教師 0, 先住民 0

解法 4
宣教師 3, 先住民 3
左 -> 右 宣教師 1 先住民 1
宣教師 2, 先住民 2
右 -> 左 宣教師 1 先住民 0
宣教師 3, 先住民 2
左 -> 右 宣教師 0 先住民 2
宣教師 3, 先住民 0
右 -> 左 宣教師 0 先住民 1
宣教師 3, 先住民 1
左 -> 右 宣教師 2 先住民 0
宣教師 1, 先住民 1
右 -> 左 宣教師 1 先住民 1
宣教師 2, 先住民 2
左 -> 右 宣教師 2 先住民 0
宣教師 0, 先住民 2
右 -> 左 宣教師 0 先住民 1
宣教師 0, 先住民 3
左 -> 右 宣教師 0 先住民 2
宣教師 0, 先住民 1
右 -> 左 宣教師 0 先住民 1
宣教師 0, 先住民 2
左 -> 右 宣教師 0 先住民 2
宣教師 0, 先住民 0

（状態における数字は左岸にいる人数です）