In our previous post we looked at two approaches to solve the following problem:The gameSoldiers soldiers approached silently the remarkable place.
In the gloom the courtyard below looked of considerable size, and as several dark ways led from it under great round arches, it perhaps seemed bigger than it really was.
Daylight was still a few hours away. The commander silently rose his right hand causing the company to come to an halt. He surveyed the hill where his men were standing which surrounded the castle below. It seemed to be the perfect spot. They needed to be careful and silent since the danger would only disappear at sunrise. He was surprised they had been able to make it this far in the middle of the night without having been detected by the Count's minions.
The commander looked at his men; they were the best of the best. If anyone was going to remove this evil castle from this land these were the men capable of doing it. His hand drew a wide circle around the hill and the men moved the canons into position. They would need them to destroy the solid castle which could withstand castleHits hits (one canon shot, one hit).
Then they waited. As they sat they heard a sound in the courtyard —the agonized cry of a woman. Peering through the tall grass there, indeed, was a woman with disheveled hair, holding her hands over her heart as one distressed with running. She was leaning against a corner of the gateway. She seemed to be facing somebody for she shouted in a voice laden with menace:—
“Monster, give me my child!”
She threw herself on her knees, and raising up her hands, cried the same words in tones which wrung the soldiers' hearts. Then she tore her hair and beat her breast, and abandoned herself to all the violences of extravagant emotion. Finally, she threw herself forward, and, though they could not see her, they could hear the beating of her naked hands against the door.
Somewhere high overhead, probably on the tower, they heard the voice of the Count calling in his harsh, metallic whisper. His call seemed to be answered from far and wide by the howling of wolves. Before many minutes had passed a pack of them poured, like a pent-up dam when liberated, through the wide entrance into the courtyard.
There was no cry from the woman, and the howling of the wolves was but short. Before long they streamed away singly, licking their lips.
The wait was now unbearable for the men, but it was over quickly: The sun rose rapidly and the commander gave the sign. Taking turns, each soldier shot his canon at the castle. The castle strength was now down to \(castleHits=castleHits-gameSoldiers\).
They then waited for new canon balls to arrive, knowing the Count would not sit idly- and indeed as the sun set on the horizon and night fell, they saw a commotion, then the castle doors opening and defendersPerWave defenders leaving the castle. The enemies moved slowly toward the soldiers, who checked their rifles and waited in tense silence. Their commander had given instructions on what to do each day: how many (if any) should fire their rifles at the defenders and how many (if any) should fire their canons at the castle. He had sat beforehand with the city's scientist who had given him the best course of action for his men to employ each day such that the soldiers could destroy the castle in the minimum number of days.
In the ensuing days the castle and the soldiers battled it out following these rules:
- All the soldiers fired first. A soldier could fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier could only shoot once). One shot at a defender killed him. One shot at the castle decreased its strength by 1.
- Then each of the defenders would shoot one soldier (and only one) killing him.
- If the castle still had strength points (i.e. \(castleHits>0\)) it would send a new batch of defendersPerWave defenders at this point. The total number of defenders in the next round would be then \(defenders=defenders + defendersPerWave\).
- Repeat 1 through 3 in each new day.
- If all soldiers were killed by the defenders, the castle would win.
- If there were zero defenders left after the soldiers shot and the castle strength was also zero, the soldiers would win.
The scientist was highly respected but as the days went on and their comrades died like flies, the soldiers questioned whether his approach was indeed the best. Some of the soldiers asked the commander why not use the technique of killing the defenders first and only then shoot at the castle. The commander showed them how this approach would lengthen their campaign (see previous post) since it would not lead to the minimum number of days to win and above all sometimes would lead at the castle winning (see tests 0,6,9,15 were this approach leads to a win for the castle).
Some then argued that all their might should focus on the castle but again the commander showed them how it also failed to lead to victory sometimes (again see previous post, in particular the tests 11,12,17,18,22,26 and 26 where this approach leads to a win for the castle). He then decided to double check himself the scientist's calculations.
As we and the commander noticed, none of the two approaches in the previous post solved the problem correctly in all cases.
It is likely that there is a clever algorithm that solves the problem correctly always but it is not obvious right away how to go about finding it.
An easier approach is to solve the problem by brute force: Try all possible plays allowed by the rules at the beginning of each wave, trace paths from the beginning state until a state in which either the soldiers win or the castle wins (a goal state). Then pick among those paths those for which the number of rounds is minimum (as we have seen in our previous post, there will be cases where there is more than one path corresponding to a minimum number of rounds; take a look at the table in the previous post and in particular to tests that are correctly solved by both algorithms but that end up with a different number of soldiers left standing: tests 2,3,4,5,8,20,23,24).
In the following discussion we will, for every test from our previous post, compute all the paths that lead to a solution. We will store them in a dictionary where the key is the number of waves a given solution takes and the values are the paths from the start to the end goal (castle/soldiers win).
A RECURSIVE SOLUTION
A simple method to search through every possible path is given by the following code fragment
For each wave the method takes however many soldiers, defenders, castleHits are available at the beginning of that wave as arguments as well as the wave number (note how by default wave starts at 0).
The method then tries every possible path for those initial values recursively. This is achieved through the for loop
Lets walk through the loop:
If at any point in the recursion, soldiers becomes zero or smaller it means we reached a goal state where the castle wins and we just return.
If at any point in the recursion, castleHits becomes zero or smaller, it means the castle can no longer send defenderPerWaves defenders at the end of each round.
In this case we subtract the defendersPerWave that we had added to the defendersLeft in the for loop (because we didnt know at the time that castleHits<=0) and call the method soldiersVsDefenders.
Note that we do not increase the wave value in this call. This makes sense: We at first played regularly (in the for loop) and recursed by increasing the wave number and the number of defenders as if the castle still had points left. Then we realized that the castle is gone, so we subtracted back the defendersPerWave and call soldiersVsDefenders so that the correct play for this wave can be made with the remaining soldiers and defenders playing against each other (the castle is gone from the picture).
The soldiersVsDefenders method just plays out wave after wave of soldiers vs defenders recursively: All soldiers hit an equal number of defenders leaving \(defendersLeft=defenders-soldiers\) and the remaining defenders then hit back leaving \(soldiersLeft=soldiers-defendersLeft\) soldiers. Then it increases the wave number and recurses.
If at any point soldiers or defenders become zero or lower then the castle or the soldiers respectively win i.e we stop recursing.
This recursive process is a more complicated example of what sometimes is called depth first search/recursive backtracking: Starting at the root it follows a path all the way down until it finds a goal state or until it reaches a dead end. Then it backtracks up and repeats.
To visualize this process lets draw all possible paths for a few of the test cases from our previous post.
Figure 2 shows all the paths tried by the recursive algorithm for test 0, which starts with gameSoldiers=10, castleHits=11, defendersPerWave=15.
There are only 3 paths (S,D and CH stand for soldiers, defenders and castlehits at the beginning of each wave) that lead to wins: The two in red correspond to wins by the castle. The one in blue corresponds to the only possible win by the soldiers (thus it is the minimum number of waves solution we care about).
The blue solution (4 waves) is
Every single path from the initial state to an end state is a win for the castle. There are 7 such paths. There are no invalid paths like in the previous test.
Two of the paths achieve the win in 2 waves and the other 5 take 3 waves.
Test 2, starts with 2 soldiers and a castle with strength 10 which can send 1 defender per wave.
Not surprisingly most of the solutions again correspond to wins by the castle. There are wins by the castle in 3,4,5,6,7,8 waves. The soldiers however can win in 9 rounds in 2 different ways: Up until wave 7 the 2 soldiers hit at the defender and cut by 1 the castle hits. Wave 8 starts with 2 soldiers, 1 defender and 2 castleHits. The soldiers have now two options to win: Finish off the castle, and lose one soldier hit by the lone defender, then finishing off the defender in wave 9 which ends with 1 soldier left. Or hit the defender and the castle in wave 8, then in wave 9 finishing off the castle and the defender and ending with 2 soldiers. Interestingly these two solutions were found by the approximate approaches that we saw in our previous post.
Test 3, starts with 11 soldiers and a castle with strength 12 which can send 9 defenders per wave.
This case only admits a single solution: The soldiers win in two rounds.
Test 4 (12 soldiers, castleHits=32, defenders per wave =5) has 136 solutions in which the soldiers win and 797 in which the castle wins.
Test 10 in figure 4, has a single solution that leads to a win by the soldiers in 4 rounds/waves (path in blue). It also has a tie on the second wave (path in green). Eight other paths lead to a win by the castle:3 paths in 3 waves and 5 paths in 4 waves. As we saw in our previous post, the approach of always attacking the defenders first, leads to the tie (green) path, while the approach of attacking the castle leads to the correct solution (blue).
An important caveat: If you run this code as is be prepared to wait 5-7 minutes. That is how long it will take for all the 27 tests to run.
# if castleHits =0, soldiers play against defenders only
def soldiersVsDefenders(self,soldiers,defenders):
# soldiers win or castle/defenders win
if defenders <=0 or soldiers <= 0:
return
# do another round of fighting
# 1. Soldiers kill as many defenders
defendersLeft = defenders - soldiers
# 2. defendersLeft kill as many soldiers
soldiersLeft = soldiers - defendersLeft
self.soldiersVsDefenders(soldiersLeft,defendersLeft, 1+wave)
def oneWave(self,soldiers,defenders,castleHits,wave =0):
# castle/defenders wins
if soldiers <= 0:
return
# castle is dead, let soldiers play against defenders
if castleHits <= 0:
defendersLeft = defenders - self.dpw
self.soldiersVsDefenders(soldiers,defendersLeft,path, wave)
return
# try every possibility:
# 1) all soldiers hit the castle, none hits the defenders
# 2) all but one soldier hits the castle, the others hit the defenders
# 3) all but two soldiers hit the castle, the others hit the defenders
# ...
# soldiers) no soldier hits the castle, all others hit the
# defenders
for i in range(0,soldiers+1):
if i > defenders:
break
soldiersLeft = soldiers - (defenders -i)
defendersLeft = defenders - i + self.dpw
castleHitsLeft = castleHits - (soldiers -i)
self.oneWave(soldiersLeft,defendersLeft,castleHitsLeft,1+ wave)
# start game
def searchMinimumRecursive(self,soldiers,castleHits,defendersPerWave):
self.dpw = defendersPerWave
self.oneWave(soldiers,0,castleHits)
The oneWave method simulates... one round/wave of the game. It is first called by the searchMinimumRecursive with the initial values.For each wave the method takes however many soldiers, defenders, castleHits are available at the beginning of that wave as arguments as well as the wave number (note how by default wave starts at 0).
The method then tries every possible path for those initial values recursively. This is achieved through the for loop
for i in range(0,soldiers+1):
Lets walk through the loop:
- When i=0, all soldiers hit the castle and all defenders hit the soldiers so at the end of the wave, \(soldiersLeft=soldiers-defenders, defendersLeft=defenders+self.dpw, castleHitsLeft=castleHits-soldiers\). Then recurse with those values.
- When i=1, all but one of the soldiers hits the castle, one soldier hits one defender and the remaining defenders-1 defenders hit the soldiers so at the end of the wave, \(soldiersLeft=soldiers-(defenders-1), defendersLeft=defenders-1+self.dpw, castleHitsLeft=castleHits-(soldiers-1)\). Then move to the next wave with those values.
- When i=2, all but two of the soldiers hits the castle, two soldiers hit two defenders and the remaining defenders-2 defenders hit the soldiers so at the end of the wave, \(soldiersLeft=soldiers-(defenders-2), defendersLeft=defenders-2+self.dpw, castleHitsLeft=castleHits-(soldiers-2)\). Then move to the next wave with those values.
- This pattern continues until i=soldiers. For this case, all soldiers hit the defenders and the remaining defenders hit back at the soldiers so at the end of the wave, \(soldiersLeft=soldiers-(defenders-soldiers), defendersLeft=defenders-soldiers+self.dpw, castleHitsLeft=castleHits\).
If at any point in the recursion, soldiers becomes zero or smaller it means we reached a goal state where the castle wins and we just return.
If at any point in the recursion, castleHits becomes zero or smaller, it means the castle can no longer send defenderPerWaves defenders at the end of each round.
In this case we subtract the defendersPerWave that we had added to the defendersLeft in the for loop (because we didnt know at the time that castleHits<=0) and call the method soldiersVsDefenders.
Note that we do not increase the wave value in this call. This makes sense: We at first played regularly (in the for loop) and recursed by increasing the wave number and the number of defenders as if the castle still had points left. Then we realized that the castle is gone, so we subtracted back the defendersPerWave and call soldiersVsDefenders so that the correct play for this wave can be made with the remaining soldiers and defenders playing against each other (the castle is gone from the picture).
The soldiersVsDefenders method just plays out wave after wave of soldiers vs defenders recursively: All soldiers hit an equal number of defenders leaving \(defendersLeft=defenders-soldiers\) and the remaining defenders then hit back leaving \(soldiersLeft=soldiers-defendersLeft\) soldiers. Then it increases the wave number and recurses.
If at any point soldiers or defenders become zero or lower then the castle or the soldiers respectively win i.e we stop recursing.
This recursive process is a more complicated example of what sometimes is called depth first search/recursive backtracking: Starting at the root it follows a path all the way down until it finds a goal state or until it reaches a dead end. Then it backtracks up and repeats.
To visualize this process lets draw all possible paths for a few of the test cases from our previous post.
Figure 2 shows all the paths tried by the recursive algorithm for test 0, which starts with gameSoldiers=10, castleHits=11, defendersPerWave=15.
 |
