If you are just starting with Python I hope the small problems in this blog are helpful. All you need to solve or follow them is very basic knowledge of Python and curiosity.
Each post uses trinkets to run python on the browser. You can modify and run the code on the blog post itself.
Showing posts with label logic. Show all posts
Showing posts with label logic. Show all posts

Monday, July 20, 2015

Castle Defense I - Approximate methods


In the last post we considered a simple version of a tower defense game.
There were gameSoldiers, gameTowers and each tower had numHits it could take before crumbling and numKills soldiers it could kill in each round. Soldiers would start each round by shooting at a random tower removing one of its numHits. After all soldiers had fired, the remaining towers would shoot with each tower killing numKills soldiers.
In this post we will consider a slightly different variant of the game:
  • A castle is attacked at sunrise, by surprise by a group of gameSoldiers soldiers.
  • Each soldier carries a canon and a rifle. 
  • The castle has castleHits strength, i.e. it can take castleHits before it crumbles. 
  • In the first day, all soldiers fire their canons at the castle decreasing its strength to \(castleHits-gameSoldiers\).
  • Assuming the castle still has \(castleHits>0\), it will then send their own defendersPerWave soldiers per day/wave/round.
  • 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 castleHits  or the soldier can kill one of the castle defenders (if there are any) with its rifle.
  • 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). 
  • If at this point the castle is still up and there are still soldiers, the castle will send defendersPerWave which will add up to whatever defenders are still out from previous rounds. I.e. at the end of each round the castle will send a fresh batch of defendersPerWave as long as castleHits>0.
  • 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).
  • 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.
  • 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). 
  • The previous point says that it is possible for the castle to win the game even if it has zero castleHits 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).
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.
If the soldiers can not win the game we would still like to know in which round will the castle prevail.
And we would like to keep track of the remaining gameSoldiers, castleHits 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 defendersPerWave since some defenders remain from previous rounds.

REASONABLE SOLUTIONS: Attack the castle first or attack the defenders first

We can try to simulate what happens in each wave like we did in our previous post.
It seems that a possible best strategy to destroy the castle in the minimum number of waves/rounds is the following:
  • If the number of soldiers in the wave is greater or equal than the castleHits, we have castleHits 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).   
  • If the number of soldiers in the wave is smaller than the castleHits 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).
  • 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.
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)

 def attackCastle(self,gameSoldiers,castleHits, defendersPerWave):
     totalDefenders = 0
     waveStats = {}
     wave=0
     waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
     wave = 0
     while True:
        wave += 1
        # case a: castleHits <= gameSoldiers
        # gameSoldiers first fire at the castle. 
        # causing castleHits to go to zero;
        # the remaining gameSoldiers - castleHits soldiers 
        # then fire at any defenders
        if castleHits <= gameSoldiers:           
           totalDefenders -= gameSoldiers - castleHits
           castleHits = 0
           if totalDefenders < 0:
               totalDefenders = 0 
        # case b: castleHits > gameSoldiers and gameSoldiers>totalDefenders
        # the soldiers
        # first shoot all the defenders and the remaining
        # soldiers then shoot at the castle 
        elif gameSoldiers > totalDefenders:           
           castleHits -= gameSoldiers - totalDefenders
           totalDefenders = 0
        # case c: castleHits> gameSoldiers and gameSoldiers<= totalDefenders
        # the soldiers shoot at the castle
        else:
           castleHits -= gameSoldiers
        if castleHits < 0:
           castleHits = 0  
        if castleHits == 0 and totalDefenders == 0:
           waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
           return waveStats
        # castle defenders kill as many soldiers
        # as there are defenders
        gameSoldiers -= totalDefenders
        if gameSoldiers <= 0:
            gameSoldiers = 0
            waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
   
            return waveStats
        # castle sends another set of defenders out
        if castleHits > 0:
            totalDefenders += defendersPerWave
        waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
        
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.
Consider for example the case where there are initially 10 gameSoldiers, castleHits=43 and the castle sends 8 defendersPerWave.
  • In the first wave, the 10 soldiers reduce castleHits by 10. 
  • The second wave starts therefore with 10 gameSoldiers, castleHits=33 and totalDefenders=8. Since \(gameSoldiers>totalDefenders\) and \(gameSoldiers<castleHits\), 8 of the soldiers kill the 8 defenders and the other 2 soldiers reduce castleHits to 31. The castle sends another 8 defenders.
  • In the third round again 8 of the soldiers kill the 8 defenders and reduce castleHits to 29. Another 8 defenders are sent out.
  • This pattern repeats itself in the 4th (castleHits=27), 5th (castleHits=25), 6th (castleHits=23), 7th (castleHits=21), 8th (castleHits=19), 9th (castleHits=17), 10th (castleHits=15), 11th (castleHits=13), 12th (castleHits=11) and 13th (castleHits=9). 
  • In the 14th wave because \(castleHits<gameSoldiers\), the algorithm above makes 9 of the soldiers reduce castleHits to 0 and it makes the remaining soldier kill one of the defenders.
  • The 7 defenders then kill 7 of the soldiers. Since the castle is "dead" it will not send any more defenders.
  • 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. 
  • 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.
