我有一些代码，我在地牢爬行游戏中模拟玩家试图逃离地牢。我想用深度优先搜索来测试玩家能否成功。
我的方法出了问题，在 Dungeon 类中，应该测试走出地牢的every路径是否会成功： 这是我的打印声明：
self = <main_test.GraphTest testMethod=test_can_all_paths_make_it>
def test_can_all_paths_make_it(self):
dungeon = self.create_dungeon()
> self.assertEqual(dungeon.can_all_paths_make_it(Player(11)), False)
E AssertionError: True != False
coderbyte-tests/main_test.py:140: AssertionError
----------------------------- Captured stdout call -----------------------------
Checking node: <graph.Monster object at 0x7f82158aa190>, Current Health: 11
Checking neighbor: <graph.Monster object at 0x7f82158aa130>
Encountered Monster: <graph.Monster object at 0x7f82158aa130>
Checking node: <graph.Monster object at 0x7f82158aa130>, Current Health: 7
Checking neighbor: <graph.Monster object at 0x7f82158aa040>
Encountered Monster: <graph.Monster object at 0x7f82158aa040>
Checking node: <graph.Monster object at 0x7f82158aa040>, Current Health: 2
Checking neighbor: <graph.Treasure object at 0x7f8215914850>
Processing neighbor: <graph.Treasure object at 0x7f8215914850>
Checking node: <graph.Treasure object at 0x7f8215914850>, Current Health: 2
Found Treasure!
# Will any path make it to the end? Can they choose randomly and always make it?
def can_all_paths_make_it(self, player: Player) -> bool:
def dfs(node, current_health):
if isinstance(node, Treasure):
return True
if current_health <= 0:
return False
if node is not node.next:
return False
for neighbor in node.next:
if isinstance(neighbor, Monster):
# Simulate a battle with the monster
new_health = current_health - neighbor.damage
if not dfs(neighbor, new_health):
return False
elif not dfs(neighbor, current_health):
return False
return True
return dfs(self.monster, player.health)
逻辑好像有点不对，因为有些测试用例失败了。 （测试用例不会准确显示我的错误，除了在输出 False 时期望 True 之外）。
我知道，为了测试是否所有路径都能成功，我需要考虑死胡同、生命值的损失以及它们是否在宝藏。
出了什么问题，如何解决？
这是测试用例
import unittest
从图表导入怪物、宝藏、玩家、地下城
类 GraphTest(unittest.TestCase):
# a(3) -> b(4) -> c(5) -> treasure
def create_dungeon(self) -> Dungeon:
a = Monster("a", 3)
b = Monster("b", 4)
c = Monster("c", 5)
treasure = Treasure()
a.append_monster(b)
b.append_monster(c)
c.append_treasure(treasure)
return Dungeon(a)
# a(3) -> b(4) c(5) -> treasure
def create_dungeon2(self) -> Dungeon:
a = Monster("a", 3)
b = Monster("b", 4)
c = Monster("c", 5)
treasure = Treasure()
a.append_monster(b)
c.append_treasure(treasure)
return Dungeon(a)
# a(1) -> b(4)
# | |
# v v
# c(2) -> d(1) -> treasure
def create_dungeon3(self):
a = Monster("a", 1)
b = Monster("b", 4)
c = Monster("c", 2)
d = Monster("d", 1)
treasure = Treasure()
a.append_monster(b)
a.append_monster(c)
b.append_monster(d)
c.append_monster(d)
d.append_treasure(treasure)
return Dungeon(a)
# a(1) -> b(4) -> e(1)
# | |
# v v
# c(2) -> d(1) -> treasure
'''
Probability review: Just because there are 2 different possiblilites does not
mean that they are equal probability. For example, on any given day, there could be
rain or no rain. That doesn't imply that rain has a 50% chance.
In this case, there are 3 different paths:
a->c->d->treasure, a->b->d->treasure, and a->b->e.
Here, a->c->d->tresure has a 50% chance of happening, a->b->e is 25%, and a->b->d->treasure is 25%.
An easy way to think about it that the probability of A reaching C is 50% and C reaching D is 100%
and D reaching Treasure is 100%. Overall, it would be 50% chance to do A->C->D->Treasure.
'''
def create_dungeon4(self):
a = Monster("a", 1)
b = Monster("b", 4)
c = Monster("c", 2)
d = Monster("d", 1)
e = Monster("e", 1)
treasure = Treasure()
a.append_monster(b)
a.append_monster(c)
b.append_monster(d)
c.append_monster(d)
b.append_monster(e)
d.append_treasure(treasure)
return Dungeon(a)
# a(1) -> b(5) -> e(1)
# | | |
# v v v
# c(2) -> d(7) -> f(2) -> treasure
# optimal -> a -> b -> e -> f
def create_dungeon5(self):
a = Monster("a", 1)
b = Monster("b", 5)
c = Monster("c", 2)
d = Monster("d", 7)
e = Monster("e", 1)
f = Monster("f", 2)
treasure = Treasure()
a.append_monster(b)
a.append_monster(c)
b.append_monster(e)
b.append_monster(d)
c.append_monster(d)
d.append_monster(f)
e.append_monster(f)
f.append_treasure(treasure)
return Dungeon(a)
# a(1) -> b(5) -> e(1) ------
# | | | |
# v v v v
# c(2) -> d(7) -> f(2) -> treasure
# optimal -> a -> b -> e -> f
def create_dungeon6(self):
a = Monster("a", 1)
b = Monster("b", 5)
c = Monster("c", 2)
d = Monster("d", 7)
e = Monster("e", 1)
f = Monster("f", 2)
treasure = Treasure()
a.append_monster(b)
a.append_monster(c)
b.append_monster(e)
b.append_monster(d)
c.append_monster(d)
d.append_monster(f)
e.append_monster(f)
e.append_treasure(treasure)
f.append_treasure(treasure)
return Dungeon(a)
def test_can_at_least_one_path_make_it(self):
dungeon = self.create_dungeon()
self.assertEqual(dungeon.can_at_least_one_path_make_it(), True)
dungeon = self.create_dungeon2()
self.assertEqual(dungeon.can_at_least_one_path_make_it(), False)
def test_can_all_paths_make_it(self):
dungeon = self.create_dungeon()
self.assertEqual(dungeon.can_all_paths_make_it(Player(11)), False)
dungeon = self.create_dungeon()
self.assertEqual(dungeon.can_all_paths_make_it(Player(12)), True)
dungeon = self.create_dungeon2()
self.assertEqual(dungeon.can_all_paths_make_it(Player(7)), False)
dungeon = self.create_dungeon3()
self.assertEqual(dungeon.can_all_paths_make_it(Player(5)), False)
dungeon = self.create_dungeon3()
self.assertEqual(dungeon.can_all_paths_make_it(Player(6)), True)
dungeon = self.create_dungeon4()
self.assertEqual(dungeon.can_all_paths_make_it(Player(100)), False)
def test_probability_player_will_make_it(self):
dungeon = self.create_dungeon()
self.assertEqual(dungeon.probability_player_will_make_it(Player(12)), 1.0)
dungeon = self.create_dungeon()
self.assertEqual(dungeon.probability_player_will_make_it(Player(11)), 0.0)
dungeon = self.create_dungeon2()
self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 0.0)
dungeon = self.create_dungeon3()
self.assertEqual(dungeon.probability_player_will_make_it(Player(1)), 0.0)
dungeon = self.create_dungeon3()
self.assertEqual(dungeon.probability_player_will_make_it(Player(5)), 0.5)
dungeon = self.create_dungeon3()
self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 1.0)
dungeon = self.create_dungeon4()
self.assertEqual(dungeon.probability_player_will_make_it(Player(1)), 0.0)
dungeon = self.create_dungeon4()
self.assertEqual(dungeon.probability_player_will_make_it(Player(5)), 0.5)
dungeon = self.create_dungeon4()
self.assertEqual(dungeon.probability_player_will_make_it(Player(100)), 0.75)
def test_can_make_it(self):
dungeon = self.create_dungeon5()
self.assertEqual(dungeon.can_make_it(Player(9)), True)
dungeon = self.create_dungeon5()
self.assertEqual(dungeon.can_make_it(Player(8)), False)
dungeon = self.create_dungeon6()
self.assertEqual(dungeon.can_make_it(Player(7)), True)
dungeon = self.create_dungeon6()
self.assertEqual(dungeon.can_make_it(Player(6)), False)
我自己创建了这个打印语句 def can_all_paths_make_it(self, 玩家: 玩家) -> bool: def dfs(节点, current_health): print(f"正在检查节点：{node}，当前运行状况：{current_health}")
if isinstance(node, Treasure):
print("Found Treasure!")
return True
if current_health <= 0:
print("Player has lost all health!")
return False
if not isinstance(node.next, list):
print("Invalid path: node.next is not a list")
return False # If node.next is not a list, it's not a valid path
for neighbor in node.next:
print(f"Checking neighbor: {neighbor}")
if isinstance(neighbor, Monster):
print(f"Encountered Monster: {neighbor}")
# Simulate a battle with the monster
new_health = current_health - neighbor.damage
if not dfs(neighbor, new_health):
return False
elif not dfs(neighbor, current_health):
return False
return True
return dfs(self.monster, player.health)
有几个问题：
if current_health <= 0生命值只会因邻近怪物的伤害而减少，而不会因第一个怪物的伤害而减少。您应该将该损坏逻辑移出循环并将其应用到当前节点。
if node is not node.next:if not node.next:这是更正后的代码：
def can_all_paths_make_it(self, player: Player) -> bool:
def dfs(node, current_health):
if current_health < 0: # the player died
return False
if isinstance(node, Treasure): # bingo!
return True
if isinstance(node, Monster): # have to fight
current_health -= node.damage
if not node.next: # dead end
return False
return all(dfs(neighbor, current_health)
for neighbor in node.next)
return dfs(self.monster, player.health)