| Figure 2 test0 solutions as found by the recursive method |
There are only 3 paths (S,D and CH stand for soldiers, defenders and castlehits at the beginning of each wave) that lead to wins: The two in red correspond to wins by the castle. The one in blue corresponds to the only possible win by the soldiers (thus it is the minimum number of waves solution we care about).
The blue solution (4 waves) is
S=10, D=0, CH=11→ S=10, D=15,CH=1 → S=4,D=6, CH= 0 → S=2, D=2, CH=0 → S=2, D=0, CH=0
Notice how we didn't include S=4,D=21,CH=0 in the path because it corresponds to the jump from the oneWave method to the soldiersVsDefenders method as discussed above. The method oneWave realizes that the castle is gone, subtracts the 15 defendersPErWave to the number of defenders that had added incorrectly and calls soldiersVsDefenders that then battle each other. The two castle wins (both in 3 waves) areS=10, D=0, CH=11→ S=10, D=15,CH=1 → S=5,D=20, CH= 1 → S=0, D=16, CH=0
andS=10, D=0, CH=11→ S=10, D=15,CH=1 → S=5,D=20, CH= 1 → S=0, D=15, CH=1
A few words about these solutions and figure 2:- We adopt the convention that in the wave that the castle wins, the castle does not send defendersPerWave more defenders (otherwise the number of defenders in the last solution would be 30 not 15 in the last wave);
- Most end states (including both of the red solutions), have a negative final number of soldiers. We discard all of those for which the castleHits is also negative. Those for which castleHits are 0 or greater are good solutions and that is how we picked the two red solutions.
- The transitions labeled soldiersVsDefenders indicate that the algorithm having reached zero castle hits calls soldiersVsDefenders from then on.
- Each transition is labeled by the value of i in the loop above. So we see that the only solution that leads to a win by the soldiers has 9 of the soldiers hitting at 9 of the defenders and one soldier hitting at the castle in the second wave. The two solutions that lead to a win by the castle have all 10 soldiers hit at 10 of the defenders but not at the castle (in the second wave) which turns out to be a big mistake for the soldiers.
 | |
