Логическая рекурсивная функция поиска в глубину ⇐ Python

[Anonymous]

У меня есть код, в котором я имитирую игрока, пытающегося сбежать из подземелья в игре-бродилке по подземельям. Я хочу использовать поиск в глубину, чтобы проверить, сможет ли игрок добиться успеха.

Что-то идет не так в моем методе внутри класса Dungeon, который должен проверять, будет ли каждый путь из темницы успешным: Вот мои распечатки:

self = защита test_can_all_paths_make_it (self): подземелье = self.create_dungeon() > self.assertEqual(dungeon.can_all_paths_make_it(Player(11)), False) E AssertionError: Истина! = Ложь coderbyte-tests/main_test.py:140: AssertionError ----------------------------- Захваченный стандартный вывод ------------------ ----------- Проверка узла: , текущее состояние: 11 Проверка соседа: Встреча с монстром: Проверка узла: , текущее состояние: 7 Проверка соседа: Встреча с монстром: Проверка узла: , текущее состояние: 2 Проверка соседа: Сосед по обработке: Проверка узла: , Текущее состояние: 2 Найдено сокровище! # Дойдёт ли какой-нибудь путь до конца? Могут ли они выбирать случайным образом и всегда успеть? def can_all_paths_make_it(self, player: Player) -> bool: def dfs (узел, current_health): если isinstance(узел, Сокровище): вернуть истину если текущее_здоровье b(4) -> c(5) -> сокровище def create_dungeon(self) -> Подземелье: а = Монстр("а", 3) б = Монстр("б", 4) с = Монстр("с", 5) сокровище = Сокровище() а.append_monster(б) б.append_monster (с) c.append_treasure(сокровище) вернуть Подземелье(а) # a(3) -> b(4) c(5) -> сокровище def create_dungeon2(self) -> Подземелье: а = Монстр("а", 3) б = Монстр("б", 4) с = Монстр("с", 5) сокровище = Сокровище() а.append_monster(б) c.append_treasure(сокровище) вернуть Подземелье(а) # а(1) -> б(4) # | | # в в # c(2) -> d(1) -> сокровище защита create_dungeon3(self): а = Монстр("а", 1) б = Монстр("б", 4) с = Монстр("с", 2) d = Монстр("d", 1) сокровище = Сокровище() а.append_monster(б) а.append_monster(с) б.append_monster(d) c.append_monster(d) d.append_treasure(сокровище) вернуть Подземелье(а) # a(1) -> b(4) -> e(1) # | | # в в # c(2) -> d(1) -> сокровище ''' Обзор вероятностей: то, что существуют две разные возможности, не означает, что означают, что они равновероятны. Например, в любой день может быть дождь или отсутствие дождя. Это не означает, что вероятность дождя составляет 50%. В этом случае есть 3 разных пути: a->c->d->сокровище, a->b->d->сокровище и a->b->e. Здесь вероятность появления a->c->d->сокровища составляет 50%, a->b->e — 25%, а a->b->d->сокровище — 25%. Простой способ подумать об этом: вероятность того, что A достигнет C, равна 50%, а C достигнет D, равна 100%. и D достижения сокровища составляет 100%. В целом вероятность выполнения A->C->D->Treasure составляет 50%. ''' защита create_dungeon4(self): а = Монстр("а", 1) б = Монстр("б", 4) с = Монстр("с", 2) d = Монстр("d", 1) е = Монстр("е", 1) сокровище = Сокровище() а.append_monster(б) а.append_monster(с) б.append_monster(d) c.append_monster(d) b.append_monster(e) d.append_treasure(сокровище) вернуть Подземелье(а) # a(1) -> b(5) -> e(1) # | | | # в в в # c(2) -> d(7) -> f(2) -> сокровище # оптимальный -> a -> b -> e -> f защита create_dungeon5(self): а = Монстр("а", 1) б = Монстр("б", 5) с = Монстр("с", 2) d = Монстр("d", 7) е = Монстр("е", 1) f = Монстр("f", 2) сокровище = Сокровище() а.append_monster(б) а.append_monster(с) b.append_monster(e) б.append_monster(d) c.append_monster(d) d.append_monster(f) e.append_monster(f) f.append_treasure(сокровище) вернуть Подземелье(а) # a(1) -> b(5) -> e(1) ------ # | | | | # v v v v # c(2) -> d(7) -> f(2) -> сокровище # оптимальный -> a -> b -> e -> f защита create_dungeon6(self): а = Монстр("а", 1) б = Монстр("б", 5) с = Монстр("с", 2) d = Монстр("d", 7) е = Монстр("е", 1) f = Монстр("f", 2) сокровище = Сокровище() а.append_monster(б) а.append_monster(с) б.append_monster(e) б.append_monster(d) c.append_monster(d) d.append_monster(f) e.append_monster(f) e.append_treasure(сокровище) f.append_treasure(сокровище) вернуть Подземелье(а) защита test_can_at_least_one_path_make_it (self): подземелье = self.create_dungeon() self.assertEqual(dungeon.can_at_least_one_path_make_it(), True) подземелье = self.create_dungeon2() self.assertEqual(dungeon.can_at_least_one_path_make_it(), False) защита test_can_all_paths_make_it (self): подземелье = self.create_dungeon() self.assertEqual(dungeon.can_all_paths_make_it(Player(11)), False) подземелье = self.create_dungeon() self.assertEqual(dungeon.can_all_paths_make_it(Player(12)), True) подземелье = self.create_dungeon2() self.assertEqual(dungeon.can_all_paths_make_it(Player(7)), False) подземелье = self.create_dungeon3() self.assertEqual(dungeon.can_all_paths_make_it(Player(5)), False) подземелье = self.create_dungeon3() self.assertEqual(dungeon.can_all_paths_make_it(Player(6)), True) подземелье = self.create_dungeon4() self.assertEqual(dungeon.can_all_paths_make_it(Player(100)), False) защита test_probability_player_will_make_it(self): подземелье = self.create_dungeon() self.assertEqual(dungeon.probability_player_will_make_it(Player(12)), 1.0) подземелье = self.create_dungeon() self.assertEqual(dungeon.probability_player_will_make_it(Player(11)), 0.0) подземелье = self.create_dungeon2() self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 0.0) подземелье = self.create_dungeon3() self.assertEqual(dungeon.probability_player_will_make_it(Player(1)), 0.0) подземелье = self.create_dungeon3() self.assertEqual(dungeon.probability_player_will_make_it(Player(5)), 0.5) подземелье = self.create_dungeon3() self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 1.0) подземелье = self.create_dungeon4() self.assertEqual(dungeon.probability_player_will_make_it(Player(1)), 0.0) подземелье = self.create_dungeon4() self.assertEqual(dungeon.probability_player_will_make_it(Player(5)), 0.5) подземелье = self.create_dungeon4() self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 0,75) защита test_can_make_it (сам): подземелье = self.create_dungeon5() self.assertEqual(dungeon.can_make_it(Player(9)), True) подземелье = self.create_dungeon5() self.assertEqual(dungeon.can_make_it(Player(8)), False) подземелье = self.create_dungeon6() self.assertEqual(dungeon.can_make_it(Player(7)), True) подземелье = self.create_dungeon6() self.assertEqual(dungeon.can_make_it(Player(6)), False) Для себя я создал этот оператор печати def can_all_paths_make_it(self, player: Player) -> бул: def dfs (узел, current_health): print(f"Проверка узла: {node}, текущее состояние: {current_health}")
if isinstance(node, Treasure): print("Найдено сокровище!") вернуть истину если текущее_здоровье