There is however a slightly different strategy that will lead to a win for the soldiers side:
  • Everything proceeds as described above up to the 13th wave.
  • In the 14th wave, again 2 of the soldiers should shoot the castle leaving it with 7 castleHits points and the other 8 soldiers should kill the 8 defenders. 
  • In the 15th wave, 7 of the soldiers vanish the castleHits points and the remaining 3 soldiers kill 3 of the defenders. The remaining 5 defenders will kill 5 of the soldiers. 
  • Finally in the 16th wave, the remaining 5 soldiers kill the 5 defenders and win the game.
This is indeed the solution which leads to the minimum number of rounds (16 days/rounds).

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 (castleHits=5), 16th (castleHits=3), 17th (castleHits=1), 18th (castleHits=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.
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 "which approach/algorithm leads to the least number of soldiers killed" this would indeed be a good candidate.
In code this algorithm looks like this

def attackDefenders(self,gameSoldiers,castleHits, defendersPerWave):
     totalDefenders = 0
     waveStats = {}
     wave=0
     waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
     wave = 0
     
     while True:
        wave += 1
        # case a: There are (at least) as many totalDefenders
        # as gameSoldiers so the gameSoldiers
        # all shoot at the defenders, then the 
        # remaining defenders shoot back
        if totalDefenders >= gameSoldiers:           
           totalDefenders -= gameSoldiers
           gameSoldiers -= totalDefenders
          
        # case b:There are more gameSoldiers than defenders
        # so the soldiers kill all defenders and the 
        # remaining soldiers shoot at the castle
        elif castleHits >= 0:           
           castleHits -= gameSoldiers - totalDefenders
           totalDefenders = 0
        # case c: There are more gameSoldiers than defenders and
        # castleHits=0. The soldiers shoot all defenders
        # (and win the game)
        else:
           totalDefenders = 0

        if castleHits < 0:
           castleHits = 0 
        
        # soldiers win
        if castleHits == 0 and totalDefenders == 0:
           waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
           return waveStats
      
        # castle wins
        if gameSoldiers <= 0:
            gameSoldiers = 0
            waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
   
            return waveStats
        
        # castle sends another set of defenders out
        if castleHits > 0:
            totalDefenders += defendersPerWave
      
        waveStats[wave] = {'gameSoldiers':gameSoldiers,
                        'castleHits':castleHits,
                        'defenders':totalDefenders}
        # prevent infinite loops
        if wave>50:           
            return waveStats


As this example shows, the simple algorithms we described above do not work for every initial values of gameSoldiers, castleHits and defendersPerWave. We should keep looking.

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.
The code is organized in 3 files:
castledefense.py: 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).
tests.py : 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 .
main.py: This file simply creates a CastleDefenseITest object and runs its runTests method.
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).
I summarize the results in the following table.
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).
The cells highlighted in cyan indicates the algorithm predicts the correct side wins or ties but it takes more moves/rounds than the minimum.
Test Number Test Values Min Rounds Rounds for attackCastle Rounds for attackDefenders
0
gameSoldiers=10
castleHits=11
defendersPerWave=15
Soldiers win in 4 Soldiers win in 4 Castle Wins in 3
1
gameSoldiers=3
castleHits=10
defendersPerWave=4
Castle wins in 2 Castle wins in 2 Castle Wins in 3
2
gameSoldiers=2
castleHits=10
defendersPerWave=1
Soldiers win in 9 Soldiers win in 9
(1 soldier standing)
Soldiers win in 9
(2 soldiers standing)
3
gameSoldiers=11
castleHits=12
defendersPerWave=9
Soldiers win in 2 Soldiers win in 2
(11 soldiers standing)
Soldiers win in 2
(11 soldiers standing)
4
gameSoldiers=12
castleHits=32
defendersPerWave=5
Soldiers win in 4 Soldiers win in 4
(12 soldiers standing)
Soldiers win in 4 (12 soldiers standing)
5
gameSoldiers=12
castleHits=44
defendersPerWave=6
Soldiers win in 7 Soldiers win in 7 (10 soldiers standing) Soldiers win in 7 (12 soldiers standing)
6
gameSoldiers=7
castleHits=10
defendersPerWave=8
Soldiers win in 4 Soldiers win in 4 Castle wins in 4
7
gameSoldiers=4
castleHits=6
defendersPerWave=7
Castle wins in 2 Castle wins in 2 Castle wins in 3
8
gameSoldiers=8
castleHits=10
defendersPerWave=6
Soldiers win in 2 Soldiers win in 2 (8 soldiers standing) Soldiers win in 2 (8 soldiers standing)
9
gameSoldiers=4
castleHits=5
defendersPerWave=5
Soldiers win in 3 Soldiers win in 3 Castle wins in 3
10
gameSoldiers=5
castleHits=8
defendersPerWave=5
Soldiers win in 4 Soldiers win in 4 Its a tie!
11
gameSoldiers=10
castleHits=50
defendersPerWave=9
Soldiers win in 37 Castle wins in 33 Soldiers win in 41
12
gameSoldiers=19
castleHits=50
defendersPerWave=15
Soldiers win in 8 Castle wins in 6 Soldiers win in 9
13
gameSoldiers=10
castleHits=50
defendersPerWave=10
Soldiers win in 2 Soldiers win in 2 It's a tie!
14
gameSoldiers=8
castleHits=9
defendersPerWave=18
Castle wins in 2 Castle wins in 2 Castle wins in 2
15
gameSoldiers=9
castleHits=11
defendersPerWave=12
Soldiers win in 4 Soldiers win in 4 Castle wins in 3
16
gameSoldiers=5
castleHits=37
defendersPerWave=5
Castle wins in 2 Castle wins in 2 It's a tie!
17
gameSoldiers=9
castleHits=33
defendersPerWave=8
Soldiers win in 22 Castle wins in 18 Soldiers win in 25
18
gameSoldiers=8
castleHits=21
defendersPerWave=7
Soldiers win in 11 Castle win in 8 Soldiers win in 14
19
gameSoldiers=12
castleHits=13
defendersPerWave=50
Castle wins in 2 Castle wins in 2 Castle wins in 2
20
gameSoldiers=7
castleHits=31
defendersPerWave=5
Soldiers win in 13 Soldiers win in 13
(2 soldiers standing)
Soldiers win in 13 (7 soldiers standing)
21
gameSoldiers=19
castleHits=50
defendersPerWave=14
Soldiers win in 7 Soldiers win in 7 (5 soldiers standing) Soldiers win in 8 (19 soldiers standing)
22
gameSoldiers=20
castleHits=50
defendersPerWave=18
Soldiers win in 12 Castle wins in 8 Soldiers win in 16
23
gameSoldiers=3
castleHits=30
defendersPerWave=1
Soldiers win in 15 Soldiers win in 15 (2 soldiers standing) Soldiers win in 15 (3 soldiers standing)
24
gameSoldiers=2
castleHits=50
defendersPerWave=1
Soldiers win in 49 Soldiers win in 49 (1 soldier standing) Soldiers win in 49 (2 soldiers standing)
25
gameSoldiers=9
castleHits=43
defendersPerWave=7
Soldiers win in 17 Castle wins in 16 Soldiers win in 18
26
gameSoldiers=10
castleHits=43
defendersPerWave=8
Soldiers win in 16 Castle wins in 15 Soldiers win in 18

