Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #95030 > unrolled thread

How to trace the recursive path?

Back to article view | Back to comp.lang.python

Contents

  How to trace the recursive path? jennyfurtado2@gmail.com - 2015-08-05 09:33 -0700
    Re: How to trace the recursive path? Terry Reedy <tjreedy@udel.edu> - 2015-08-05 21:15 -0400

#95030 — How to trace the recursive path?

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)

       


      

[toc] | [next] | [standalone]

#95052

trace --trackcalls
Display the calling relationships exposed by running the program.

will give you part of what you want, but only counts.

I would just add print('xyx calledl') at the top of each function you 
want traced.

-- 
Terry Jan Reedy

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web