| Figure 3- test1 solutions as found by the recursive method |
Two of the paths achieve the win in 2 waves and the other 5 take 3 waves.
Test 2, starts with 2 soldiers and a castle with strength 10 which can send 1 defender per wave.
Not surprisingly most of the solutions again correspond to wins by the castle. There are wins by the castle in 3,4,5,6,7,8 waves. The soldiers however can win in 9 rounds in 2 different ways: Up until wave 7 the 2 soldiers hit at the defender and cut by 1 the castle hits. Wave 8 starts with 2 soldiers, 1 defender and 2 castleHits. The soldiers have now two options to win: Finish off the castle, and lose one soldier hit by the lone defender, then finishing off the defender in wave 9 which ends with 1 soldier left. Or hit the defender and the castle in wave 8, then in wave 9 finishing off the castle and the defender and ending with 2 soldiers. Interestingly these two solutions were found by the approximate approaches that we saw in our previous post.
Test 3, starts with 11 soldiers and a castle with strength 12 which can send 9 defenders per wave.
This case only admits a single solution: The soldiers win in two rounds.
Test 4 (12 soldiers, castleHits=32, defenders per wave =5) has 136 solutions in which the soldiers win and 797 in which the castle wins.
Test 10 in figure 4, has a single solution that leads to a win by the soldiers in 4 rounds/waves (path in blue). It also has a tie on the second wave (path in green). Eight other paths lead to a win by the castle:3 paths in 3 waves and 5 paths in 4 waves. As we saw in our previous post, the approach of always attacking the defenders first, leads to the tie (green) path, while the approach of attacking the castle leads to the correct solution (blue).
 | |