Here are some interesting facts we can glance from this table:
  • 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.
  • If the castle wins it wins in 2 rounds always.
  • When the castle wins, the attackCastle algorithm always predicts correctly the castle win in 2 rounds.
  • The attackDefenders algorithm also predicts correctly that the castle wins but sometimes it takes 3 rounds.
  • 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.
  • 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
    # prevent infinite loops
    if wave>50:           
       return waveStats 
    to prevent the loop of never ending in cases where there is a tie.
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.

In our next post we will look at a couple of approaches/algorithms that solve this problem correctly always.

Sunday, June 21, 2015

Goal Grades



  
Emily is a very smart girl. 
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.
She has gotten so used to overperform academically that she decided to take 5 AP classes in her 10th grade.
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. 
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.
The other two (AP French and AP History) are not as important but she still must earn 85% or more in each.
With these percents dancing in her head, she sits down in front of the computer a few weeks before taking the tests. 
She wants to figure out how many points she has to earn in each of the tests to achieve her goal.
 
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,
then AP Chemistry, AP French and the last element representing the scores for AP History, i.e. she organizes the classes in alphabetical order)
 

pointsEarned = [[382, 710, 805, 615, 377, 255, 256, 30, 70, 316, 372, 173],   
                [17, 23, 50, 200, 19, 56, 83, 91, 77, 9, 0],
                [26, 530, 60, 18, 547, 53, 529, 671, 90, 140, 208, 19, 329, 242, 233],
                [55, 77, 82, 60],
                [408, 800, 5, 306, 2, 703, 311, 163, 760, 742, 640, 574, 301, 565]]
