tag:blogger.com,1999:blog-12741950191365609472017-08-22T05:20:22.873-07:00Python In ShortLearn Python through short programs
jenny furtadonoreply@blogger.comBlogger13125tag:blogger.com,1999:blog-1274195019136560947.post-82669651744821371692015-09-15T18:37:00.000-07:002016-07-03T23:06:21.525-07:00Castle Defense III-Exact mathematical solution<style>.post-container { margin: 20px 20px 0 0; border: 2px solid #333; overflow: auto } .post-thumb { float: right } .post-thumb a { display: block } .post-content { margin-left: 2px } </style> <br /><div class="post-container"><div class="post-thumb"></div><div class="post-content"><a href="http://1.bp.blogspot.com/-dqzal2qBcD4/V3XHZJN5p0I/AAAAAAAAALY/VItzKLq41Fcp1DbSC8oj8LIKi7nuatW_QCK4B/s1600/castle5.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="600" src="https://1.bp.blogspot.com/-dqzal2qBcD4/V3XHZJN5p0I/AAAAAAAAALY/VItzKLq41Fcp1DbSC8oj8LIKi7nuatW_QCK4B/s1600/castle5.jpg" width="640" /></a><br /><h3 style="text-align: center;"><b>A recap</b></h3>In the previous two posts we looked at two different ways of solving the following problem: A group of \(n\) soldiers, each carrying a canon and a rifle, attacks a castle which has initial strength \(s\). If \(s>0\) at the end of a bloody day, the castle can send \(dpw\) defenders a day out of its gates to battle the soldiers. <i>On the<b> </b> the first day, all soldiers fire their canons at the castle decreasing its strength to \(s-n\).</i> <i>In the ensuing days the castle and the soldiers battle it out following these rules:</i><br /><ol><li><i>All the soldiers fire first. A soldier can either fire his canon at the castle or his rifle at one of the defenders (but not both and each soldier can only shoot once). One shot at a defender kills him. One shot at the castle decreases its strength by 1.</i></li><li><i>Each of the defenders will then shoot one soldier (and only one) killing him.</i></li><li><i>If the castle still has strength points (i.e. \(s>0\)) it will send a new batch of <b>defendersPerWave</b> (dpw) defenders at this point. The total number of defenders in the next round (day) will then be \(defenders=defenders + defendersPerWave\).</i></li><li><i>Repeat 1 through 3 each new day.</i></li><li><i>If all soldiers are killed by the defenders, the castle wins even if its strength is zero.</i></li><li><i>If there are zero defenders left after the soldiers shot and the castle strength is also zero, the soldiers win.</i></li></ol>The soldiers want to destroy the castle and its defenders in the minimum number of days/waves. If that is not possible how many days does it take for them to lose? <br /><div>In the <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">first post</a> of this series we described two simple strategies in which the soldiers, in each wave, either decided to attack the castle first and only then its defenders or vice versa, i.e. attack the defenders first and only then the castle. Neither of these approaches was able to find the minimum number of days solution for every set of initial values of \(s\), \(n\) and \(dpw\).</div><div><br /></div><div>In the <a href="http://pythonshort.blogspot.com/2015/08/castle-defense-ii-exact-recursive.html" target="_blank">second post </a>we described a recursive brute force search algorithm that correctly finds the minimum number of days for the soldiers to win and the exact steps-the path from the initial state towards the end goal- that the soldiers should take to win the battle in that minimum number of days. The algorithm is also used to find all possible solutions not just those that lead to a win by the soldiers in a minimum number of days but also solutions in which the castle wins and solutions in which the soldiers win in a non minimum number of days.</div><div><br /></div><div>In this post we will do a careful mathematical study of the problem and use its peculiar structure to determine, given the number of initial soldiers \(n\), the number of initial castle hits/strength \(s\) and the number of defenders per wave \(dpw\),<br />1) Whether the soldiers can win and, if they can, what is the minimum number of days it takes for them to do so and what is the strategy the soldiers should use to accomplish it. We will be able to give a complete answer to this.<br />2) If the soldiers can not win, what is the minimum number of days for the castle to win and which strategy should the castle follow to achieve this. This is harder than 1) but we will go over some cases.<br />3) Finally is there a simple way to find all the paths that lead to a win by either side? Unfortunately it is too difficult to find these without an exhaustive search.<br /><br />This post is fairly advanced mathematically and it is perhaps the hardest of this blog's posts so far. The result of all this hardship is a deeper insight into the problem as well as a quicker way to solve it. In particular we will see that the analysis will give the best strategy the soldiers should follow and therefore will tell us the path from the initial state to the goal state without the need to do a computationally expensive search like we did in our <a href="http://pythonshort.blogspot.com/2015/08/castle-defense-ii-exact-recursive.html" target="_blank">second post </a>.</div><div><br /></div><h3 style="text-align: center;">1. The case \(s\leq n\) : The castle can not win</h3><div><br /></div><div>If the number of soldiers \(n\) is greater or equal to the castle strength \(s\), then the soldiers clearly win in one day (in the first day right after they discharge their canons on the castle).</div><div><br /></div><div><h3 style="text-align: center;"><b>2. </b>The case \(s > n\): <b>When can the soldiers win?</b></h3></div><div>In the opposite case where the number of initial soldiers is smaller than the initial castle strength, there will always be (bad) soldier strategies that lead to the castle winning<b>.</b></div><div><b><br /></b></div><div>In some cases however even if they follow the best strategy, the soldiers can not win. In this section we would like to determine for what initial values of \(n,s,dpw\) can the soldiers win and the minimum number of days it will take for them to achieve the win.</div><div><br /></div><div>Lets introduce some notation: For a given day <i>i,</i> let \(c_{i}\) be the remaining castle strength, \(s_{i}\) be the remaining number of soldiers and \(d_{i}\) the remaining number of castle defenders. Let \(dpw\) be the number of defenders the castle sends each new day/wave.</div><div><br /></div><div><br /></div><div><h4 style="text-align: center;"><b><u>2.a Best strategy if \(dpw<n\): Kill all defenders every day</u></b></h4></div><div><br /></div><div>Consider first the case where \(d_{i}=dpw\) at the start of a given day, i.e. the soldiers killed all defenders the previous day.</div><div><br /></div><div>Suppose that on this day the soldiers kill some defenders, leaving \(x\) of them at the end of the day (i.e. \(dpw-x\) of the soldiers killed \(dpw-x\) defenders, the remaining \(s_{i}-(dpw-x)\) soldiers shot at the castle and the \(x\) defenders shot back at the soldiers leaving \(s_{i}-x\) of them standing), and the castle is left standing (i.e. \(c_{i}>0\)). Then the start of the new day (\(i+1\)) begins with the following numbers</div><div><br /></div><div>\begin{align}<br />s_{i+1} &= s_{i}-x\tag{1}\label{ref1}\\ \\<br />d_{i+1}& = dpw+x\tag{2}\label{ref2}\\ \\<br />c_{i+1}&=c_{i}-[s_{i}-(d_{i}-x)]=c_{i}-[s_{i}-(dpw-x)]=(c_{i}+dpw)-(s_{i}+x)<br />\tag{3}\label{ref3}<br />\end{align}<br /><br />Clearly on day \(i+1\) there are more defenders and less soldiers than on day \(i\).<br /><br />Lets suppose that the soldiers on day \(i+1\) decide to kill all \(d_{i+1}\) defenders again. This means that the remaining \(s_{i+1}-d_{i+1}\) soldiers attack the castle. We still assume that \(c_{i+1}>0\).<br />Then at the start of the next day we will be left with<br /><br />\begin{align}<br />s_{i+2}& = s_{i+1}=s_{i}-x\\ \\<br />d_{i+2}& = dpw\\ \\<br />c_{i+2}&=c_{i+1}-(s_{i+1}-d_{i+1})=c_{i}+dpw-s_{i}-x-s_{i}+x+dpw+x=c_{i}+2dpw + x-2s_{i}\tag{4}\label{ref4}<br />\end{align}<br /><br />where we replaced the quantities on day \(i+1\) with \ref{ref1},\ref{ref2},\ref{ref3}.<br /><br />If however the soldiers killed all defenders every single day (i.e. \(x=0\)), we would have on day \(i+2\)<br /><br />\begin{align}<br />s_{i+2}& = s_{i+1}=s_{i}\\ \\<br />d_{i+2}&= dpw \\ \\<br />c_{i+2}&=c_{i}+2dpw -2s_{i}\tag{5}\label{ref5}<br />\end{align}<br /><br />i.e. the castle would end up with less strength points (since \(c_{i+2}\) in \ref{ref5} is smaller than \(c_{i+2}\) in \ref{ref4}).<br /><br />From this analysis we see that the castle strength is smaller on day \(i+2\) if the soldiers kill all defenders every single day instead of leaving some alive and firing a few extra shots at the castle.<br /><br />Therefore the soldiers, if they can, should never leave defenders and the castle alive on the same day. It is possible that \(c_{i+2}=c_{i}+2dpw + x-2s_{i}<0\), i.e. the soldiers finish the castle on day \(i+1\) while leaving \(x\) defenders alive. But they could also have been done with the castle on day \(i+1\) or earlier if they kept killing all defenders (since if \(c_{i}+2dpw + x-2s_{i}<0\) obviously \(c_{i}+2dpw-2s_{i}<0\) ) and they would have the added bonus of not having lost any soldier. So while it is not always completely disadvantageous to leave some defenders alive, it is never advantageous since the soldiers can finish always in the same number of days and with all the soldiers alive by always killing all the defenders.</div><div><br /></div><div>Given this optimal strategy, how many days does it take for the soldiers to win? It is convenient to break this question into two: 1) In which day should the castle be destroyed, i.e. how many days should it take to bring the castle down and 2) How many days <u>after the castle has been destroyed</u> it takes for the soldiers to kill all defenders. It turns out that to answer 1) we must first answer 2).</div><div><br /></div><div><br /></div><div><div><h4 style="text-align: center;">Number of days to kill all defenders (after the castle has been destroyed)</h4></div><div><br /></div><div>Lets suppose the castle is destroyed on day \(q\). Since up to day \(q\) the soldiers have been killing all defenders every day, all the soldiers are still alive. Let \(n\) be the number of initial soldiers (i.e. \(s_{1}=n\)). At the start of day \(q\), \(c_{q}\) of the \(n\) soldiers shoot at the castle destroying it. The remaining \(n-c_{q}\) soldiers fire then at the \(dpw\) defenders leaving<br />\begin{equation}<br />x=dpw-(n-c_{q})=c_{q}+dpw-n<br />\end{equation}<br />of the defenders standing.<br /><br />Afterwards the number of soldiers and defenders in the days after the castle was destroyed \(q+1, q+2, q+3, ...\), changes like this<br /><br />\begin{align}<br />d_{q+1}&=x\\ \\<br />s_{q+1}&=n-x\\ \\<br />d_{q+2}&=d_{q+1}-s_{q+1}=2x-n\\ \\<br />s_{q+2}&=s_{q+1}-d_{q+2}=n-x-2x+n=2n-3x\\ \\<br />d_{q+3}&=d_{q+2}-s_{q+2}=2x-n-2n+3x=5x-3n\\ \\<br />s_{q+3}&=s_{q+2}-d_{q+3}=2n-3x-5x+3n=5n-8x<br />\end{align}<br /><br />More generally we can write<br /><br />\begin{align}<br />d_{q+i+1}&=xFib(2i+1)-nFib(2i)\tag{def}\label{def}\\ \\<br />s_{q+i+1}&=nFib(2i+1)-xFib(2i+2)\tag{sold}\label{sold}<br />\end{align}<br />where \(Fib\) is the Fibonacci sequence of numbers (see for example <a href="https://en.wikipedia.org/wiki/Fibonacci_number" target="_blank">Wikipedia</a>).<br /><br />It turns out that the Fibonacci \(p\) term can be written in closed form as<br /><br />\begin{align}<br />Fib(p) &=\frac{\phi^{p}-(-\phi)^{-p}}{\sqrt{5}}\\ \\<br />\phi &=\frac{1+\sqrt{5}}{2}<br />\end{align}<br /><br />where \(\phi\) is the golden ratio (see for example <a href="http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html" target="_blank">Wolfram Mathworld</a>).<br /><br />It follows that the number of defenders reaches zero, \(d_{q+i+1}=0\) for \(i=k\) such that<br /><br />\begin{align}<br />xFib(2k+1)-nFib(2k)=\frac{x(\phi^{2k+1}-(-\phi)^{-2k-1})-n(\phi^{2k}-(-\phi)^{-2k})}{\sqrt{5}}=0<br />\end{align}<br /><br />Because any negative number raised to an even power like \(2k\) is a positive number, this can be rewritten as<br />\begin{align}<br />(x\phi-n)\phi^{2k}+(x\phi^{-1}+n)\phi^{-2k}&=0<br />\end{align}<br />or<br />\begin{align}<br />\phi^{4k}(n-x\phi)&=(n+x\phi^{-1})<br />\end{align}<br />Taking the logarithm in the base \(\phi\) of both sides then leads to<br />\begin{align}<br />\log_{\phi}\phi^{4k}(n-x\phi)&= 4k+\log_{\phi}(n-x\phi)=\log_{\phi}(n+x\phi^{-1})<br />\end{align}<br />solving for \(k\) gives,<br />\begin{align}<br />k&=\left\lceil\frac{\log_{\phi}\frac{n+x\phi^{-1}}{n-x\phi}}{4}\right\rceil\tag{6}\label{ref6}\\ \\<br />x\equiv x_{q}&=dpw-(n-c_{q})=c_{q}+dpw-n\tag{7}\label{ref7}\\ \\<br />\phi &=\frac{1+\sqrt{5}}{2}<br />\end{align}<br /><br />The ceiling in the above expression takes into account that depending on the values of \(x,n\) there might not be an integer value of \(k\) for which the number of defenders is zero, i.e. the defenders might be zero for a decimal value of \(k\). We should therefore round up to the nearest integer that decimal value, since we are interested in finding out the day \(k\) in which the number of defenders becomes zero or negative, i.e. the soldiers will win on the day \(k\) after \(q\) in which \(d_{q+k}<=s_{q+k}\).<br /><br />Note that to find \(k,x\) we need to know \(c_{q}\) which is the castle strength at the beginning of the day the castle was destroyed. To find it we next turn to finding \(q\), the number of days to destroy the castle.<br /><br /></div></div><div><h4 style="text-align: center;">Number of days to destroy the castle</h4><div><br /></div><div>Following the optimal strategy, the soldiers decrease the castle strength to \(s-n\) on the first day and every day (after the first), \(dpw\) of the soldiers kill \(dpw\) defenders and the remainder \(n-dpw\) soldiers decrease the castle strength by \(n-dpw\). The number of soldiers remains \(n\). That means that at the beginning of the day \(q\) in which the soldiers destroy the castle, the soldiers, castle strength and the remaining defenders are</div>\begin{align}<br />s_{q}&=n\\ \\<br />c_{q}&= s-n-(q-1)(n-dpw)=s-nq+(q-1)dpw\\ \\<br />d_{q}&=x_{q}=dpw-(n-c_{q})=dpw-n+c_{q}=s+qdpw-(q+1)n\tag{8}\label{ref8}<br />\end{align} <br /><div><br />The question for the soldiers is: should they attack the castle on day \(q\) or should they wait?<br />They should wait another day if the number of days to destroy the \(x\) remaining soldiers given by \ref{ref7} starting on day \(q+1\) plus one day is smaller than the number of days to destroy the \(x\) remaining soldiers given by \ref{ref7} starting on day \(q\) or in other words (using \ref{ref6})<br />\begin{align}<br />\frac{\log_{\phi}\frac{n+x_{q+1}\phi^{-1}}{n-x_{q+1}\phi}}{4}+1<\frac{\log_{\phi}\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}}{4}<br />\end{align}<br />We can rewrite this as<br />\begin{align}<br />\log_{\phi}\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}-\log_{\phi}\frac{n+x_{q+1}\phi^{-1}}{n-x_{q+1}\phi}>4<br />\end{align}<br />or combining the subtraction in the \(log\) and then removing the \(log\)<br />\begin{align}<br />\frac{n+x_{q}\phi^{-1}}{n-x_{q}\phi}\frac{n-x_{q+1}\phi}{n+x_{q+1}\phi^{-1}}>\phi^{4}<br />\end{align}cross multiplying leads to<br />\begin{align}<br />n^{2}-nx_{q+1}\phi+nx_{q}\phi^{-1}-x_{q}x_{q+1}>\phi^{4}[n^{2}+nx_{q+1}\phi^{-1}-nx_{q}\phi-x_{q}x_{q+1}]<br />\end{align}<br />rearranging and taking into account that<br />\begin{align}<br />\phi^{4} &=\frac{7+3\sqrt{5}}{2}=3\phi+2\\ \\<br />\end{align}<br />we arrive at<br />\begin{align}<br />(3\phi+1)n^{2}+(3+2\phi^{-1}+\phi)nx_{q+1}-(3\phi^{2}+2\phi+\phi^{-1})nx_{q}\phi-(3\phi+1)x_{q}x_{q+1}<0\tag{9}\label{ref9}<br />\end{align}<br />noticing that<br />\begin{align}<br />\phi^{-1}&=-\frac{1}{2}(1-\sqrt{5})\\ \\<br />\phi^{2}&=\frac{3+\sqrt{5}}{2}=\phi+1\\ \\<br />3+2\phi^{-1}+\phi&= 3\phi+1\\ \\<br />3\phi^{2}+2\phi+\phi^{-1}&=2(3\phi+1)<br />\end{align}<br />we can rewrite \ref{ref9} as<br />\begin{align}<br />(3\phi+1)[n^{2}+nx_{q+1}-2nx_{q}\phi-x_{q}x_{q+1}]<0<br />\end{align}<br />or<br />\begin{align}<br />n^{2}+nx_{q+1}-2nx_{q}\phi-x_{q}x_{q+1}<0\tag{10}\label{ref10}<br />\end{align}<br />we can see from \ref{ref7} or \ref{ref8} that<br />\begin{align}<br />x_{q+1}&=s+(q+1)dpw-(q+2)n=x_{q}+dpw-n\tag{11}\label{ref11}<br />\end{align}<br />so replacing this into \ref{ref10} we get<br />\begin{align}<br />x^{2}_{q}-ndpw+dpwx_{q}>0<br />\end{align}<br />solving this quadratic equation and keeping only the positive solution (since we are assuming \(x_{q}>0\)) we get<br />\begin{align}<br />x_{q}>\frac{-dpw+\sqrt{dpw^{2}+4ndpw}}{2}<br />\end{align}<br />replacing \(x_{q}\) with \ref{ref8} we get<br />\begin{align}<br />2s+2q(dpw-n)-2n>-dpw+\sqrt{dpw^{2}+4ndpw}<br />\end{align}<br />solving for \(q\)<br />\begin{align}<br />q=\left\lceil\frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{2(dpw-n)}\right\rceil\tag{12}\label{ref12}<br />\end{align} <br />This is the minimum number of days it takes for the soldiers to kill the castle.<br />We also point out that the optimal strategy followed by the soldiers of always killing all defenders each day and then attacking the castle is only possible if \(dpw<n\).<br /><br /><h4 style="text-align: center;"><u>2.b The case \(n<s<2n, dpw\geq n, 2n<dpw+s<(\phi+1)n\)</u></h4><div><br /></div>What happens if \(dpw\geq n\)? At the end of the first day, the castle is down to \(c_{2}=s-n\) strength points and sends out \(dpw\) defenders.<br />On the second day, the soldiers have to split their fire on the castle and on the defenders. Otherwise if they just fire at the castle, they will be all killed by the end of the second day. They also have to kill enough defenders that they are not killed by the remaining defenders.<br />Lets write down the changes in the number of soldiers, defenders and castle hits as the days go by:<br />At the beginning of the 2nd day we have<br />\begin{align}<br />s_{2}&=n\\<br />d_{2}&=dpw\\<br />c_{2}&=s-n<br />\end{align}<br />Lets assume that the soldiers leave \(x_{2}\) defenders alive on the second day.<br />At the beginning of the 3rd day then<br />\begin{align}<br />s_{3}&=n-x_{2}\\<br />d_{3}&=dpw+x_{2}\\<br />c_{3}&=c_{2}-[n-(dpw-x_{2})]=s-2n+dpw-x_{2}=(s-2n)+dpw-x_{2}<br />\end{align}<br />Lets assume that the soldiers leave \(x_{3}\) defenders alive on the third day.<br />At the beginning of the 4th day then<br />\begin{align}<br />s_{4}&=n-x_{2}-x_{3}\\<br />d_{4}&=dpw+x_{3}\\<br />c_{4}&=c_{3}-[n-x_{2}-(dpw+x_{2}-x_{3})]=(s-2n)+(dpw-n)+dpw+x_{2}-x_{3}<br />\end{align}<br />Lets assume that the soldiers leave \(x_{4}\) defenders alive on the fourth day.<br />At the beginning of the 5th day then<br />\begin{align}<br />s_{5}&=n-x_{2}-x_{3}-x_{4}\\<br />d_{5}&=dpw+x_{4}\\<br />c_{5}&=c_{4}-[n-x_{2}-x_{3}-(dpw+x_{3}-x_{4})]=(s-2n)+ 2(dpw-n)+dpw + 2x_{2}+x_{3}-x_{4}\tag{13}\label{ref13}<br />\end{align}<br />A necessary condition for the soldiers to win is that on the last day of the battle, lets call it \(q\), the castle strength \(c_{q}=0\) but the number of soldiers \(s_{q}>0\).<br />If we follow the pattern in \ref{ref13} we have on the last day of the battle (\(x_{2}, x_{3},...,x_{q-1}\) is the number of defenders left alive by the soldiers on days 2,3,...,\(q-1\))<br />\begin{align}<br />s_{q}&=n-x_{2}-x_{3}-...-x_{q-1}\\<br />d_{q}&=dpw+x_{q-1}\\<br />c_{q}&=c_{q-1}-[n-x_{2}-x_{3}-...-x_{q-2}-(dpw+x_{q-2}-x_{q-1})]=(s-2n)+ (q-2)(dpw-n)+dpw+(q-3)x_{2}+(q-4)x_{3}+...-x_{q-1}<br />\end{align}<br /><span style="color: red;">This result shows that if \(s\geq 2n, dpw\geq n\), \(c_{q}>0\), i.e. it is impossible for the soldiers to win because the castle strength can never become zero.</span><br /><span style="color: red;">Therefore for the soldiers to have a chance the castle strength must be \(n\leq s<2n\).</span><br /><br />Clearly the best strategy for the soldiers is not to only shoot at the defenders every day (as they should do if \(dpw<n\)). Since \(dpw\geq n\), if the soldiers only fire at the defenders and not at the castle, the castle will keep adding \(dpw\) defenders every round and it will win quickly.<br /><br />The following table shows the values of \(x_{n-1},c_{n},d_{n},s_{n}\) if the castle is destroyed at the end of the 2nd, 3rd, 4th day. We simply set \(c_{3}=0\) above if the castle is destroyed on the second day, or \(c_{4}=0\) above if the castle is destroyed on the third day, etc.<br /><br />Notice that because the castle is destroyed, it doesnt add \(dpw\) to the defenders on the day it is destroyed. <br /><br /><table border="1" style="width: 100%;"><tbody><tr><th>Day castle killed</th><th>\(x_{n-1}\)</th><th>\(s_{n}\)</th><th>\(d_{n}\)</th></tr><tr><td align="center">2 (\(c_{3}=0\))</td><td align="center">\(x_{2}=(s-n)+(dpw-n)\)</td><td align="center">\(s_{3}=n-x_{2}=n-(s-n)-(dpw-n)\)</td><td align="center">\(d_{3}=x_{2}=(s-n)+(dpw-n)\)</td></tr><tr><td align="center">3 (\(c_{4}=0\))</td><td align="center">\(x_{3}=(s-n)+2(dpw-n)+x_{2}\)</td><td align="center">\(s_{4}=n-x_{2}-x_{3}=n-(s-n)-2(dpw-n)\)-2x_{2}</td><td align="center">\(d_{4}=x_{3}=(s-n)+2(dpw-n)+x_{2}\)</td></tr><tr><td align="center">4 (\(c_{5}=0\))</td><td align="center">\(x_{4}=(s-n)+3(dpw-n)+2x_{2}+x_{3}\)</td><td align="center">\(s_{5}=n-x_{2}-x_{3}-x_{4}=n-(s-n)-3(dpw-n)-3x_{2}-2x_{3}\)</td><td align="center">\(d_{5}=x_{4}=(s-n)+3(dpw-n)+2x_{2}+x_{3}\)</td></tr></tbody></table></div></div><br />Since \(s-n>0,dpw-n\geq 0, x_{2}\geq 0, x_{3}\geq 0\) it is obvious from this table that the number of soldiers on the day the castle is destroyed is largest and the number of defenders on that same day is the smallest if the castle is destroyed on the second day (i.e. \(s_{3} > s_{4} > s_{5}, d_{3} < d_{4} < d_{5}\)).<br /><span style="color: red;">That means that the fastest way for the soldiers to win is by destroying the castle on the second day.</span><br /><br />It is also clear from the table that:<br /><br /><ul><li> The higher \(s\) and \(dpw\) the smaller the number of soldiers and the higher the number of defenders on the day the castle is destroyed. This means that there is a narrow range of values of \(s\) and \(dpw\) for which the soldiers can win.</li><li>The number of defenders and soldiers if the castle is destroyed on day 3 is dependent on \(x_{2}\) i.e. how many defenders where left alive by the soldiers on day 2. The higher \(x_{2}\) the higher the number of defenders on day 3 (i.e. the higher \(d_{4}\)) and the lower the number of soldiers (i.e. the lower \(s_{4}\)). Now notice that \(x_{2}\) is the highest when the castle is destroyed on day 2 because that is when most of the soldiers fire is directed towards the castle.</li><li>\(x_{2}\) is the smallest when the soldiers shoot just at the defenders and not at all at the castle.</li><li>The number of defenders if the castle is destroyed on day 4 is dependent on \(x_{2}, x_{3}\) i.e. how many defenders where left alive by the soldiers on day 2 and day 3. The higher \(x_{3}\) the higher the number of defenders on day 4 (i.e. the higher \(d_{5}\)). Now notice that \(x_{3}\) is the highest when the castle is destroyed on day 3 because that is when most of the soldiers fire is directed towards the castle.</li><li>\(x_{3}\) is the smallest when the soldiers shoot just at the defenders and not at all at the castle.</li></ul><br />It is quite tricky to find all possible solutions in which the soldiers win without an exhaustive search. For example if \(dpw=n\), there is always an infinite number of solutions in which the soldiers win: they can kill the castle on day 2, or day 3, or day 4 or day 5 or any day they want. How? For example if they want to destroy the castle on day 5 they kill the \(dpw=n\) defenders that the castle sent on days 2,3,4 and then on day 5 they destroy the castle. The same pattern can be repeated if the soldiers want to destroy the castle on any day.<br /><br />Besides having to destroy the castle by the second day, the soldiers must be able to finish off the defenders. This can be accomplished in \(k\) days after the castle is destroyed with \(k\) given by \ref{ref6}. What is \(x\) in the expression \ref{ref6} for \(k\)? It is the number of defenders left at the end of the second day. We know that at the end of the first day the castle is down to \(s-n\) strength points and at the end of the second day \(s-n\) of the soldiers finish it of. The remaining \(n-(s-n)=2n-s\) then attack the \(dpw\) defenders leaving \(x=dpw-(2n-s)=dpw+s-2n\) defenders.<br />This agrees with the expression for \(x\) in \ref{ref7}.<br /><br />From day 3 onward the soldiers and the defenders battle it out and their numbers change according with the logic above that led to \ref{ref7}. In particular the number of defenders and soldiers after \(2+i+1\) days is given by \ref{def} and \ref{sold}. The game progresses until the number of defenders is negative or zero while the number of soldiers is positive.<br /><br />We already know that since \(dpw\geq n, n<s<2n\), that \(s+dpw>2n\) so obviously \(x=dpw+s-2n>0\). But \(x\) can not be arbitrarily large otherwise the defenders will overwhelm the soldiers and win the game. In other words we want the number of soldiers to be positive for all values of \(i\) in \ref{sold}. Since the soldiers number will be the smallest the larger the value of \(i\) this means we want the smallest possible value of the soldiers to still be positive. This happens when we take the limit \(i\rightarrow \infty\) i.e.<br />\begin{align}<br />n-x\lim_{i\to\infty}\frac{Fib(2i+2)}{Fib(2i+1)}>0<br />\end{align}<br />since \(\lim_{i \to \infty}Fib(2i+2)/Fib(2i+1)=\phi\) (see for example <a href="https://en.wikipedia.org/wiki/Fibonacci_number" target="_blank">Wikipedia</a>) this is the same as<br />\begin{align}<br />x\phi<n<br />\end{align}<br />or after replacing \(x=dpw+s-2n\)<br />\begin{align}<br />dpw+s<(2+\phi^{-1})n=(\phi+1)n<br />\end{align}<br />In other words the soldiers can win if \(dpw\geq n, n<s<2n\) only if \(2n<dpw+s<(\phi+1)n\) .<br /><br /><h3 style="text-align: center;">Recaping the ways the soldiers can win</h3>It is time to summarize all the cases described in detail above.<br /><table border="1" style="width: 100%;"> <tbody><tr><th>Case</th><th>Condition</th><th>Soldiers minimum moves to win</th><th>Soldiers strategy</th></tr><tr><td align="center">1 </td><td align="center">\(s\leq n \)</td> <td align="center">1</td><td align="center">All soldiers fire their cannons at the castle.</td></tr><tr><td align="center">2a</td><td align="center">\(s> n\)<br />\( dpw < n\) </td><td align="center">\(q+max(0,k) days\)<br />\begin{align}<br />q&=\left\lceil \frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{{2(dpw-n)}}\right\rceil\\ \\ <br />k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+qdpw-(q+1)n)\phi^{-1}}{n-(s+qdpw-(q+1)n)\phi}}{4}\right\rceil\tag{14}\label{ref14}\\ \\<br />\end{align} </td> <td align="center">Kill \(dpw\) defenders for the first \(q\) days until the castle strength vanishes.<br />Afterwards just shoot at the defenders left and be done in \(k\) days. </td></tr><tr><td align="center">2b</td><td align="center">\(n < s < 2n\)<br /><br />\( dpw \geq n\)<br /><br />\( 2n < dpw+s<(\phi+1)n\) </td><td align="center">\( 2 + max(0,k) days\) <br />\begin{align}<br />k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+dpw-2n)\phi^{-1}}{n-(s+dpw-2n)\phi}}{4}\right\rceil\tag{15}\label{ref15}\\ \\<br />\end{align}</td><td align="center">Destroy the castle in two days and battle the defenders in the next \(k\) days.</td></tr><tr><td align="center">2c </td><td align="Center">\(n < s < 2n\)<br /><br />\( dpw \geq n\)<br /><br />\( 2n < dpw+s\geq(\phi+1)n\)</td><td align="center">Can not win</td><td align="center">No winning strategy</td></tr><tr><td align="center">2d</td><td align="center">\( s > 2n\)<br /><br />\(dpw\geq n\) </td><td align="center">Can not win</td><td align="center">No winning strategy</td></tr></tbody></table><br /><br /><div><h4 style="text-align: center;">Minimum number of days for the castle to win</h4><div>The general case is quite complicated and we will just describe a few cases.<br /><br /></div><div>If \(dpw+s\leq 2n, s>n,dpw<n\) the castle can not win. After the first day, \(dpw+castleStrength\leq n\) and since there are \(n\) soldiers and they attack first, the soldiers win on the second day.</div><div><br /></div><div>If \(dpw+s> 2n, s>n, dpw<n\) the castle sometimes will not be able to win and when it can win it will need more than 2 days at a minimum to win because the number of defenders per day is not enough to kill the soldiers in one day (the maximum value of \(dpw=n-1\)).</div><div><br /></div><div>At the end of the first day \(dpw+castleStrength>n, castleStrength=s-n\).</div><div><br /></div><div>If \(dpw=n-1\) which is the maximum value of defenders to obey \(dpw<n\), the castle will take at least 3 days to win. It can win on the third day only if \(s>2n\) [the soldiers attack the castle only on the first two days leaving it with \(1\) strength point and leaving \(1\) soldier only standing. If that soldier then destroys the castle, it will be killed by the \(2n-2\) defenders on the third day. </div><div><br /></div><div>If \(s=n+2, dpw=n-1, n>1\), the castle can not win. The soldiers on the first day reduce the castle strength to 2. On the second day the soldiers have two options: 1) they destroy the castle and kill \(n-2\) defenders leaving only one. That one kills a soldier and is then killed by the remaining soldiers on the third day. 2) If on the contrary the soldiers killed all defenders and 1 strength point, the third day would start with \(n-1\) defenders and the castle with \(1\) strength point, so the \(n\) soldiers would still win on the third day. If \(dpw<n-1\) the same arguments apply but to even less defenders. Besides \(s+dpw\leq 2n\). It follows that if \(s=n+2\) the castle can never win.</div><div><br /></div><div>If \(s=n+3, dpw=n-1, n>2\), the castle can win under certain circumstances. </div><div>The soldiers on the first day reduce the castle strength to 3. They then have 3 options: 1) On the second day they destroy the castle and kill all but 2 defenders. These kill 2 soldiers leaving at least one. The third day starts with \(2\) defenders and at least one soldier. <b>The castle wins on the third day only if there is one soldier (i.e. if \(n=3\)).</b> If there are two or more soldiers, the castle can not win.</div><div>2) On the second day they leave the castle with 1 point and kill all but 1 defender which then kills 1 soldier. The third day starts with \(n-1\) soldiers, \(n\) defenders and 1 castle strength point.<b> The castle can now always win if the soldiers always hit the defenders but not the castle. </b>That way the castle keeps sending \(n-1\) defenders, while the soldiers decrease steadily. Following this approach the castle can only win on the third day if \(n=3\) [by destroying the castle and killing one defender, then the remaining two defenders kill the 2 soldiers] or on the fourth day if \(n=4\), etc.</div><div>3) On the second day they leave the castle with 2 points and kill all defenders. The third day starts with \(n-1\) defenders, \(n\) soldiers and 2 castle strength points. This is similar to what happens on the second day of the case \(s=n+2,dpw=n-1,n>1\) so we know there is no solution where the castle can win.</div><div></div><div>If \(s=n+3, dpw<n-1\) we have \(s+dpw\leq 2n+1\) which is the same case as \(s=n+2, dpw<n\) above and has no solutions.<br /><br /></div></div><h4 style="text-align: center;">2.c The case \(n\geq 2n, dpw\geq n, dpw+s\geq(\phi+1)n\)</h4><div>Left as an exercise.</div><h4 style="text-align: center;">2.d The case \(s\geq 2n, dpw\geq n\)</h4><span style="font-weight: normal;">If \(s\geq 2n, dpw\geq n\), the castle can always win in 2 days minimum if on both days the soldiers attack only the castle and never attack the defenders.</span><span style="font-weight: normal;"> The soldiers can not win but can delay the castle victory by attacking the castle and the defenders in the same wave.</span><br /><br />If \(dpw=n\) the soldiers can tie the game by always killing all defenders starting on day 2.<br /><br /> Lets recap all possibilities.<br /><br /><h4 style="text-align: center;">Recap </h4><div><br /><table border="1" style="width: 100%;"> <tbody><tr><th>Case</th><th>Condition</th><th>Soldiers minimum moves win</th><th>Castle minimum moves win</th></tr><tr> <td align="center">1</td> <td align="center">\(s\leq n\)</td> <td align="center">Win in one day</td> <td align="center">Can not win</td> </tr><tr><td align="center">2a</td><td align="center">\(s> n\)<br />\( dpw < n\) </td><td align="center">\(q+max(0,k)\) days<br />\begin{align}<br />q&=\left\lceil \frac{\sqrt{dpw^{2}+4ndpw}-dpw+2n-2s}{2(dpw-n)}\right\rceil\\ \\<br />k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+qdpw-(q+1)n)\phi^{-1}}{n-(s+qdpw-(q+1)n)\phi}}{4}\right\rceil\\ \\<br />\end{align} </td> <td align="center">Win in two days if \(dpw+s > 3n\)<br /><br />Can not win if \(dpw+s\leq 3n\) </td> </tr><tr><td align="center">2b</td><td align="center">\(n < s < 2n\)<br /><br />\( dpw \geq n\)<br /><br />\( 2n < dpw+s<(\phi+1)n\) </td><td align="center">\( 2 + max(0,k) days\) <br />\begin{align}<br />k&=\left\lceil\frac{\log_{\phi}\frac{n+(s+dpw-2n)\phi^{-1}}{n-(s+dpw-2n)\phi}}{4}\right\rceil\\ \\<br />\end{align}</td><td align="center">Left as an exercise</td></tr><tr><td align="center">2c </td><td align="Center">\(n < s < 2n\)<br /><br />\( dpw \geq n\)<br /><br />\( 2n < dpw+s\geq(\phi+1)n\)</td><td align="center">Can not win</td><td align="center">Left as an exercise</td></tr><tr><td align="center">2d</td><td align="center">\( s > 2n\)<br /><br />\(dpw\geq n\) </td><td align="center">Can not win</td><td align="center">Win in 2 days (soldiers attack the castle only)</td></tr></tbody></table><br /></div><br /><br /><ul><li>If \(s\geq 2n, dpw\geq n\), the castle can always win in 2 days minimum (if the soldiers attack the castle and not the defenders). The soldiers can not win but can delay the castle victory by attacking the castle and the defenders in the same wave.</li></ul><div><br /></div><ul><li>If \(n<s<2n, dpw\geq n, (\phi+1)n<dpw+s\), the soldiers can not win but the castle might take more than 2 days to win at a minimum. Consider the following example</li></ul><br /><div><span style="font-weight: bold;">\(n=3819, s=5000, dpw=5000\)</span></div>The soldiers can not win. The castle can win in 3 rounds (but not in 2):<br />At the end of the first day, the castle is down to 1181. If the soldiers on day 2 instead of destroying the castle kill 3819 defenders, the remaining 1181 defenders would fire back and leave 2638 soldiers at the start of day 3 with 6181 defenders. If all the soldiers then attacked the castle on day 3, the soldiers would be all killed and would lose on day 3. <br /><br />On the other hand if we start with one extra soldier<br /><span style="font-weight: bold;">\(n=3820, s=5000, dpw=5000\)</span><br />This falls into the second case above, since \(dpw+s=10000<(\phi+1)3820\). The soldiers can win in<br />\(2+k\) days where<br />\begin{align}<br />k&=\left\lceil\frac{\log_{\phi}\frac{3820+(10000-2\times 3820)\phi^{-1}}{3820-(10000-2\times 3820)\phi}}{4}\right\rceil=\left\lceil\frac{\log_{\phi}\frac{3820+2360\phi^{-1}}{3820-2360\phi}}{4}\right\rceil=5<br />\end{align} <br /><div>I.e the soldiers can win in 7 waves:<br />At the end of the first day the castle strength is down to 1180, and there are 5000 defenders.<br />At the end of the second day, the castle is gone and 5000- 2640=2360 defenders remain. They then kill that many soldiers leaving 1460 soldiers.<br />At the end of the third day, there are 2360-1460=900 defenders and 1460-900=560 soldiers.<br />At the end of the fourth day, there are 900-560=340 defenders and 560-340=220 soldiers.<br />At the end of the fifth day, there are 340-220=120 defenders and 220-120=100 soldiers.<br />At the end of the sixth day there are 120-100=20 defenders and 100-20=80 soldiers.<br />At the end of the seventh day the soldiers win.<br /><br />The castle can still win in 3 waves minimum if the soldiers attack the castle on the first day, attack the defenders on the second and attack the castle on the third day.<br /><br />Notice that if the number of soldiers were \(n=3819\) and the soldiers followed the same strategy, we would have<br />End of first day: castle strength=1181 and 5000 defenders.<br />End of second day: castle strength=0, 5000-2638=2362 defenders, 3819-2362=1457 soldiers.<br />End of third day: 2362-1457=905 defenders and 1457-905=552 soldiers<br />End of fourth day: 905-552=353 defenders and 552-353=199 soldiers<br />End of fifth day: 353-199=154 defenders and 199-154=45 soldiers<br />End of sixth day: 154-45=109 defenders and all soldiers are dead.<br />The castle wins in six rounds. The soldiers can not win. What a difference a single soldier makes!<br /><h2><div style="text-align: center;"><span style="font-weight: normal;"><br /></span></div><span style="font-weight: normal;"><div style="text-align: center;">Code Implementation</div></span></h2></div><h4><span style="font-weight: normal;">Using the mathematical logic above it is straightforward to write code that finds the minimum number of days for the soldiers to win, as well as the path/strategy the soldiers should follow to accomplish that feat.</span></h4><div><span style="font-weight: normal;">The tests in the tests.py class are labeled according with whether they fall under cases 2a, 2b, 2c, 2d in the classification given in the tables above.</span><br /><span style="font-weight: normal;">The code in CastleDefenseIIIMath.py uses the formulae we derived above to quickly find the minimum number of days solution for the soldiers to win. </span><br /><span style="font-weight: normal;"><br /></span><span style="font-weight: normal;">There are now 54 tests as opposed to 27 in our previous two posts.</span><br /><span style="font-weight: normal;">If you want to run just the previous 27 tests, make all_tests=old_tests in tests.py. This will run very quickly.</span><br />Some of the newer tests (like tests 37 and 46) take some time to execute but with some minutes of patience you will get the solution. Many of those newer tests would be impossible to run in a timely manner with our previous exhaustive search code.</div><br /><iframe allowfullscreen="" frameborder="0" height="600" marginheight="0" marginwidth="0" src="https://trinket.io/embed/python/5146cd2c52" width="100%"></iframe></div></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-58992638178232287622015-08-15T07:59:00.000-07:002015-10-12T08:01:42.333-07:00Castle Defense II - Exact Recursive Solution<style>.post-container { margin: 20px 20px 0 0; border: 2px solid #333; overflow: auto } .post-thumb { float: right } .post-thumb a { display: block } .post-content { margin-left: 2px } </style> <br /><div class="post-container"><div class="post-thumb"></div><div class="post-content"><a href="http://3.bp.blogspot.com/-yxMX3qImVjw/VfJRBxX_2PI/AAAAAAAAAKM/oEiBfJCUOU0/s1600/P1040122c.JPG" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="600" src="http://3.bp.blogspot.com/-yxMX3qImVjw/VfJRBxX_2PI/AAAAAAAAAKM/oEiBfJCUOU0/s1600/P1040122c.JPG" width="640" /></a><a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">In our previous post </a> we looked at two approaches to solve the following problem:<br /><i>The <b>gameSoldiers </b>soldiers approached silently the remarkable place.</i><br /><i>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. </i><br /><i>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.</i><br /><i>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 <b>castleHits</b> hits (one canon shot, one hit).</i><br /><i>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:—</i><br /><i> </i><i>“Monster, give me my child!”</i><br /><i> </i><i>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.</i><br /><i> </i><i>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.</i><br /><i> </i><i>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.</i><br /><i>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 <b>\(castleHits=castleHits-gameSoldiers\)</b>.</i><br /><i>They then waited for new canon balls to arr</i><i>ive, </i><i>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<b> defendersPerWave</b> 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.</i><br /><br /><i>In the ensuing days the castle and the soldiers battled it out following these rules:</i><br /><ol><li><i>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.</i></li><li><i>Then each of the defenders would shoot one soldier (and only one) killing him. </i></li><li><i>If the castle still had strength points (i.e. \(castleHits>0\)) it would send a new batch of <b>defendersPerWave</b> defenders at this point. The total number of defenders in the next round would be then \(defenders=defenders + defendersPerWave\).</i></li><li><i>Repeat 1 through 3 in each new day.</i></li><li><i>If all soldiers were killed by the defenders, the castle would win.</i></li><li><i>If there were zero defenders left after the soldiers shot and the castle strength was also zero, the soldiers would win. </i></li></ol><i>The scientist had given not just the minimum number of rounds the soldiers needed to win the battle (or if not possible the minimum number of rounds for the castle to win) but also the number of soldiers, defenders and castle hit points at the end/beginning of each round for the minimum number of rounds solution. </i><br /><i>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 <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a>) 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). </i><br /><i>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 <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a>, 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.</i><br /><br />As we and the commander noticed, none of the two approaches in the <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a> solved the problem correctly in all cases.<br />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.<br />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 <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a>, 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 <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a> 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).<br />In the following discussion we will, for every test from our <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a>, 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).<br /><br /><h3 style="text-align: center;"><b>A RECURSIVE SOLUTION</b></h3><div>A simple method to search through every possible path is given by the following code fragment<br /><pre class="python" name="code"><b><br /><br /> # if castleHits =0, soldiers play against defenders only<br /> def soldiersVsDefenders(self,soldiers,defenders):<br /> # soldiers win or castle/defenders win<br /> if defenders <=0 or soldiers <= 0: <br /> return<br /> <br /> # do another round of fighting<br /> # 1. Soldiers kill as many defenders <br /> defendersLeft = defenders - soldiers<br /> # 2. defendersLeft kill as many soldiers<br /> soldiersLeft = soldiers - defendersLeft <br /> <br /> self.soldiersVsDefenders(soldiersLeft,defendersLeft, 1+wave)<br /><br /> <br /> def oneWave(self,soldiers,defenders,castleHits,wave =0):<br /> # castle/defenders wins<br /> if soldiers <= 0: <br /> return<br /><br /> # castle is dead, let soldiers play against defenders<br /> if castleHits <= 0: <br /> defendersLeft = defenders - self.dpw<br /> self.soldiersVsDefenders(soldiers,defendersLeft,path, wave)<br /> return<br /> <br /> # try every possibility:<br /> # 1) all soldiers hit the castle, none hits the defenders<br /> # 2) all but one soldier hits the castle, the others hit the defenders<br /> # 3) all but two soldiers hit the castle, the others hit the defenders<br /> # ...<br /> # soldiers) no soldier hits the castle, all others hit the <br /> # defenders<br /> for i in range(0,soldiers+1):<br /> if i > defenders: <br /> break<br /> soldiersLeft = soldiers - (defenders -i)<br /> defendersLeft = defenders - i + self.dpw<br /> castleHitsLeft = castleHits - (soldiers -i)<br /> <br /> self.oneWave(soldiersLeft,defendersLeft,castleHitsLeft,1+ wave)<br /><br /> # start game<br /> def searchMinimumRecursive(self,soldiers,castleHits,defendersPerWave):<br /> self.dpw = defendersPerWave<br /> self.oneWave(soldiers,0,castleHits)<br /></b> <br /></pre>The oneWave method simulates... one round/wave of the game. It is first called by the searchMinimumRecursive with the initial values.<br />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).<br />The method then tries every possible path for those initial values recursively. This is achieved through the for loop<br /><pre class="python" name="code"><b> <br /> for i in range(0,soldiers+1):<br /></b></pre><br />Lets walk through the loop:<br /><ul><li>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.</li><li>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.</li><li>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.</li><li>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\). </li></ul>If at any point in the loop \(i>defenders\) we quit the loop (otherwise the formulas for soldiersLeft, defendersLeft,castleHitsLeft would be wrong: since \(defenders-i\) would be <0, the next wave would start with more soldiers than the previous wave which is obviously not correct).<br />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.<br />If at any point in the recursion, <b>castleHits</b> becomes zero or smaller, it means the castle can no longer send <b>defenderPerWaves</b> defenders at the end of each round.<br />In this case we subtract the <b>defendersPerWave</b> 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.<br />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 <b>defendersPerWave</b> 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).<br />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.<br />If at any point soldiers or defenders become zero or lower then the castle or the soldiers respectively win i.e we stop recursing.<br />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.<br />To visualize this process lets draw all possible paths for a few of the test cases from our <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a>.<br />Figure 2 shows all the paths tried by the recursive algorithm for test 0, which starts with gameSoldiers=10, castleHits=11, defendersPerWave=15. <br /><br /><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody><tr><td style="text-align: center;"><a href="http://3.bp.blogspot.com/-uUxuoGByVTg/VdkwIY9HwEI/AAAAAAAAAJA/1QSjt3eKjFA/s1600/red00001.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="290" src="http://3.bp.blogspot.com/-uUxuoGByVTg/VdkwIY9HwEI/AAAAAAAAAJA/1QSjt3eKjFA/s1900/red00001.jpg" width="1150" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;"><b>Figure 2 test0 solutions as found by the recursive method</b></td></tr></tbody></table><br />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).<br />The blue solution (4 waves) is <br /><h3><span style="color: blue;">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</span></h3>Notice how we didn't include S=4,D=21,CH=0 in the path because it corresponds to the jump from the <b>oneWave</b> method to the <b>soldiersVsDefenders</b> method as discussed above. The method <b>oneWave</b> 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) are <br /><h3><span style="color: red;">S=10, D=0, CH=11→ S=10, D=15,CH=1 → S=5,D=20, CH= 1 → S=0, D=16, CH=0 </span></h3>and <br /><h3><span style="color: red;">S=10, D=0, CH=11→ S=10, D=15,CH=1 → S=5,D=20, CH= 1 → S=0, D=15, CH=1 </span></h3>A few words about these solutions and figure 2:<br /><ul><li>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); </li><li>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. </li><li>The transitions labeled soldiersVsDefenders indicate that the algorithm having reached zero castle hits calls soldiersVsDefenders from then on.</li><li>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. </li></ul>Lets look at test1 in figure 3, which does not have any solution leading to a win for the soldiers. Accordingly all solutions are marked in red.<br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="http://3.bp.blogspot.com/-fUYYKSTIIak/Vdlb1jCSgGI/AAAAAAAAAJQ/J0l0o3X7xsA/s1600/castleIItest_1reduced.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="266" src="http://3.bp.blogspot.com/-fUYYKSTIIak/Vdlb1jCSgGI/AAAAAAAAAJQ/J0l0o3X7xsA/s1600/castleIItest_1reduced.jpg" width="1140" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;"><b>Figure 3- test1 solutions as found by the recursive method</b></td><td class="tr-caption" style="text-align: center;"><br /></td></tr></tbody></table> 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. <br />Two of the paths achieve the win in 2 waves and the other 5 take 3 waves.<br /><br />Test 2, starts with 2 soldiers and a castle with strength 10 which can send 1 defender per wave.<br />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 <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a>.<br /><br />Test 3, starts with 11 soldiers and a castle with strength 12 which can send 9 defenders per wave.<br />This case only admits a single solution: The soldiers win in two rounds.<br /><br />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.<br /><br />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 <a href="http://pythonshort.blogspot.com/2015/07/castle-defense-i-approximate-methods.html" target="_blank">previous post</a>, 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).<br /><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody><tr><td style="text-align: center;"><a href="http://3.bp.blogspot.com/-u20oxbcIUCo/VdomG0Z0VbI/AAAAAAAAAJw/3wWPN2zkZvw/s1600/castleIItest_10.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="266" src="http://3.bp.blogspot.com/-u20oxbcIUCo/VdomG0Z0VbI/AAAAAAAAAJw/3wWPN2zkZvw/s1600/castleIItest_10.jpg" width="1140" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;"><b>Figure 4- test10 solutions as found by the recursive method</b></td><td class="tr-caption" style="text-align: center;"><br /></td></tr></tbody></table><br /><br /><h3 style="text-align: center;"><b>RECURSIVE CODE WALKTHROUGH</b></h3>Without further ado, lets look at the complete code that computes all the wins by the castle and the soldiers.<br /><br /><iframe allowfullscreen="" frameborder="0" height="600" marginheight="0" marginwidth="0" src="https://trinket.io/embed/python/2954d2cdcd" width="100%"></iframe></div>An important caveat:<span style="color: red;"> If you run this code as is be prepared to wait 5-7 minutes. </span>That is how long it will take for all the 27 tests to run. <br />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.<br /><br />The file<b> tests.py</b> contains the 27 tests. It also has the <b>runTests</b> 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.<br /><br />The file <b>CastleDefenseIIRecursive.py</b> contains the main algorithm (in the methods <b>searchMinimumRecursive</b> which calls the method <b>oneWave</b> which will call the method <b>soldiersVsDefenders</b> in the case where castleHits reach zero but there are soldiers and defenders to battle it out).<br /><br />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 <b>tests.py</b> 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 <b>self.trackCastleWins</b> in <b>CastleDefenseIIRecursive</b>. 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.<br /><br />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).<br />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.<br /><br />The method<b> printSolutions</b> (which is called by <b>searchMinimumRecursive</b> 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).<br /><br /><h3 style="text-align: center;">PATH COMPUTATION</h3><div>The complicated part of the code in <b>CastleDefenseIIRecursive.py</b> 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.</div><div>In the method <b>searchMinimumRecursive</b>, the path is initialized with the initial state and it is passed as an argument to the call <b>self.oneWave</b>. </div><div>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.</div><div>With each recursive call the wave value goes up by one and another step is added to the path list.</div><div><br /></div><div>If, during a recursive call, the number of soldiers becomes negative or zero (i.e. the soldiers lose), we </div><div>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. </div><div><br /></div><div>All of this is easier to understand by looking for example at figure 3. Consider the path <span style="color: red;">(S=3,D=0,CH=10)→ (S=3,D=4,CH=7)→ (S=-1,D=8,CH=4)</span>. 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 <span style="color: red;">(S=3,D=0,CH=10)→ (S=3,D=4,CH=7)→ (S=0,D=7,CH=5), </span>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 <span style="color: red;">(S=3,D=0,CH=10)→ (S=3,D=4,CH=7) → (S=0,D=4,CH=4) </span><span style="color: red;"> </span><span style="color: red;">→</span><span style="color: red;"> (S=0,D=7,CH=5)</span>, for the second path which is obviously wrong.<br /><br />The other possibility during a recursive call is that the number of castleHits becomes 0 or negative.<br />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.<br />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.<br /><br />Again to understand this logic it is easier to look at an example. Consider the path <span style="color: blue;">(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)</span> in figure 2<span style="color: blue;">. </span>Since we are returning all the way up to the step (S=4,D=21,CH=0) (which is where<b> self.oneWave</b> called <b>self.soldiersVsDefenders</b>) 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).<br /><br />The final piece is in the method <b>self.oneWave</b> loop. After we return back to<b> self.oneWave</b> (from another <b>self.oneWave</b> call or from <b>self.soldiersVsDefenders</b>) 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. <br /><br />To understand this, consider the last path in figure 3, <span style="color: red;">(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)</span>. 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. </div><h3 style="text-align: center;"><b>OUTPUT</b></h3>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.<br />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.<br />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.<br /><br /><pre class="jqconsole jqconsole-blurred" style="background: none rgb(249, 249, 249); border: none; box-sizing: border-box; color: #222222; font-size: 1.2em; line-height: 1.2em; min-height: 100%; padding: 10px; position: relative; white-space: pre-wrap;"><span style="box-sizing: border-box;">Executing test 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">soldiers win wave: number of solutions with that wave {9: 2}</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">castle win wave : number of solutions with that wave {3: 2, 4: 2, 5: 2, 6: 2, 7: 2, 8: 2}</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">number of soldier wins: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">number of castle wins: 12</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">***************</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Recursive Solution</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">***************</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Starting numbers (Begin of Wave 1)</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">defenders per wave =1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">----------------</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 10</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 8</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 3</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 6</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 5</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 5</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 6</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 3</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 8</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 9</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Soldiers win in 9 rounds</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Starting numbers (Begin of Wave 1)</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">defenders per wave =1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">----------------</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 10</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 8</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 3</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 6</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 5</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 5</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 6</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 3</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 8</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 9</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Soldiers win in 9 rounds</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">=================================</span></pre><br />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<b> self.waveStats</b> has all solutions we could easily modify the<b> runTests</b> method to also print those castle wins.<br />If the soldiers can not win, then the code will output the minimum number of castle wins solutions like in test 7 below<br /><pre class="jqconsole jqconsole-blurred" style="background: none rgb(249, 249, 249); border: none; box-sizing: border-box; color: #222222; font-size: 1.2em; line-height: 1.2em; min-height: 100%; padding: 10px; position: relative; white-space: pre-wrap;"><span style="box-sizing: border-box;">========================================</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Executing test 7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">soldiers win wave: number of solutions with that wave {}</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">castle win wave : number of solutions with that wave {2: 2, 3: 2}</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">number of soldier wins: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">number of castle wins: 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">***************</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Recursive Solution</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">***************</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Starting numbers (Begin of Wave 1)</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">defenders per wave =7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">----------------</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 6</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 5</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Castle wins in 2 rounds</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Starting numbers (Begin of Wave 1)</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">defenders per wave =7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">----------------</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 6</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 7</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">End of Wave 2</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Soldiers: 0</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Number of Defenders: 4</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Total castle hits left: 1</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> </span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Castle wins in 2 rounds</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">========================================</span></pre><br /><h3 style="text-align: center;">SUMMARY</h3><div>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<br /><br /></div><br /><table border="1" style="width: 100%;"> <tbody><tr> <th>Test</th> <th>Initial Soldiers/CastleHits/Defenders per wave</th> <th>Wins by the Soldiers (Wave/number of wins)</th> <th>Wins by the Castle (Wave/number of wins)</th> </tr><tr> <td align="center">0</td> <td align="center">10/11/15</td> <td align="center"><b>1</b> (wave 4/1 win)</td> <td align="center"><b>2 </b>(wave 3/2 wins)</td> </tr><tr> <td align="center">1</td> <td align="center">3/10/4</td> <td align="center"><span style="color: red;">None</span></td> <td align="center"><b>7</b> (wave 2/2 wins, wave 3/5 wins)</td> </tr><tr> <td align="center">2</td> <td align="center">2/10/1</td> <td align="center"><b>2</b> (wave 9/2 wins)</td> <td align="center"><b>12</b> (wave 3/2 wins, wave 4/2 wins, wave 5/2 wins, wave 6/2 wins, wave 7/2 wins, wave 8/2 wins)</td> </tr><tr> <td align="center">3</td> <td align="center">11/12/9</td> <td align="center"><b>1</b> (wave 2/1 win)</td> <td align="center"><span style="color: red;">None</span></td> </tr><tr> <td align="center">4</td> <td align="center">12/32/5</td> <td align="center"><b>136</b> (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) </td> <td align="center"><b>797</b> (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)</td> </tr><tr> <td align="center">5</td> <td align="center">12/44/6</td> <td align="center"><b>2743</b> (wave 7/15 wins, wave 8/66 wins, ..., wave 27/1 win )</td> <td align="center"><b>54157</b> (wave 3/16 wins, wave 4/123 wins, ..., wave 26/2 wins)-<b><span style="color: lime;">more than 20 minutes in chrome to get these</span></b></td> </tr><tr> <td align="center">6</td> <td align="center">7/10/8</td> <td align="center"><b>1</b> (wave 4/1 win)</td> <td align="center"><b>15</b> (wave 3/6 wins, wave 4/9 wins)</td> </tr><tr> <td align="center">7</td> <td align="center">4/6/7</td> <td align="center"><span style="color: red;">None</span></td> <td align="center"><b>4</b> (wave 2/2 wins, wave 3/2 wins)</td> </tr><tr> <td align="center">8</td> <td align="center">8/10/6</td> <td align="center"><b>1</b> (wave 2/1 win)</td> <td align="center"><span style="color: red;">None</span></td> </tr><tr> <td align="center">9</td> <td align="center">4/5/5</td> <td align="center"><b>1</b> (wave 3/1 win)</td> <td align="center"><b>2</b> (wave 3/2 wins)</td> </tr><tr> <td align="center">10</td> <td align="center">5/8/5</td> <td align="center"><b>1</b> (wave 4/1 win)</td> <td align="center"><b>8</b> (wave 3/3 wins, wave 4/5 wins)</td> </tr><tr> <td align="center">11</td> <td align="center">10/50/9</td> <td align="center"><b>14</b> (wave 37/2 wins, wave 38/1 win, wave 39/3 wins, wave 40/3 wins, wave 41/4 wins, wave 42/1 win)</td> <td align="center"><b>4561</b> (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 )</td> </tr><tr> <td align="center">12</td> <td align="center">19/50/15</td> <td align="center"><b>4408</b> (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)</td> <td align="center"><b>208689</b> (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)-<b><span style="color: lime;">more than 5 hours in chrome to get these</span></b></td> </tr><tr> <td align="center">13</td> <td align="center">10/50/10</td> <td align="center"><span style="color: red;">None</span></td> <td align="center"><b>97</b> (wave 2/1 win, wave 3/42 wins, wave 4/49 wins, wave 5/5 wins)</td> </tr><tr> <td align="center">14</td> <td align="center">8/9/18</td> <td align="center"><span style="color: red;">None</span></td> <td align="center"><b>2</b> (wave 2/2 wins)</td> </tr><tr> <td align="center">15</td> <td align="center">9/11/12</td> <td align="center"><b>1</b> (wave 4/1 win)</td> <td align="center"><b>5</b> (wave 3/5 wins)</td> </tr><tr> <td align="center">16</td> <td align="center">5/37/5</td> <td align="center"><span style="color: red;">None</span></td> <td align="center"><b>18</b> (wave 2/1 win, wave 3/12 wins, wave 4/5 wins)</td> </tr><tr> <td align="center">17</td> <td align="center">9/33/8</td> <td align="center"><b>12</b> (wave 22/2 wins, wave 23/2 wins, wave 24/2 wins, wave 25/4 wins, wave 26/2 wins)</td> <td align="center"><b>1825</b> (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)</td> </tr><tr> <td align="center">18</td> <td align="center">8/21/7</td> <td align="center"><b>9</b> (wave 11/1 win, wave 12/1 win, wave 13/3 wins, wave 14/3 wins, wave 15/1 win)</td> <td align="center"><b>558</b> (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)</td> </tr><tr> <td align="center">19</td> <td align="center">12/13/50</td> <td align="center"><span style="color: red;">None</span></td> <td align="center"><b>2</b> (wave 2/2 wins)</td> </tr><tr> <td align="center">20</td> <td align="center">7/31/5</td> <td align="center"><b>65</b> (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)</td> <td align="center"><b>3228</b> (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)</td> </tr><tr> <td align="center">21</td> <td align="center">19/50/14</td> <td align="center"><b>5457</b> (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)</td> <td align="center"><b>181537</b> (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)-<b><span style="color: lime;">more than 3 hours in chrome to get these</span></b></td> </tr><tr> <td align="center">22</td> <td align="center">20/50/18</td> <td align="center"><b>678</b> (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)</td> <td align="center"><b>88037</b> (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)-<b><span style="color: lime;">more than 1 hour and a half in chrome to get these</span></b></td> </tr><tr> <td align="center">23</td> <td align="center">3/30/1</td> <td align="center"><b>26</b> (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)</td> <td align="center"><b>300</b> (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)</td> </tr><tr> <td align="center">24</td> <td align="center">2/50/1</td> <td align="center"><b>2</b> (wave 49/2 wins)</td> <td align="center"><b>92</b> (wave 3 through wave 48 with 2 wins for each wave)</td> </tr><tr> <td align="center">25</td> <td align="center">9/43/7</td><td align="center"><b>139</b> (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)</td> <td align="center"><b>14706</b> (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)</td> </tr><tr> <td align="center">26</td> <td align="center">10/43/8</td> <td align="center"><b>177</b> (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</td> <td align="center"><b>18165 </b>(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) </td> </tr></tbody></table><div><br />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.<br />Other interesting facts:<br /><br />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.<br /><br />There are nearly always more solutions where the castle wins than solutions where the soldiers win.</div></div></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-14532345527094333582015-07-20T19:32:00.000-07:002015-08-22T08:29:18.094-07:00Castle Defense I - Approximate methods<style>.post-container { margin: 20px 20px 0 0; border: 2px solid #333; overflow: auto } .post-thumb { float: right } .post-thumb a { display: block } .post-content { margin-left: 2px } </style> <br /><div class="post-container"><div class="post-thumb"></div><div class="post-content"><a href="http://1.bp.blogspot.com/-SO6sPGnWIiY/Vb0VL6JT2LI/AAAAAAAAAIE/6llfJLNMvuo/s1600/TowerDefenseII.JPG" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="600" src="http://1.bp.blogspot.com/-SO6sPGnWIiY/Vb0VL6JT2LI/AAAAAAAAAIE/6llfJLNMvuo/s640/TowerDefenseII.JPG" width="640" /></a>In the <a href="http://pythonshort.blogspot.com/2015/07/tower-defense-i.html">last post</a> we considered a simple version of a tower defense game.<br />There were <b>gameSoldiers</b>, <b>gameTowers</b> and each tower had <b>numHits </b>it could take before crumbling and<b> numKills </b>soldiers it could kill in each round. Soldiers would start each round by shooting at a random tower removing one of its <b>numHits. </b>After all soldiers had fired, the remaining towers would shoot with each tower killing <b>numKills</b> soldiers.<br />In this post we will consider a slightly different variant of the game:<br /><ul><li>A castle is attacked at sunrise, by surprise by a group of<b> gameSoldiers</b> soldiers.</li><li>Each soldier carries a canon and a rifle. </li><li>The castle has <b>castleHits</b> strength, i.e. it can take <b>castleHits</b> before it crumbles. </li><li>In the first day, all soldiers fire their canons at the castle decreasing its strength to \(castleHits-gameSoldiers\).</li><li>Assuming the castle still has \(castleHits>0\), it will then send their own <b>defendersPerWave</b> soldiers per day/wave/round.</li><li>In the beginning of each day/round/wave, the soldiers shoot and each soldier can either hit the castle with a canon subtracting one of its <b><b>castleHits</b><span style="font-weight: normal;"> </span> </b>or the soldier can kill one of the castle defenders (if there are any) with its rifle.</li><li>After all soldiers have shot, the total k castle defenders shoot killing k of the soldiers (assuming there are k soldiers, if there are less then the defenders shoot however many soldiers there are and the castle wins the game). </li><li>If at this point the castle is still up and there are still soldiers, the castle will send <b>defendersPerWave</b> which will add up to whatever defenders are still out from previous rounds<b>. </b>I.e. at the end of each round the castle will send a fresh batch of d<b><b>efendersPerWave<span style="font-weight: normal;"> </span></b></b>as long as <b>castleHits>0.</b></li><li>Notice that since the soldiers attack the castle by surprise, at the beginning of the first round the castle has not sent any of its defenders out (but it will at the end of the first round).</li><li>The game ends with a win for the soldiers if both the castle and all of its defenders are dead and one or more of the soldiers is alive.</li><li>It ends with a win for the castle if no soldiers are left and either \(castleHits>0\) or the number of defenders is > 0 (or both). </li><li>The previous point says that it is possible for the castle to win the game even if it has zero <b>castleHits</b> points as long as there are no soldiers left and there are one or more defenders left (presumably the defenders could then rebuild the castle).</li></ul>We would like to know how fast can the soldiers destroy the castle and all its defenders, i.e. what is the minimum number of days/rounds/waves it takes for the soldiers to win the game.<br />If the soldiers can not win the game we would still like to know in which round will the castle prevail.<br />And we would like to keep track of the remaining <b>gameSoldiers</b>,<b> castleHits</b> and total number of defenders at the end of a round (which is the same as at the beginning of the next round). This will be, in general, greater than just <b>defendersPerWave</b> since some defenders remain from previous rounds.<br /><br /><div style="text-align: center;"><b>REASONABLE SOLUTIONS: Attack the castle first or attack the defenders first</b></div><br />We can try to simulate what happens in each wave like we did in our previous post.<br />It seems that a possible best strategy to destroy the castle in the minimum number of waves/rounds is the following:<br /><ul><li>If the number of soldiers in the wave is greater or equal than the <b>castleHits</b>, we have <b>castleHits</b> of the soldiers shoot at the castle causing it to lose all of its hit points. The remaining soldiers (i.e. \(gameSoldiers - castleHits\)) than shoot at any existing defenders (if \(gameSoldiers-castleHits \geq defenders\) the soldiers win the game in that wave). </li><li>If the number of soldiers in the wave is smaller than the <b>castleHits</b> but greater than the number of defenders, we have the soldiers eliminate all of the defenders and any remaining soldiers shoot then at the castle (that way the castle defenders can not shoot at the soldiers in that round).</li><li>If the number of soldiers in the wave is smaller than both castleHits and the number of defenders, we have the soldiers shoot at the castle.</li></ul>An algorithm based on this approach is then (as in our previous post we use the dictionary waveStats with the waves as keys and all quantities we want to track per wave as the values)<br /><pre class="python" name="code"><b><br /> def attackCastle(self,gameSoldiers,castleHits, defendersPerWave):<br /> totalDefenders = 0<br /> waveStats = {}<br /> wave=0<br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'castleHits':castleHits,<br /> 'defenders':totalDefenders}<br /> wave = 0<br /> while True:<br /> wave += 1<br /> # case a: castleHits <= gameSoldiers<br /> # gameSoldiers first fire at the castle. <br /> # causing castleHits to go to zero;<br /> # the remaining gameSoldiers - castleHits soldiers <br /> # then fire at any defenders<br /> if castleHits <= gameSoldiers: <br /> totalDefenders -= gameSoldiers - castleHits<br /> castleHits = 0<br /> if totalDefenders < 0:<br /> totalDefenders = 0 <br /> # case b: castleHits > gameSoldiers and gameSoldiers>totalDefenders<br /> # the soldiers<br /> # first shoot all the defenders and the remaining<br /> # soldiers then shoot at the castle <br /> elif gameSoldiers > totalDefenders: <br /> castleHits -= gameSoldiers - totalDefenders<br /> totalDefenders = 0<br /> # case c: castleHits> gameSoldiers and gameSoldiers<= totalDefenders<br /> # the soldiers shoot at the castle<br /> else:<br /> castleHits -= gameSoldiers<br /> if castleHits < 0:<br /> castleHits = 0 <br /> if castleHits == 0 and totalDefenders == 0:<br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'castleHits':castleHits,<br /> 'defenders':totalDefenders}<br /> return waveStats<br /> # castle defenders kill as many soldiers<br /> # as there are defenders<br /> gameSoldiers -= totalDefenders<br /> if gameSoldiers <= 0:<br /> gameSoldiers = 0<br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'castleHits':castleHits,<br /> 'defenders':totalDefenders}<br /> <br /> return waveStats<br /> # castle sends another set of defenders out<br /> if castleHits > 0:<br /> totalDefenders += defendersPerWave<br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'castleHits':castleHits,<br /> 'defenders':totalDefenders}<br /> <br /></b></pre>Although this simulation algorithm seems reasonable and works often it also fails sometimes. In fact following this strategy it will lead sometimes to the soldiers losing the game when they could win it with a different approach. <br />Consider for example the case where there are initially 10 <b>gameSoldiers</b>, <b>castleHits=43</b> and the castle sends 8 <b>defendersPerWave</b>. <br /><ul><li>In the first wave, the 10 soldiers reduce <b>castleHits</b> by 10. </li><li>The second wave starts therefore with 10 <b>gameSoldiers</b>,<b> castleHits=33</b> and <b>totalDefenders=8</b>. Since \(gameSoldiers>totalDefenders\) and \(gameSoldiers<castleHits\), 8 of the soldiers kill the 8 defenders and the other 2 soldiers reduce <b>castleHits</b> to 31. The castle sends another 8 defenders.</li><li>In the third round again 8 of the soldiers kill the 8 defenders and reduce <b>castleHits</b> to 29. Another 8 defenders are sent out.</li><li>This pattern repeats itself in the 4th (<b>castleHits</b>=27), 5th (<b>castleHits=25</b>), 6th (<b>castleHits=23</b>), 7th (<b>castleHits=21</b>), 8th (<b>castleHits=19</b>), 9th (<b>castleHits=17</b>), 10th (<b>castleHits=15</b>), 11th (<b>castleHits=13</b>), 12th (<b>castleHits=11</b>) and 13th (<b>castleHits=9</b>). </li><li>In the 14th wave because \(castleHits<gameSoldiers\), the algorithm above makes 9 of the soldiers reduce <b>castleHits</b> to 0 and it makes the remaining soldier kill one of the defenders.</li><li>The 7 defenders then kill 7 of the soldiers. Since the castle is "dead" it will not send any more defenders.</li><li>In the 15th round, the 3 remaining soldiers kill 3 of the 7 defenders and the remaining 4 defenders then kill the 3 soldiers with the win going to the castle. </li><li>Notice how the castle has crumbled in the 14th wave but it still wins the game because 4 of its defenders remain and all soldiers were killed.</li></ul>There is however a slightly different strategy that will lead to a win for the soldiers side:<br /><ul><li>Everything proceeds as described above up to the 13th wave.</li><li>In the 14th wave, again 2 of the soldiers should shoot the castle leaving it with 7 <b>castleHits</b> points and the other 8 soldiers should kill the 8 defenders. </li><li>In the 15th wave, 7 of the soldiers vanish the <b>castleHits</b> points and the remaining 3 soldiers kill 3 of the defenders. The remaining 5 defenders will kill 5 of the soldiers. </li><li>Finally in the 16th wave, the remaining 5 soldiers kill the 5 defenders and win the game.</li></ul>This is indeed the solution which leads to the minimum number of rounds (16 days/rounds).<br /><br />Another seemingly good algorithm is one that always has the soldiers killing as many defenders as possible, with the remaining soldiers shooting then at the castle. This would not lead to the correct minimum for the example above: the game would go on to a 15th wave (<b>castleHits</b>=5), 16th (<b>castleHits</b>=3), 17th (<b>castleHits</b>=1), 18th (<b>castleHits</b>=0, all 8 defenders killed and all 10 soldiers standing still). So the soldiers would win but in 18 days/rounds/waves instead of the minimum 16 waves.<br />Intuitively it is clear that while this approach protects the soldiers from the defenders it is not the fastest possible (in fact it will be the slowest possible). If the question we were trying to solve were <i>"which approach/algorithm leads to the least number of soldiers killed"</i> this would indeed be a good candidate.<br />In code this algorithm looks like this<br /><pre class="python" name="code"><b><br />def attackDefenders(self,gameSoldiers,castleHits, defendersPerWave):<br /> totalDefenders = 0<br /> waveStats = {}<br /> wave=0<br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'castleHits':castleHits,<br /> 'defenders':totalDefenders}<br /> wave = 0<br /> <br /> while True:<br /> wave += 1<br /> # case a: There are (at least) as many totalDefenders<br /> # as gameSoldiers so the gameSoldiers<br /> # all shoot at the defenders, then the <br /> # remaining defenders shoot back<br /> if totalDefenders >= gameSoldiers: <br /> totalDefenders -= gameSoldiers<br /> gameSoldiers -= totalDefenders<br /> <br /> # case b:There are more gameSoldiers than defenders<br /> # so the soldiers kill all defenders and the <br /> # remaining soldiers shoot at the castle<br /> elif castleHits >= 0: <br /> castleHits -= gameSoldiers - totalDefenders<br /> totalDefenders = 0<br /> # case c: There are more gameSoldiers than defenders and<br /> # castleHits=0. The soldiers shoot all defenders<br /> # (and win the game)<br /> else:<br /> totalDefenders = 0<br /><br /> if castleHits < 0:<br /> castleHits = 0 <br /> <br /> # soldiers win<br /> if castleHits == 0 and totalDefenders == 0:<br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'castleHits':castleHits,<br /> 'defenders':totalDefenders}<br /> return waveStats<br /> <br /> # castle wins<br /> if gameSoldiers <= 0:<br /> gameSoldiers = 0<br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'castleHits':castleHits,<br /> 'defenders':totalDefenders}<br /> <br /> return waveStats<br /> <br /> # castle sends another set of defenders out<br /> if castleHits > 0:<br /> totalDefenders += defendersPerWave<br /> <br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'castleHits':castleHits,<br /> 'defenders':totalDefenders}<br /> # prevent infinite loops<br /> if wave>50: <br /> return waveStats<br /></b><br /></pre><br />As this example shows, the simple algorithms we described above do not work for every initial values of <b>gameSoldiers</b>, <b>castleHits</b> and <b>defendersPerWave</b>. We should keep looking. <br /><br /><span style="color: blue;">Before we move on to look at an algorithm that does solve the problem correctly in all cases, lets write down the code we have so far.</span><br /><span style="color: blue;">The code is organized in 3 files:</span><br /><span style="color: blue;"><b><u>castledefense.py</u></b>: This is where the 2 algorithms above are (encapsulated in class CastleDefenseI) in two methods called attackCastle and attackDefenders (this one to reflect the fact that the soldiers primarily shoot at the defenders and only then at the castle).</span><br /><span style="color: blue;"><u><b>tests.py :</b> </u>This file contains all tests (encapsulated in class CastleDefenseITest). In particular the example discussed above at length is the last one: test_26. Note how tests.py imports CastleDefenseI in order for each test to be able to access both of the methods attackCastle and attackDefenders .</span><br /><span style="color: blue;"><b><u>main.py</u>:</b> This file simply creates a CastleDefenseITest object and runs its runTests method.</span><br /><span style="color: blue;">If you press run you can see which tests fail and which ones are correctly solved by one or both of the above two algorithms (you will need a little patience to run all 26 tests; if your browser freezes let the script keep running for about 1-2 minutes).</span><br /><iframe allowfullscreen="" frameborder="0" height="600" marginheight="0" marginwidth="0" src="https://trinket.io/embed/python/19e32b0134" width="100%"></iframe> I summarize the results in the following table.<br />The cells highlighted in red indicate the algorithm predicts the wrong side will win (i.e. the castle will win when in fact there is a minimum number of rounds that lead to a win by the soldiers).<br />The cells highlighted in cyan indicates the algorithm predicts the correct side wins or ties but it takes more moves/rounds than the minimum. <br /><table border="1" style="width: 100%;"> <tbody><tr> <th>Test Number </th><th>Test Values</th><th>Min Rounds</th><th>Rounds for attackCastle</th><th>Rounds for attackDefenders</th></tr><tr> <td align="center">0</td> <td><table> <tbody><tr> <td>gameSoldiers=10 </td> </tr><tr> <td>castleHits=11 </td> </tr><tr> <td>defendersPerWave=15 </td> </tr></tbody> </table></td> <td align="center">Soldiers win in 4</td> <td align="center">Soldiers win in 4</td> <td align="center"><span style="background-color: red;"><b>Castle Wins in 3</b></span></td></tr><tr> <td align="center">1</td> <td><table> <tbody><tr> <td>gameSoldiers=3</td> </tr><tr> <td>castleHits=10</td> </tr><tr> <td>defendersPerWave=4</td> </tr></tbody> </table></td> <td align="center">Castle wins in 2</td> <td align="center">Castle wins in 2</td> <td align="center"><span style="background-color: cyan;"><b>Castle Wins in 3</b></span></td></tr><tr> <td align="center">2</td> <td><table> <tbody><tr> <td>gameSoldiers=2</td> </tr><tr> <td>castleHits=10</td> </tr><tr> <td>defendersPerWave=1</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 9</td> <td align="center">Soldiers win in 9<br />(1 soldier standing) </td> <td align="center">Soldiers win in 9<br />(2 soldiers standing) </td></tr><tr> <td align="center">3</td> <td><table> <tbody><tr> <td>gameSoldiers=11</td> </tr><tr> <td>castleHits=12</td> </tr><tr> <td>defendersPerWave=9</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 2</td> <td align="center">Soldiers win in 2<br />(11 soldiers standing) </td> <td align="center">Soldiers win in 2<br />(11 soldiers standing) </td></tr><tr> <td align="center">4</td> <td><table> <tbody><tr> <td>gameSoldiers=12</td> </tr><tr> <td>castleHits=32</td> </tr><tr> <td>defendersPerWave=5</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 4</td> <td align="center">Soldiers win in 4<br />(12 soldiers standing) </td> <td align="center">Soldiers win in 4 (12 soldiers standing)</td></tr><tr> <td align="center">5</td> <td><table> <tbody><tr> <td>gameSoldiers=12</td> </tr><tr> <td>castleHits=44</td> </tr><tr> <td>defendersPerWave=6</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 7</td> <td align="center">Soldiers win in 7 (10 soldiers standing)</td> <td align="center">Soldiers win in 7 (12 soldiers standing)</td></tr><tr> <td align="center">6</td> <td><table> <tbody><tr> <td>gameSoldiers=7</td> </tr><tr> <td>castleHits=10</td> </tr><tr> <td>defendersPerWave=8</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 4</td> <td align="center">Soldiers win in 4</td> <td align="center"><span style="background-color: red;"><b>Castle wins in 4</b></span></td></tr><tr> <td align="center">7</td> <td><table> <tbody><tr> <td>gameSoldiers=4</td> </tr><tr> <td>castleHits=6</td> </tr><tr> <td>defendersPerWave=7</td> </tr></tbody> </table></td> <td align="center">Castle wins in 2</td> <td align="center">Castle wins in 2</td> <td align="center"><span style="background-color: cyan;"><b>Castle wins in 3</b></span></td></tr><tr> <td align="center">8</td> <td><table> <tbody><tr> <td>gameSoldiers=8</td> </tr><tr> <td>castleHits=10</td> </tr><tr> <td>defendersPerWave=6</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 2</td> <td align="center">Soldiers win in 2 (8 soldiers standing)</td> <td align="center">Soldiers win in 2 (8 soldiers standing)<b><br /></b></td></tr><tr> <td align="center">9</td> <td><table> <tbody><tr> <td>gameSoldiers=4</td> </tr><tr> <td>castleHits=5</td> </tr><tr> <td>defendersPerWave=5</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 3</td> <td align="center">Soldiers win in 3</td> <td align="center"><span style="background-color: red;"><b>Castle wins in 3</b></span> </td></tr><tr> <td align="center">10</td> <td><table> <tbody><tr> <td>gameSoldiers=5</td> </tr><tr> <td>castleHits=8</td> </tr><tr> <td>defendersPerWave=5</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 4</td> <td align="center">Soldiers win in 4</td> <td align="center"><span style="background-color: cyan;"><b>Its a tie!</b></span> </td></tr><tr> <td align="center">11</td> <td><table> <tbody><tr> <td>gameSoldiers=10</td> </tr><tr> <td>castleHits=50</td> </tr><tr> <td>defendersPerWave=9</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 37</td> <td align="center"><span style="background-color: red;"><b>Castle wins in 33</b></span></td> <td align="center"><span style="background-color: cyan;"><b>Soldiers win in 41</b></span> </td></tr><tr> <td align="center">12</td> <td><table> <tbody><tr> <td>gameSoldiers=19</td> </tr><tr> <td>castleHits=50</td> </tr><tr> <td>defendersPerWave=15</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 8</td> <td align="center"><span style="background-color: red;"><b>Castle wins in 6</b></span></td> <td align="center"><span style="background-color: cyan;"><b>Soldiers win in 9</b></span> </td></tr><tr> <td align="center">13</td> <td><table> <tbody><tr> <td>gameSoldiers=10</td> </tr><tr> <td>castleHits=50</td> </tr><tr> <td>defendersPerWave=10</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 2</td> <td align="center">Soldiers win in 2</td> <td align="center"><span style="background-color: cyan;"><b>It's a tie!</b></span> </td></tr><tr> <td align="center">14</td> <td><table> <tbody><tr> <td>gameSoldiers=8</td> </tr><tr> <td>castleHits=9</td> </tr><tr> <td>defendersPerWave=18</td> </tr></tbody> </table></td> <td align="center">Castle wins in 2</td> <td align="center">Castle wins in 2</td> <td align="center">Castle wins in 2</td></tr><tr> <td align="center">15</td> <td><table> <tbody><tr> <td>gameSoldiers=9</td> </tr><tr> <td>castleHits=11</td> </tr><tr> <td>defendersPerWave=12</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 4</td> <td align="center">Soldiers win in 4</td> <td align="center"><b><span style="background-color: red;">Castle wins in 3</span></b></td></tr><tr> <td align="center">16</td> <td><table> <tbody><tr> <td>gameSoldiers=5</td> </tr><tr> <td>castleHits=37</td> </tr><tr> <td>defendersPerWave=5</td> </tr></tbody> </table></td> <td align="center">Castle wins in 2</td> <td align="center">Castle wins in 2</td> <td align="center"><span style="background-color: cyan;"><b>It's a tie!</b></span></td></tr><tr> <td align="center">17</td> <td><table> <tbody><tr> <td>gameSoldiers=9</td> </tr><tr> <td>castleHits=33</td> </tr><tr> <td>defendersPerWave=8</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 22</td> <td align="center"><b><span style="background-color: red;">Castle wins in 18</span></b></td> <td align="center"><span style="background-color: cyan;"><b>Soldiers win in 25</b></span></td></tr><tr> <td align="center">18</td> <td><table> <tbody><tr> <td>gameSoldiers=8</td> </tr><tr> <td>castleHits=21</td> </tr><tr> <td>defendersPerWave=7</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 11</td> <td align="center"><span style="background-color: red;"><b>Castle win in 8</b></span></td> <td align="center"><span style="background-color: cyan;"><b>Soldiers win in 14</b></span></td></tr><tr> <td align="center">19</td> <td><table> <tbody><tr> <td>gameSoldiers=12</td> </tr><tr> <td>castleHits=13</td> </tr><tr> <td>defendersPerWave=50 </td> </tr></tbody> </table></td> <td align="center">Castle wins in 2</td> <td align="center">Castle wins in 2</td> <td align="center">Castle wins in 2</td></tr><tr> <td align="center">20</td> <td><table> <tbody><tr> <td>gameSoldiers=7</td> </tr><tr> <td>castleHits=31</td> </tr><tr> <td>defendersPerWave=5</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 13</td> <td align="center">Soldiers win in 13<br />(2 soldiers standing) </td> <td align="center">Soldiers win in 13 (7 soldiers standing)</td></tr><tr> <td align="center">21</td> <td><table> <tbody><tr> <td>gameSoldiers=19</td> </tr><tr> <td>castleHits=50</td> </tr><tr> <td>defendersPerWave=14</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 7</td> <td align="center">Soldiers win in 7 (5 soldiers standing)</td> <td align="center"><b><span style="background-color: cyan;">Soldiers win in 8 (19 soldiers standing)</span></b></td></tr><tr> <td align="center">22</td> <td><table> <tbody><tr> <td>gameSoldiers=20</td> </tr><tr> <td>castleHits=50</td> </tr><tr> <td>defendersPerWave=18</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 12</td> <td align="center"><span style="background-color: red;"><b>Castle wins in 8</b></span></td> <td align="center"><span style="background-color: cyan;"><b>Soldiers win in 16</b></span></td></tr><tr> <td align="center">23</td> <td><table> <tbody><tr> <td>gameSoldiers=3</td> </tr><tr> <td>castleHits=30</td> </tr><tr> <td>defendersPerWave=1</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 15</td> <td align="center">Soldiers win in 15 (2 soldiers standing)</td> <td align="center">Soldiers win in 15 (3 soldiers standing)</td></tr><tr> <td align="center">24</td> <td><table> <tbody><tr> <td>gameSoldiers=2</td> </tr><tr> <td>castleHits=50</td> </tr><tr> <td>defendersPerWave=1</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 49</td> <td align="center">Soldiers win in 49 (1 soldier standing)</td> <td align="center">Soldiers win in 49 (2 soldiers standing)</td></tr><tr> <td align="center">25</td> <td><table> <tbody><tr> <td>gameSoldiers=9</td> </tr><tr> <td>castleHits=43</td> </tr><tr> <td>defendersPerWave=7</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 17</td> <td align="center"><span style="background-color: red;"><b>Castle wins in 16</b></span></td> <td align="center"><span style="background-color: cyan;"><b>Soldiers win in 18</b></span></td></tr><tr> <td align="center">26</td> <td><table> <tbody><tr> <td>gameSoldiers=10</td> </tr><tr> <td>castleHits=43</td> </tr><tr> <td>defendersPerWave=8</td> </tr></tbody> </table></td> <td align="center">Soldiers win in 16</td> <td align="center"><span style="background-color: red;"><b>Castle wins in 15</b></span></td> <td align="center"><span style="background-color: cyan;"><b>Soldiers win in 18</b></span></td></tr></tbody> </table></div></div><br />Here are some interesting facts we can glance from this table:<br /><ul><li>There are a few tests in which both algorithms agree with the minimum number of rounds (soldiers win) but the attackDefenders algorithm always leaves more soldiers alive than the attackCastle approach.</li><li>If the castle wins it wins in 2 rounds always.</li><li>When the castle wins, the attackCastle algorithm always predicts correctly the castle win in 2 rounds.</li><li>The attackDefenders algorithm also predicts correctly that the castle wins but sometimes it takes 3 rounds.</li><li>When the attackCastle algorithm predicts the soldiers win it always takes the minimum number of rounds (and therefore it is always correct in those cases). The attackDefenders algorithm will in several tests require more rounds for the soldiers to win.</li><li>The attackDefenders algorithm will sometimes lead to a tie (in tests 10, 13 and 16) while the attackCastle will never lead to a tie. If you look at the algorithm code you will notice a condition at the very end of the infinite loop<pre class="python" name="code"><b># prevent infinite loops<br />if wave>50: <br /> return waveStats</b> </pre>to prevent the loop of never ending in cases where there is a tie. </li></ul>Both algorithms make mistakes but it is clear that overall the attackCastle method is better (makes less errors) at predicting the minimum number of days/rounds it takes for the soldiers to win.<br /><br />In our next post we will look at a couple of approaches/algorithms that solve this problem correctly always. jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com1tag:blogger.com,1999:blog-1274195019136560947.post-46081195315752781762015-07-07T07:55:00.000-07:002015-07-17T05:25:31.063-07:00Tower Defense I <style>.post-container { margin: 20px 20px 0 0; border: 2px solid #333; overflow: auto } .post-thumb { float: right } .post-thumb a { display: block } .post-content { margin-left: 2px } </style> <br /><div class="post-container"><div class="post-thumb"></div><div class="post-content"><a href="http://2.bp.blogspot.com/-qGSj1WVhS7E/VZtNksa8PaI/AAAAAAAAAHs/-tWV10uLhAc/s1600/Towersb.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="600" src="http://2.bp.blogspot.com/-qGSj1WVhS7E/VZtNksa8PaI/AAAAAAAAAHs/-tWV10uLhAc/s1600/Towersb.jpg" /></a><br /><pre style="white-space: pre-wrap; word-wrap: break-word;">Most of us have played, have heard or have seen somebody play a Tower Defense style game. <br />The list of such games is very large: Bloons Tower Defense, Plants vs Zombies, Kingdom Rush, PixelJunk Monsters, Defense Grid, geoDefense, Jelly Defense, Dungeons Defenders and on and on.<br />Hopefully you’ve spent some quality time setting up your defenses, killing enemies and advancing through several rounds/waves.<br /><br />The basic idea of these strategy/turn based games is simple: The game progresses in rounds/waves. In each round your opponent (usually the computer) has a certain number of "soldiers" that traverse a maze along which you sprinkle, in strategic locations, one or more "towers" (how many towers you place depends typically on how many you can afford, since each tower will have its own price).<br />The towers will fire at the approaching soldiers; it might take one or several hits to kill a soldier (you earn "money" with each successful hit).<br />The goal of the towers is to prevent any of the soldiers to reach the exit of the maze. Each soldier that leaves the maze will cause you to lose one life.<br /></pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="white-space: pre-wrap; word-wrap: break-word;">In this post we will consider a simple version/variant of the game. </pre><pre style="white-space: pre-wrap; word-wrap: break-word;">Lets suppose the game starts with <b>gameTowers</b> towers, and <b>gameSoldiers</b> soldiers.</pre><pre style="white-space: pre-wrap; word-wrap: break-word;">Each tower can kill <b>numKills </b>soldiers per round (one hit one kill) and can sustain <b>numHits</b> before the tower crumbles. </pre><pre style="white-space: pre-wrap; word-wrap: break-word;">Each soldier in turn can hit one random tower per round causing that tower to lose one of its <b>numHits</b>. More than one soldier can hit the same tower in the same round.</pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="white-space: pre-wrap; word-wrap: break-word;">The game proceeds in the following manner: for a given wave/round each soldier will hit a tower. When all soldiers have done so, each tower will then hit <b>numKills</b> soldiers. If there are any soldiers and towers left, the game moves to the next wave. Otherwise if there are only soldiers/towers left, the soldiers/towers win. </pre><pre style="white-space: pre-wrap; word-wrap: break-word;">One last important detail: At the start of each new round the surviving towers will get reloaded with <b>numKills. Those are fully spent within the round when it is the towers turn </b>(if there are enough soldiers; the towers can only shoot one of their <b>numKills</b> per soldier; if there are not enough soldiers to shoot at, that will be the last round and the towers win the game).<b> </b>The damage they suffer however carries over from round to round. I.e. all towers start the game with<b> numHits </b>but those will decrease from round to round (and within the same round) for those towers hit by the soldiers.</pre><pre style="white-space: pre-wrap; word-wrap: break-word;"> </pre><pre style="white-space: pre-wrap; word-wrap: break-word;">Given these rules and the 4 constants <b>gameSoldiers, numHits, numKills, gameTowers</b> we would like to know how fast can the soldiers destroy the towers or if that is not possible (i.e. if the towers will win). </pre><pre style="white-space: pre-wrap; word-wrap: break-word;">In which round all the soldiers/towers will be destroyed and how many soldiers/towers are left in that round? If only towers are left we would also like to know how many hits and kills each of them has left. (It is not possible for the game to end with a tie.)</pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="white-space: pre-wrap; word-wrap: break-word;">We can go one step further and ask how many towers and soldiers are left after each wave/round. We can gather this information in a dictionary where the keys are the wave number and the values are a list of the values we are interested in tracking after the end of each round. We will call this dictionary waveStats.</pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><h3 style="text-align: center; white-space: pre-wrap; word-wrap: break-word;"><b>An Algorithm to Maximize the number of Towers destroyed</b></h3><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="white-space: pre-wrap; word-wrap: break-word;">A simple algorithm that maximizes the number of towers destroyed is the following</pre><pre style="white-space: pre-wrap; word-wrap: break-word;"></pre><pre class="python" name="code"> <b>def attack(self, gameSoldiers, numHits, numKills, gameTowers):<br /> totalHits = numHits * gameTowers<br /> gTowers = gameTowers<br /> gSoldiers = gameSoldiers<br /> waveStats = {}<br /> wave=0<br /> waveStats[wave] = {'gameSoldiers':gameSoldiers,<br /> 'gameTowers':gameTowers,<br /> 'numHitsLeft':numHits*gameTowers,<br /> 'numKillsLeft':numKills*gameTowers}<br /> <br /> # keep iterating as long as there are towers and soldiers<br /> while totalHits>0 and gSoldiers>0:<br /> wave += 1<br /> # first the soldiers fire<br /> totalHits -= gSoldiers <br /> # break if no tower is left<br /> if totalHits <=0:<br /> waveStats[wave] = {'gameSoldiers':gSoldiers,<br /> 'gameTowers': 0,<br /> 'numHitsLeft': 0,<br /> 'numKillsLeft': 0}<br /> break <br /> # then the towers fire<br /> gTowers = (totalHits + numHits-1)/numHits<br /> <br /> if gSoldiers > numKills * gTowers:<br /> gSoldiers -= numKills * gTowers<br /> waveStats[wave] = {'gameSoldiers':gSoldiers,<br /> 'gameTowers':gTowers,<br /> 'numHitsLeft':totalHits,<br /> 'numKillsLeft':0}<br /> else:<br /> waveStats[wave] = {'gameSoldiers':0,<br /> 'gameTowers':gTowers,<br /> 'numHitsLeft':totalHits,<br /> 'numKillsLeft': numKills* gTowers - gSoldiers}<br /> gSoldiers = 0<br /> <br /> return waveStats</b><br /></pre><br />The idea of the algorithm is simple:<br />We compute the number of total hits the towers can take. That number is initially the product of each tower's hits by the number of towers.<br />Then as long as the number of total hits is greater than zero and the number of soldiers is also greater than zero (if one of these is zero or smaller than zero the game is over) we perform round after round of the game (each iteration of the while loop is one wave/round of the game).<br /><br />In each round, first the soldiers still alive (gSoldiers) fire removing \(gSoldiers\) hit points from the total of hits available.<br />Then the towers still available (gTowers) shoot back killing \( numKills * gTowers\) and leaving \(gSoldiers - numKills * gTowers\) soldiers for the next round.<br /><br />If however \(numKills * gTowers\) is greater than \(gSoldiers\), then the towers will only shoot \(gSoldiers\) and keep the remaining \(numKills * gTowers - gSoldiers\) (this will only happen in the last round of a game won by the towers).<br /><br />A final note on how we compute the number of towers (gTowers) available after the soldiers shoot on each round. Intuitively we would divide the number of hits available by the number of hits per tower<br />$$gTowers = \frac{totalHits}{numHits}$$.<br /><br />This works if totalHits is a multiple of numHits. If it is not a multiple it will give us a smaller number of towers. For example consider \(totalHits=11\) and \(numHits=5\). Doing \(totalHits/numHits=2\) but obviously there are 3 towers (2 that can take 5 hits each and 1 tower that can only take 1 hit) not 2. Similarly if \(totalHits=4\) and \(numHits=5\) we get \(totalHits/numHits=0\) but again there is 1 tower (that can take 4 hits points) instead of 0 towers. We see that this division always under-counts the number of towers by one when the two numbers are not divisible.<br /><br />If we instead add \(numHits -1\) to \(totalHits\) before dividing the whole thing by \(numHits\) we will be guaranteed to round the division by one. For the example above \(totalHits=11\) and \(numHits=5\) we get \((totalHits + numHits -1)/numHits=(11+4)/5=3\). And if \(totalHits=4\) and \(numHits=5\) we get \((totalHits + numHits -1)/numHits=(4+4)/5=1\).<br /><br />It is important to notice that the number of towers destroyed can vary enormously.<br />For example imagine we have 2 towers with 4 hits each and 3 kills each and we have 5 soldiers. The 5 soldiers could shoot one of the towers twice and the other three times. Both towers would stay alive and would then kill the 5 soldiers in the first round.<br />In the approach we just presented, the soldiers will shoot one of the towers 4 times thus destroying it and shoot the second tower once (from our discussion above \(gTowers = (3+3)/4=1\) is the number of towers at the end of the first round). That tower will go on to kill 3 of the soldiers and the game would go on to a second round where the remaining tower would still kill the remaining soldier.<br />In other words in the algorithm we presented the soldiers will always destroy (in each round) the maximum number of towers they can. Take some time convincing yourself that this is the case.<br /><br /><span style="color: blue;">Below is the code. Press the Run button to execute the examples. It might take 3 or 4 minutes to run all 19 examples. Be patient and you will be rewarded (you can also delete/comment out a few of the tests in the all_tests list of the run_tests method and thus shorten the runtime quite a bit).</span><br /><br /><iframe allowfullscreen="" frameborder="0" height="600" marginheight="0" marginwidth="0" src="https://trinket.io/embed/python/e1d9efe4bb" width="100%"></iframe> Lets look at the first test result<br /><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;"><pre style="border-radius: 6px; padding: 1em;">Executing test 0<br />Starting numbers<br />----------------<br />Number of Soldiers: 13<br />Number of Towers: 8<br />Total hits left: 16 (2 and 0 per tower)<br />Total kills Left: 24 (3 and 0 per tower)<br /> <br />End of Wave 1<br />Number of Soldiers: 7<br />Number of Towers: 2<br />Total hits left: 3 (2 and 1 per tower)<br /> <br />End of Wave 2<br />Number of Soldiers: 7<br />Number of Towers: 0<br />Total hits left: 0 (0 and 0 per tower)<br /> <br />Soldiers win in 2 rounds</pre></pre>We start with 13 soldiers and 8 towers. Each tower can take 2 hits (16 total) and can kill 3 soldiers per round (24 total). In the first wave, the 13 soldiers destroy 6 of the towers and leave 2 towers one with 2 hits left and another with 1 hit left. These two towers then kill 6 soldiers leaving 7.<br />In the second wave those 7 soldiers destroy easily the remaining two towers winning the game in two rounds.<br /><div><b><br /></b></div><span style="color: blue;">You can also run some of the tests graphically using the game below. We will come back to this game in a future post.</span><br /><span style="color: blue;">One thing that you might notice (in particular in test 11) is that for some tests the result of the game is not the same!</span><br /><span style="color: blue;">If you run the last test a few times, the towers will win most of the times. There will be however a few times in which the soldiers will win. </span><br /><span style="color: blue;">This happens because the towers are placed randomly. Thus although most of the times the soldiers shoot at the closest tower sometimes two or more towers are within the same range of closeness to the soldier and therefore the soldiers shooting does not result in the maximum number of towers being destroyed in one wave. Instead the soldiers will spread their bullets evenly over two or three close towers leading to an extra tower to survive to the next round. In that case enough towers might survive each round that the towers have enough firepower to finally win.</span><br /><span style="color: blue;">Wins by the soldiers will happen when the towers are placed such that the soldiers shooting results in maximal number of towers destroyed. </span><br /><br /><h3><div style="text-align: center;"><iframe frameborder="0" height="600" marginheight="0" marginwidth="0" src="http://codeskulptor.comxa.com/Towers.html" width="100%"></iframe> <b style="text-align: center; white-space: pre-wrap;">An Algorithm to Minimize the number of Towers destroyed</b></div><div style="text-align: center;"><br /></div></h3> It is interesting to consider the opposite case in which the soldiers try to destroy the least number of towers in a given round. Of course that is not in their interest but it is very much in the towers interest. Because the towers can only shoot after the soldiers they are at a disadvantage and will be happy to accept any give away.<br /><br />Intuitively, to achieve this, the soldiers should spread their shots through all the towers (or as many towers as possible) instead of focusing their aim in as few towers as possible to destroy those few towers.<br />Lets consider the three different cases:<br /><br />a) <u><span style="color: blue;">\(gameSoldiers = gameTowers\)</span></u><br /><br />Soldiers should shoot each tower equally in the first round. If \(numHits=1\) then all towers are killed. Otherwise since \(numKills>0\) the towers will then kill all soldiers in the first round (because \(numKills * gameTowers = numKills * gameSoldiers \geq gameSoldiers\)).<br />So this strategy guarantees the soldiers defeat every time in the first round if \(numHits>1\)!<br />In fact in this case there is no way the soldiers can ever win even if they destroy the highest number of towers they can in each round. All they can do is prolong the game a few extra rounds: consider 2 towers, 2 soldiers, 2 numHits per tower and 1 numKills per tower. If the 2 soldiers destroy one of the towers then the remaining tower will leave one soldier and the game goes an extra round before that soldier is also killed.<br />Here it is a "proof" that the towers always win if \(numHits>1\) no matter the soldiers strategy:<br /><br /><ul><li>The number of towers destroyed in the first round is \(gameSoldiers/numHits=gameTowers/numHits\). The number of towers that remain is then \(gameTowers-gameTowers/numHits=gameTowers(numHits-1)/numHits=gameSoldiers(numHits-1)/numHits\). These remaining towers will then kill \(numKills*gameSoldiers(numHits-1)/numHits\) soldiers. This is smallest when \(numKills=1\). Lets assume that is true in the following.</li><li>At the start of the second round \(gameSoldiers/numHits\) soldiers are left and \(gameSoldiers(numHits-1)/numHits\) are left. If \(numHits>1\) this is half or less of the soldiers. Lets assume then \(numHits=2\) in order to maximize the number of soldiers. This will minimize the number of towers as well. So we have in the second round \(gameSoldiers/2\) soldiers and towers (each tower with 2 numHits and 1 numKills). We are then in the same situation we started with (i.e. the same number of soldiers and towers) so we repeat the reasoning. The towers and soldiers are halved to \(gameSoldiers/4\) entering the third round.</li><li>In general entering the \(nth\) round there will be \(gameSoldiers/2^{n-1}\) soldiers and towers.</li><li>Eventually there will be a round where only 1 soldier and 1 tower are left (assume for simplicity that \(gameSoldiers=2^{n-1}\) so this will happen in round \(n\)). The soldier can shoot off one of the 2 numHits left and the tower will then kill the soldier. Game over!</li></ul><div>b) <u><span style="color: blue;">\(gameSoldiers < gameTowers\)</span></u><br /><br />In this case the \(gameSoldiers\) should shoot \(gameSoldiers\) towers. Assuming that \(numHits>1\), all towers survive and given that \(numKills>0\) they kill all soldiers in the first round.<br />If \(numHits=1\) on the other hand it is possible that even with this bad strategy the soldiers will win sometimes: Suppose the game starts with 4 towers each with \(numHits=numKills=1\) and there are 3 soldiers. The soldiers kill 3 towers. The remaining tower kills one soldier and it is then killed in the second round by one of the remaining two soldiers.<br /><br />c) <span style="color: blue;"> <u>\(gameSoldiers > gameTowers\)</u></span><br /><br />It is harder to find a strategy that minimizes tower destruction consistently. If \(numHits=1\) then the soldiers win right away.<br />Otherwise if \(gameSoldiers/gameTowers = n\) (\(n\) being an integer) we can consider two cases:<br /><br /><ul><li>If \(n>=numHits\) the soldiers win right away. </li><li>If \(n<numHits\) lets suppose n=2. Then at least half the soldiers are killed in the first round (if \(numKills=1\); if \(numKills>1\) more than half of the soldiers will be killed in the first round). The second round starts then with at least an equal number of soldiers and towers or more towers than soldiers and we fall in one of the previous two cases. If n=3 at least one third of the soldiers are killed in the first round (if \(numKills=1\)). The start of the second round is the same as the case n=2. Similarly for \(n=4,5,...\) we can always reduce the problem to \(n-1\) but starting at a later round. Thus if \(n=10\) we know that the start of the second round can be reduced to the case \(n=9\), the start of the third round can be reduced to the case \(n=8\) and so on until the start of the ninth round can be reduced to the \(n=2\) case.</li></ul><div>We will leave to the reader to analyze the case were \(gameSoldiers/gameTowers\) is not an integer.</div><div><br /></div><div>This last section was intended to make us think a bit beyond the initial problem posed (how fast can the soldiers destroy the towers). Our analysis was not completely rigorous but it did provide a way to understand what the game outcome is depending on the relation between \(gameSoldiers\) and \(gameTowers\). The important takeaway is that it is useful to break a problem in steps and sometimes reduce some of those steps to previous steps that we are able to solve/reason about.</div></div></div></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-25330271656245657302015-06-21T12:23:00.000-07:002015-06-21T12:27:15.294-07:00Goal Grades<style>.post-container { margin: 20px 20px 0 0; border: 2px solid #333; overflow: auto } .post-thumb { float: right } .post-thumb a { display: block } .post-content { margin-left: 2px } </style> <br /><div class="post-container"><div class="post-thumb"></div><div class="post-content"><a href="http://2.bp.blogspot.com/-AwepLeEaIM8/VTvnWnjVnjI/AAAAAAAAAEM/KpcQ9QtqQJM/s1200/PassingGrade.JPG" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="600" src="http://2.bp.blogspot.com/-AwepLeEaIM8/VTvnWnjVnjI/AAAAAAAAAEM/KpcQ9QtqQJM/s1200/PassingGrade.JPG" /></a><br /><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> <br />Emily is a very smart girl. </pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">Over the years, she has earned high grades and high accolades from peers and teachers alike in all of her honors and advanced high school classes.</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">She has gotten so used to overperform academically that she decided to take 5 AP classes in her 10th grade.</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">Almost a year went by and she now thinks, after struggling constantly to find the time to do so many assignments and extra curricular activities, that she might have been too ambitious. And to top it all, she now faces the 5 AP tests. </pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">Three of her AP classes (AP Calculus, AP Chemistry and AP Biology) are crucial for her focus area in the years ahead. She will have to earn 94% or more of the total possible points in each of these.</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">The other two (AP French and AP History) are not as important but she still must earn 85% or more in each.</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">With these percents dancing in her head, she sits down in front of the computer a few weeks before taking the tests. </pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">She wants to figure out how many points she has to earn in each of the tests to achieve her goal.</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> </pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">She writes down a list of points she earned during the year in each assignment of each class. She stores this in a python list of lists (with the first element of the list representing the assignment scores for AP Biology, the second the scores for AP Calculus,</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">then AP Chemistry, AP French and the last element representing the scores for AP History, i.e. she organizes the classes in alphabetical order)</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> </pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"><pre class="python" name="code">pointsEarned = [[382, 710, 805, 615, 377, 255, 256, 30, 70, 316, 372, 173], <br /> [17, 23, 50, 200, 19, 56, 83, 91, 77, 9, 0],<br /> [26, 530, 60, 18, 547, 53, 529, 671, 90, 140, 208, 19, 329, 242, 233],<br /> [55, 77, 82, 60],<br /> [408, 800, 5, 306, 2, 703, 311, 163, 760, 742, 640, 574, 301, 565]]<br /></pre></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">Similarly the points possible in each assignment of each class are stored in the list of lists</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">pointsPossible = [[999, 947, 839, 689, 491, 758, 652, 156, 123, 731, 455, 526],</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> [20, 30, 50, 250, 20, 70, 100, 100, 100, 10, 10],<br /> [87, 648, 609, 65, 554, 150, 736, 837, 368, 147, 223, 438, 475, 893, 349],</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> [100,100,100,100],<br /> [949, 936, 7, 404, 191, 899, 964, 393, 914, 805, 706, 619, 529, 734]]<br /> <br />The maximum possible points of each test go in the list</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">testsPossible = [50517, 1500, 58913,500, 9946] </pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">and the minimum percent goal for each test goes into the list</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">percentsMin = [94,94,94,85,85]</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">Emily then computed the lowest 5 test scores that she needs to meet her goals using the following python code</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="word-wrap: break-word;"><span style="white-space: pre-wrap;"> <br /></span><pre class="python" name="code"><b style="color: black; white-space: pre-wrap;"> </b><b> # Loop through the integers between 0 and testMax</b></pre><b> # and exit when you have reached pointsNeeded def pointsNeeded(self, pointsEarned, pointsPossible, testMax, percentMin): totalPoss = 0 totalEarned = 0 # compute total possible points (from assignments and test) # and total earned points (just from assignments) for i in range(len(pointsPossible)): totalPoss += pointsPossible[i] totalEarned += pointsEarned[i] # take into account the max possible test points # when computing the total possible points totalPoss += testMax # if the totalEarned points equals the desired percent # Emily can skip the final test if (percentMin*totalPoss) == (100*totalEarned): return 0 # Loop through the max test possible points and quit as soon as # it is higher or equal than the minimum number of points needed for i in range(testMax + 1): if 100*i >= (percentMin*totalPoss - 100*totalEarned): return i # The score needed in the test is higher than the maximum possible points of # the test return -1</b><pre class="python" name="code" style="color: black; white-space: pre-wrap;"><b><br /> def testsMin(self,pointsEarned,pointsPossible,testsMax,percentsMin):<br /> goalTestsScores = []<br /> <br /> for i in range(len(pointsEarned)):<br /> goalTestsScores.append(self.pointsNeeded(pointsEarned[i],pointsPossible[i],testsMax[i],percentsMin[i]))<br /> <br /> return goalTestsScores</b><br /></pre><span style="white-space: pre-wrap;"></span></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> </pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> Notice that there are 3 possible cases:</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> a) She already has enough points in a class to achieve her desired percent. She can basically skip the test. That is the case above where a 0 is returned.</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> b) She needs to have some value between 1 and testMax in the test. That is the second return (return i) above. There is a loop through the testMax points until we hit or surpass</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">the points needed.</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> c) Finally it might be the case that she is so far behind in the class that even having the maximum score in the test will not allow her to reach the desired percent. That is the final return above (return -1). </pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"></pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;">After writing this code Emily realized she could have just computed the points needed directly. She rewrote the points needed function like this</pre><pre style="color: black; white-space: pre-wrap; word-wrap: break-word;"> </pre><pre class="python" name="code"> <b> # Compute the points needed directly<br /> def pointsNeeded(self, pointsEarned, pointsPossible, testMax, percentMin):<br /> totalPoss = 0<br /> earned = 0<br /> <br /> for i in range(len(pointsPossible)):<br /> totalPoss += pointsPossible[i]<br /> earned += pointsEarned[i]<br /> totalPoss += testMax<br /> <br /> # the 99 is needed to round up by 1<br /> pointsNeeded = (percentMin*totalPoss+99)/100 - earned<br /> <br /> # We might need more points than testMax<br /> if pointsNeeded > testMax:<br /> return -1<br /> <br /> # The number of points earned can be larger than what we need<br /> # i.e. we dont even have to take the final test<br /> if pointsNeeded < 0:<br /> return 0<br /> return pointsNeeded</b><br /></pre><pre class="python" name="code"><b><br /></b></pre><pre class="python" name="code">The only slightly tricky part is the fact she adds 99 to round up the score. Why is this needed?</pre><pre class="python" name="code">Suppose percentMin = 70, totalPass = 66, earned = 44. </pre><pre class="python" name="code">Then (70*66/100)=46 since this is integer division. </pre><pre class="python" name="code">pointsNeeded = 46-44=2. </pre><pre class="python" name="code">That is with 44+2=46 Emily would get 70% of 66. But is that true? 46/66= 0.696969... not 0.7.So indeed Emily would need 3 points not 2. </pre><pre class="python" name="code">This is because 70*66/100 = 46.2 not 46. We want to round up and</pre><pre class="python" name="code">(70*66 + 99)/100 = 47</pre><pre class="python" name="code">which gives the 3 points needed.</pre><pre class="python" name="code"></pre><pre class="python" name="code">When Emily runs her code she gets</pre><pre class="python" name="code"></pre><pre class="python" name="code"><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">CLASS 0<br />points earned in assignments [382, 710, 805, 615, 377, 255, 256, 30, 70, 316, 372, 173]<br />total points earned in assignments 4361<br />max assignment points [999, 947, 839, 689, 491, 758, 652, 156, 123, 731, 455, 526]<br />max points in test 50517<br />max possible points (assignments and tests) 57883<br />minimum test score to get 94% of the total possible points: 50050<br />CLASS 1<br />points earned in assignments [17, 23, 50, 200, 19, 56, 83, 91, 77, 9, 0]<br />total points earned in assignments 625<br />max assignment points [20, 30, 50, 250, 20, 70, 100, 100, 100, 10, 10]<br />max points in test 1500<br />max possible points (assignments and tests) 2260<br />minimum test score to get 94% of the total possible points: 1500<br />CLASS 2<br />points earned in assignments [26, 530, 60, 18, 547, 53, 529, 671, 90, 140, 208, 19, 329, 242, 233]<br />total points earned in assignments 3695<br />max assignment points [87, 648, 609, 65, 554, 150, 736, 837, 368, 147, 223, 438, 475, 893, 349]<br />max points in test 58913<br />max possible points (assignments and tests) 65492<br />minimum test score to get 94% of the total possible points: 57868<br />CLASS 3<br />points earned in assignments [55, 77, 82, 60]<br />total points earned in assignments 274<br />max assignment points [100, 100, 100, 100]<br />max points in test 500<br />max possible points (assignments and tests) 900<br />minimum test score to get 85% of the total possible points: 491<br />CLASS 4<br />points earned in assignments [408, 800, 5, 306, 2, 703, 311, 163, 760, 742, 640, 574, 301, 565]<br />total points earned in assignments 6280<br />max assignment points [949, 936, 7, 404, 191, 899, 964, 393, 914, 805, 706, 619, 529, 734]<br />max points in test 9946<br />max possible points (assignments and tests) 18996<br />minimum test score to get 85% of the total possible points: 9867<br />=======================</pre></pre>We see that Emily needs to score 50050 out of 50517 in Biology's final test, 1500 out of 1500 (a perfect score!) in Calculus, 57868 out of 58913 in Chemistry, 491 out of 500 in French and in History 9867 out of 9946.<br />She will need quite a bit of luck to achieve her goals.<br /><br />We end this post with Emily's complete code<br /><br /></div><iframe src="https://trinket.io/embed/python/8e64e1e89e?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" width="100%" allowfullscreen></iframe></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-84694398386405786522015-06-11T21:02:00.000-07:002015-06-21T12:19:27.573-07:00Popularity Measures<style>.post-container { margin: 20px 20px 0 0; border: 2px solid #333; overflow: auto } .post-thumb { float: right } .post-thumb a { display: block } .post-content { margin-left: 2px } </style> <br /><div class="post-container"><div class="post-thumb"></div><div class="post-content"><a href="http://1.bp.blogspot.com/-weAaticaFmA/VXpaKYbrjwI/AAAAAAAAAHM/4NSYmd7X_2U/s1200/FriendScore2.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://1.bp.blogspot.com/-weAaticaFmA/VXpaKYbrjwI/AAAAAAAAAHM/4NSYmd7X_2U/s1200/FriendScore2.jpg" /></a>I picked up the two sheets that lay at the bottom of the table I was eating. It looked like a story or some sort of reminiscence. Curious, I began to read it.<br /><br /><i>Everybody knows who the five of us are: Phoebe, Diane, CJ, Charlotte and Sydney. Our hair is blonde or brown or black or red, straight or curly, always movie-perfect. When we run our fingers through the silky strands or fat curls and hold it away from our faces you can just catch a glimpse of our striking eyes. When you do, you get shivers at the mere sight of them. </i><br /><i><br /></i><i>We sit on the benches outside school after a long day, seeing everyone who walks past us, in and out of our 200-year-old school. We sweep over you with our eyes as if you were an uninteresting landscape. We've seen everything the world has to offer, and we've dismissed it. </i><br /><i><br /></i><i>Our book bags spill into the corridor in front of us. They are our prized possessions. We reach into them to refold twenties into our Coach leather wallets, to idly rearrange a silk sweater that matches our socks, to lift and complain about that all-around too heavy bio textbook. We mention the biology teacher's name and flutter our lashes, rolling our eyes. We also discuss the theater teacher, and that one English teacher.</i><br /><i><br /></i><i>You can't get enough of us. You've seen girls like us every step of the way through school. We're way out of your league. We know we are royalty among a sea of plebeians. </i><br /><i><br /></i><i>We walk in the formation of migrating geese. Phoebe is at the head, with Sydney and Diane on her left and right, Charlotte and CJ last. Only Charlotte cares that she's last. We haven't figured out what CJ cares about; we don't spend much brain time on the subject. </i><br /><i><br /></i><i>Phoebe is in the student association board and today she is agitated. It seems in the board meeting tasked with dividing student's fees among different school groups, the geek girls claimed their programming club should get more money then our fashion group. Phoebe rightly claimed that our fashion soirees attracted far more people than the geeky programmer club could ever dream. Words flew and Phoebe at some point tossed out "We are far more popular than you little geeks, and that is enough to make our case". </i><br /><i>But the geeks retorted "You might think that but the facts do not support your thesis." </i><br /><i>A committee was setup to decide the popularity question. It was agreed that if indeed we are the most popular our club will receive more money than the programming club, and otherwise they will get it.</i><br /><br /><h3 style="text-align: center;"><i><b>Greatest Number of 2-Friends</b></i></h3><i>The popularity measure we all agreed on was the number of friends or friends of friends of each student.</i><br /><i>If our group had a higher number of 2-friends than the other group, we would win. Phoebe tasks Sydney and Diane to work with two girls from the programming club, Cathleen and Mira, to find out the number of 2-friends of each student of our school.</i><br /><i><br /></i><i>In their talks with </i><i> Cathleen and Mira, </i><i>Sydney and Diane spent some time learning about ways of representing friendships. </i><br /><i>The first way is by means of an undirected graph. </i><br /><i>Below is the friendship graph for the five of us, Cathleen and Mira, and Jasmine, Roberta and Michaela. </i><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://4.bp.blogspot.com/-d7SeSVWYJe4/VW8K2TkDqII/AAAAAAAAAGY/n0RcjxVyidQ/s1600/friends.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://4.bp.blogspot.com/-d7SeSVWYJe4/VW8K2TkDqII/AAAAAAAAAGY/n0RcjxVyidQ/s1600/friends.jpg" /></a></div><i><br /></i><i>An edge means the two girls connected are friends. Absence of an edge means absence of friendship.</i><br /><i>At the top of the graph there is our group. All girls are friends with each other. CJ surprisingly also became friends with Cathleen. Roberta and Mira are also friends with Cathleen. </i><br /><i>Jasmine has only one direct friend which is Roberta. However because Roberta is friends with Michaela and Cathleen, Jasmine has three 2-friends.</i><br /><i>CJ has five direct friends but because Mira and Roberta are friends with Cathleen she has seven 2 friends. Sydney, Daphne, Diane and Phoebe have four direct friends but because CJ is friends with Cathleen they all have five 2-friends. </i><br /><i>Cathleen has 3 direct friends but through CJ she gets 4 more 2-friends and through Mira and Roberta she gets 2 more. </i><br /><i>Based on this set of students, she would have the most 2-friends (9 = 3 direct + 6 friends of friends). CJ would be second with 7.</i><br /><i>Here it is the ranking</i><br /><table border="1" style="width: 50%;"><tbody><tr><th>Student</th><th>friends </th><th>friends of friends</th><th>2-friends</th></tr><tr><td align="center">Cathleen</td> <td align="center">3</td> <td align="center">6</td> <td align="center">9</td></tr><tr> <td align="center">CJ</td> <td align="center">5</td> <td align="center">2</td> <td align="center">7</td></tr><tr><td align="center">Sydney, Daphne, Diane and Phoebe </td> <td align="center">4</td> <td align="center">1</td> <td align="center">5</td></tr><tr><td align="center">Roberta </td> <td align="center">3</td> <td align="center">2</td> <td align="center">5</td></tr><tr><td align="center">Mira, Michaela </td> <td align="center">2</td> <td align="center">2</td> <td align="center">4</td> </tr><tr><td align="center">Jasmine </td> <td align="center">1</td> <td align="center">2</td> <td align="center">3</td></tr></tbody></table><i>To decide if student A is a 2-friend of B the key is to check whether A and B are separated by at most two edges (i.e. whether there is a path between A and B with one or two edges). If there is they are 2-friends otherwise they are not.</i><br /><i>According with the above table our team has a total of 27 two-friends. The remaining five girls have 21 two-friends. So if we based the results on just these 10 people our team would win.</i><br /><i><br /></i><i>Graphs are a nice visual representation of friendships but to compute the 2-friends of the hundreds of students required using a different representation called an adjacency matrix. In it, each student is numbered from 0 to n-1 with n being the number of students. </i><br /><i>Student i (0 <= i<n) friends are represented by a string of n characters. Character j is T(True) if students i,j are friends and F(False) otherwise. </i><br /><i>This string is element i in a list we will call</i><i> friends.</i><br /><i>Lets illustrate this by translating the graph to this representation. </i><br /><i>We number Daphne as 0, Diane as 1, Sydney as 2, Phoebe as 3, CJ as 4, Cathleen as 5, Mira as 6, Roberta as 7, Michaela as 8 and Jasmine as 9.</i><br /><i>Then from the graph above we can see that the string representation for Daphne, is</i><br /><i>friends[0]='FTTTTFFFFF'. </i><br /><i>For Diane it would be friends[1]='TFTTTFFFFF'.</i><br /><i>For Jasmine it would be friends[9]='FFFFFFFTFF'.</i><br /><i>The complete list would be</i><br /><i> friends = ['FTTTTFFFFF', # Daphne as 0 </i><br /><pre class="python" name="code"><i> 'TFTTTFFFFF', # Diane as 1</i><br /><br /><i> 'TTFTTFFFFF', # Sydney as 2 </i><br /><br /><i> 'TTTFTFFFFF', # Phoebe as 3</i><br /><br /><i> 'TTTTFTFFFF', # CJ as 4</i><br /><br /><i> 'FFFFTFTTFF', # Cathleen as 5</i><br /><br /><i> 'FFFFFTFFTF', # Mira as 6</i><br /><br /><i> 'FFFFFTFFTT', # Roberta as 7</i><br /><br /><i> 'FFFFFFTTFF', # Michaela as 8</i><br /><br /><i> 'FFFFFFFTFF'] # Jasmine as 9</i><br /></pre><br /><i>Note how in this representation we don't consider a student to be friends with itself and so friends[0][0]='F', friends[1][1]='F', etc. (This is because, in this problem, we are only interested in 2 or higher friendship and a person being friends with herself is 1-friends).</i><br /><i><br /></i><i>Clearly the adjacency matrix friends[i][j] is symmetric (i.e. friends[i][j]=friends[j][i]). </i><br /><i>It is a somewhat memory wasteful representation because most of the entries will be 'F'. In practice we could only keep the entries that are 'T' since those are the only relevant for the 2-friendship computation. </i><br /><i><br /></i><i>Given the list friends, a simple python method to compute the largest number of 2 friends, as well as the number of 2 friends of each person is</i><br /><b></b><br /><pre class="python" name="code"><b>def mostTwoFriends(self,friends):<br /> best = 0<br /> self.nFriends = {}<br /> for i in range(0,len(friends)):<br /> count = 0<br /> for j in range(0,len(friends[i])):<br /> if i == j:<br /> continue<br /> # direct friends<br /> if friends[i][j] == 'T':<br /> count += 1<br /> else:<br /> # check whether i and j have a friend k in common<br /> for k in range(0, len(friends)):<br /> if k == i or k == j:<br /> continue<br /> if friends[i][k] == 'T' and friends[j][k] == 'T':<br /> count += 1<br /> break<br /> self.nFriends[i] = count<br /> best = max(best, count)<br /> <br /> return best<br /></b><br /></pre><i>nFriends is a dictionary whose keys are the person number and whose values are the number of 2-friends for each person. </i><br /><i>A brief analysis of the code: We are trying to determine if i and j are 2-friends, i.e. if they are related directly or through a k common friend. </i><br /><i>So for each pair of people i,j, we check first if they are direct friends. If they are we count it and move to the next pair. If they are not we check whether i,j have a friend k in common (the k loop). </i><br /><i>If they are we count it and bail out</i><i>, i.e. we break out of the k loop above.</i><br /><i>Notice that it is possible that i,j have more than one k friend in common. </i><br /><i>For example Cathleen and Michaela have Mira and Roberta as common friends. The method above only counts one of these because once we figure out that Cathleen and Michaela are related through say Mira we know they are 2-friends count it and skip the other k friend.</i><br /><h3 style="text-align: center;"><i><b>Greatest Number of 3-Friends</b></i></h3><i><br /></i><i>It turns out that the two groups tied up under the 2-friends popularity measure. It was proposed that we go one step further, measure the 3-friends number for each student and use it to untie. </i><br /><i>Lets say you are person 0. </i><br /><i>3-friends counts person 1 as your friend if you are her friend, or there is a person 2 that is your friend and is friends with person 1 or there is a person 3 that is friends with person 2 which in turn is friends with person 1. </i><br /><i>Looking at the graph above the number of 3-friends for each girl is now</i><br /><table border="1" style="width: 100%;"><tbody><tr><th>Student</th><th>friends </th><th>friends of friends</th><th>friends of friends of friends</th><th>3-friends</th></tr><tr><td align="center">Cathleen</td> <td align="center">3</td> <td align="center">6</td> <td align="center">0</td> <td align="center">9</td></tr><tr> <td align="center">CJ</td> <td align="center">5</td> <td align="center">2</td><td align="center">2</td><td align="center">9</td></tr><tr><td align="center">Roberta </td> <td align="center">3</td> <td align="center">2</td> <td align="center">4</td><td align="center">9</td></tr><tr><td align="center">Mira </td> <td align="center">2</td> <td align="center">2</td> <td align="center">5</td><td align="center">9</td> </tr><tr><td align="center">Sydney, Daphne, Diane and Phoebe </td> <td align="center">4</td> <td align="center">1</td> <td align="center">2</td> <td align="center">7</td></tr><tr><td align="center">Michaela </td> <td align="center">2</td> <td align="center">2</td> <td align="center">1</td><td align="center">5</td> </tr><tr><td align="center">Jasmine </td> <td align="center">1</td> <td align="center">2</td> <td align="center">2</td><td align="center">5</td></tr></tbody></table><i>To decide if student A is a 3-friend of B the key is to check whether A and B are separated by at most three edges (i.e. whether there is a path between A and B with one, two or three edges). If there is they are 3-friends otherwise they are not.</i><br /><i>For this particular group of 10 students there is now a tie: our group has 37 three-friends (versus 27 two-friends) but the other 5 girls also have 37 three-friends (versus 21 two friends). </i><br /><i>The maximum number of two and three friends is however the same (9) although there are now more girls with that maximum. </i><br /><i>Whereas before Cathleen was the only one with 9 two-friends, now besides her, also CJ , Roberta and Mira have 9 three-friends.</i><br /><i>It cant be higher since there are only 10 people and a person can at most have 9 2 and 3-friends.</i><br /><i><br /></i><i>Note that the number of 3-friends for each person will always be at least equal to the number of 2-friends because we are keeping all the 2-friends counts and adding an extra possibility: that i and j can be connected via a path of length 3.</i><br /><i><br /></i><i>We could extend the above method, which checks for paths between i and j of length 1 and 2, to also check for paths of length 3. </i><br /><i>We would have to add a fourth nested loop and end up with this convoluted code</i><br /><pre class="python" name="code"><b> def mostThreeFriendsPoor(self,friends):<br /> best = 0<br /> self.nFriends = {}<br /> for i in range(0,len(friends)):<br /> count = 0<br /> for j in range(0,len(friends[i])):<br /> if i == j:<br /> continue<br /> # direct friends<br /> if friends[i][j] == 'T':<br /> count += 1<br /> else:<br /> doneCounting3 = False<br /> # check whether i and j have a friend k in common<br /> for k in range(0, len(friends)):<br /> if doneCounting3:<br /> break<br /> if k == i or k == j:<br /> continue<br /> if friends[i][k] == 'T' and friends[j][k] == 'T':<br /> count += 1<br /> break<br /> else:<br /> # check whether i has a friend p which is a friend of k which in turn is a friend of j<br /> for p in range(0, len(friends)):<br /> if p == k or p == i:<br /> continue<br /> if friends[i][p] == 'T' and friends[p][k] == 'T' and friends[k][j] == 'T':<br /> count += 1<br /> doneCounting3 = True<br /> break<br /> self.nFriends[i] = count<br /> best = max(best, count)<br /> <br /> return best<br /></b><br /></pre><i>This works but </i><br /><i>1) It is quite confusing and messy and most importantly</i><br /><i>2) This pattern of nesting more and more loops inside the k loop will become very inefficient and slow if we use it for finding the number of four,five,six friends. </i><br /><i>For n-friends it would lead to n+1 nested loops.</i><br /><i>Lets try to understand the logic we do in loops k and p:</i><br /><i>We are trying to determine if i and j are 3-friends, i.e. if they are related directly, through a k friend or through a k and p friends. </i><br /><i>So if they are related through a k friend we count it and bail out (we dont care if k additionally is related to some other friend p which is friends with j). </i><br /><i>If however k is not friends with i or j directly we want to see if there is a path of length 3 connecting i and j via k and p. </i><br /><i>As soon as we find one we want to bail out from the k and p loops.</i><br /><i>Note in particular the extra variable doneCounting3 whose only purpose is to break out of loop k if we find a 3-friend in loop p. </i><br /><i>Python break statement only allows us to break from one loop at a time. </i><br /><i>In this particular case we would like not just to break from loop p but also from loop k and one (bad) way of doing this is to signal through the boolean variable doneCounting3 loop k so that the upper loop can break out. </i><br /><i>To summarize: We are trying to find if i and j are related through a path of length 1,2, or 3. As soon as we find one such path we bail out and move on to the next i,j pair. That is the purpose of the break statements.</i><br /><i><br /></i><i>To further illustrate this consider the above graph. </i><br /><i>There are two paths of length 2 between Cathleen and Michaela. </i><br /><i>One goes through Mira and the other goes through Roberta. </i><br /><i>We only want to count one of them, so as soon as we find one (in the k loop) we get out. </i><br /><i>Similarly there are two paths of length 3 between CJ and Michaela one through Mira and the other through Roberta. Once we find one we break from both the k and p loops.</i><br /><i><br /></i><i>We can make the code less messy by breaking it into two methods:</i><br /><pre class="python" name="code"><b><br /> def countPathsOfLengthTwoOrThree(self,count,friends,i,j):<br /> # check whether i and j have a friend k in common<br /> for k in range(0, len(friends)):<br /> if k == i or k == j:<br /> continue<br /> if friends[i][k] == 'T' and friends[j][k] == 'T':<br /> count += 1<br /> return count<br /> # check whether i has a friend p which is a friend of k which in turn is a friend of j, <br /> # i.e. look for a path of length 3 between i and j<br /> for p in range(0, len(friends)):<br /> if p == k or p == i:<br /> continue<br /> if friends[i][p] == 'T' and friends[p][k] == 'T' and friends[k][j] == 'T':<br /> count += 1<br /> return count<br /> return count<br /> <br /> def mostThreeFriends(self,friends):<br /> best = 0<br /> self.nFriends = {}<br /> for i in range(0,len(friends)):<br /> count = 0<br /> for j in range(0,len(friends[i])):<br /> if i == j:<br /> continue<br /> # direct friends<br /> if friends[i][j] == 'T':<br /> count += 1<br /> else:<br /> count = self.countPathsOfLengthTwoOrThree(count,friends,i,j) <br /> self.nFriends[i] = count<br /> best = max(best, count)<br /> <br /> return best<br /></b><br /></pre><br /><i>Notice how instead of a break when we find a path of length 2 or instead of using the variable doneCounting3 when we find a path of length 3, we simply return from countPathsOfLengthTwoOrThree. </i><br /><i>The code is now more readable. </i><br /><i><br /></i><i><span style="color: blue;">Lets assemble the code to compute 2 and 3 friends we have so far.</span></i><br /><iframe allowfullscreen="" frameborder="0" height="600" marginheight="0" marginwidth="0" src="https://trinket.io/embed/python/ef7e04a9e5" width="100%"></iframe><i><br /><span style="color: blue;">There are 3 files: </span></i><br /><i><span style="color: blue;">NFriendsClass.py has the class NFriends with the methods described previously.</span></i><br /><i><span style="color: blue;">TestClass.py has the class Test with 22 tests. The very first test corresponds to the graph we have used through this post. </span></i><br /><i><span style="color: blue;">Only the first 7 tests are run, otherwise your browser would freeze.</span></i><br /><i><span style="color: blue;">Press the run button to run those first 7 tests (be prepared to wait a minute).</span></i><br /><i><span style="color: blue;">You can run more or different tests by uncommenting them in the method run_tests.</span></i><br /><i><span style="color: blue;">Running the 22 tests will take 3 to 5 minutes. Your browser might freeze two or three times.</span></i><br /><i><span style="color: blue;">Just let it run and you will be rewarded by the wait.</span></i><br /><i><span style="color: blue;">The third file main.py merely creates a Test object and runs its run_tests method.</span></i><br /><h3 style="text-align: center;"><i><b>Finding the greatest number of k-friends using Breadth First Search (BFS)</b></i></h3><i>Another tie ensues and again the answer is to go to the computation of the 4-friends of each student.</i><br /><i>We should at this point pursue a different strategy that let us compute the k-friends of each student with a single method for any k>=2.</i><br /><i>Lets go back to the graph above. Suppose we want to find the k-friends of person 0. </i><br /><i>Starting from 0 we visit all the nodes that are directly connected to person 0: person 1,2,3,4.</i><br /><i>This gives us 4 k-friends of person 0.</i><br /><i>We next visit all the nodes that can be connected to 0 by a path of length 2: we find person 5.</i><br /><i>Next we visit all the nodes that can be connected to 0 by a path of length 3: we find persons 6 and 7.</i><br /><i>Next we visit all the nodes that can be connected to 0 by a path of length 4: we find persons 8 and 9.</i><br /><i>Thus person 0 has 9 four-friends and in fact 9 k-friends for k>=4.</i><br /><i>As a curiosity all people in the graph will have 9 k-friends for k>=4. </i><br /><br /><i>The graph traversal we just described is known as Breadth First Search (BFS) and gives a way of computing the number of k-friends for every person/node. We just have to loop through every node and traverse the graph starting at that node. </i><br /><i>We can, like before, compute the maximum among all such counts.</i><i> </i><br /><i>One final remark: It is possible that besides the number of k-friends for each person we might be interested in knowing how each pair of people i,j is related through a k-friend.</i><br /><i>The BFS graph traversal gives us these paths automatically as part of the traversal.</i><br /><span style="color: blue;"><i>Lets take a look at the code (click the run button to see the number of 2,3,4,5-friends for two graphs: the 10 person graph we started this post and the 50 graph person we end this post with, see below; processing the 50 person graph might take 3-4 minutes and might freeze the browser, just be patient and you should see the result)</i></span><br /><i><br /></i></div><iframe allowfullscreen="" frameborder="0" height="600" marginheight="0" marginwidth="0" src="https://trinket.io/embed/python/92d7acce7b" width="100%"></iframe> <span style="color: blue;">Besides the three previous files there is now a fourth file QueueClass.py which contains a simple implementation of a Queue in python. A Queue (implemented using a list) is a data structure that accepts new elements at its end (back) but removes them from its front.</span><br /><span style="color: blue;">The following two methods in NFriendsClass.py do BFS of a given graph.</span><br /><pre class="python" name="code"><b><br />def BFS(self,graph,start,end,q):<br /> # if start is not connected to any other node<br /> # there is nothing to do just return<br /> if not graph.has_key(start):<br /> return 0<br /> temp_path = [start]<br /> q.enqueue(temp_path)<br /> while q.IsEmpty() == False:<br /> tmp_path = q.dequeue()<br /> last_node = tmp_path[len(tmp_path)-1]<br /> if last_node == end:<br /> if len(tmp_path)-1 <= self.n:<br /> self.paths.setdefault(start,[]).append(tmp_path)<br /> return 1<br /> else:<br /> return 0<br /> for link_node in graph[last_node]:<br /> if link_node not in tmp_path:<br /> new_path = []<br /> new_path = tmp_path + [link_node]<br /> q.enqueue(new_path)<br /> return 0<br /> <br /> def mostNFriendsBFS(self, friends):<br /> # convert list of friends to adjacency list<br /> # as a dictionary<br /> graph = {}<br /> self.nFriends = {}<br /> self.paths = {}<br /> for i in range(0,len(friends)):<br /> for j in range(0,len(friends)):<br /> if i == j:<br /> continue<br /> if friends[i][j]== 'T':<br /> if graph.has_key(i):<br /> graph[i].append(j)<br /> else:<br /> graph[i]=[]<br /> graph[i].append(j)<br /> <br /> # empty dictionaries evaluate to false<br /> # if the graph is empty there are no paths<br /> # so return right away<br /> if not graph:<br /> return 0<br /> best = 0 <br /> <br /> for i in range(0,len(friends)):<br /> count = 0 <br /> for j in range(0,len(friends)):<br /> if i == j:<br /> continue<br /> pathQueue = Queue()<br /> count += self.BFS(graph,i, j,pathQueue)<br /> self.nFriends[i] = count<br /> best = max(best,count)<br /> return best<br /></b><br /></pre><i>In the method mostNFriendsBFS we first convert the graph from the adjacency matrix representation we have been using up to now to an adjacency list representation. This representation is more compact for these sparse graphs and it also makes the search slightly faster.</i><br /><i>Then we loop through every pair of people i,j considering i as the start node and j as the end node of the path in the graph of length at most k (if finding k-friends).</i><br /><i>For each pair, the method BFS then does the BFS graph traversal from i to j. </i><br /><i>It places the start node (i.e. i) in a queue, then visits all nodes connected to it and puts the path from i to hose nodes in the queue (paths of length 1). </i><br /><i>In the second round the method removes one of those paths of length 1 from the queue and visits every node connected to the last node in the path: i.e. visits all paths of length 2 from i. </i><br /><i>The method exits if the last node in the path it just got from the queue is the same as the end node (i.e. j).</i><br /><i>Additionally if that end node is on a path of length smaller or equal to k (k-friends search) it adds one to the count of k-friends of i and stores the path from i to j in a dictionary with the start nodes as keys.</i><br /><i>Otherwise it returns 0 for the count (since i and j are connected by a path of length greater than k and therefore are not k-friends-instead they are k+1 or k+2, etc friends).</i><br /><i>A look at the TestClass.py and in particular at its __init__ method, reveals that for each test graph we are computing 2,3,4,5-friends. For most test graphs going above 3-friendship does not change the max number of friends.</i><br /><i>For example as we mentioned before, the max number of 3 and above friends for the 10 graph we have been using is always 9.</i><br /><i>But lets look at the graph from test_15. It consists of 50 people (0 to 49) and is depicted below.</i><br /><i>Some of the nodes are disconnected from the main graph (like 31-38 or 6-37-30). </i><br /><i>Running the code above, we learn that the max number of 2-friends is 12. The code tells us that only person 9 has that many 2-friends and gives us the following paths (of length 2 or less) from 9 to 12 other people.</i><br /><pre class="jqconsole jqconsole-blurred" style="background: none rgb(249, 249, 249); border: none; box-sizing: border-box; color: #222222; font-size: 1.2em; line-height: 1.2em; min-height: 100%; padding: 10px; position: relative; white-space: pre-wrap;"><span style="box-sizing: border-box;">person 9: 12</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;"> --------</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 1:[9, 35, 1]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 3:[9, 18, 3]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 12:[9, 35, 12]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 18:[9, 18]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 19:[9, 24, 19]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 21:[9, 18, 21]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 22:[9, 22]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 24:[9, 24]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 25:[9, 24, 25]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 34:[9, 24, 34]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 35:[9, 35]</span><span style="box-sizing: border-box;"><br /></span><span style="box-sizing: border-box;">Path from 9 to 47:[9, 18, 47]</span><br /></pre><i>These match with what we see in the graph below.<br />Next up it tells us that the max number of 3-friends is 19. There are a few people with that many 3-friends: 15, 21 and 33 (person 9 has 17 3-friends).<br />Next up the max number of 4-friends is 27 with only person 21 achieving that number.<br />Finally the max number of 5-friends is 31 with persons 15 and 21 having this number of 5-friends.</i><br /><i>You can, like before, run other tests by uncommenting them in the run_tests method of TestClass.py.</i><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-bTlchr9BTS0/VXn_xeQsyVI/AAAAAAAAAGs/qh5vV3Jhu6Y/s1600/friends2.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="http://3.bp.blogspot.com/-bTlchr9BTS0/VXn_xeQsyVI/AAAAAAAAAGs/qh5vV3Jhu6Y/s1600/friends2.jpg" /></a></div><i><br /></i></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-3067061849981034682015-05-23T22:52:00.000-07:002015-05-27T15:02:45.091-07:00Run Length Encoding a SwanRun Length Encoding (RLE) is a simple data compression scheme.<br />This scheme compresses strings by replacing consecutive characters by the number of occurrences of the character followed by that character.<br />For example aaaBBccD@@@ would be represented as 3a2B2c1D3@ or 3a2B2cD3@, i.e. the number 1 can be omitted when, like above with D, there is only one character. In this post we will leave the 1 out.<br />Each sequence of a repeated character is called a run thus the name Run Length Encoding.<br /><br />RLE or more complicated data compression schemes make modern communication possible: by reducing the size of images and videos by 20 times or more, the compressed image/video is much faster and cheaper to transmit.<br />Consider the following swan "image"<br /><pre><span style="font-size: 10px;"><br />@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@,,,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@.#S@@@@..%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@%:@@@@@@@@@S%,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@+@@@@@@@@@@@@@%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@.S@@@@@@@@@@@@@@@%+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@%@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@%@@@@@%@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@:+@@@@S%@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@*.@@@*##@@@@@@@@@@@@@,#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@*.@@@%.?@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@:?,@?*%#@@@@*%.%@@@@@@@+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@:.%@+.:@@@:%S@@S@@@@@@@?@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@?,@%:@@@:..@@@@@:@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@.@@:.#%*@@@@@@@@#@@@@@@,S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@%@@@#@@@@@@@@@@@@*@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@#*@@S,@@@@@@@@@@@@:@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@%+@@.?@@@@@@@@@@@@@:@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@?@,..@@@@@@@@@@@@@@S@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@#?#,@@@@@@@@@@@@@@@%@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@@,?@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@@S:@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@?@@@@@@@@@@@@@@@@@@@@@@@@::*+SSSSS.*:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@:.@@@@@@@@,%@@@@@@@@@@@@@@@@@@@@..%%?+.:,,,,,*.S?%%?@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@.,@@@@@@@@@@@@@@@,.?+,@@@@@@@@@@@@@@@@@?.@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@S@@@@@@@@@%@@@@@@@@@@@@@@:%S,@@@@@@@@@@@@@@@@@@@?,@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@*@@@@@@@@@@@@.%S@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@*#@@@@@@@@@%@@@@@@@@@@,%.@@@@@@@@@@@@@@@@@@@@@@@S*@@,..%??%%%%%S.:,@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@++@@@@@@@@@%%,@@@@@@@@@@@@@@@@@@@@@@@,%,%%.*@@@@@@@@@,:+?%S:@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@%:@@@@@@@@,%@@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@%#.@@@@@@@@@@@@@@@@@@,S%+@@@@@@@<br />@@@@@@@@@@@@@@@@@@@*,@@@@@@@@@%@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@,#.@@@@<br />@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@:@@@@@@,%@@@@@@@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@:%.@@@@@<br />@@@@@@@@@@@@@@@@@@#:@@@@@@@@@%@@@@@@+%@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%@@@@@@@@@@@@@@@@@@@@@@@%.@@@@@@@<br />@@@@@@@@@@@@@@@@@%:@@@@@@@@@.S@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*%@@@@@@@@@@@@@@@@@@@@@@..@@@@@@@@@<br />@@@@@@@@@@@@@@@@@.@@@@@@@@@@%@@@@:#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#,@@@@@@@@@@@@@@@@@@@@@#*@@@@@@@@@@<br />@@@@@@@@@@@@@@@@.@@@@@@@@@@:.@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@<br />@@@@@@@@@@@@@@@:%@@@@@@@@@@%@@@S.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%.@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@%@@@@@@@@@@@%@@SS@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.S@@@@@@@@@@@@@@@@@@@@@%,@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@*S@@@@@@@@@@*.@@S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,.@@@@@@@@@@@@@@@@@@@@@.*@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@#@@@@@@@@@@@%@.%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%S@@@@@@@@@@@@@@@@@@@@@@S@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@.:@@@@@@@@@@@%:%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S%@@@@@@@@@@@@@@@@@@@@@@*@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@%@@@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S.@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@,@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.%@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@S@@@@@@@@@@@@@,@@@@@@@@@@@@@@@@@@@@@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S%@@@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@?@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*%S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%%+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@:,,:*+%%#+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*S@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@.S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S.@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@#,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+S@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@?,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%*@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@,%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@+%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,.%%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@S#%..S.*:,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:S%%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@,,:*.+.%#%S.*,,@@@@@@@@@@@@@@@@@@@@,+.%%S*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,+:*.++SS...#..S.*,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br />@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@<br /></span><br /></pre>The image consists of only the 11 symbols<br /><h3>#, ?, %, . , S, +, ., *, :, , , @</h3>adding up to a total of 6400 characters (100 characters on each of 64 rows).<br />We can easily see that compressing this image using RLE will achieve a significant compression rate.<br /><h2 style="text-align: center;">Encoding</h2>How do we perform such compression?<br />First in the trinket code below notice how we have 2 files: one is the usual<b> main.py</b> and the other is named <b>data.py</b>.<br />This <b>data.py</b> file contains a single list called <b>swan</b>. Each element in the list is a row of the swan image above. So this list has 64 elements (64 rows) each with a string 100 characters long.<br /><br />Access to this list from <b>main.py</b> is achieved through the line<br /><br /><b>import data</b><br /><br />at the top of <b>main.py.</b> Then whenever we want to access the swan list we do<br /><br /><b>swan = data.swan </b><br /><br />We then loop through every element of the swan list. For each element we loop through each one of its characters and keep a running counter of how many consecutive identical characters there are. Once we detect a change of character we append the count and the character it counts to a string variable (rowEncoded) representing the RLE of the row, reset the counter to 1 and keep counting how many of the new character there are. If there is only one character we do not prepend the count to the character as mentioned above.<br /><br />This becomes perhaps clearer looking at the code<br /><b></b><br /><pre class="python" name="code"><b> <br />import data<br /><br />swan = data.swan<br /><br />'''<br />Given an image (represented by a list of its rows)<br />Run Length Encodes each row of the image and returns<br />the result as a list of the encoded image rows<br />'''<br />def encode(image):<br /> imageEncoded = []<br /> # loop through every image row<br /> for row in image:<br /> rowEncoded = ''<br /> count = 0<br /> char = row[0]<br /> # loop through every character in the row<br /> # and count how many consecutive elements of <br /> # that character are on that image row<br /> for character in row:<br /> # switching to a new character<br /> if char != character:<br /> # dont add 1 <br /> if count == 1:<br /> rowEncoded += char<br /> else:<br /> rowEncoded += str(count) + char<br /> char = character<br /> count = 1<br /> else:<br /> count += 1<br /> # encode the last character in the row<br /> if count == 1:<br /> rowEncoded += char<br /> else:<br /> rowEncoded += str(count) + char<br /> <br /> # add encoded row to list holding the image encoding<br /> imageEncoded.append(rowEncoded)<br /> return imageEncoded <br /> <br />imageEncoded = encode(swan)<br /></b></pre><b></b><br /><br />With this encoding the first 5 rows of the above swan image become <br /><pre class="jqconsole jqconsole-blurred" style="background: none rgb(249, 249, 249); border: none; box-sizing: border-box; color: #222222; font-size: 1.2em; line-height: 1.2em; min-height: 100%; padding: 10px; position: relative; white-space: pre-wrap;">100@<br />18@3,79@<br />14@.#S4@2.%:75@<br />13@%:9@S%,73@<br />12@+13@%.72@<br /></pre><br />Notice how the characters in each line add up always to 100 which is the number of characters in each row of the original image.<br /><br />In total there are now <span style="background-color: #f9f9f9; color: #222222; font-size: 1.2em; line-height: 1.2em; white-space: pre-wrap;">1196 </span>characters instead of the 6400 in the original image, i.e. 1196/6400 = 0.186 or 18.6 percent of the original characters.<br /><br /><h2 style="text-align: center;">Decoding</h2>To decode an image encoded with RLE (the inverse of what we just did) we again loop through each element of the list holding the encoded rows. For each such element we loop through its characters.<br />If the character is a digit we hold it in a counter variable. Otherwise we append the character following the digit as many times as the digit. If we find a character without a digit preceding it we assume it only appears once and thus we only append it once.<br /><br />Some important details are in order in this process: a character might appear more than 9 times in a row, i.e. 2 or more digits. For example above the second row is 18@3,79@. That is 18 @(s) followed by 3 , followed by 79 @(s). As we scan each of the characters we come across the 1 and store it in our count variable. The next character is also a digit, 8 so we want to store in our count variable<br /><br /><b>count = count*10+8 </b><br /><br />we need to remember though that 1 and 8 will be represented by their ASCII characters (49 and 56).<br />Therefore we should instead do, in python,<br /><br />count = count*10 + ord(character) - ord('0')<br /><br />since the python function ord will return the ascii (more properly the unicode) value of the character we pass it to it.<br /><br />Also because of the fact that the count can be greater than 9, we will assume for simplicity that our string does not have any numbers (otherwise a string like 222d that would be converted to 32d would seem to imply that d appears 32 times).<br /><br />The decode code in python is then<br /><pre class="python" name="code"><b> <br /><br />'''<br />Given a run length encoded image (represented by a list of its rows)<br />decode each row of the image and return<br />the result as a list of the unencoded image rows. It also<br />returns the total number of characters in both the <br />original encoded image and the unencoded image<br />'''<br />def decode(encodedImage):<br /> imageDecoded = []<br /> # loop through every image row<br /> for row in encodedImage:<br /> rowDecoded = ''<br /> count = 0<br /> char = row[0]<br /> # loop through every character in the row<br /> # and count how many consecutive elements of <br /> # that character are on that image row<br /> for character in row:<br /> # switching to a new character<br /> if character.isdigit():<br /> count = count*10 + ord(character)-ord('0')<br /> else:<br /> if count == 0:<br /> count = 1<br /> rowDecoded += character*count<br /> count = 0<br /> # add decoded row to list holding the image decoding <br /> imageDecoded.append(rowDecoded)<br /> return imageDecoded<br /> <br /></b></pre>Note how we do<br /><br />rowDecoded += character*count<br /><br />This will append <b>count</b> number of <b>character</b> to the string <b>rowDecoded</b>. It is a very short way of doing what we want rather than the more verbose way of looping <b>count</b> times and adding<b> character </b>each time to <b>rowDecoded</b>.<br /><br /><br /><b><span style="color: blue;">Assembling the encode and decode methods in a class RunLengthEncoding and a few tests in a Test class we end this post with the following python code </span></b><iframe allowfullscreen="" frameborder="0" height="600" marginheight="0" marginwidth="0" src="https://trinket.io/embed/python/07abfeaf36?start=result" width="100%"></iframe>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-2652812134091428792015-05-15T06:56:00.003-07:002015-05-20T17:48:44.444-07:00At how many intersections can the candy shop be? <style>.post-container { margin: 20px 20px 0 0; border: 2px solid #333; overflow: auto } .post-thumb { float: right } .post-thumb a { display: block } .post-content { margin-left: 2px } </style> <br /><div class="post-container"><div class="post-thumb"><a href="http://1.bp.blogspot.com/-FPlAxeY_NXA/VUmNaPQpNYI/AAAAAAAAAFE/hk1MKCr9ivo/s1600/CandyShop.JPG" imageanchor="1"><img src="http://1.bp.blogspot.com/-FPlAxeY_NXA/VUmNaPQpNYI/AAAAAAAAAFE/hk1MKCr9ivo/s1000/CandyShop.JPG" /></a></div><div class="post-content"><h3>The Reminiscences of Dr. Watson</h3><b>During the first week or so we had no callers, and I had begun to think that my companion was as friendless a man as I was myself.</b><br /><b>Presently, however, I found that he had many acquaintances, and those in the most different classes of society.</b><br /><b>There was one little sallow rat-faced, dark-eyed fellow who was introduced to me as Mr. Lestrade, and who came three or four times in a single week.</b><br /><b>One morning a young girl called, fashionably dressed, and stayed for half an hour or more.</b><br /><b>The same afternoon brought a grey-headed, seedy visitor, who appeared to me to be much excited, and who was closely followed by a slipshod elderly woman.</b><br /><b>On another occasion an old white-haired gentleman had an interview with my companion; and on another a railway porter in his velveteen uniform.</b><br /><b><br /></b><b>When any of these nondescript individuals put in an appearance, Sherlock Holmes used to beg for the use of the sitting-room, and I would retire to my bed-room.</b><br /><b>He always apologized to me for putting me to this inconvenience. "I have to use this room as a place of business," he said, "and these people are my clients."</b><br /><b>Again I had an opportunity of asking him a point blank question, and again my delicacy prevented me from forcing another man to confide in me.</b><br /><b>I imagined at the time that he had some strong reason for not alluding to it, but he soon dispelled the idea by coming round to the subject of his own accord.</b><br /><b>It was upon the 4th of March, as I have good reason to remember, that I rose somewhat earlier than usual, and found that Sherlock Holmes had not yet finished his breakfast.</b><br /><b>The landlady had become so accustomed to my late habits that my place had not been laid nor my coffee prepared.</b><br /><b>With the unreasonable petulance of mankind I rang the bell and gave a curt intimation that I was ready. Then I picked up a magazine from the table and attempted to while away the time with it, while my companion munched silently at his toast.</b><br /><b>Suddenly several strong knocks on the door arose me from my stupor. My companion sprang up quickly and opened the door. A very old gentleman stood at the entrance.</b><br /><b>Mr. Sherlock Holmes motioned the visitor to the sitting-room and turning to me said "Watson would you be so kind as to follow us?".</b><br /><b> A bit intrigued, I inspected the old man carefully; despite his age, he moved confidently and still looked as if he was at the top of his faculties. There was, however, a sadness in his gaze.</b><br /><b>"This is Mr. Radnoor" introduced my companion, "and this is Dr. Watson." "If am not mistaken Mr. Radnoor's story is of the particularly unusual sort". Sherlock pointed the visitor to one of the chairs, and we all sat. "Thank you Mr. Holmes." After a short pause and a sigh the old man started his story.</b><br /><b>"It all started many many years ago when I was a small boy growing up in Stadford.</b><br /><b> I did small jobs for Dr. Cavetar that often carried me all across town.</b><br /><b>During one of these assignments I came across a candy shop with the most unusual assortment of candy I had ever seen.</b><br /><b>Behind the counter was the prettiest girl I had ever seen as well. Timidly at first, then growing in confidence I ordered this and that candy and soon I had enough for a month. The young lady neatly packed my order and handed it to me with the most beautiful of smiles.</b><br /><b>Stuttering, I thanked her and walked away.</b><br /><b>In the next few days whenever I ate one of the candies I couldn't dispel the memory of the girl's smile.</b><br /><b>I returned often to the store and in due time the beautiful lady became Mrs. Radnoor.</b><br /><b>We moved across country, then to India and lived a wonderful life together." </b><br /><b>At this point, the old man pulled his handkerchief and wiped away a tear. </b><br /><b>"Mrs. Radnoor died a week ago." he explained. </b><br /><b>"I have not had a night's sleep since then. I would like to return to the candy shop of my youth were it all started. It has been many years though and my memory is not what it used to be. I do not remember where exactly the shop is located and I thought you could help me."</b><br /><b>Sherlock Holmes bent forward and prompted the gentleman "Please do tell us everything you still remember about that shop."</b><br /><br /><b>Mr. Radnoor looked pensive before saying "These are the facts I remember:"</b><br /><ul><li><b>"I do remember that from any given point (x,y) in the city of Statford I could move to the four neighboring (x-1,y), (x,y-1), (x+1,y),(x,y+1) points in a quarter hour.</b></li><li><b>I also recall that the ith time I went to the candy shop I went from point (x[i],y[i]) and drove for not more than a quarter hour * L[i]. </b></li><li><b>The candy shop was located at a point with integer coordinates. </b></li><li><b>I never walked more than 5 hours-this happened on the day I asked Mrs. Radnoor to marry me- (i.e. L[i] was at most 20).</b></li><li><b>The coordinates (x[i],y[i]) are within the rectangle (-20, 20), i.e. -20<=x[i], y[i]<= 20).</b></li><li><b> Dr. Cavetar's office was at (0,0).</b></li></ul><b> I am afraid that is all I can tell you".</b><br /><b><br /></b><b>Sherlock Holmes rose and guaranteed to Mr. Radnoor that he would have a solution with the number of possible locations as well as corresponding paths from the starting position to those candy shop locations by next day. The gentleman's eyes glinted with gratitude and he thanked my companion profusely.</b><br /><b><br /></b><b>"What do you make of it, Watson?". </b><br /><b>"Well, lets say he did one visit to the candy shop and walked for at most a quarter hour. We know that he either didn't move, in which case the candy shop would be at Dr. Cavetar's office or he moved once in which case the candy shop could be at (1,0),(0,1),(-1,0),(0,-1). I.e. the candy shop could be at 5 different locations.</b><br /><b>If he walked for at most half an hour, then besides these 5 locations he could have from each of the one step locations reached 8 more making it 13 locations. That is an awful lot of locations. How do you think we can help him?".</b><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="http://4.bp.blogspot.com/-uXQ7N9c7DLo/VU7-ejcjJhI/AAAAAAAAAFY/MSI5XKfzXZo/s1800/candyshop1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="203" src="http://4.bp.blogspot.com/-uXQ7N9c7DLo/VU7-ejcjJhI/AAAAAAAAAFY/MSI5XKfzXZo/s640/candyshop1.jpg" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Dr. Watson second example: 13 locations for the candy shop. The paths in red take half an hour to reach from (0,0). The paths in black take only a quarter of an hour.</td></tr></tbody></table><br /><b>"Do not be so pessimistic Watson. The case can be less complicated. Lets imagine Mr. Radnoor starts at point (2,1) in his first visit and walks at most half an hour. Then we have 13 possible locations as you pointed out. In his second visit lets say he starts at (3,-1) and also walks at most half an hour. Then among the 13 possible locations from (2,1) only those that are reachable from (3,-1) are possible locations for the shop. There are only 4 locations like that: (2,-1), (3,0), (3,1) and (2,0)."</b><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody><tr><td style="text-align: center;"><a href="http://3.bp.blogspot.com/-LkBpA-KrSqk/VU7_QEAt0AI/AAAAAAAAAFg/e8fpS1MErxg/s1600/candyshop2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="204" src="http://3.bp.blogspot.com/-LkBpA-KrSqk/VU7_QEAt0AI/AAAAAAAAAFg/e8fpS1MErxg/s1800/candyshop2.jpg" width="640" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Sherlock example: There are only 4 possible locations for the candy shop. (3,1) and (2,0) takes a quarter of an hour to reach from (2,1) but half an hour from (3,-1). On the contrary (2,-1) and (3,0) takes a quarter of an hour to reach from (3,-1) but half an hour from (2,1).</td></tr></tbody></table><b>"Interesting example Holmes. If he went a third time to the shop from (5,0) and walked at most three quarters of an hour, there would then be only 3 possible locations: (3,0), (3,1) and (2,0). He could not reach (2,-1) from (5,0) in at most three steps." </b><br /><b><br /></b><b>"Exactly my dear Watson. How to solve the problem in general you may ask. To find the number of possible locations of the candy shop is elementary. Here it is the thought process:</b><br /><br /><ul><li><b>Let (csx, csy) be the location of the candy shop (these are integers!). The maximum values of csx and csy are (x[i],y[i]) + L[i] since at most the gentleman moves L[i] units. Since x[i],y[i] and L[i] can at most be 20, this comes to a maximum value of 40. </b></li><li><b>Similarly the minimum value of csx,csy will be -40 (when x[i]= -20 or/and y[i]=-20 and L[i]=20 and we move 20 steps in the negative direction).</b></li><li><b>So we can consider every single point inside or on the boundary of the rectangle -40, 40 as a candidate for the candy shop location. </b></li><li><b>For each such point (csx,csy) in the rectangle, lets define the distance between the candy shop and (x[i],y[i]) as abs(x[i]-csx)+abs(y[i]-csy). This is really the number of quarter hours Mr. Radnoor walks from (x[i],y[i]). We know this number is at most L[i].</b></li><li><b>(csx,csy) will only be a valid location if this distance (which is called the Manhattan distance) is smaller or equal than L[i] for every i."</b></li></ul><b>This translates to Python as </b><br /><pre class="python" name="code">def countPossibleLocations(self, P, L):<br /> count = 0<br /> candy_shop_locations = []<br /> for csx in range(-41,41):<br /> for csy in range(-41, 41):<br /> possible = True<br /> # For each possible (csx,csy) compute the Manhattan distance to <br /> # each point (x[i],y[i]). If that distance is <= than L[i]<br /> # for every (x[[i],y[i]) then (csx,csy) is a possible location<br /> for i in range(0, len(P)):<br /> manhattan = abs(P[i][0] - csx) + abs(P[i][1] - csy)<br /> possible = possible and (manhattan <= L[i])<br /> if possible:<br /> count += 1<br /> candy_shop_locations.append((csx,csy))<br /> return count,candy_shop_locations<br /></pre><br /><b>Notice how we store the coordinates of the possible candy shop locations in a list that is also returned by this method.</b><br /><b><br /></b><b>To find the paths that lead from each starting point (x[i],y[i]) to each (csx,csy) candy shop possible location in at most L[i] number of steps is also elementary: The Manhattan distance between (csx,csy) and a starting point is the shortest distance between those two points. We know from the discussion above that this distance is always <=L[i].</b><br /><b>A possible path from (x[i],y[i]) with this length is to move along say the x direction until the x coordinate matches csx and then move along the y direction until the y coordinate matches csy.</b><br /><b>The only other detail we need to pay attention is that if csx is to the left of x[i] we need to move left otherwise we move right. Similarly for csy and y[i] (up or down).</b><br /><b> </b><b>In Python</b><br /><pre class="python" name="code"> def findPaths(self,Cs,P): <br /> paths = []<br /> for i in range(0,len(P)): </pre><pre class="python" name="code"> for j in range(0,len(Cs)):<br /> path = []</pre><pre class="python" name="code"> # move left<br /> if Cs[j][0]< P[i][0]:<br /> stepx = -1</pre><pre class="python" name="code"> # move right<br /> else:<br /> stepx = 1<br /> stepsx = 0<br /> path.append([P[i][0],P[i][1]])</pre><pre class="python" name="code"> #go along the x axis until Cs[j][0] and P[i][0] match<br /> for x in range(0,abs(Cs[j][0]-P[i][0])):<br /> stepsx += stepx<br /> path.append([P[i][0]+stepsx,P[i][1]])</pre><pre class="python" name="code"> # move down<br /> if Cs[j][1]< P[i][1]:<br /> stepy = -1</pre><pre class="python" name="code"> # move up<br /> else:<br /> stepy = 1<br /> stepsy = 0</pre><pre class="python" name="code"> #go along the y axis until Cs[j][1] and P[i][1] match<br /> for y in range(0,abs(Cs[j][1]-P[i][1])):<br /> stepsy += stepy<br /> path.append([P[i][0] + stepsx,P[i][1]+stepsy])<br /> <br /> paths.append(path)<br /> <br /> return paths<br /> <br /></pre><b>For example for the example that you talked about before Watson where the starting locations (x[[i],y[i]) and the maximum number of steps L[i] are </b><br /><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">[(2, 1), (3, -1), (5, 0)] num of steps [2, 2, 3]</pre>The possible candy shop locations are<br /><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">Locations [(2, 0), (3, 0), (3, 1)]</pre>And the possible shortest paths as computed by the method above will be <br /><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">Possible paths <br />[[2, 1], [2, 0]]<br />[[2, 1], [3, 1], [3, 0]]<br />[[2, 1], [3, 1]]<br />[[3, -1], [2, -1], [2, 0]]<br />[[3, -1], [3, 0]]<br />[[3, -1], [3, 0], [3, 1]]<br />[[5, 0], [4, 0], [3, 0], [2, 0]]<br />[[5, 0], [4, 0], [3, 0]]<br />[[5, 0], [4, 0], [3, 0], [3, 1]]</pre><b>The first, third and fifth paths takes only a quarter hour (one step). </b><br /><b>The second, fourth, sixth and eighth paths take half an hour (2 steps).</b><br /><b>The seventh and ninth paths take three quarters of an hour (3 steps). </b><br /><b>One final point is that these paths are not the only possible shortest paths. </b><br /><b>They always follow first along the x axis then along the y axis. </b><br /><b>Another possibility would be to always start along the y axis and once the y coordinates match start moving along the x axis. </b><br /><b>And many other shortests paths exist that result from moving sometimes along the x axis sometimes along the y axis in a non predictable way (Mr. Radnoor could move in a random direction each step as long as he goes from (x[i],y[i]) to (csx,csy). </b><br /><b><br /></b><b>Gathering all the pieces we have the following Python code</b><br /><div class="separator" style="clear: both; text-align: center;"><iframe src="https://trinket.io/embed/python/6ce3e2640c?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe></div><b><br /></b></div></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-69369624479320802002015-05-11T19:13:00.000-07:002015-05-20T17:48:52.814-07:00Blackjack wins and losses<style>.post-container { margin: 20px 20px 0 0; border: 2px solid #333; overflow: auto } .post-thumb { float: right } .post-thumb a { display: block } .post-content { margin-left: 2px } </style> <br /><div class="post-container"><div class="post-thumb"><a href="http://2.bp.blogspot.com/-NEivCbQ-j1A/VTvdi098F7I/AAAAAAAAADk/oLoQYSqmrus/s1150/BlackJackWinner.jpg" imageanchor="1"><img src="http://2.bp.blogspot.com/-NEivCbQ-j1A/VTvdi098F7I/AAAAAAAAADk/oLoQYSqmrus/s900/BlackJackWinner.jpg" /></a></div><div class="post-content"><b>Blackjack, also known as twenty-one, is the most widely played casino game in the world.</b></div><div style="color: black;"><b>The basic rules of Blackjack are (there are several variations/extensions of these rules)</b></div><ul style="color: black;"><li><b>The goal of blackjack is to beat the dealer's hand without going over 21.</b></li><li><b>Face cards are worth 10. Aces are worth 1 or 11, whichever makes a better hand. All other cards are worth their numeric value.</b></li><li><b>Each player starts with two cards, one of the dealer's cards is hidden until the end. The player and dealer add the value of their two cards to figure out the value they have.</b></li><li><b>To 'Hit' is to ask for another card. To 'Stand' is to hold your total and end your turn.</b></li><li><b>If a player goes over 21 he/she busts, and the dealer wins regardless of the dealer's hand.</b></li><li><b>If a player scores lower than the dealer then he/she loses his/her bet.</b></li><li><b>If the player scores higher than the dealer or the dealer goes over 21, and the player does not go over 21, then the player wins his bet (in addition to keeping his original wager).</b></li><li><b>If the player is dealt 21 from the start (Ace & 10), he/she has a blackjack.</b></li><li><b>Blackjack usually means the player wins 1.5 the amount of his/her bet. Depends on the casino.</b></li><li><b>If both dealer and player have a blackjack, then the hand is a push. Note that if the dealer has a blackjack, and the player has a 21 (but does not have blackjack), then the dealer wins, and the player loses his wager.</b></li><li><b>Dealer will hit until his/her cards total 17 or higher.</b></li></ul><div style="color: black;"><b>Imagine we would like to know the amount of money a player wins or loses in a hand. We know the bet the player put on, the dealer and player's score and whether the dealer and the player have a blackjack or not.</b></div><div style="color: black;"><b>There are only four possibilities based on the rules above: </b></div><b><br /></b><ul><li><b>If the player has a blackjack and the dealer does not have a blackjack the player wins 3/2*bet.</b></li><li><b>If the player and the dealer both have a blackjack the player keeps his wager and neither side loses, so the player wins 0.</b></li><li><b>If the player goes over 21, he or she loses -bet.</b></li><li><b>If the player scores higher than the dealer or the dealer goes over 21 (but the player does not go over 21) the player wins +bet.</b></li></ul><b><br /></b><b>To avoid rounding issues when the player wins with blackjack, lets assume that the bet is always an even number of dollars. Then the four possible outcomes can be translated to a set of if statements in Python as follows </b><br /><pre class="python" name="code"><b> <br /> def blackjackWinsAndLosses(self, bet, dealerScore, playerScore, dealerHasBlackjack, playerHasBlackjack):<br /> # player loses<br /> if playerScore > 21 or (playerScore < dealerScore and dealerScore<=21):<br /> return -bet<br /> # neither player nor dealer win<br /> if dealerHasBlackjack and playerHasBlackjack:<br /> return 0<br /> # dealer has blackjack but player does not, player loses<br /> if dealerHasBlackjack and not playerHasBlackjack:<br /> return -bet<br /> # player has blackjack but dealer does not<br /> if playerHasBlackjack and not dealerHasBlackjack:<br /> return 3/2.0*bet<br /> # dealer has more than 21 or player's score is higher than dealer<br /> if dealerScore > 21 or playerScore > dealerScore:<br /> return bet<br /> return 0<br /></b></pre><b>The only tricky part of this problem is taking into account all the conditions correctly. </b><br /><b>For example, if we exchanged the last if statement with the first if statement we would get an incorrect result if the dealer had a blackjack (resulting in a loss for the player instead of a win).</b><br /><b>Another potential source of confusion is if both player and dealer have more than 21. In that case the player loses even if its score is higher than the dealer's score. </b><br/><b><span style="color: blue;">The following Python code gathers all the pieces and tests the method above.</span></b></div><br /><div class="separator" style="clear: both; text-align: center;"><iframe src="https://trinket.io/embed/python/da774a7f09?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com2tag:blogger.com,1999:blog-1274195019136560947.post-9541041931558848622015-05-05T08:03:00.001-07:002015-05-20T16:13:17.272-07:00How tall is my tower?<div style="align: right; background-size: cover; background: url("http://3.bp.blogspot.com/-ghuIwlSbb08/VU_BUsosmhI/AAAAAAAAAGE/exl6r6cNrFE/s1200/BlockTower3.JPG"); color: black; padding: 50px;"><b><span style="color: #274e13;">Little Nicole just turned one. </span></b><br /><b><span style="color: #274e13;">She can stand for the first time. </span></b><br /><b><span style="color: #274e13;">She wonders the heights she can reach.</span></b><br /><b><span style="color: #274e13;">She peers through her dad's bookshelves.</span></b><br /><b><span style="color: #274e13;">She pulls the books one by one and stacks them up. </span></b><br /><b><span style="color: #274e13;">She asks her mom for water and tries to grab the cup from the cupboard. </span></b><br /><b><span style="color: #274e13;">At night she stands on her crib and demands that a story be told or else she will climb out of it.</span></b><br /><b><span style="color: #274e13;">But her favorite pastime is to build a tower with her wooden blocks.</span></b><br /><b><span style="color: #274e13;">Her blocks have numbers 0,1,2,...painted on them and the most curious thing is that they have different heights. The heights are always an integer number of inches.</span></b><br /><b><span style="color: #274e13;">Little Nicole always piles the blocks in a single column and in order with the bottom block having the lowest number (0) and the top block having the highest number n-1. </span></b><br /><br /><b><span style="color: #274e13;">She stacks the blocks one by one and becomes ever more careful as she approaches the highest she can reach. </span></b><br /><b><span style="color: #274e13;">Sometimes there are accidents halfway. She gets too excited picking and placing the blocks, tumbles and the whole enterprise comes crashing down with Nicole.</span></b><br /><b><span style="color: #274e13;">Sometimes there are accidents because the tower gets too tall and little Nicole cant reach higher. When she tries to put one more while standing on her tip toes she loses her balance and it is a big disaster. </span></b><br /><b><span style="color: #274e13;">Sometimes she will climb on top of her little chair and keep adding blocks. But with each new block the tower gets more and more tilted and suddenly boom the top half falls down.</span></b><br /><b><span style="color: #274e13;">One day her dad splits the blocks into two groups. One of the groups has only blocks with even heights. The other has only blocks with odd height.</span></b><br /><b><span style="color: #274e13;">He then gives Nicole a challenge: </span></b><br /><b><span style="color: #274e13;">Following her rules (see above) build the tallest possible tower without ever putting a block of even height on top of a block of odd height. </span></b><br /><b><span style="color: #274e13;">For example if block 0 has height 4 and block 1 has height 7 the tallest tower would be 11 with 4 at the bottom. But if we reverse the heights, i.e. block 0 has height 7 and block 1 has height 4, the tallest tower would be 7 because block 1 has an even height and cant go on top of block 0 which has an odd height.</span></b><br /><b><span style="color: #274e13;"><br /></span></b><b><span style="color: #274e13;">Little Nicole starts eagerly </span></b><b><span style="color: #274e13;">alternating blocks from either group on top of each other. Her dad promptly tells her this will not work. </span></b><br /><b><span style="color: #274e13;">He gives her a few hints: </span></b><br /><br /><ul><li><b><span style="color: #274e13;">If she picks an odd height block first then all the blocks will have to be odd. Depending on the blocks' heights this might (or not) make the tallest tower.</span></b></li><li><b><span style="color: #274e13;">If she picks an even block first it is possible that the tallest tower might be made entirely of even height blocks.</span></b></li><li><b><span style="color: #274e13;">In general if she starts with an even block the pattern will be even, even,...,even, odd, odd,...,odd, i.e. once she switches from even to odd she can not switch back to even.</span></b></li><li><b><span style="color: #274e13;">There might be several towers all with the same height but different placement of the even and odd blocks. </span></b></li></ul><br /><b><span style="color: #274e13;">He then shows her some examples with 2 and 3 blocks.</span></b><br /><b><span style="color: #274e13;">Nicole's dad realizes that it is not obvious how to find the sequence that yields the tallest tower when dealing with four or more blocks and decides to write some code to help him obtain this sequence given a set of blocks' heights.</span></b><br /><b><span style="color: #274e13;"><br /></span></b><b><span style="color: #274e13;">A simple strategy to find the tallest tower is </span></b><br /><b><span style="color: #274e13;">a) Compute how tall is the height of a tower with only n odd height blocks. </span></b><br /><b><span style="color: #274e13;">b) Then compute the height of a tower with only one even height block at the bottom and n-1 odd height blocks above it. </span></b><br /><b><span style="color: #274e13;">c) Then compute the height of a tower with only two even height blocks at the bottom and n-2 odd height blocks above these two. </span></b><br /><b><span style="color: #274e13;">d) And so on until all the blocks have an even height. </span></b><br /><b><span style="color: #274e13;">If we keep track of the tallest tower of these we will get the answer.</span></b><br /><b><span style="color: #274e13;"><br /></span></b><b><span style="color: #274e13;">We can ask ourselves how does this compare to the tallest tower built under the reverse rule that an odd height block can not go on top of an even height block. </span></b><br /><b><span style="color: #274e13;"><br /></span></b><b><span style="color: #274e13;">And what if little Nicole simply put the blocks in order from 0 (at the bottom) to n (at the top)? We can convince ourselves that this will always result in a tower as tall as possible. That's because this tower will use all the blocks while the two other procedures might not.</span></b><br /><b><span style="color: #274e13;"><br /></span></b><b><span style="color: blue;">The following code computes, for a given number of blocks with differing heights, what the tallest tower is under each of the three approaches: even blocks can never go on top of odd ones, odd blocks can never go on top of even ones or simply stack the blocks from label 0 to label n-1. It also displays the respective towers. </span></b><br /><b><span style="color: blue;">For example in the last test the blocks are (from label 0 to label 10)</span></b><br /><span style="background-color: #eeeeee;"><br /></span><span style="background-color: #eeeeee;">[44, 3, 44, 3, 44, 47, 2, 47, 2, 47, 2]</span><br /><b><span style="color: blue;"><br /></span></b><br /><b><span style="color: blue;">The highest tower with no even height block on top of an odd height block is 44,44,44,47,47,47. The tallest tower with no odd height block on top of an even height block is 3,3,47,47,47,2. But notice that the tower 47,47,47,3,3,2 has the same height as does the tower 3,47,3,47,47,2.</span></b><br /><b><span style="color: blue;">Basically given a tallest tower, any permutation of the even height blocks and any permutation of the odd height blocks will lead to a tower with the same (tallest) height.</span></b></div><div width="1500px"><div class="separator" style="clear: both; text-align: center;"><iframe src="https://trinket.io/embed/python/c46943988f?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe></div></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-34125965860520465742015-04-18T17:45:00.001-07:002015-05-20T16:11:10.899-07:00How many carrots on a line?<div style="background-attachment: initial; background-clip: initial; background-image: url(http://4.bp.blogspot.com/-hl2REobjFqs/VQ92Qr3NEqI/AAAAAAAAABo/yWSy8w9zIvA/s1200/DreamingAboutCarrots.JPG); background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; padding: 10px;"><b><span style="color: #274e13;">You live a simple and happy life in your farm.</span></b><b><span style="color: #274e13;"> </span></b><br /><b><span style="color: #274e13;">You grow all sorts of vegetables in the fields.</span></b><br /><b><span style="color: #274e13;">Some days of the year, you toil the soil all day planting carrots, tomatoes, lettuce, cabbage, beet, pepper and many others. </span></b><br /><b><span style="color: #274e13;">At night you are so tired that you sleep deeply and without any dreams. </span></b><br /><b><span style="color: #274e13;">The rains come and the fields become a deep luxuriant green with spots of red, yellow, orange, purple and patches of mint green.</span></b><br /><b><span style="color: #274e13;">One day while harvesting that season's carrots, you sit midday on a rock for a brief respite. Lines and lines of carrots extend in every direction. </span></b><br /><span style="color: #274e13;"><b>The sun shines strongly above. You are thirsty and tired. Suddenly you see some leaves move slightly. As in a dream (perhaps you did indeed take a nap?) you see a neatly dressed carrot man approach you.</b></span><br /><span style="color: #274e13;"><br /></span><b><span style="color: #274e13;">"Good day sir" says the carrot man. After a short pause as if expecting you to say something he continues "we see you working all day pulling our neighbors from the soil and we ask each other how long before we too will be taken from our homes?".</span></b><br /><span style="color: #274e13;"><b><br /></b><b>"I have never thought of it that way. I don't even know how many of you there are?" you mumble a bit embarrassed.</b></span><br /><b><span style="color: #274e13;">"There is a very simple way to estimate that sir. Imagine that there is one carrot being living at each integer set of coordinates (x,y) of this field.. Then you certainly can figure out how many carrots lie in the line between any two carrots at coordinates (x1,y1) and (x2,y2)? If you then extend your reasoning to find how many carrots are in a rectangle that has its diagonal given by the same line segment you can find out how many of us there are."</span></b><br /><b><span style="color: #274e13;">Having completed this discourse the carrot man turned and slowly walked to the neighboring row of carrots, past it and soon he had disappeared among the greenery.</span></b><br /><span style="color: #274e13;"><b>After this conversation you hesitate going back to your carrot pulling task. You try to solve the problem posed by the carrot man instead. How many carrots there are in the line segment between two carrots? And how many carrots lie in a rectangle whose diagonal is given by the same line segment?</b></span><br /><h1 style="text-align: center;"><span style="color: #274e13;">How many carrots on a line?</span></h1><h3><span style="color: #274e13;"><u>Cross Product</u></span></h3><b><span style="color: #274e13;">Given two carrots at (x1,y1) and (x2,y2) a simple strategy is the following:</span></b><br /><b><span style="color: #274e13;">Consider all carrots that lie inside (but not on the border) of a rectangle where the lower left corner is at coordinates min(x1,x2), min(y1,y2) and the top right corner is at coordinates max(x1,x2),max(y1,y2). </span></b><br /><b><span style="color: #274e13;">We can check for each of these carrots whether they lie or not in the segment connecting (x1,y1) to (x2,y2). How? </span></b><br /><b><span style="color: #274e13;">Form the vector that joins the two ends of the segment. Its components will be (max(x1,x2)-min(x1,x2), max(y1,y2)-min(y1,y2)). </span></b><br /><b><span style="color: #274e13;">Then form the vector connecting the lower left corner of the rectangle at (min(x1,x2),min(y1,y2)) to the point inside the rectangle at integer coordinates (i,j). </span></b><br /><b><span style="color: #274e13;">This vector has coordinates (i-min(x1,x2)),j-min(y1,y2)). </span></b><br /><b><span style="color: #274e13;">The point lies on the segment when the angle between these 2 vectors is zero.</span></b><br /><span style="color: #274e13;"><br /></span><span style="color: #274e13;"><b>The cross product of these two vectors is the product of their magnitudes times the sin of the angle between them. Therefore the cross product will vanish if these two vectors are collinear, i.e. if the point lies on the segment.</b></span><br /><b><span style="color: #274e13;">The cross product is a vector parallel to the z axis (the axis perpendicular to the field where the carrots lay) with value</span></b><br /><div style="text-align: center;"><h3><b><span style="color: cyan;">(i-min(x1,x2))*(max(y1,y2)-min(y1,y2)) - (j-min(y1,y2))*(max(x1,x2)-min(x1,x2))</span></b></h3></div><span style="color: #274e13;"><b><br /></b><b>All points inside the rectangle for which this difference is zero, are on the line segment.</b></span><br /><h3><b style="color: #274e13;"><u>Greatest Common Divisor (GCD)</u></b></h3><span style="color: #274e13;"><b>Since we are dealing with integers, there is another way we can find the number of points using number theory.</b></span><br /><span style="color: #274e13;"><b><br /></b><b>Without loss of generality we can always put the lower left corner of the rectangle at the origin of the coordinates (0,0) and the top right corner at the point (x2-x1,y2-y1) (assuming x2>x1 and y2>y1). The rectangle has sides of length (x2-x1) and (y2-y1).</b></span><br /><span style="color: #274e13;"><b><br /></b><b>All integer points on this segment must obey the line equation y=(y2-y1)/(x2-x1)x. Or y/x=(y2-y1)/(x2-x1).</b></span><br /><span style="color: #274e13;"><b><br /></b><b>Lets suppose that the GCD of (y2-y1) and (x2-x1) is ...GCD. We can write</b></span><br /><b style="color: #274e13;"><br /></b><b><span style="color: cyan;">y = GCD*p/(GCD*q)x</span></b><br /><b><span style="color: #274e13;"><br />where p and q are relatively prime (coprime), i.e. they have no common divisors.</span></b><br /><span style="color: #274e13;"><b><br /></b><b>It is clear then that the following integer points are on the segment: (q,p), (2q,2p), (3q,3p),..., ((GCD-1)x, (GCD-1)y). Therefore there are GCD-1 integer points/carrots in the segment (excluding the endpoints).</b></span><br /><span style="color: #274e13;"><b><br /></b><b>For an example consider (x2-x1)=10 and (y2-y1)=15. Then y/x=3*5/(2*5). Pairs (2,3), (4,6), (6,9), (8,12) are all in the segment. The GCD is 5 and there are 4 points on the segment.</b></span><br /><span style="color: #274e13;"><b><br /></b><b>This also shows that if (x2-x1) and (y2-y1) are coprimes (i.e. they dont have any common divisors), there can not be any integer point lying on the segment (other than the endpoints).</b></span><br /><b><span style="color: #274e13;">Put another way dividing the rectangle of size (x2-x1,y2-y1) into the greatest number of identical rectangles is equivalent to finding the greatest common divisor of (x2-x1) and (y2-y1).</span></b><br /><br /><h1 style="text-align: center;"><b><span style="color: #274e13;">How many carrots in a rectangle?</span></b></h1><b><span style="color: #274e13;">Lets now look at the second question:</span></b><br /><b><span style="color: #274e13;">How many carrots are inside the rectangle whose diagonal is the segment from (x1,y1) to (x2,y2)?</span></b><br /><b><span style="color: #274e13;">The easiest way to count those is to count them as we loop through every point of integer coordinates on or inside the rectangle.</span></b><br /><b><span style="color: #274e13;"><br /></span></b><b><span style="color: #274e13;">But since the problem is so easy we can try to be clever and come up with a formula for this number.</span></b><br /><b><span style="color: #274e13;"><br /></span></b><b><span style="color: #274e13;">To find out how many carrots are right on the rectangle border we could use the cross product or gcd methods above applied to each of the four sides of the rectangle. Actually the top and bottom sides will have the same number of carrots as will the left and right sides so we can just use two sides and multiply by two.</span></b><br /><b><span style="color: #274e13;">But it is easier to do things manually:</span></b><br /><b><span style="color: #274e13;">The bottom side will have (x2-x1)+1 points (because of the origin). Adding the top side this gives</span></b><br /><b><span style="color: #274e13;">2[x2-x1+1]. The left and right side contribute 2[y2-y1+1]. But 4 of the points are counted twice, so</span></b><br /><b><span style="color: #274e13;">the total number of carrots on the boundaries of the rectangle is</span></b><br /><b><span style="color: #274e13;">2[x2-x1+1+y2-y1+1-2]=2(x2-x1+y2-y1)</span></b><br /><b><span style="color: #274e13;"><br />How many carrots will be inside the rectangle? Divide the rectangle by vertical lines parallel to its left and right sides and starting at integer values of x. There will be (x2-x1)-1 of those lines (excluding the left and right sides). For each of those lines there will (y2-y1)-1 points with integer y coordinates. So there will be a total of [x2-x1-1][y2-y1-1] interior carrots.</span></b><br /><b><span style="color: #274e13;"><br />The total number of carrots in the rectangle (interior and boundary) is then</span></b><br /><b><br /><span style="color: cyan;">(x2-x1)(y2-y1)+ (x2-x1+y2-y1)+1 </span></b><br /><b><span style="background-color: white;"><span style="color: #38761d;"><br /></span></span></b> </div><b><span style="background-color: white; color: blue;">The following code implements both the cross product and gcd solutions. In particular notice the implementation of gcd using the Euclidean algorithm. The code also counts the number of points inside and on the rectangle and compares it with the formula above.</span><br /> <br /></b><br /><div width="1500px"><iframe src="https://trinket.io/embed/python/6b5ac0a709?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-74642447575932869972015-03-26T18:56:00.000-07:002015-05-20T16:37:54.272-07:00The Longest River Jump<div style="background-size: cover; background: url("http://1.bp.blogspot.com/-K1gTdnTxJ98/VQ9x88DJA3I/AAAAAAAAABc/q2MXUpE-PYU/s1600/Swimmer'sDelight.JPG"); color: black; padding: 10px;"><b>A frog needs to cross a river that is 10 feet wide. </b><br /><br /><b>There are 2 stones in the water she can jump on. </b><br /><br /><b>A few jumps are needed, but her only concern is the longest one. </b><br /><br /><b>This is obviously the most problematic, so she wishes to choose a path that makes this jump as small as possible. </b><br /><br /><b>The length of a jump between two stones of coordinates (x1,y1) and (x2,y2) is the Euclidian distance: </b><br /><br /><b>sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) </b><br /><br /><b>The edge of the shore where the frog initially stands is at x=0 and runs along the y-axis (it is the y-axis). </b><br /><br /><b>This means that the minimal distance between the shore and the first stone the frog jumps on is the x-value of the location of that stone. </b><br /><br /><b>The edge of the opposite shore is at x=10 and runs also along the y-axis (i.e. the 2 shores are parallel to the y-axis). </b><br /><br /><b>The x-coordinates of the 2 stones are given in a list x [x1, x2] and the y-coordinates are given in a list y [y1,y2]. </b><br /><br /><b>Clearly each path will have a jump that is the longest. </b><br /><br /><b>The question is then how to find the path where the longest jump is the smallest possible among all possible paths and to actually compute the length of its longest jump. This is the smallest longest jump the frog needs to make. We will round it to the nearest integer (just to make testing easier)? <br /><br />For example imagine the 2 stones are both located at y=5, one at x=3 and the other at x=7 (i.e. [x1=3,x2=7], [y1=5,y2=5]). <br /><br />An inexperient or playful frog might hop from (x=0,y=5) to the stone at (x2=7,y2=5) (a jump of length 7), then jump to the stone at (x1=3,y1=5) (a jump of length 4) and from there jump to the shore at (x=10, y=5) (another jump of length 7). <br /><br /> The longest jump in this case is 7 (2 jumps of 7). <br /><br />But our frog is craftier. She first jumps from (x=0, y=5) to the stone at (x1=3,y1=5) (a jump of length 3), then jumps to the stone at (x2=7,y2=5) (a jump of length 4) and from there reaches the other shore with a jump of length 3 (to x=10,y=5). <br /><br />The longest jump in this case is 4. This path is indeed the smallest longest jump for the given position of the two stones. The situation is illustrated bellow</b><br /><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"></div><table cellpadding="0" cellspacing="0" class="tr-caption-container" style="background-color: rgba(255,255,255,0.5); float: left; margin-right: 1em; text-align: left;"><tbody><tr><td style="text-align: center;"><a href="http://1.bp.blogspot.com/-5J48f0bFbRA/VR9xgXGwYvI/AAAAAAAAACw/g6IesFX39hE/s1600/jumpexample.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" src="http://1.bp.blogspot.com/-5J48f0bFbRA/VR9xgXGwYvI/AAAAAAAAACw/g6IesFX39hE/s1600/jumpexample.jpg" height="140" width="200" /></a></td></tr><tr><td class="tr-caption" style="text-align: center;">Playful frog path in black (first 1, then 2 then 3 in red).<br />Shortest largest jump in green (1->2->3 in blue).</td></tr></tbody></table><b><br /><br />Or imagine the stones are at (x1=3,x2=6) and (y1=5,y2=2). The frog will first jump from (x=0,y=5) to the stone at (x1=3,y=5) (a jump of length 3), then to the stone at (x2=6,y2=2) (a jump of length sqrt(3*3 + 3*3)= sqrt(18)= 4, when rounded) and finally from there to (x=10,y=2) a jump of length 4. <br /><br />The longest jump is therefore 4. <br /> <br />Since there are only 2 stones, the general strategy to find the smallest largest jump is simple: <br /><br /> If the starting shore is denoted by S, the stones by A and B and the destination shore by E, we have the following alternatives: </b><br /><b><br /></b><br /><h1><b> S→ A→ B→ E</b><b><br /><br />S → B → A → E</b><b><br /><br /> S → A → E</b><b><br /><br />S → B→ E </b></h1><b>(S→A→A→E is the same as S→A→E and similarly S→B→B→E is the same as S→B→E) <br /><br />We compute the largest jump for each of these paths and pick the one corresponding to the smallest of these largest jumps. Note that the best path is not always one that goes through the 2 stones, i.e. it might be the case that the frog only has to jump on one stone instead of two. <br /><br />For example imagine the two stones are at x=[3,3] and y=[3,5]. Then the best path would be for the frog to jump to either one of the stones first and then jump straight to the shore E, instead of jumping to the second stone and then to the shore E.<br /><br />The last example also shows that there might be more than one best path. There the frog could pick either stone to jump first and both paths will come up with 7 as the longest jump. <br /><br />That is because we are supposing that the frog is as close to the first as to the second stone, i.e. we neglect any jump she might have to do while on the shore to get in front of one of the stones. <br /><br /> This reasoning generalizes to the case where there are 3 stones A, B and C. The possible paths would now be </b><br /><b></b><br /><h1><b>S→ A→ B→C→ E</b><b><br /></b><b>S → A → C →B → E</b><b><br /></b><b> S→ B→ A→C→ E</b><b><br /></b><b>S → B → C →A →E</b><b><br /></b><b>S→ C→ A→B→ E</b><b><br /></b><b>S → C → B →A → E</b><b><br /></b><b> S→ A→ B→ E</b><b><br /></b><b>S → B → A → E</b><b><br /></b><b> S→ A→ C→ E</b><b><br /></b><b>S → C → A → E</b><b><br /></b><b> S→ B→ C→ E</b><b><br /></b><b>S → C → B → E</b><b><br /></b><b> S → A → E</b><b><br /></b><b>S → B→ E</b><b><br /></b><b>S → C→ E </b></h1></div><br /><span style="color: blue;"><b>The following code solves the 2 stone case.<br /> Note that all paths with the same smallest largest jump are shown. <br />In particular notice the last case. The two stones are located at the same x coordinate. The frog has three options all leading to a smallest largest jump of 7:<br />It can jump on any one stone, then jump to the far shore. <br />Or it can jump to one stone, then to the other, then from there to the shore.<br />Of course this last case involves three jumps instead of just two but since our problem does not require the number of jumps to be a minimum this is ok even if not fully optimal. <br /> Notice also the first case. The smallest longest path of length 4 involves going from the shore to (3, 5) then to (7, 5) then to the far shore. The reverse (7, 5) then to (3, 5) does not lead to a best path because the longest jump is 7 instead of 4. </b></span><br /><div width="1500px"><iframe src="https://trinket.io/embed/python/5f65fb023c?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe></div><b><span style="color: blue;"> And the following code solves the case for the 3 stone case. <br />The code is a generalization of the 2 stone case.<br /> To enumerate all possible paths we first consider all paths involving one stone only (one for loop), then those involving two stones (two for loops) and finally those using all the 3 stones (three for loops). </span></b><br /><div width="1500px"><iframe src="https://trinket.io/embed/python/978f17a0fd?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe> We might ask whether there is a more elegant way to solve the problem for any number of stones without keeping nesting for loops. <br />If we use regular python, instead of skulpt, we can use the itertools module and its method permutations to solve the n=3 case with a variation of the following code <br /><pre class="python" name="code">def longestJump(x, y):<br /> best_jump = 10 # infinity<br /> best_path = ()<br /> <br /> for i, j, k in itertools.permutations(range(3)): <br /> jump0 = x[i] # shore to i<br /> jump1 = sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2) # i to j<br /> jump2 = sqrt((x[j]-x[k])**2 + (y[i]-y[j])**2) # j to k<br /> jump3 = 10 - x[k] # k to far shore<br /> longest = max(jump0, jump1, jump2, jump3)<br /> if longest < best_jump:<br /> best_jump = longest<br /> best_path = (i, j, k)<br /> return best_jump, best_path<br /></pre><br />This code still assumes n=3 and in particular forces us to explicitly enumerate all the jumps (to be clear, for 3 stones we also need to generate the permutations of 2 stones and consider also the 1 stone case, just like we did when we used several for loops above). It can be easily adapted to n=2,4,5 but we will have to change it for each of those cases. <br /><br />General search code to handle any number of stones can be written if we think of the problem as searching for the best paths in a graph. Each stone is a vertex in this graph. The initial and the final shores are also added as vertices to the graph. Lets say we number the initial shore as vertex 0, the n stones as vertices 1 through n and the end shore as vertex n+1 (so the graph has n+2 vertices). Noticing that the frog never jumps back once it reaches the end shore and it never jumps from a stone to the initial shore nor can it jump from one shore to the other (i.e. it has to jump to at least one stone), we can generate the graph for the problem with the following code<br /><br /><pre class="python" name="code"> def GenerateGraph(self,num_stones): <br /> # each stone plus the initial starting and ending points is<br /> # a vertex. The starting point is index 0 and the <br /> # ending point is at index num_stones +1<br /> n = self.num_stones + 1<br /> for i in range(0, n+1):<br /> self.graph[i]=list()<br /> <br /> for i in range(1, n):<br /> # from the initial starting point we can<br /> # reach every stone<br /> self.graph[0].append(i)<br /> for j in range(1, n):<br /> if i == j:<br /> continue<br /> # we can go from any stone to any other stone <br /> self.graph[i].append(j)<br /> # we can go from any stone to the far shore <br /> self.graph[i].append(j+1)<br /></pre><br />This generates the graph as a dictionary of adjacency lists (lists with the vertices that can be reached from each vertex that is a key of the dictionary). For example for 3 stones it is:<br /><span style="background-color: #eeeeee;">{0: [1, 2, 3], 1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2, 4], 4: []}</span><br />This graph is independent of the position of the stones, so for a given number of stones it can be generated just once.<br />With the graph on hand, we can find all possible paths from one shore (vertex 0) to the other (vertex n+1) using breadth first search. Paths from the shore to any one stone are added to a queue and popped one by one. Each time we pop one of these paths we look at all the vertices connected to the last vertex on the path. If it is not the terminal vertex (n+1) we added it to the path and then added it to the queue. If it is the terminal vertex we added it to a list of all the paths from 0 to n+1.<br /><br />For example for the 3 stones case, starting at one shore, we add vertex 0 to a queue. Then we go through all the vertices that can be reached from 0 (1,2,3) and add the paths 0--> 1, 0-->2, 0-->3 to the queue as lists.<br />We then pop path 0-->1 from the queue, go through all the vertices that can be reached from 1 and add the resulting paths to the queue: 0-->1-->2, 0-->1-->3. Paths that go from 0 to 4 (shore to shore) like 0-->1-->4 are added to a list with all possible paths 0 to 4 paths. Next we would pop path 0-->2 and repeat the process. The paths 0-->2-->1, 0-->2-->3 would be added to the queue and 0-->2-->4 would be added to the list of all paths fro 0 to 4. And so on. We end up with the following paths from 0 to 4:<br /><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">[</pre># one stone paths <br /><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">[0, 1, 4], [0, 2, 4], [0, 3, 4], </pre># 2 stone paths <br /><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">[0, 1, 2, 4], [0, 1, 3, 4], [0, 2, 1, 4], [0, 2, 3, 4], [0, 3, 1, 4], [0, 3, 2, 4], </pre># 3 stone paths <br /><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">[0, 1, 2, 3, 4], [0, 1, 3, 2, 4], [0, 2, 1, 3, 4], [0, 2, 3, 1, 4], [0, 3, 1, 2, 4], [0, 3, 2, 1, 4]</pre><pre style="background-color: #eeeeee; border-radius: 6px; padding: 1em;">]</pre><div><br />Again notice how these paths are independent of the position of the 3 stones and therefore can be generated just once for a given number of stones. </div><br />The final step is to search through all these paths to get all those where the longest jump is the smallest. The easiest way is to loop through all the paths and for each compute the longest jump length. Store the paths in a dictionary where the key is the longest jump. Then the best paths are the ones with the lowest key.<br /><br />The complete code (including a python implementation of a Queue) is below. Tests for 2,3,4, and 5 stones are given. You can try other cases (what is the highest number of stones the code can handle, i.e. before the browser becomes unresponsive?). </div><div width="1500px"><iframe src="https://trinket.io/embed/python/4570e788b1?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com0tag:blogger.com,1999:blog-1274195019136560947.post-59963442458880577062015-03-23T18:07:00.000-07:002015-05-20T16:23:37.363-07:00Intersection of two line segments in the planeWe are given two line segments (in the plane) through their two end point (x,y) coordinates. To simplify the problem lets assume the two segments are either horizontal or vertical and their endpoint coordinates are integers.<br /><div><br /></div><div>The two segments might not intersect at all, they might intersect at a single point or they might have a whole segment in common. The following figure shows those three possibilities. The last pair of segments (red and cyan) overlap in a segment, the pair before the red-cyan pair intersects at a single point and the first three pairs of segments do not intersect. Notice that the overlap segment will either be horizontal or vertical since the two segments are both horizontal or both vertical when a segment overlap occurs.</div><div><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/-UPY463kzA68/VQ4VXW-m1QI/AAAAAAAAABI/Io4632LMLxE/s1600/segments.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://3.bp.blogspot.com/-UPY463kzA68/VQ4VXW-m1QI/AAAAAAAAABI/Io4632LMLxE/s1600/segments.jpg" height="125" width="200" /></a></div><div>How would we write a simple python program that returns a string 'NO INTERSECTION', 'POINT INTERSECTION' or 'SEGMENT INTERSECTION' for each of the three possible cases outlined above and returns the intersection segment?</div><div><br /></div><div> Lets suppose the endpoint coordinates of the first segment are given as a python list s1:[x1 y1 x2 y2] and similarly for the second segment s2:[x1 y1 x2 y2].<br /><br /> It is tempting to use a few if statements to check for the different configurations of the two line segments but boundary cases make such an approach hard to get right: Imagine one of the line segments is just a single point in the other segment. In this case we want to return "POINT INTERSECTION" not "SEGMENT INTERSECTION". Yet another case is if the two line segments are both points.<br /><br /> An easier and better solution is to write code that naturally handles all possible cases. We can first easily determine the overlapping region of the two line segments, and then see if it is a point, a segment, or if there is no overlap.<br /><br />The x coordinate of the leftmost endpoint of the intersection segment will be<br /><br /> <b>left = max(min(s1.x1,s1.x2),min(s2.x1,s2.x2))</b>.<br /><br />That is we search among the endpoints of s1 and s2 for the the one with the largest left coordinate (the min gets the endpoint in each segment that is the leftmost).<br /><br />Similarly the x coordinate of the rightmost endpoint of the intersection segment will be<br /><b><br /></b><b>right = min(max(s1.x1,s1.x2),max(s2.x1,s2.x2)).</b><br /><br />That is we search among the endpoints of s1 and s2 for the one with the smallest right coordinate (the max gets the endpoint in each segment that is the rightmost).<br /><b><br /></b>We can extend this logic to find the y coordinates of the endpoints of the intersection segment:<br /><br /><b>bottom = max(min(s1.y1,s1.y2),min(s2.y1,s2.y2))</b><br /><br /><b>top = min(max(s1.y1,s1.y2),max(s2.y1,s2.y2))</b><br /><br />With the coordinates of the segment endpoints we can promptly find out if there is intersection or not. For example if <b>left > right or bottom>top </b>there is no intersection whatsoever. If <b>left=right and bottom=top</b> the 2 segments meet at a single point. Otherwise they overlap in a segment.<br /><br /><br /><span style="color: blue;">Here it is this solution (you can change the code and try different approaches: it will be executed roughly every minute, and you can change this interval by editing the value 60000 to the value most convenient to you) </span></div><div width="1500px"><iframe src="https://trinket.io/embed/python/b1c5365a64?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe></div><div width="1500px"><span style="color: blue;">And a more concise way of coding it up is</span><iframe src="https://trinket.io/embed/python/b0a5f898f8?start=result" width="100%" height="600" frameborder="0" marginwidth="0" marginheight="0" allowfullscreen></iframe></div>jenny furtadohttps://plus.google.com/100045160124658972924noreply@blogger.com1