How to trace the recursive path?

jennyfurtado2 at gmail.com jennyfurtado2 at gmail.com
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)

       


      


More information about the Python-list mailing list