Similarly the points possible in each assignment of each class are stored in the list of lists
pointsPossible = [[999, 947, 839, 689, 491, 758, 652, 156, 123, 731, 455, 526],
                  [20, 30, 50, 250, 20, 70, 100, 100, 100, 10, 10],
                  [87, 648, 609, 65, 554, 150, 736, 837, 368, 147, 223, 438, 475, 893, 349],
                  [100,100,100,100],
                  [949, 936, 7, 404, 191, 899, 964, 393, 914, 805, 706, 619, 529, 734]]
           
The maximum possible points of each test go in the list

testsPossible = [50517, 1500, 58913,500, 9946] 

and the minimum percent goal for each test goes into the list

percentsMin = [94,94,94,85,85]
Emily then computed the lowest 5 test scores that she needs to meet her goals using the following python code

  
    # Loop through the integers between 0 and testMax
# 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

    def testsMin(self,pointsEarned,pointsPossible,testsMax,percentsMin):
        goalTestsScores = []
      
        for i in range(len(pointsEarned)):
            goalTestsScores.append(self.pointsNeeded(pointsEarned[i],pointsPossible[i],testsMax[i],percentsMin[i]))
                                  
        return goalTestsScores

     

 Notice that there are 3 possible cases:
     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.
     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
the points needed.
     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). 

After writing this code Emily realized she could have just computed the points needed directly. She rewrote the points needed function like this
 
    # Compute the points needed directly
    def pointsNeeded(self, pointsEarned, pointsPossible, testMax, percentMin):
        totalPoss = 0
        earned = 0
        
        for i in range(len(pointsPossible)):
            totalPoss += pointsPossible[i]
            earned += pointsEarned[i]
        totalPoss += testMax
        
        # the 99 is needed to round up by 1
        pointsNeeded = (percentMin*totalPoss+99)/100 - earned
        
        # We might need more points than testMax
        if pointsNeeded > testMax:
            return -1
        
        # The number of points earned can be larger than what we need
        # i.e. we dont even have to take the final test
        if pointsNeeded < 0:
            return 0
        return pointsNeeded