| Figure 4- test10 solutions as found by the recursive method |
RECURSIVE CODE WALKTHROUGH
Without further ado, lets look at the complete code that computes all the wins by the castle and the soldiers.The code builds upon the recursive algorithm described above but it is moderately complicated due to the handling of the several goal states and above all by the computation of the path. We added many comments to make it more readable/understandable.
The file tests.py contains the 27 tests. It also has the runTests method which will run them all. You can edit the all_tests list in this method, to run just a few tests (or even only one test) at a time.
The file CastleDefenseIIRecursive.py contains the main algorithm (in the methods searchMinimumRecursive which calls the method oneWave which will call the method soldiersVsDefenders in the case where castleHits reach zero but there are soldiers and defenders to battle it out).
The main algorithm computes all the paths that go from the initial state to a state corresponding to a win by either the soldiers or the castle (not just the shortest paths but ALL paths; a nice challenge for you is to modify the code to find only the shortest paths). It is the computation of all these paths that makes the program so slow (for some of the 27 tests there are thousands of solutions). In order to limit the running time you will notice that in tests.py some tests (test_5, test_12, test_22, test_25, test_26) will only keep solution paths in which the soldiers win. This is controlled by setting to false the boolean self.trackCastleWins in CastleDefenseIIRecursive. You will notice that if this flag is false, whenever a goal state in which the castle wins (i.e. the number of defenders is <=0) is found in either the oneWave method or the soldiersVsDefenders method, the path it is not added to the self.waveStats dictionary. If you are curious to see the runtime increase you can switch to True this flag in those 4 tests.
The solution paths are stored as lists in the dictionary self.waveStats. These paths are grouped by the number of waves they take (the length of a path is always wave+1). These waves are the keys in the dictionary. Because of this grouping, for a given key lets say 3 there will be paths that correspond both to wins by the soldiers and by the castle. These paths all take 3 waves. In order to find a path with minimum wave/rounds in self.waveStats that correspond to a soldier's wins, the method searchMinimumRecursive in CastleDefenseIIRecursive loops through the keys in self.waveStats in sorted order from smallest to largest. As soon as it finds a path with soldiers>0 it returns all the paths at that key to the test that called searchMinimumRecursive (it assumes that all those paths are wins by the soldiers).
If it reaches the end of the loop and it did not find any solution with soldiers>0, that means the soldiers can never win and it then returns all paths (corresponding to castle wins) at the smallest key in the dictionary. The runTests method will then display each step of each minimum wave path.
The method printSolutions (which is called by searchMinimumRecursive for each test) prints additional information: How many winning solutions corresponding to wins by the soldiers per wave were found and similarly how many solutions corresponding to wins by the castle per wave were found. It also prints out how many total paths correspond to wins by the soldiers and by the castle (independently of the number of rounds each of these paths takes).
PATH COMPUTATION
The complicated part of the code in CastleDefenseIIRecursive.py is the computation of the paths. Lets walk through the code to understand how each path from the initial state to a goal state (castle/soldiers win) is computed.
In the method searchMinimumRecursive, the path is initialized with the initial state and it is passed as an argument to the call self.oneWave.
In the for loop of this method that tries all the possible outcomes, the number of soldiers, defenders and castleHits in the next wave is appended to the path list and self.oneWave is called recursively.
With each recursive call the wave value goes up by one and another step is added to the path list.
If, during a recursive call, the number of soldiers becomes negative or zero (i.e. the soldiers lose), we
replace the very last step in the path list, with a zero number of soldiers and subtract defenders per wave from the number of defenders. This is because in the recursive call that led to soldiersLeft<=0, self.dpw were added to defendersLeft under the assumption that there were soldiers left for another round. Then the corrected path is added to the dictionary of solution paths, self.waveStats and right before the method returns the last step is removed because we are returning to the recursive call where self.wave is one less.
All of this is easier to understand by looking for example at figure 3. Consider the path (S=3,D=0,CH=10)→ (S=3,D=4,CH=7)→ (S=-1,D=8,CH=4). After correcting the last step to (S=0, D=4, CH=4) and adding the whole path to the dictionary of paths, we want to remove this last step, right before returning/backtracking to the level above. The code will then try the next path (S=3,D=0,CH=10)→ (S=3,D=4,CH=7)→ (S=0,D=7,CH=5), correct the last step, add the path to the dictionary and remove this last step from the path before backtracking again one level up. If we did not remove the last step in the first path, then we would end up with the path (S=3,D=0,CH=10)→ (S=3,D=4,CH=7) → (S=0,D=4,CH=4) → (S=0,D=7,CH=5), for the second path which is obviously wrong.
The other possibility during a recursive call is that the number of castleHits becomes 0 or negative.
Then in the self.oneWave method, we subtract from defendersLeft the number of defenders per wave (because these were added in the calling method without realizing that since castleHits<=0, the castle cant send any more defenders), correct the last step in the path and call self.soldiersVsDefenders.
This method appends to the path with each wave until either the number of defenders or soldiers becomes zero or negative. If the number of soldiers is positive, but the number of defenders is negative, that means that in the previous call, self.soldiersVsDefenders added soldiers to the existing number of soldiers (since it does soldiersLeft=soldiers-defendersLeft and since defendersLeft<0, this means we are increasing the number of soldiers) which is not a valid move. Therefore we should subtract the number of defenders that we previously added to the number of soldiers. Thats what we do with soldiers=soldiers+defenders. The path is corrected, added to self.waveStats and then all the steps added to the path since self.oneWave called self.soldiersVsDefenders are removed, since we are returning to the self.oneWave method.
Again to understand this logic it is easier to look at an example. Consider the path (S=10,D=0,CH=11) → (S=10,D=15,CH=1) → (S=4,D=21,CH=0) → (S=4,D=6, CH=0) → (S=2, D=2, CH=0) → (S=2, D=0, CH=0) in figure 2. Since we are returning all the way up to the step (S=4,D=21,CH=0) (which is where self.oneWave called self.soldiersVsDefenders) we have to remove all the steps after that one before returning otherwise we would end up with an incorrect next path (just like in the example above were the castle wins).
The final piece is in the method self.oneWave loop. After we return back to self.oneWave (from another self.oneWave call or from self.soldiersVsDefenders) we check if it is the end of the loop (if soldiers<defenders, the end of the loop is at i=soldiers, otherwise it is at i=defenders, since when i>defenders we break out of it). If it is, we remove all steps that are above the current wave.
To understand this, consider the last path in figure 3, (S=3,D=0,CH=10) → (S=3,D=4,CH=7) → (S=2, D=5,CH=7) → (S=-1(0),D=7(3),CH=7). When we return to self.oneWave where i=2, we remove the last step. But we immediately return to self.oneWave where i=3 so we have to remove the previous to last step to keep the path length equal to the length of the wave were we are returning to.
The other possibility during a recursive call is that the number of castleHits becomes 0 or negative.
Then in the self.oneWave method, we subtract from defendersLeft the number of defenders per wave (because these were added in the calling method without realizing that since castleHits<=0, the castle cant send any more defenders), correct the last step in the path and call self.soldiersVsDefenders.
This method appends to the path with each wave until either the number of defenders or soldiers becomes zero or negative. If the number of soldiers is positive, but the number of defenders is negative, that means that in the previous call, self.soldiersVsDefenders added soldiers to the existing number of soldiers (since it does soldiersLeft=soldiers-defendersLeft and since defendersLeft<0, this means we are increasing the number of soldiers) which is not a valid move. Therefore we should subtract the number of defenders that we previously added to the number of soldiers. Thats what we do with soldiers=soldiers+defenders. The path is corrected, added to self.waveStats and then all the steps added to the path since self.oneWave called self.soldiersVsDefenders are removed, since we are returning to the self.oneWave method.
Again to understand this logic it is easier to look at an example. Consider the path (S=10,D=0,CH=11) → (S=10,D=15,CH=1) → (S=4,D=21,CH=0) → (S=4,D=6, CH=0) → (S=2, D=2, CH=0) → (S=2, D=0, CH=0) in figure 2. Since we are returning all the way up to the step (S=4,D=21,CH=0) (which is where self.oneWave called self.soldiersVsDefenders) we have to remove all the steps after that one before returning otherwise we would end up with an incorrect next path (just like in the example above were the castle wins).
The final piece is in the method self.oneWave loop. After we return back to self.oneWave (from another self.oneWave call or from self.soldiersVsDefenders) we check if it is the end of the loop (if soldiers<defenders, the end of the loop is at i=soldiers, otherwise it is at i=defenders, since when i>defenders we break out of it). If it is, we remove all steps that are above the current wave.
To understand this, consider the last path in figure 3, (S=3,D=0,CH=10) → (S=3,D=4,CH=7) → (S=2, D=5,CH=7) → (S=-1(0),D=7(3),CH=7). When we return to self.oneWave where i=2, we remove the last step. But we immediately return to self.oneWave where i=3 so we have to remove the previous to last step to keep the path length equal to the length of the wave were we are returning to.
OUTPUT
Below is the output for test 2. It first shows that the soldiers can only win in 9 rounds/waves and there are 2 solutions with that number of waves.Next it shows that the castle on the other hand can win in 3, 4, 5, 6, 7, 8 waves and in each of these cases there are 2 solutions that lead to the win.
The 2 paths leading to a win by the soldiers (in 9 rounds) are then shown. They are the same up until the end of wave 7. At the start of wave 8 there are 2 soldiers, 1 defender and 2 castle hits. In the first solution the 2 soldiers vanish the castle hits then lose one soldier and kill the defender in wave 9. One soldier is left standing. In the second solution, the 2 soldiers kill the defender and one of the castle hits and in wave 9 repeat the same strategy, leaving 2 soldiers standing.
Executing test 2 soldiers win wave: number of solutions with that wave {9: 2} castle win wave : number of solutions with that wave {3: 2, 4: 2, 5: 2, 6: 2, 7: 2, 8: 2} number of soldier wins: 2 number of castle wins: 12 *************** Recursive Solution *************** Starting numbers (Begin of Wave 1) defenders per wave =1 ---------------- Number of Soldiers: 2 Number of Defenders: 0 Total castle hits left: 10 End of Wave 1 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 8 End of Wave 2 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 7 End of Wave 3 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 6 End of Wave 4 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 5 End of Wave 5 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 4 End of Wave 6 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 3 End of Wave 7 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 2 End of Wave 8 Number of Soldiers: 1 Number of Defenders: 1 Total castle hits left: 0 End of Wave 9 Number of Soldiers: 1 Number of Defenders: 0 Total castle hits left: 0 Soldiers win in 9 rounds Starting numbers (Begin of Wave 1) defenders per wave =1 ---------------- Number of Soldiers: 2 Number of Defenders: 0 Total castle hits left: 10 End of Wave 1 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 8 End of Wave 2 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 7 End of Wave 3 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 6 End of Wave 4 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 5 End of Wave 5 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 4 End of Wave 6 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 3 End of Wave 7 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 2 End of Wave 8 Number of Soldiers: 2 Number of Defenders: 1 Total castle hits left: 1 End of Wave 9 Number of Soldiers: 2 Number of Defenders: 0 Total castle hits left: 0 Soldiers win in 9 rounds =================================
Note that for a given test, if the soldiers can win, the code will output all the minimum number of rounds solutions corresponding to the soldiers wins. It will not show the wins by the castle that take a minimum number of waves. Since however the dictionary self.waveStats has all solutions we could easily modify the runTests method to also print those castle wins.
If the soldiers can not win, then the code will output the minimum number of castle wins solutions like in test 7 below
======================================== Executing test 7 soldiers win wave: number of solutions with that wave {} castle win wave : number of solutions with that wave {2: 2, 3: 2} number of soldier wins: 0 number of castle wins: 4 *************** Recursive Solution *************** Starting numbers (Begin of Wave 1) defenders per wave =7 ---------------- Number of Soldiers: 4 Number of Defenders: 0 Total castle hits left: 6 End of Wave 1 Number of Soldiers: 4 Number of Defenders: 7 Total castle hits left: 2 End of Wave 2 Number of Soldiers: 0 Number of Defenders: 5 Total castle hits left: 0 Castle wins in 2 rounds Starting numbers (Begin of Wave 1) defenders per wave =7 ---------------- Number of Soldiers: 4 Number of Defenders: 0 Total castle hits left: 6 End of Wave 1 Number of Soldiers: 4 Number of Defenders: 7 Total castle hits left: 2 End of Wave 2 Number of Soldiers: 0 Number of Defenders: 4 Total castle hits left: 1 Castle wins in 2 rounds ========================================
SUMMARY
We end this post with a table that summarizes the output for all 27 tests. In particular it shows the number of wins for both soldiers and castle organized by the number of waves those wins take
| Test | Initial Soldiers/CastleHits/Defenders per wave | Wins by the Soldiers (Wave/number of wins) | Wins by the Castle (Wave/number of wins) |
|---|---|---|---|
| 0 | 10/11/15 | 1 (wave 4/1 win) | 2 (wave 3/2 wins) |
| 1 | 3/10/4 | None | 7 (wave 2/2 wins, wave 3/5 wins) |
| 2 | 2/10/1 | 2 (wave 9/2 wins) | 12 (wave 3/2 wins, wave 4/2 wins, wave 5/2 wins, wave 6/2 wins, wave 7/2 wins, wave 8/2 wins) |
| 3 | 11/12/9 | 1 (wave 2/1 win) | None |
| 4 | 12/32/5 | 136 (wave 4/2 wins, wave 5/21 wins, wave 6/29, wave 7/19, wave 8/22, wave 9/15, wave 10/15 wins, wave 11/9 wins, wave 12/4 wins) | 797 (wave 3/6 wins, wave 4/71 wins, wave 5/115 wins, wave 6/146 wins, wave 7/152 wins, wave 8/126 wins, wave 9/90 wins, wave 10/54, wave 11/26 wins, wave 12/9 wins, wave 13/2 wins) |
| 5 | 12/44/6 | 2743 (wave 7/15 wins, wave 8/66 wins, ..., wave 27/1 win ) | 54157 (wave 3/16 wins, wave 4/123 wins, ..., wave 26/2 wins)-more than 20 minutes in chrome to get these |
| 6 | 7/10/8 | 1 (wave 4/1 win) | 15 (wave 3/6 wins, wave 4/9 wins) |
| 7 | 4/6/7 | None | 4 (wave 2/2 wins, wave 3/2 wins) |
| 8 | 8/10/6 | 1 (wave 2/1 win) | None |
| 9 | 4/5/5 | 1 (wave 3/1 win) | 2 (wave 3/2 wins) |
| 10 | 5/8/5 | 1 (wave 4/1 win) | 8 (wave 3/3 wins, wave 4/5 wins) |
| 11 | 10/50/9 | 14 (wave 37/2 wins, wave 38/1 win, wave 39/3 wins, wave 40/3 wins, wave 41/4 wins, wave 42/1 win) | 4561 (wave 3/39 wins, wave 4/99 wins, wave 5/134 wins, wave 6/136 wins, wave 7/136 wins, wave 8/136 wins, ..., wave 43/2 wins ) |
| 12 | 19/50/15 | 4408 (wave 8/4 wins, wave 9/23 wins, wave 10/75 wins, wave 11/156 wins, wave 12/257 wins, wave 13/364 wins, wave 14/448 wins, wave 15/488 wins, wave 16/482,...,wave 28/11 wins, wave 29/3 wins, wave 30/2 wins) | 208689 (wave 3/104 wins, wave 4/546 wins, wave 5/1560 wins, wave 6/3420 wins, wave 7/6390 wins, wave 8/10326, wave 9/14686 wins, wave 10/18782 wins,...,wave 29/9 wins, wave 30/2 wins)-more than 5 hours in chrome to get these |
| 13 | 10/50/10 | None | 97 (wave 2/1 win, wave 3/42 wins, wave 4/49 wins, wave 5/5 wins) |
| 14 | 8/9/18 | None | 2 (wave 2/2 wins) |
| 15 | 9/11/12 | 1 (wave 4/1 win) | 5 (wave 3/5 wins) |
| 16 | 5/37/5 | None | 18 (wave 2/1 win, wave 3/12 wins, wave 4/5 wins) |
| 17 | 9/33/8 | 12 (wave 22/2 wins, wave 23/2 wins, wave 24/2 wins, wave 25/4 wins, wave 26/2 wins) | 1825 (wave 3/32 wins, wave 4/76 wins, wave 5/101 wins, wave 6/101 wins, wave 7/101 wins, wave 8/101 wins, ..., wave 26/2 wins) |
| 18 | 8/21/7 | 9 (wave 11/1 win, wave 12/1 win, wave 13/3 wins, wave 14/3 wins, wave 15/1 win) | 558 (wave 3/26 wins, wave 4/57 wins, wave 5/73 wins, wave 6/73 wins, wave 8/65 wins, wave 9/58 wins, wave 10/46 wins, wave 11/37 wins, wave 12/25 wins, wave 13/15 wins, wave 14/8 wins, wave 15/2 wins) |
| 19 | 12/13/50 | None | 2 (wave 2/2 wins) |
| 20 | 7/31/5 | 65 (wave 13/4 wins, wave 14/4 wins, wave 15/6 wins, wave 16/6 wins, wave 17/6 wins, wave 18/6, wave 19/6 wins, wave 20/6 wins, wave 21/6 wins, wave 22/6 wins, wave 23/5 wins, wave 24/4 wins) | 3228 (wave 3/16 wins, wave 4/40 wins, wave 5/69 wins, wave 6/103 wins, wave 8/171 wins, wave 9/205 wins, wave 10/239 wins, wave 11/268 wins, wave 12/287 wins, wave 13/291 wins, wave 14/276 wins, wave 15/252 wins, ..., wave 25/2 wins) |
| 21 | 19/50/14 | 5457 (wave 7/6 wins, wave 8/45 wins, wave 9/134 wins, wave 10/269 wins, wave 11/426 wins, wave 12/570, wave 13/661 wins, wave 14/671 wins, wave 15/618 wins, wave 16/525 wins, wave 17/425 wins, ..., wave 30/1 win) | 181537 (wave 3/93 wins, wave 4/542 wins, wave 5/1667 wins, wave 6/3870 wins, wave 7/7361 wins, wave 8/11905 wins, wave 9/16518 wins, wave 10/20271 wins, wave 11/22018 wins, wave 12/21557 wins, wave 13/19346 wins, wave 14/16095 wins, ..., wave 29/2 wins)-more than 3 hours in chrome to get these |
| 22 | 20/50/18 | 678 (wave 12/2 wins, wave 13/3 wins, wave 14/9 wins, wave 15/19 wins, wave 16/32 wins, wave 17/45, wave 18/50 wins, wave 19/54 wins, wave 20/57 wins, wave 21/57 wins, wave 22/56 wins, ..., wave 30/2 wins) | 88037 (wave 3/137 wins, wave 4/606 wins, wave 5/1310 wins, wave 6/2167 wins, wave 7/3140 wins, wave 8/4077 wins, wave 9/4962 wins, wave 10/5737 wins, wave 11/6359 wins, wave 12/6794 wins, wave 13/6960 wins, wave 14/6872 wins, ..., wave 32/2 wins)-more than 1 hour and a half in chrome to get these |
| 23 | 3/30/1 | 26 (wave 15/2 wins, wave 16/2 wins, wave 17/2 wins, wave 18/2 wins, wave 19/2 wins, wave 20/2, wave 21/2 wins, wave 22/2 wins, wave 23/2 wins, wave 24/2 wins, wave 25/2 wins, wave 26/2 wins, wave 27/2 wins) | 300 (wave 3/1 win, wave 4/3 wins, wave 5/5 wins, wave 6/7 wins, wave 7/9 wins, wave 8/11 wins, wave 9/13 wins, wave 10/15 wins, wave 11/17 wins, wave 12/19 wins, wave 13/21 wins, wave 14/23 wins, ..., wave 26/2 wins) |
| 24 | 2/50/1 | 2 (wave 49/2 wins) | 92 (wave 3 through wave 48 with 2 wins for each wave) |
| 25 | 9/43/7 | 139 (wave 17/1 win, wave 18/4 wins, wave 19/7 wins, wave 20/8 wins, wave 21 to 31/9 wins each, wave 32/8 wins, wave 33/7 wins, wave 34/4 wins, wave 35/1 win) | 14706 (wave 3/27 wins, wave 4/77 wins, wave 5/136 wins, wave 6/209 wins, wave 7/282 wins, wave 8/355 wins, wave 9/428 wins, wave 10/501 wins, wave 11/ 574 wins, wave 12/647 wins,...,wave 35/2 wins) |
| 26 | 10/43/8 | 177 (wave 16/1 win, wave 17/2 wins, wave 18/8 wins, wave 19/9 wins, wave 20/11 wins, wave 21-wave 30/12 wins each, wave 31/10 wins, wave 32/8 wins, wave 33/6 wins, wave 34/2 wins | 18165 (wave 3/34 wins, wave 4/100 wins, wave 5/181 wins, wave 6/282 wins, wave 7/383 wins, wave 8/484 wins, wave 9/585 wins, wave 10/686 wins, wave 11/787 wins, wave 12/888 wins,...,wave 31/ 55 wins, wave 32/25 wins, wave 33/9 wins, wave 34/2 wins) |
For tests 5, 12, 21 and 22 we had to run the program for quite a long time (the approximate time is indicated in green) to find out the number of castle wins. The larger that number, the longer the run time. Test 12 took more than 5 hours (in Chrome) to find out that there are 208689 different ways for the castle to win.
Other interesting facts:
In every case where there is no soldiers win (test 1,7,13,14,16, 19) the shortest wave win by the castle always takes 2 waves. If there is at least a soldiers' win, and there are castle wins, the smallest castle win always requires 3 waves.
There are nearly always more solutions where the castle wins than solutions where the soldiers win.
No comments:
Post a Comment