# How to trace the recursive path?

Wed Aug 5 18:33:16 CEST 2015

```Consider this code (shown in my previous post)

class CastleDefenseI:
INFINITY = 999999999

def __init__(self):
self.dpw = 0

def soldiersVsDefenders(self,soldiers,defenders):
# soldiers win
if defenders <=0:
return 0
# castle/defenders win
if soldiers <= 0:
return self.INFINITY

# do another round of fighting
# 1. Soldiers kill as many defenders
defendersLeft = defenders - soldiers
# 2. defendersLeft kill as many soldiers
soldiersLeft = soldiers - defendersLeft
return 1 + self.soldiersVsDefenders(soldiersLeft,defendersLeft)

def oneWave(self,soldiers,defenders,castleHits):
# castle/defenders wins
if soldiers <= 0:
return self.INFINITY
# castle is dead, let soldiers play against defenders
if castleHits <= 0:
defendersLeft = defenders - self.dpw
return self.soldiersVsDefenders(soldiers,defendersLeft)

# try every possibility:
# 1) all soldiers hit the castle, none hits the defenders
# 2) one soldier hits the castle, the others hit the defenders
# 3) two soldiers hit the castle, the others hit the defenders
# ...
# soldiers) no soldier hits the castle, all others hit the
# defenders
mini = self.INFINITY
for i in range(0,soldiers):
if i > defenders:
break
soldiersLeft = soldiers - (defenders -i)
defendersLeft = defenders - i + self.dpw
castleHitsLeft = castleHits - (soldiers -i)
mini = min(mini,1 + self.oneWave(soldiersLeft,defendersLeft,castleHitsLeft))
return mini

def playGame(self,soldiers,castleHits,defendersPerWave):
self.dpw = defendersPerWave
numWaves = self.oneWave(soldiers,0,castleHits)
if numWaves >= self.INFINITY:
return -1
else:
return numWaves

solution = CastleDefenseI()
gameSoldiers = 10
castleHits = 11
defendersPerWave = 15

#prints 4
print solution.playGame(gameSoldiers, castleHits, defendersPerWave)

How would I print the path that leads to
if soldiers <= 0 (in oneWave and soldiersVsDefenders)
if defenders<=0 (in soldiersVsDefenders)

I have started going down this direction (incorrect)

class CastleDefenseI:
INFINITY = 999999999

def __init__(self):
self.dpw = 0

def soldiersVsDefenders(self,soldiers,defenders,path):
# soldiers win
if defenders <=0:
return 0
# castle/defenders win
if soldiers <= 0:
return self.INFINITY

# do another round of fighting
# 1. Soldiers kill as many defenders
defendersLeft = defenders - soldiers
# 2. defendersLeft kill as many soldiers
soldiersLeft = soldiers - defendersLeft
path.append({"soldiers":soldiersLeft,"defenders":defendersLeft,
"castleHits":0})
return 1 + self.soldiersVsDefenders(soldiersLeft,defendersLeft,path)

def oneWave(self,soldiers,defenders,castleHits,path):
# castle/defenders wins
if soldiers <= 0:
print path
return self.INFINITY
# castle is dead, let soldiers play against defenders
if castleHits <= 0:
defendersLeft = defenders - self.dpw
path.append({"soldiers":soldiers,"defenders":defendersLeft,"castleHits":0})
return self.soldiersVsDefenders(soldiers,defendersLeft,path)

# try every possibility:
# 1) all soldiers hit the castle, none hits the defenders
# 2) one soldier hits the castle, the others hit the defenders
# 3) two soldiers hit the castle, the others hit the defenders
# ...
# soldiers) no soldier hits the castle, all others hit the
# defenders
mini = self.INFINITY
for i in range(0,soldiers):
if i > defenders:
break
soldiersLeft = soldiers - (defenders -i)
defendersLeft = defenders - i + self.dpw
castleHitsLeft = castleHits - (soldiers -i)
path = []
path.append({"soldiers":soldiersLeft,"defenders":defendersLeft,"castleHits":castleHitsLeft})
mini = min(mini,1 + self.oneWave(soldiersLeft,defendersLeft,castleHitsLeft,path))

return mini

def playGame(self,soldiers,castleHits,defendersPerWave):
self.dpw = defendersPerWave
numWaves = self.oneWave(soldiers,0,castleHits,[])
if numWaves >= self.INFINITY:
return -1
else:
return numWaves

solution = CastleDefenseI()
gameSoldiers = 10
castleHits = 11
defendersPerWave = 15

#prints 4
print solution.playGame(gameSoldiers, castleHits, defendersPerWave)

```