The only slightly tricky part is the fact she adds 99 to round up the score. Why is this needed?
Suppose percentMin = 70, totalPass = 66, earned = 44. 
Then (70*66/100)=46 since this is integer division. 
pointsNeeded = 46-44=2. 
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. 
This is because 70*66/100 = 46.2 not 46. We want to round up and
(70*66 + 99)/100 = 47
which gives the 3 points needed.

When Emily runs her code she gets

CLASS 0
points earned in assignments [382, 710, 805, 615, 377, 255, 256, 30, 70, 316, 372, 173]
total points earned in assignments 4361
max assignment points        [999, 947, 839, 689, 491, 758, 652, 156, 123, 731, 455, 526]
max points in test           50517
max possible points (assignments and tests) 57883
minimum test score to get 94% of the total possible points: 50050
CLASS 1
points earned in assignments [17, 23, 50, 200, 19, 56, 83, 91, 77, 9, 0]
total points earned in assignments 625
max assignment points        [20, 30, 50, 250, 20, 70, 100, 100, 100, 10, 10]
max points in test           1500
max possible points (assignments and tests) 2260
minimum test score to get 94% of the total possible points: 1500
CLASS 2
points earned in assignments [26, 530, 60, 18, 547, 53, 529, 671, 90, 140, 208, 19, 329, 242, 233]
total points earned in assignments 3695
max assignment points        [87, 648, 609, 65, 554, 150, 736, 837, 368, 147, 223, 438, 475, 893, 349]
max points in test           58913
max possible points (assignments and tests) 65492
minimum test score to get 94% of the total possible points: 57868
CLASS 3
points earned in assignments [55, 77, 82, 60]
total points earned in assignments 274
max assignment points        [100, 100, 100, 100]
max points in test           500
max possible points (assignments and tests) 900
minimum test score to get 85% of the total possible points: 491
CLASS 4
points earned in assignments [408, 800, 5, 306, 2, 703, 311, 163, 760, 742, 640, 574, 301, 565]
total points earned in assignments 6280
max assignment points        [949, 936, 7, 404, 191, 899, 964, 393, 914, 805, 706, 619, 529, 734]
max points in test           9946
max possible points (assignments and tests) 18996
minimum test score to get 85% of the total possible points: 9867
=======================
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.
She will need quite a bit of luck to achieve her goals.

We end this post with Emily's complete code

Saturday, May 23, 2015

Run Length Encoding a Swan

Run Length Encoding (RLE) is a simple data compression scheme.
This scheme compresses strings by replacing consecutive characters by the number of occurrences of the character followed by that character.
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.
Each sequence of a repeated character is called a run thus the name Run Length Encoding.

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.
Consider the following swan "image"

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@,,,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@.#S@@@@..%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@%:@@@@@@@@@S%,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@+@@@@@@@@@@@@@%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@.S@@@@@@@@@@@@@@@%+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@%@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@%@@@@@%@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@:+@@@@S%@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@*.@@@*##@@@@@@@@@@@@@,#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@*.@@@%.?@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@:?,@?*%#@@@@*%.%@@@@@@@+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@:.%@+.:@@@:%S@@S@@@@@@@?@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@?,@%:@@@:..@@@@@:@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@.@@:.#%*@@@@@@@@#@@@@@@,S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@%@@@#@@@@@@@@@@@@*@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@#*@@S,@@@@@@@@@@@@:@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@%+@@.?@@@@@@@@@@@@@:@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@?@,..@@@@@@@@@@@@@@S@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@#?#,@@@@@@@@@@@@@@@%@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@,?@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@S:@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@?@@@@@@@@@@@@@@@@@@@@@@@@::*+SSSSS.*:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@:.@@@@@@@@,%@@@@@@@@@@@@@@@@@@@@..%%?+.:,,,,,*.S?%%?@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@.,@@@@@@@@@@@@@@@,.?+,@@@@@@@@@@@@@@@@@?.@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@S@@@@@@@@@%@@@@@@@@@@@@@@:%S,@@@@@@@@@@@@@@@@@@@?,@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@*@@@@@@@@@@@@.%S@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@*#@@@@@@@@@%@@@@@@@@@@,%.@@@@@@@@@@@@@@@@@@@@@@@S*@@,..%??%%%%%S.:,@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@++@@@@@@@@@%%,@@@@@@@@@@@@@@@@@@@@@@@,%,%%.*@@@@@@@@@,:+?%S:@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@%:@@@@@@@@,%@@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@%#.@@@@@@@@@@@@@@@@@@,S%+@@@@@@@
@@@@@@@@@@@@@@@@@@@*,@@@@@@@@@%@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@,#.@@@@
@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@:@@@@@@,%@@@@@@@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@:%.@@@@@
@@@@@@@@@@@@@@@@@@#:@@@@@@@@@%@@@@@@+%@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%@@@@@@@@@@@@@@@@@@@@@@@%.@@@@@@@
@@@@@@@@@@@@@@@@@%:@@@@@@@@@.S@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*%@@@@@@@@@@@@@@@@@@@@@@..@@@@@@@@@
@@@@@@@@@@@@@@@@@.@@@@@@@@@@%@@@@:#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#,@@@@@@@@@@@@@@@@@@@@@#*@@@@@@@@@@
@@@@@@@@@@@@@@@@.@@@@@@@@@@:.@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@
@@@@@@@@@@@@@@@:%@@@@@@@@@@%@@@S.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%.@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@
@@@@@@@@@@@@@@@%@@@@@@@@@@@%@@SS@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.S@@@@@@@@@@@@@@@@@@@@@%,@@@@@@@@@@@@@
@@@@@@@@@@@@@@*S@@@@@@@@@@*.@@S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,.@@@@@@@@@@@@@@@@@@@@@.*@@@@@@@@@@@@@@
@@@@@@@@@@@@@@#@@@@@@@@@@@%@.%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%S@@@@@@@@@@@@@@@@@@@@@@S@@@@@@@@@@@@@@@
@@@@@@@@@@@@@.:@@@@@@@@@@@%:%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S%@@@@@@@@@@@@@@@@@@@@@@*@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@%@@@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S.@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@,@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.%@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@
@@@@@@@@@@@@S@@@@@@@@@@@@@,@@@@@@@@@@@@@@@@@@@@@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S%@@@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@?@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*%S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%%+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@:,,:*+%%#+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*S@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@.S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S.@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@#,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+S@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@?,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%*@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@,%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@+%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,.%%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@S#%..S.*:,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:S%%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@,,:*.+.%#%S.*,,@@@@@@@@@@@@@@@@@@@@,+.%%S*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,+:*.++SS...#..S.*,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

The image consists of only the 11 symbols

#, ?, %, . , S, +, ., *, :, , , @

adding up to a total of 6400 characters (100 characters on each of 64 rows).
We can easily see that compressing this image using RLE will achieve a significant compression rate.

Encoding

How do we perform such compression?
First in the trinket code below notice how we have 2 files: one is the usual main.py and the other is named data.py.
This data.py file contains a single list called swan. 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.

Access to this list from main.py is achieved through the line

import data

at the top of main.py. Then whenever we want to access the swan list we do

swan = data.swan 

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.

This becomes perhaps clearer looking at the code

 
import data

swan = data.swan

'''
Given an image (represented by a list of its rows)
Run Length Encodes each row of the image and returns
the result as a list of the encoded image rows
'''
def encode(image):
    imageEncoded = []
    # loop through every image row
    for row in image:
        rowEncoded = ''
        count = 0
        char = row[0]
        # loop through every character in the row
        # and count how many consecutive elements of 
        # that character are on that image row
        for character in row:
            # switching to a new character
            if  char != character:
               # dont add 1 
               if count == 1:
                   rowEncoded += char
               else:
                   rowEncoded += str(count) + char
               char = character
               count = 1
            else:
               count += 1
        # encode the last character in the row
        if count == 1:
            rowEncoded += char
        else:
            rowEncoded += str(count) + char
            
        # add encoded row to list holding the image encoding
        imageEncoded.append(rowEncoded)
    return imageEncoded    
    
imageEncoded = encode(swan)


With this encoding the first 5 rows of the above swan image become
100@
18@3,79@
14@.#S4@2.%:75@
13@%:9@S%,73@
12@+13@%.72@

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.

In total there are now 1196 characters instead of the 6400 in the original image, i.e.  1196/6400 = 0.186 or 18.6 percent of the original characters.

Decoding

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.
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.

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

count = count*10+8 

we need to remember though that 1 and 8 will be represented by their ASCII characters (49 and 56).
Therefore we should instead do, in python,

count = count*10 + ord(character) - ord('0')

since the python function ord will return the ascii (more properly the unicode) value of the character we pass it to it.

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).

The decode code in python is then
 

'''
Given a run length encoded image (represented by a list of its rows)
decode each row of the image and return
the result as a list of the unencoded image rows. It also
returns the total number of characters in both the 
original encoded image and the unencoded image
'''
def decode(encodedImage):
    imageDecoded = []
    # loop through every image row
    for row in encodedImage:
        rowDecoded = ''
        count = 0
        char = row[0]
        # loop through every character in the row
        # and count how many consecutive elements of 
        # that character are on that image row
        for character in row:
            # switching to a new character
            if  character.isdigit():
               count = count*10 + ord(character)-ord('0')
            else:
               if count == 0:
                   count = 1
               rowDecoded += character*count
               count = 0
        # add decoded row to list holding the image decoding      
        imageDecoded.append(rowDecoded)
    return imageDecoded
   
Note how we do

rowDecoded += character*count

This will append count number of character to the string rowDecoded. It is a very short way of doing what we want rather than the more verbose way of looping count times and adding character each time to rowDecoded.


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

Monday, May 11, 2015

Blackjack wins and losses


Blackjack, also known as twenty-one, is the most widely played casino game in the world.
The basic rules of Blackjack are (there are several variations/extensions of these rules)
  • The goal of blackjack is to beat the dealer's hand without going over 21.
  • Face cards are worth 10. Aces are worth 1 or 11, whichever makes a better hand. All other cards are worth their numeric value.
  • 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.
  • To 'Hit' is to ask for another card. To 'Stand' is to hold your total and end your turn.
  • If a player goes over 21 he/she busts, and the dealer wins regardless of the dealer's hand.
  • If a player scores lower than the dealer then he/she loses his/her bet.
  • 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).
  • If the player is dealt 21 from the start (Ace & 10), he/she has a blackjack.
  • Blackjack usually means the player wins 1.5 the amount of his/her bet. Depends on the casino.
  • 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.
  • Dealer will hit until his/her cards total 17 or higher.
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.
There are only four possibilities based on the rules above: 

  • If the player has a blackjack and the dealer does not have a blackjack the player wins 3/2*bet.
  • If the player and the dealer both have a blackjack the player keeps his wager and neither side loses, so the player wins 0.
  • If the player goes over 21, he or she loses -bet.
  • 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.

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
 
       def blackjackWinsAndLosses(self, bet, dealerScore, playerScore, dealerHasBlackjack, playerHasBlackjack):
            # player loses
            if playerScore > 21 or (playerScore < dealerScore and dealerScore<=21):
                return -bet
            # neither player nor dealer win
            if dealerHasBlackjack and playerHasBlackjack:
                return 0
            # dealer has blackjack but player does not, player loses
            if dealerHasBlackjack and not playerHasBlackjack:
                return -bet
            # player has blackjack but dealer does not
            if playerHasBlackjack and not dealerHasBlackjack:
                return 3/2.0*bet
            # dealer has more than 21 or player's score is higher than dealer
            if dealerScore > 21 or playerScore > dealerScore:
                return bet
            return 0
The only tricky part of this problem is taking into account all the conditions correctly.
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).
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.
The following Python code gathers all the pieces and tests the method above.