Don't forget to also checkout my second blog containing articles to all other related ICT topics!!

Thursday, May 31, 2012

Python performance pitfalls (?) or issues (?)

I just want to warn you that Python has its glitches performance wise. Functional programming buzzwords are immutability and lazy evaluation (reduced memory footprint). But Python is doing something wrong here one would say. Check for yourself and I would love Python gurus to explain why my attempts to go with the lazy flow resulted in killing the performance.
import cProfile

def vector_op(v1,v2,op):
    return [op(x,y) for x,y in zip(v1,v2)]

v1 = range(1, 10000000)
v2 = range(1, 10000000)
cProfile.run('print sum(vector_op(v1,v2, lambda x,y: x + y))')

99999990000000
         10000046 function calls (10000040 primitive calls) in 59.064 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  9999999   25.622    0.000   25.622    0.000 :1()
        1   31.126   31.126   58.165   58.165 PythonApplication1.py:21(vector_op)
        1    0.837    0.837    0.837    0.837 {sum}
        1    1.417    1.417    1.417    1.417 {zip}

Let's not return an array but a generator expression.
import cProfile

def vector_op_lazy(v1,v2,op):
    return (op(x,y) for x,y in zip(v1,v2))

v1 = range(1, 10000000)
v2 = range(1, 10000000)
cProfile.run('print sum(vector_op_lazy(v1,v2, lambda x,y: x + y))')

What is really surprising is that it even takes more time now. So what are we doing still wrong?
99999990000000
         20000046 function calls (20000040 primitive calls) in 91.824 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  9999999   26.132    0.000   26.132    0.000 :1()
 10000000   46.346    0.000   72.478    0.000 PythonApplication1.py:25()
        1   17.966   17.966   90.444   90.444 {sum}
        1    1.378    1.378    1.378    1.378 {zip}

Let's also use xrange which is lazy evaluated and see how far that gets us.
import cProfile

def vector_op_lazy(v1,v2,op):
    return (op(x,y) for x,y in zip(v1,v2))

v1 = xrange(1, 10000000)
v2 = xrange(1, 10000000)
cProfile.run('print sum(vector_op_lazy(v1,v2, lambda x,y: x + y))')

99999990000000
         20000046 function calls (20000040 primitive calls) in 96.393 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  9999999   27.329    0.000   27.329    0.000 :1()
 10000000   48.976    0.000   76.305    0.000 PythonApplication1.py:27()
        1   19.059   19.059   95.364   95.364 {sum}
        1    1.028    1.028    1.028    1.028 {zip}

Will izip do us anygood in this case?
import cProfile
from itertools import izip

def vector_op_lazy(v1,v2,op):
    return (op(x,y) for x,y in izip(v1,v2))

v1 = xrange(1, 10000000)
v2 = xrange(1, 10000000)
cProfile.run('print sum(vector_op_lazy(v1,v2, lambda x,y: x + y))')

99999990000000
         20000045 function calls (20000039 primitive calls) in 91.346 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  9999999   26.304    0.000   26.304    0.000 :1()
 10000000   46.759    0.000   73.063    0.000 PythonApplication1.py:27()
        1   18.280   18.280   91.343   91.343 {sum}

What about not using a lambda expression?
import cProfile
from itertools import izip

def vector_op_lazy(v1,v2,op):
    return (op(x,y) for x,y in izip(v1,v2))

def op_add(x,y):
    return x + y

v1 = xrange(1, 10000000)
v2 = xrange(1, 10000000)
cProfile.run('print sum(vector_op_lazy(v1,v2, op_add))')

99999990000000
         20000045 function calls (20000039 primitive calls) in 89.603 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
 10000000   46.009    0.000   71.799    0.000 PythonApplication1.py:27()
  9999999   25.790    0.000   25.790    0.000 PythonApplication1.py:29(op_add)
        1   17.804   17.804   89.603   89.603 {sum}

Ok... last hope?! Let's inline the addition instead of calling operator function.
import cProfile
from itertools import izip

def vector_op_lazy(v1,v2):
    return (x + y for x,y in izip(v1,v2))

v1 = xrange(1, 10000000)
v2 = xrange(1, 10000000)

cProfile.run('print sum(vector_op_lazy(v1,v2))')

99999990000000
         10000046 function calls (10000040 primitive calls) in 45.078 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
 10000000   27.925    0.000   27.925    0.000 PythonApplication1.py:27()
        1   17.153   17.153   45.077   45.077 {sum}

That seemed to help a lot, so beware of using too much abstraction when performance really matters. Not making the extra number of function calls reduces the execution time a lot. So now just for fun let us not return a generator expression but an array again.
import cProfile
from itertools import izip

def vector_op(v1,v2):
    return [x + y for x,y in zip(v1,v2)]

v1 = xrange(1, 10000000)
v2 = xrange(1, 10000000)
cProfile.run('print sum(vector_op(v1,v2))')

What the f@ck... The generator expression in combination with the sum function seems like total killing performance. Storing the result from the zip call in an array and next calling sum boosted performance.
99999990000000
         47 function calls (41 primitive calls) in 14.603 seconds
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1   12.678   12.678   13.733   13.733 PythonApplication1.py:25(vector_op)
        1    0.810    0.810    0.810    0.810 {sum}
        1    1.056    1.056    1.056    1.056 {zip}

This answer from stackoverflow is very useful to understand the outcome of this test. I conclude this article that it always makes good sense to profile your app and decide for yourself what is the best approach.

Monday, May 28, 2012

final exam CS212: Portmanteau

This is the sixth and last question from the Udacity CS212 final exam. I will update this article with my solution in 1 week. Please do not comment anything during the final exam week !!
# Unit 6: Fun with Words

"""
A portmanteau word is a blend of two or more words, like 'mathelete',
which comes from 'math' and 'athelete'.  You will write a function to
find the 'best' portmanteau word from a list of dictionary words.
Because 'portmanteau' is so easy to misspell, we will call our
function 'natalie' instead:

    natalie(['word', ...]) == 'portmanteauword'

In this exercise the rules are: a portmanteau must be composed of
three non-empty pieces, start+mid+end, where both start+mid and
mid+end are among the list of words passed in.  For example,
'adolescented' comes from 'adolescent' and 'scented', with
start+mid+end='adole'+'scent'+'ed'. A portmanteau must be composed
of two different words (not the same word twice).

That defines an allowable combination, but which is best? Intuitively,
a longer word is better, and a word is well-balanced if the mid is
about half the total length while start and end are about 1/4 each.
To make that specific, the score for a word w is the number of letters
in w minus the difference between the actual and ideal lengths of
start, mid, and end. (For the example word w='adole'+'scent'+'ed', the
start,mid,end lengths are 5,5,2 and the total length is 12.  The ideal
start,mid,end lengths are 12/4,12/2,12/4 = 3,6,3. So the final score
is

    12 - abs(5-3) - abs(5-6) - abs(2-3) = 8.

yielding a score of 12 - abs(5-(12/4)) - abs(5-(12/2)) -
abs(2-(12/4)) = 8.

The output of natalie(words) should be the best portmanteau, or None
if there is none. 

Note (1): I got the idea for this question from
Darius Bacon.  Note (2): In real life, many portmanteaux omit letters,
for example 'smoke' + 'fog' = 'smog'; we aren't considering those.
Note (3): The word 'portmanteau' is itself a portmanteau; it comes
from the French "porter" (to carry) + "manteau" (cloak), and in
English meant "suitcase" in 1871 when Lewis Carroll used it in
'Through the Looking Glass' to mean two words packed into one. Note
(4): the rules for 'best' are certainly subjective, and certainly
should depend on more things than just letter length.  In addition to
programming the solution described here, you are welcome to explore
your own definition of best, and use your own word lists to come up
with interesting new results.  Post your best ones in the discussion
forum. Note (5) The test examples will involve no more than a dozen or so
input words. But you could implement a method that is efficient with a
larger list of words.
"""

def natalie(words):
    "Find the best Portmanteau word formed from any two of the list of words."

def test_natalie():
    "Some test cases for natalie"
    assert natalie(['adolescent', 'scented', 'centennial', 'always', 'ado']) == 'adolescented'
    assert natalie(['eskimo', 'escort', 'kimchee', 'kimono', 'cheese']) == 'eskimono'
    assert natalie(['kimono', 'kimchee', 'cheese', 'serious', 'us', 'usage']) == 'kimcheese'
    assert natalie(['circus', 'elephant', 'lion', 'opera', 'phantom']) == 'elephantom'
    assert natalie(['programmer', 'coder', 'partying', 'merrymaking']) == 'programmerrymaking'
    assert natalie(['int', 'intimate', 'hinter', 'hint', 'winter']) == 'hintimate'
    assert natalie(['morass', 'moral', 'assassination']) == 'morassassination'
    assert natalie(['entrepreneur', 'academic', 'doctor', 'neuropsychologist', 'neurotoxin', 'scientist', 'gist']) == 'entrepreneuropsychologist'
    assert natalie(['perspicacity', 'cityslicker', 'capability', 'capable']) == 'perspicacityslicker'
    assert natalie(['backfire', 'fireproof', 'backflow', 'flowchart', 'background', 'groundhog']) == 'backgroundhog'
    assert natalie(['streaker', 'nudist', 'hippie', 'protestor', 'disturbance', 'cops']) == 'nudisturbance'
    assert natalie(['night', 'day']) == None
    assert natalie(['dog', 'dogs']) == None
    assert natalie(['test']) == None
    assert natalie(['']) ==  None
    assert natalie(['ABC', '123']) == None
    assert natalie([]) == None
    return 'tests pass'


print test_natalie()

My solution:
# Unit 6: Fun with Words

"""
A portmanteau word is a blend of two or more words, like 'mathelete',
which comes from 'math' and 'athelete'.  You will write a function to
find the 'best' portmanteau word from a list of dictionary words.
Because 'portmanteau' is so easy to misspell, we will call our
function 'natalie' instead:

    natalie(['word', ...]) == 'portmanteauword'

In this exercise the rules are: a portmanteau must be composed of
three non-empty pieces, start+mid+end, where both start+mid and
mid+end are among the list of words passed in.  For example,
'adolescented' comes from 'adolescent' and 'scented', with
start+mid+end='adole'+'scent'+'ed'. A portmanteau must be composed
of two different words (not the same word twice).

That defines an allowable combination, but which is best? Intuitively,
a longer word is better, and a word is well-balanced if the mid is
about half the total length while start and end are about 1/4 each.
To make that specific, the score for a word w is the number of letters
in w minus the difference between the actual and ideal lengths of
start, mid, and end. (For the example word w='adole'+'scent'+'ed', the
start,mid,end lengths are 5,5,2 and the total length is 12.  The ideal
start,mid,end lengths are 12/4,12/2,12/4 = 3,6,3. So the final score
is

    12 - abs(5-3) - abs(5-6) - abs(2-3) = 8.

yielding a score of 12 - abs(5-(12/4)) - abs(5-(12/2)) -
abs(2-(12/4)) = 8.

The output of natalie(words) should be the best portmanteau, or None
if there is none. 

Note (1): I got the idea for this question from
Darius Bacon.  Note (2): In real life, many portmanteaux omit letters,
for example 'smoke' + 'fog' = 'smog'; we aren't considering those.
Note (3): The word 'portmanteau' is itself a portmanteau; it comes
from the French "porter" (to carry) + "manteau" (cloak), and in
English meant "suitcase" in 1871 when Lewis Carroll used it in
'Through the Looking Glass' to mean two words packed into one. Note
(4): the rules for 'best' are certainly subjective, and certainly
should depend on more things than just letter length.  In addition to
programming the solution described here, you are welcome to explore
your own definition of best, and use your own word lists to come up
with interesting new results.  Post your best ones in the discussion
forum. Note (5) The test examples will involve no more than a dozen or so
input words. But you could implement a method that is efficient with a
larger list of words.
"""

def natalie(words):
    "Find the best Portmanteau word formed from any two of the list of words."
    #we will represent a natalie with a tuple (word, score)
    natalies = []
    for (word1, word2) in getWordPairs(words):
        mid = ''
        endpos = 1
        while word1.find(word2[0:endpos]) != -1 and endpos <= len(word2):
           mid = word2[0:endpos]
           endpos +=1
        start = substringBefore(word1, mid)
        end = substringAfter(word2, mid)
        if mid == '' or len(start) == 0 or len(end) == 0:
            #we didn't find a natalie
            continue
        word = start + mid + end
        score = len(word) - abs(len(start)-(len(word)/4.0)) - abs(len(mid)-(len(word)/2.0)) - abs(len(end)-(len(word)/4.0))
        natalies.append((word, score))
    if len(natalies) == 0:
        return None
    max_score = max([natalie[1] for natalie in natalies])
 #remark: I only return the first hit among several best matches
    return [ele[0] for ele in natalies if ele[1] == max_score][0] 


def substringAfter(text, substring):
    start = text.find(substring)
    if start == -1:
        return ''
    return text[start + len(substring):]

def substringBefore(text, substring):
    start = text.find(substring)
    if start == -1:
        return ''
    return text[:start]                             

def getWordPairs(words):
    from itertools import permutations
    perms = list(permutations(words, 2))
    return perms

def test_natalie():
    "Some test cases for natalie"
    assert natalie(['adolescent', 'scented', 'centennial', 'always', 'ado']) == 'adolescented'
    assert natalie(['eskimo', 'escort', 'kimchee', 'kimono', 'cheese']) == 'eskimono'
    assert natalie(['kimono', 'kimchee', 'cheese', 'serious', 'us', 'usage']) == 'kimcheese'
    assert natalie(['circus', 'elephant', 'lion', 'opera', 'phantom']) == 'elephantom'
    assert natalie(['programmer', 'coder', 'partying', 'merrymaking']) == 'programmerrymaking'
    assert natalie(['int', 'intimate', 'hinter', 'hint', 'winter']) == 'hintimate'
    assert natalie(['morass', 'moral', 'assassination']) == 'morassassination'
    assert natalie(['entrepreneur', 'academic', 'doctor', 'neuropsychologist', 'neurotoxin', 'scientist', 'gist']) == 'entrepreneuropsychologist'
    assert natalie(['perspicacity', 'cityslicker', 'capability', 'capable']) == 'perspicacityslicker'
    assert natalie(['backfire', 'fireproof', 'backflow', 'flowchart', 'background', 'groundhog']) == 'backgroundhog'
    assert natalie(['streaker', 'nudist', 'hippie', 'protestor', 'disturbance', 'cops']) == 'nudisturbance'
    assert natalie(['night', 'day']) == None
    assert natalie(['dog', 'dogs']) == None
    assert natalie(['test']) == None
    assert natalie(['']) ==  None
    assert natalie(['ABC', '123']) == None
    assert natalie([]) == None
    return 'tests pass'

final exam CS212: Darts probability

This is the fifth question from the Udacity CS212 final exam. I will update this article with my solution in 1 week. Please do not comment anything during the final exam week !!
# Unit 5: Probability in the game of Darts

"""
In the game of darts, players throw darts at a board to score points.
The circular board has a 'bulls-eye' in the center and 20 slices
called sections, numbered 1 to 20, radiating out from the bulls-eye.
The board is also divided into concentric rings.  The bulls-eye has
two rings: an outer 'single' ring and an inner 'double' ring.  Each
section is divided into 4 rings: starting at the center we have a
thick single ring, a thin triple ring, another thick single ring, and
a thin double ring.  A ring/section combination is called a 'target';
they have names like 'S20', 'D20' and 'T20' for single, double, and
triple 20, respectively; these score 20, 40, and 60 points. The
bulls-eyes are named 'SB' and 'DB', worth 25 and 50 points
respectively. Illustration (png image): http://goo.gl/i7XJ9

There are several variants of darts play; in the game called '501',
each player throws three darts per turn, adding up points until they
total exactly 501. However, the final dart must be in a double ring.

Your first task is to write the function double_out(total), which will
output a list of 1 to 3 darts that add up to total, with the
restriction that the final dart is a double. See test_darts() for
examples. Return None if there is no list that achieves the total.

Often there are several ways to achieve a total.  You must return a
shortest possible list, but you have your choice of which one. For
example, for total=100, you can choose ['T20', 'D20'] or ['DB', 'DB']
but you cannot choose ['T20', 'D10', 'D10'].
"""

def test_darts():
    "Test the double_out function."
    assert double_out(170) == ['T20', 'T20', 'DB']
    assert double_out(171) == None
    assert double_out(100) in (['T20', 'D20'], ['DB', 'DB'])

"""
My strategy: I decided to choose the result that has the highest valued
target(s) first, e.g. always take T20 on the first dart if we can achieve
a solution that way.  If not, try T19 first, and so on. At first I thought
I would need three passes: first try to solve with one dart, then with two,
then with three.  But I realized that if we include 0 as a possible dart
value, and always try the 0 first, then we get the effect of having three
passes, but we only have to code one pass.  So I creted ordered_points as
a list of all possible scores that a single dart can achieve, with 0 first,
and then descending: [0, 60, 57, ..., 1].  I iterate dart1 and dart2 over
that; then dart3 must be whatever is left over to add up to total.  If
dart3 is a valid element of points, then we have a solution.  But the
solution, is a list of numbers, like [0, 60, 40]; we need to transform that
into a list of target names, like ['T20', 'D20'], we do that by defining name(d)
to get the name of a target that scores d.  When there are several choices,
we must choose a double for the last dart, but for the others I prefer the
easiest targets first: 'S' is easiest, then 'T', then 'D'.
"""


def double_out(total):
    """Return a shortest possible list of targets that add to total,
    where the length <= 3 and the final element is a double.
    If there is no solution, return None."""
    # your code here

"""
It is easy enough to say "170 points? Easy! Just hit T20, T20, DB."
But, at least for me, it is much harder to actually execute the plan
and hit each target.  In this second half of the question, we
investigate what happens if the dart-thrower is not 100% accurate.

We will use a wrong (but still useful) model of inaccuracy. A player
has a single number from 0 to 1 that characterizes his/her miss rate.
If miss=0.0, that means the player hits the target every time.
But if miss is, say, 0.1, then the player misses the section s/he
is aiming at 10% of the time, and also (independently) misses the thin
double or triple ring 10% of the time. Where do the misses go?
Here's the model:

First, for ring accuracy.  If you aim for the triple ring, all the
misses go to a single ring (some to the inner one, some to the outer
one, but the model doesn't distinguish between these). If you aim for
the double ring (at the edge of the board), half the misses (e.g. 0.05
if miss=0.1) go to the single ring, and half off the board. (We will
agree to call the off-the-board 'target' by the name 'OFF'.) If you
aim for a thick single ring, it is about 5 times thicker than the thin
rings, so your miss ratio is reduced to 1/5th, and of these, half go to
the double ring and half to the triple.  So with miss=0.1, 0.01 will go
to each of the double and triple ring.  Finally, for the bulls-eyes. If
you aim for the single bull, 1/4 of your misses go to the double bull and
3/4 to the single ring.  If you aim for the double bull, it is tiny, so
your miss rate is tripled; of that, 2/3 goes to the single ring and 1/3
to the single bull ring.

Now, for section accuracy.  Half your miss rate goes one section clockwise
and half one section counter-clockwise from your target. The clockwise 
order of sections is:

    20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5

If you aim for the bull (single or double) and miss on rings, then the
section you end up on is equally possible among all 20 sections.  But
independent of that you can also miss on sections; again such a miss
is equally likely to go to any section and should be recorded as being
in the single ring.

You will need to build a model for these probabilities, and define the
function outcome(target, miss), which takes a target (like 'T20') and
a miss ration (like 0.1) and returns a dict of {target: probability}
pairs indicating the possible outcomes.  You will also define
best_target(miss) which, for a given miss ratio, returns the target 
with the highest expected score.

If you are very ambitious, you can try to find the optimal strategy for
accuracy-limited darts: given a state defined by your total score
needed and the number of darts remaining in your 3-dart turn, return
the target that minimizes the expected number of total 3-dart turns
(not the number of darts) required to reach the total.  This is harder
than Pig for several reasons: there are many outcomes, so the search space 
is large; also, it is always possible to miss a double, and thus there is
no guarantee that the game will end in a finite number of moves.
"""


def outcome(target, miss):
    "Return a probability distribution of [(target, probability)] pairs."
    #your code here

def best_target(miss):
    "Return the target that maximizes the expected score."
    #your code here
    
def same_outcome(dict1, dict2):
    "Two states are the same if all corresponding sets of locs are the same."
    return all(abs(dict1.get(key, 0) - dict2.get(key, 0)) <= 0.0001
               for key in set(dict1) | set(dict2))

def test_darts2():
    assert best_target(0.0) == 'T20'
    assert best_target(0.1) == 'T20'
    assert best_target(0.4) == 'T19'
    assert same_outcome(outcome('T20', 0.0), {'T20': 1.0})
    assert same_outcome(outcome('T20', 0.1), 
                        {'T20': 0.81, 'S1': 0.005, 'T5': 0.045, 
                         'S5': 0.005, 'T1': 0.045, 'S20': 0.09})
    assert same_outcome(
        outcome('SB', 0.2),
        {'S9': 0.01, 'S8': 0.01, 'S3': 0.01, 'S2': 0.01, 'S1': 0.01, 'DB': 0.04,
         'S6': 0.01, 'S5': 0.01, 'S4': 0.01, 'S19': 0.01, 'S18': 0.01, 'S13': 0.01,
         'S12': 0.01, 'S11': 0.01, 'S10': 0.01, 'S17': 0.01, 'S16': 0.01,
         'S15': 0.01, 'S14': 0.01, 'S7': 0.01, 'S20': 0.01, 'SB': 0.76})
     

My solution:
# Unit 5: Probability in the game of Darts

"""
In the game of darts, players throw darts at a board to score points.
The circular board has a 'bulls-eye' in the center and 20 slices
called sections, numbered 1 to 20, radiating out from the bulls-eye.
The board is also divided into concentric rings.  The bulls-eye has
two rings: an outer 'single' ring and an inner 'double' ring.  Each
section is divided into 4 rings: starting at the center we have a
thick single ring, a thin triple ring, another thick single ring, and
a thin double ring.  A ring/section combination is called a 'target';
they have names like 'S20', 'D20' and 'T20' for single, double, and
triple 20, respectively; these score 20, 40, and 60 points. The
bulls-eyes are named 'SB' and 'DB', worth 25 and 50 points
respectively. Illustration (png image): http://goo.gl/i7XJ9

There are several variants of darts play; in the game called '501',
each player throws three darts per turn, adding up points until they
total exactly 501. However, the final dart must be in a double ring.

Your first task is to write the function double_out(total), which will
output a list of 1 to 3 darts that add up to total, with the
restriction that the final dart is a double. See test_darts() for
examples. Return None if there is no list that achieves the total.

Often there are several ways to achieve a total.  You must return a
shortest possible list, but you have your choice of which one. For
example, for total=100, you can choose ['T20', 'D20'] or ['DB', 'DB']
but you cannot choose ['T20', 'D10', 'D10'].
"""

def test_darts():
    "Test the double_out function."
    assert double_out(170) == ['T20', 'T20', 'DB']
    assert double_out(171) == None
    assert double_out(100) in (['T20', 'D20'], ['DB', 'DB'])

"""
My strategy: I decided to choose the result that has the highest valued
target(s) first, e.g. always take T20 on the first dart if we can achieve
a solution that way.  If not, try T19 first, and so on. At first I thought
I would need three passes: first try to solve with one dart, then with two,
then with three.  But I realized that if we include 0 as a possible dart
value, and always try the 0 first, then we get the effect of having three
passes, but we only have to code one pass.  So I creted ordered_points as
a list of all possible scores that a single dart can achieve, with 0 first,
and then descending: [0, 60, 57, ..., 1].  I iterate dart1 and dart2 over
that; then dart3 must be whatever is left over to add up to total.  If
dart3 is a valid element of points, then we have a solution.  But the
solution, is a list of numbers, like [0, 60, 40]; we need to transform that
into a list of target names, like ['T20', 'D20'], we do that by defining name(d)
to get the name of a target that scores d.  When there are several choices,
we must choose a double for the last dart, but for the others I prefer the
easiest targets first: 'S' is easiest, then 'T', then 'D'.
"""


def double_out(total):
    """Return a shortest possible list of targets that add to total,
    where the length <= 3 and the final element is a double.
    If there is no solution, return None."""
    from itertools import ifilter
    targets = getTargets()
    #first we try to finish with a single shot (double out)
    for target in targets:
        if target[0] == total and target[2] == 'D':
            return [target[1]]
    #now we try to finish with two shots of which the last must be a double out
    for target1 in targets:
        for target2 in ifilter(lambda target: target[2] == 'D', targets):
            if target1[0] + target2[0] == total:
                return [target1[1], target2[1]]
    #so it seems we are bad at darts and are going to need 3 throws
    for target1 in targets:
        if target1[0] < total:
            for target2 in targets:
                if target1[0] + target2[0] < total:
                    for target3 in ifilter(lambda target: target[2] == 'D', targets):
                        if target1[0] + target2[0] + target3[0] == total:
                            return [target1[1], target2[1], target3[1]]
    return None


def getTargets():
    #returns a sorted (high to low) array of tuples of all possible targets in form
    #[(60, 'T20', 'T'), (57, 'T19', 'T'), ...,(50, 'DB', 'D'), ...,(19, 'S19', 'S'),...]
    targets =  [(3*i, 'T' + str(i), 'T') for i in range(1,21)] +  [(2*i, 'D' + str(i), 'D') for i in range(1,21)] + [(i, 'S' + str(i), 'S') for i in range(1,21)] + [(25, 'SB', 'S'), (50, 'DB', 'D')]
    targets.sort()
    targets.reverse()
    return targets

"""
def getTarget(targets, restvalue):
    #return best target for remaining points to throw or None if we can't double out
    for target in targets:
        if target[0] < restvalue:
            return target
        if target[0] == restvalue and target[2] == 'D':
            return target
    return None
"""

"""
It is easy enough to say "170 points? Easy! Just hit T20, T20, DB."
But, at least for me, it is much harder to actually execute the plan
and hit each target.  In this second half of the question, we
investigate what happens if the dart-thrower is not 100% accurate.

We will use a wrong (but still useful) model of inaccuracy. A player
has a single number from 0 to 1 that characterizes his/her miss rate.
If miss=0.0, that means the player hits the target every time.
But if miss is, say, 0.1, then the player misses the section s/he
is aiming at 10% of the time, and also (independently) misses the thin
double or triple ring 10% of the time. Where do the misses go?
Here's the model:

First, for ring accuracy.  If you aim for the triple ring, all the
misses go to a single ring (some to the inner one, some to the outer
one, but the model doesn't distinguish between these). If you aim for
the double ring (at the edge of the board), half the misses (e.g. 0.05
if miss=0.1) go to the single ring, and half off the board. (We will
agree to call the off-the-board 'target' by the name 'OFF'.) If you
aim for a thick single ring, it is about 5 times thicker than the thin
rings, so your miss ratio is reduced to 1/5th, and of these, half go to
the double ring and half to the triple.  So with miss=0.1, 0.01 will go
to each of the double and triple ring.  Finally, for the bulls-eyes. If
you aim for the single bull, 1/4 of your misses go to the double bull and
3/4 to the single ring.  If you aim for the double bull, it is tiny, so
your miss rate is tripled; of that, 2/3 goes to the single ring and 1/3
to the single bull ring.

Now, for section accuracy.  Half your miss rate goes one section clockwise
and half one section counter-clockwise from your target. The clockwise 
order of sections is:

    20 1 18 4 13 6 10 15 2 17 3 19 7 16 8 11 14 9 12 5

If you aim for the bull (single or double) and miss on rings, then the
section you end up on is equally possible among all 20 sections.  But
independent of that you can also miss on sections; again such a miss
is equally likely to go to any section and should be recorded as being
in the single ring.

You will need to build a model for these probabilities, and define the
function outcome(target, miss), which takes a target (like 'T20') and
a miss ration (like 0.1) and returns a dict of {target: probability}
pairs indicating the possible outcomes.  You will also define
best_target(miss) which, for a given miss ratio, returns the target 
with the highest expected score.

If you are very ambitious, you can try to find the optimal strategy for
accuracy-limited darts: given a state defined by your total score
needed and the number of darts remaining in your 3-dart turn, return
the target that minimizes the expected number of total 3-dart turns
(not the number of darts) required to reach the total.  This is harder
than Pig for several reasons: there are many outcomes, so the search space 
is large; also, it is always possible to miss a double, and thus there is
no guarantee that the game will end in a finite number of moves.
"""


def outcome(target, miss):
    "Return a probability distribution of [(target, probability)] pairs."
    from itertools import product
    ring = ring_outcome(target,miss)
    section = section_outcome(target, miss)
    if target in ['SB', 'DB']:
        result = {'SB': ring['SB'] * section['B'] + ring['S'] * section['B'], 'DB': ring['DB'] * section['B']} 
        for i in range(1,21):
            result['S' + str(i)] = section[str(i)]
        return result
    else:
        return dict((combi[0][0] + combi[1][0],  combi[0][1] * combi[1][1]) for combi in product(ring.items(), section.items()))


def ring_outcome(target, miss):
    #target = 'T20' | 'SB' | 'D5' | ...
    #returns dictionary of ring outcomes
    if target[0:2] == 'SB': #single bull
        return {'SB': 1 - miss, 'DB': miss * 0.25, 'S': miss * 0.75}
    elif target[0:2] == 'DB': #double bull
        return {'DB': 1 - miss * 3, 'SB': miss * 3 * 1./3, 'S': miss * 3 * 2./3}
    elif target[0] == 'T': #triple ring
        return {'T': 1 - miss, 'S': miss}   
    elif target[0] == 'D': #double ring
        return {'D': 1- miss, 'S': miss * 0.5} #OFF = miss * 0.5
    elif target[0] == 'S': #single ring
        return {'S': 1 - (miss / 5), 'D': (miss / 5) * 0.5, 'T': (miss / 5) * 0.5}
    else: #should not occur
        return {}

def section_outcome(target, miss):
    #target = 'T20' | 'SB' | 'D5' | ...
    #returns dictionary of section outcomes
    clockwise = [20, 1, 18, 4, 13, 6, 10, 15, 2, 17, 3, 19, 7, 16, 8, 11, 14, 9, 12, 5]
    misstargets = dict((str(clockwise[i]), (str(5),str(1))) if i == 1 else (str(clockwise[i]), (str(12),str(20))) if i == 19 else (str(clockwise[i]), (str(clockwise[i - 1]),str(clockwise[i + 1]))) for i in range(20))
    if target[0:2] in  ['SB', 'DB']:
        d = dict((str(i), miss / 20) for i in range(1,21))
        d['B'] = 1 - miss
        return d
    else:
        section = target[1:]
        leftmiss = misstargets[section][0]
        rightmiss = misstargets[section][1]
        return {section: 1 - miss, leftmiss: miss * 0.5, rightmiss: miss * 0.5}

def best_target(miss):
    "Return the target that maximizes the expected score."
    #[(60, 'T20', 'T'), (57, 'T19', 'T'), ...,(50, 'DB', 'D'), ...,(19, 'S19', 'S'),...]
    targets = getTargets()
    #first we create a dictionary (target: value) e.g. ('T20': 60)
    valueDict = dict((target[1], target[0]) for target in targets)
    return max(getAverageScore(target[1], miss, valueDict) for target in targets)[1]


def getAverageScore(target, miss, valueDict):
    #returns a tuple of format (score, target) e.g. (17.5,'T20') so we can use max function easily
    target_outcome = outcome(target, miss)
    score = 0
    for entry in target_outcome.items():
        miss_target = entry[0]
        probability = entry[1]
        score += probability * valueDict[miss_target]
    return (score, target)

    
def same_outcome(dict1, dict2):
    "Two states are the same if all corresponding sets of locs are the same."
    return all(abs(dict1.get(key, 0) - dict2.get(key, 0)) <= 0.0001
               for key in set(dict1) | set(dict2))

def test_darts2():
    assert best_target(0.0) == 'T20'
    assert best_target(0.1) == 'T20'
    assert best_target(0.4) == 'T19'
    assert same_outcome(outcome('T20', 0.0), {'T20': 1.0})
    assert same_outcome(outcome('T20', 0.1), 
                        {'T20': 0.81, 'S1': 0.005, 'T5': 0.045, 
                         'S5': 0.005, 'T1': 0.045, 'S20': 0.09})

final exam CS212: parking lot search

This is the fourth question from the Udacity CS212 final exam. I will update this article with my solution in 1 week. Please do not comment anything during the final exam week !!
"""
UNIT 4: Search

Your task is to maneuver a car in a crowded parking lot. This is a kind of 
puzzle, which can be represented with a diagram like this:

| | | | | | | |  
| G G . . . Y |  
| P . . B . Y | 
| P * * B . Y @ 
| P . . B . . |  
| O . . . A A |  
| O . S S S . |  
| | | | | | | | 

A '|' represents a wall around the parking lot, a '.' represents an empty square,
and a letter or asterisk represents a car.  '@' marks a goal square.
Note that there are long (3 spot) and short (2 spot) cars.
Your task is to get the car that is represented by '**' out of the parking lot
(on to a goal square).  Cars can move only in the direction they are pointing.  
In this diagram, the cars GG, AA, SSS, and ** are pointed right-left,
so they can move any number of squares right or left, as long as they don't
bump into another car or wall.  In this diagram, GG could move 1, 2, or 3 spots
to the right; AA could move 1, 2, or 3 spots to the left, and ** cannot move 
at all. In the up-down direction, BBB can move one up or down, YYY can move 
one down, and PPP and OO cannot move.

You should solve this puzzle (and ones like it) using search.  You will be 
given an initial state like this diagram and a goal location for the ** car;
in this puzzle the goal is the '.' empty spot in the wall on the right side.
You should return a path -- an alternation of states and actions -- that leads
to a state where the car overlaps the goal.

An action is a move by one car in one direction (by any number of spaces).  
For example, here is a successor state where the AA car moves 3 to the left:

| | | | | | | |  
| G G . . . Y |  
| P . . B . Y | 
| P * * B . Y @ 
| P . . B . . |  
| O A A . . . |  
| O . . . . . |  
| | | | | | | | 

And then after BBB moves 2 down and YYY moves 3 down, we can solve the puzzle
by moving ** 4 spaces to the right:

| | | | | | | |
| G G . . . . |
| P . . . . . |
| P . . . . * *
| P . . B . Y |
| O A A B . Y |
| O . . B . Y |
| | | | | | | |

You will write the function

    solve_parking_puzzle(start, N=N)

where 'start' is the initial state of the puzzle and 'N' is the length of a side
of the square that encloses the pieces (including the walls, so N=8 here).

We will represent the grid with integer indexes. Here we see the 
non-wall index numbers (with the goal at index 31):

 |  |  |  |  |  |  |  |
 |  9 10 11 12 13 14  |
 | 17 18 19 20 21 22  |
 | 25 26 27 28 29 30 31
 | 33 34 35 36 37 38  |
 | 41 42 43 44 45 46  |
 | 49 50 51 52 53 54  |
 |  |  |  |  |  |  |  |

The wall in the upper left has index 0 and the one in the lower right has 63.
We represent a state of the problem with one big tuple of (object, locations)
pairs, where each pair is a tuple and the locations are a tuple.  Here is the
initial state for the problem above in this format:
"""

puzzle1 = (
 ('@', (31,)),
 ('*', (26, 27)), 
 ('G', (9, 10)),
 ('Y', (14, 22, 30)), 
 ('P', (17, 25, 33)), 
 ('O', (41, 49)), 
 ('B', (20, 28, 36)), 
 ('A', (45, 46)), 
 ('|', (0, 1, 2, 3, 4, 5, 6, 7, 8, 15, 16, 23, 24, 32, 39,
        40, 47, 48, 55, 56, 57, 58, 59, 60, 61, 62, 63)))

# A solution to this puzzle is as follows:

#     path = solve_parking_puzzle(puzzle1, N=8)
#     path_actions(path) == [('A', -3), ('B', 16), ('Y', 24), ('*', 4)]

# That is, move car 'A' 3 spaces left, then 'B' 2 down, then 'Y' 3 down, 
# and finally '*' moves 4 spaces right to the goal.

# Your task is to define solve_parking_puzzle:

N = 8

def solve_parking_puzzle(start, N=N):
    """Solve the puzzle described by the starting position (a tuple 
    of (object, locations) pairs).  Return a path of [state, action, ...]
    alternating items; an action is a pair (object, distance_moved),
    such as ('B', 16) to move 'B' two squares down on the N=8 grid."""
    
# But it would also be nice to have a simpler format to describe puzzles,
# and a way to visualize states.
# You will do that by defining the following two functions:

def locs(start, n, incr=1):
    "Return a tuple of n locations, starting at start and incrementing by incr."


def grid(cars, N=N):
    """Return a tuple of (object, locations) pairs -- the format expected for
    this puzzle.  This function includes a wall pair, ('|', (0, ...)) to 
    indicate there are walls all around the NxN grid, except at the goal 
    location, which is the middle of the right-hand wall; there is a goal
    pair, like ('@', (31,)), to indicate this. The variable 'cars'  is a
    tuple of pairs like ('*', (26, 27)). The return result is a big tuple
    of the 'cars' pairs along with the walls and goal pairs."""


def show(state, N=N):
    "Print a representation of a state as an NxN grid."
    # Initialize and fill in the board.
    board = ['.'] * N**2
    for (c, squares) in state:
        for s in squares:
            board[s] = c
    # Now print it out
    for i,s in enumerate(board):
        print s,
        if i % N == N - 1: print

# Here we see the grid and locs functions in use:

puzzle1 = grid((
    ('*', locs(26, 2)),
    ('G', locs(9, 2)),
    ('Y', locs(14, 3, N)),
    ('P', locs(17, 3, N)),
    ('O', locs(41, 2, N)),
    ('B', locs(20, 3, N)),
    ('A', locs(45, 2))))

puzzle2 = grid((
    ('*', locs(26, 2)),
    ('B', locs(20, 3, N)),
    ('P', locs(33, 3)),
    ('O', locs(41, 2, N)),
    ('Y', locs(51, 3))))

puzzle3 = grid((
    ('*', locs(25, 2)),
    ('B', locs(19, 3, N)),
    ('P', locs(36, 3)),
    ('O', locs(45, 2, N)),
    ('Y', locs(49, 3))))


# Here are the shortest_path_search and path_actions functions from the unit.
# You may use these if you want, but you don't have to.

def shortest_path_search(start, successors, is_goal):
    """Find the shortest path from start state to a state
    such that is_goal(state) is true."""
    if is_goal(start):
        return [start]
    explored = set() # set of states we have visited
    frontier = [ [start] ] # ordered list of paths we have blazed
    while frontier:
        path = frontier.pop(0)
        s = path[-1]
        for (state, action) in successors(s).items():
            if state not in explored:
                explored.add(state)
                path2 = path + [action, state]
                if is_goal(state):
                    return path2
                else:
                    frontier.append(path2)
    return []

def path_actions(path):
    "Return a list of actions in this path."
    return path[1::2]

My solution:
"""
UNIT 4: Search

Your task is to maneuver a car in a crowded parking lot. This is a kind of 
puzzle, which can be represented with a diagram like this: 

| | | | | | | |  
| G G . . . Y |  
| P . . B . Y | 
| P * * B . Y @ 
| P . . B . . |  
| O . . . A A |  
| O . S S S . |  
| | | | | | | | 

A '|' represents a wall around the parking lot, a '.' represents an empty square,
and a letter or asterisk represents a car.  '@' marks a goal square.
Note that there are long (3 spot) and short (2 spot) cars.
Your task is to get the car that is represented by '**' out of the parking lot
(on to a goal square).  Cars can move only in the direction they are pointing.  
In this diagram, the cars GG, AA, SSS, and ** are pointed right-left,
so they can move any number of squares right or left, as long as they don't
bump into another car or wall.  In this diagram, GG could move 1, 2, or 3 spots
to the right; AA could move 1, 2, or 3 spots to the left, and ** cannot move 
at all. In the up-down direction, BBB can move one up or down, YYY can move 
one down, and PPP and OO cannot move.

You should solve this puzzle (and ones like it) using search.  You will be 
given an initial state like this diagram and a goal location for the ** car;
in this puzzle the goal is the '.' empty spot in the wall on the right side.
You should return a path -- an alternation of states and actions -- that leads
to a state where the car overlaps the goal.

An action is a move by one car in one direction (by any number of spaces).  
For example, here is a successor state where the AA car moves 3 to the left:

| | | | | | | |  
| G G . . . Y |  
| P . . B . Y | 
| P * * B . Y @ 
| P . . B . . |  
| O A A . . . |  
| O . . . . . |  
| | | | | | | | 

And then after BBB moves 2 down and YYY moves 3 down, we can solve the puzzle
by moving ** 4 spaces to the right:

| | | | | | | |
| G G . . . . |
| P . . . . . |
| P . . . . * *
| P . . B . Y |
| O A A B . Y |
| O . . B . Y |
| | | | | | | |

You will write the function

    solve_parking_puzzle(start, N=N)

where 'start' is the initial state of the puzzle and 'N' is the length of a side
of the square that encloses the pieces (including the walls, so N=8 here).

We will represent the grid with integer indexes. Here we see the 
non-wall index numbers (with the goal at index 31):

 |  |  |  |  |  |  |  |
 |  9 10 11 12 13 14  |
 | 17 18 19 20 21 22  |
 | 25 26 27 28 29 30 31
 | 33 34 35 36 37 38  |
 | 41 42 43 44 45 46  |
 | 49 50 51 52 53 54  |
 |  |  |  |  |  |  |  |

The wall in the upper left has index 0 and the one in the lower right has 63.
We represent a state of the problem with one big tuple of (object, locations)
pairs, where each pair is a tuple and the locations are a tuple.  Here is the
initial state for the problem above in this format:
"""

puzzle0 = (
 ('@', (31,)),
 ('*', (26, 27)), 
 ('G', (9, 10)),
 ('Y', (14, 22, 30)), 
 ('P', (17, 25, 33)), 
 ('O', (41, 49)), 
 ('B', (20, 28, 36)), 
 ('A', (45, 46)), 
 ('|', (0, 1, 2, 3, 4, 5, 6, 7, 8, 15, 16, 23, 24, 32, 39,
        40, 47, 48, 55, 56, 57, 58, 59, 60, 61, 62, 63)))

# A solution to this puzzle is as follows:

#     path = solve_parking_puzzle(puzzle1, N=8)
#     path_actions(path) == [('A', -3), ('B', 16), ('Y', 24), ('*', 4)]

# That is, move car 'A' 3 spaces left, then 'B' 2 down, then 'Y' 3 down, 
# and finally '*' moves 4 spaces right to the goal.

# Your task is to define solve_parking_puzzle:

N = 8

def solve_parking_puzzle(start, N=N):
    """Solve the puzzle described by the starting position (a tuple 
    of (object, locations) pairs).  Return a path of [state, action, ...]
    alternating items; an action is a pair (object, distance_moved),
    such as ('B', 16) to move 'B' two squares down on the N=8 grid."""
    return shortest_path_search(start, csuccessors, isGoal, N)

def csuccessors(state, N, goal):
    if isGoal(state, goal):
        return {}
    cars = [car for car in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ*']
    successors = []
    currentStateDict = getStateDict(state, N)
    successors += [successor for symbol, coords in state if symbol in cars for successor in getSuccessors(symbol, coords, state, currentStateDict, N)]
    #print successors
    return dict(successors)

def getStateDict(state, N):
    dict = {}
    for i in range(1, N*N + 1):
        dict[i] = '.'          #mark as freespot
    for symbol, coords in state:
        for coord in coords:
            dict[coord] = symbol   #override used spots
    return dict

def drivesHorizontally(coords):
    #we check if first two coordinates are adjacent
    return True if coords[0] == coords[1] - 1 else False

def getSuccessors(car, coords, state, dict, N):
    #[('A', -3), ('B', 16), ('Y', 24), ('*', 4)]
    # That is, move car 'A' 3 spaces left, then 'B' 2 down, then 'Y' 3 down, 
    # and finally '*' moves 4 spaces right to the goal.
    result = []
    if drivesHorizontally(coords):
        #move left
        i = 1
        while (coords[0] - i) in dict and dict[coords[0] - i] in ['.', '@']:
            #print car + ' moves left'
            result.append((getNewState(state, car, -i), (car, -i))) 
            i += 1 
        #move right
        i = 1
        while (coords[-1] + i) in dict and dict[coords[-1] + i] in ['.', '@']:
            #print car + ' moves right'
            result.append((getNewState(state, car,  i), (car, i))) 
            i += 1 
    else:
        #move up
        i = 1
        while (coords[0] -i * N) in dict and dict[coords[0] -i * N] in ['.', '@']:
            #print car + ' moves up'
            result.append((getNewState(state, car,  -i * N), (car, -i * N))) 
            i += 1 
        #move down
        i = 1
        while (coords[-1] + i * N) in dict and dict[coords[-1] + i * N] in ['.', '@']:
            #print car + ' moves down'
            result.append((getNewState(state, car, i * N), (car, i * N))) 
            i += 1 
    return result

def getNewState(oldState, car, movedBy):
    newState = []
    for symbol, coords in oldState:
        if symbol == car:
            newState.append((symbol, addToVector(coords, movedBy)))
        else:
            newState.append((symbol, coords))
    return tuple(newState) 

def isGoal(state, goal):
    #The solution state should contain both the car and the goal ('*', (30, 31)), ('@', (31,))
    # ('@', (31,)),
    # ('*', (26, 27)), 
    for symbol, coords in state:
         if symbol == '*':
             if goal in coords:
                 return True
    return False

def getGoal(state):
    #return the goal coordinate
    for symbol, coords in state:
         if symbol == '@':
             return coords[0]
    
# But it would also be nice to have a simpler format to describe puzzles,
# and a way to visualize states.
# You will do that by defining the following two functions:

def locs(start, n, incr=1):
    "Return a tuple of n locations, starting at start and incrementing by incr."
    return tuple([start] + [start + incr*i for i in range(1,n)])


def getGoalCoordinate(N):  
   if N%2 == 0:  
      return N-1 + (N/2 -1)*N  
   else:  
      return N-1 + (N-1)/2 *N

def getWallCoords(N):
    goal = getGoalCoordinate(N)
    for i in range(1,N +1):
        if i == 1:
            for x in range(N):
                yield x
        elif i == N:
            start = (N-1) * N
            for x in range(start, start +N):
                yield x
        else: 
            start = (i-1) * N
            end  = start + N - 1
            yield start
            if end != goal:
                yield end

def grid(cars, N=N):
    """Return a tuple of (object, locations) pairs -- the format expected for
    this puzzle.  This function includes a wall pair, ('|', (0, ...)) to 
    indicate there are walls all around the NxN grid, except at the goal 
    location, which is the middle of the right-hand wall; there is a goal
    pair, like ('@', (31,)), to indicate this. The variable 'cars'  is a
    tuple of pairs like ('*', (26, 27)). The return result is a big tuple
    of the 'cars' pairs along with the walls and goal pairs."""
    return tuple([('@', (getGoalCoordinate(N),)), ('|', tuple(getWallCoords(N)))] + [car for car in cars])

def show(state, N=N):
    "Print a representation of a state as an NxN grid."
    # Initialize and fill in the board.
    board = ['.'] * N**2
    for (c, squares) in state:
        for s in squares:
            board[s] = c
    # Now print it out
    for i,s in enumerate(board):
        print s,
        if i % N == N - 1: print

# Here we see the grid and locs functions in use:

puzzle1 = grid((
    ('*', locs(26, 2)),
    ('G', locs(9, 2)),
    ('Y', locs(14, 3, N)),
    ('P', locs(17, 3, N)),
    ('O', locs(41, 2, N)),
    ('B', locs(20, 3, N)),
    ('A', locs(45, 2))))

puzzle2 = grid((
    ('*', locs(26, 2)),
    ('B', locs(20, 3, N)),
    ('P', locs(33, 3)),
    ('O', locs(41, 2, N)),
    ('Y', locs(51, 3))))

puzzle3 = grid((
    ('*', locs(25, 2)),
    ('B', locs(19, 3, N)),
    ('P', locs(36, 3)),
    ('O', locs(45, 2, N)),
    ('Y', locs(49, 3))))


# Here are the shortest_path_search and path_actions functions from the unit.
# You may use these if you want, but you don't have to.

def shortest_path_search(start, successors, is_goal, N):
    """Find the shortest path from start state to a state
    such that is_goal(state) is true."""
    goal = getGoal(start)
    if is_goal(start, goal):
        return [start]
    explored = set() # set of states we have visited
    frontier = [ [start] ] # ordered list of paths we have blazed
    while frontier:
        path = frontier.pop(0)
        s = path[-1]
        for (state, action) in successors(s,N, goal).items():
            if state not in explored:
                explored.add(state)
                path2 = path + [action, state]
                #print action
                #print show(state,N)
                if is_goal(state, goal):
                    return path2
                else:
                    frontier.append(path2)
    return []


def path_actions(path):
    "Return a list of actions in this path."
    return path[1::2]

def addToVector(v1, n):
    v2 = tuple((n for i in range(len(v1))))
    return add_vectors(v1,v2)

def add_vectors(v1, v2):
    return tuple(x + y for x,y in zip(v1,v2))

def showAndSolve(puzzle):
    show(puzzle, N)
    solution = solve_parking_puzzle(puzzle, N)
    print path_actions(solution)

final exam CS212: Polynomials

This is the third question from the Udacity CS212 final exam. I will update this article with my solution in 1 week. Please do not comment anything during the final exam week !!

"""
UNIT 3: Functions and APIs: Polynomials

A polynomial is a mathematical formula like:

    30 * x**2 + 20 * x + 10

More formally, it involves a single variable (here 'x'), and the sum of one
or more terms, where each term is a real number multiplied by the variable
raised to a non-negative integer power. (Remember that x**0 is 1 and x**1 is x,
so 'x' is short for '1 * x**1' and '10' is short for '10 * x**0'.)

We will represent a polynomial as a Python function which computes the formula
when applied to a numeric value x.  The function will be created with the call:

    p1 = poly((10, 20, 30))

where the nth element of the input tuple is the coefficient of the nth power of x.
(Note the order of coefficients has the x**n coefficient neatly in position n of 
the list, but this is the reversed order from how we usually write polynomials.)
poly returns a function, so we can now apply p1 to some value of x:

    p1(0) == 10

Our representation of a polynomial is as a callable function, but in addition,
we will store the coefficients in the .coef attribute of the function, so we have:

    p1.coef == (10, 20, 30)

And finally, the name of the function will be the formula given above, so you should
have something like this:

    >>> p1
    

    >>> p1.__name__
    '30 * x**2 + 20 * x + 10'

Make sure the formula used for function names is simplified properly.
No '0 * x**n' terms; just drop these. Simplify '1 * x**n' to 'x**n'.
Simplify '5 * x**0' to '5'.  Similarly, simplify 'x**1' to 'x'.
For negative coefficients, like -5, you can use '... + -5 * ...' or
'... - 5 * ...'; your choice. I'd recommend no spaces around '**' 
and spaces around '+' and '*', but you are free to use your preferences.

Your task is to write the function poly and the following additional functions:

    is_poly, add, sub, mul, power, deriv, integral

They are described below; see the test_poly function for examples.
"""


def poly(coefs):
    """Return a function that represents the polynomial with these coefficients.
    For example, if coefs=(10, 20, 30), return the function of x that computes
    '30 * x**2 + 20 * x + 10'.  Also store the coefs on the .coefs attribute of
    the function, and the str of the formula on the .__name__ attribute.'"""
    # your code here (I won't repeat "your code here"; there's one for each function)


def test_poly():
    global p1, p2, p3, p4, p5, p9 # global to ease debugging in an interactive session

    p1 = poly((10, 20, 30))
    assert p1(0) == 10
    for x in (1, 2, 3, 4, 5, 1234.5):
        assert p1(x) == 30 * x**2 + 20 * x + 10
    assert same_name(p1.__name__, '30 * x**2 + 20 * x + 10')

    assert is_poly(p1)
    assert not is_poly(abs) and not is_poly(42) and not is_poly('cracker')

    p3 = poly((0, 0, 0, 1))
    assert p3.__name__ == 'x**3'
    p9 = mul(p3, mul(p3, p3))
    assert p9 == poly([0,0,0,0,0,0,0,0,0,1])
    assert p9(2) == 512
    p4 =  add(p1, p3)
    assert same_name(p4.__name__, 'x**3 + 30 * x**2 + 20 * x + 10')

    assert same_name(poly((1, 1)).__name__, 'x + 1')
    assert (power(poly((1, 1)), 10).__name__ == 
            'x**10 + 10 * x**9 + 45 * x**8 + 120 * x**7 + 210 * x**6 + 252 * x**5 + 210' +
            ' * x**4 + 120 * x**3 + 45 * x**2 + 10 * x + 1')

    assert add(poly((10, 20, 30)), poly((1, 2, 3))) == poly((11, 22, 33))
    assert sub(poly((10, 20, 30)), poly((1, 2, 3))) == poly((9, 18, 27))
    assert mul(poly((10, 20, 30)), poly((1, 2, 3))) == poly((10, 40, 100, 120, 90))
    assert power(poly((1, 1)), 2) == poly((1, 2, 1))
    assert power(poly((1, 1)), 10) == poly((1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1))

    assert deriv(p1) == poly((20, 60))
    assert integral(poly((20, 60))) == poly((0, 20, 30))
    p5 = poly((0, 1, 2, 3, 4, 5))
    assert same_name(p5.__name__, '5 * x**5 + 4 * x**4 + 3 * x**3 + 2 * x**2 + x')
    assert p5(1) == 15
    assert p5(2) == 258
    assert same_name(deriv(p5).__name__,  '25 * x**4 + 16 * x**3 + 9 * x**2 + 4 * x + 1')
    assert deriv(p5)(1) == 55
    assert deriv(p5)(2) == 573


def same_name(name1, name2):
    """I define this function rather than doing name1 == name2 to allow for some
    variation in naming conventions."""
    def canonical_name(name): return name.replace(' ', '').replace('+-', '-')
    return canonical_name(name1) == canonical_name(name2)

def is_poly(x):
    "Return true if x is a poly (polynomial)."
    ## For examples, see the test_poly function

def add(p1, p2):
    "Return a new polynomial which is the sum of polynomials p1 and p2."


def sub(p1, p2):
    "Return a new polynomial which is the difference of polynomials p1 and p2."


def mul(p1, p2):
    "Return a new polynomial which is the product of polynomials p1 and p2."


def power(p, n):
    "Return a new polynomial which is p to the nth power (n a non-negative integer)."


"""
If your calculus is rusty (or non-existant), here is a refresher:
The deriviative of a polynomial term (c * x**n) is (c*n * x**(n-1)).
The derivative of a sum is the sum of the derivatives.
So the derivative of (30 * x**2 + 20 * x + 10) is (60 * x + 20).

The integral is the anti-derivative:
The integral of 60 * x + 20 is  30 * x**2 + 20 * x + C, for any constant C.
Any value of C is an equally good anti-derivative.  We allow C as an argument
to the function integral (withh default C=0).
"""
    
def deriv(p):
    "Return the derivative of a function p (with respect to its argument)."


def integral(p, C=0):
    "Return the integral of a function p (with respect to its argument)."


"""
Now for an extra credit challenge: arrange to describe polynomials with an
expression like '3 * x**2 + 5 * x + 9' rather than (9, 5, 3).  You can do this
in one (or both) of two ways:

(1) By defining poly as a class rather than a function, and overloading the 
__add__, __sub__, __mul__, and __pow__ operators, etc.  If you choose this,
call the function test_poly1().  Make sure that poly objects can still be called.

(2) Using the grammar parsing techniques we learned in Unit 5. For this
approach, define a new function, Poly, which takes one argument, a string,
as in Poly('30 * x**2 + 20 * x + 10').  Call test_poly2().
"""

def test_poly1():
    # I define x as the polynomial 1*x + 0.
    x = poly((0, 1))
    # From here on I can create polynomials by + and * operations on x.
    newp1 =  30 * x**2 + 20 * x + 10 # This is a poly object, not a number!
    assert p1(100) == newp1(100) # The new poly objects are still callable.
    assert p1.__name__ == newp1.__name__
    assert (x + 1) * (x - 1) == x**2 - 1 == poly((-1, 0, 1))

def test_poly2():
    newp1 = Poly('30 * x**2 + 20 * x + 10')
    assert p1(100) == newp1(100)
    assert p1.__name__ == newp1.__name__
    assert Poly('x + 1') * Poly('x - 1') == Poly('x**2 - 1')

My solution:

"""
UNIT 3: Functions and APIs: Polynomials

A polynomial is a mathematical formula like:

    30 * x**2 + 20 * x + 10

More formally, it involves a single variable (here 'x'), and the sum of one
or more terms, where each term is a real number multiplied by the variable
raised to a non-negative integer power. (Remember that x**0 is 1 and x**1 is x,
so 'x' is short for '1 * x**1' and '10' is short for '10 * x**0'.)

We will represent a polynomial as a Python function which computes the formula
when applied to a numeric value x.  The function will be created with the call:

    p1 = poly((10, 20, 30))

where the nth element of the input tuple is the coefficient of the nth power of x.
(Note the order of coefficients has the x**n coefficient neatly in position n of 
the list, but this is the reversed order from how we usually write polynomials.)
poly returns a function, so we can now apply p1 to some value of x:

    p1(0) == 10

Our representation of a polynomial is as a callable function, but in addition,
we will store the coefficients in the .coef attribute of the function, so we have:

    p1.coef == (10, 20, 30)

And finally, the name of the function will be the formula given above, so you should
have something like this:

    >>> p1
    

    >>> p1.__name__
    '30 * x**2 + 20 * x + 10'

Make sure the formula used for function names is simplified properly.
No '0 * x**n' terms; just drop these. Simplify '1 * x**n' to 'x**n'.
Simplify '5 * x**0' to '5'.  Similarly, simplify 'x**1' to 'x'.
For negative coefficients, like -5, you can use '... + -5 * ...' or
'... - 5 * ...'; your choice. I'd recommend no spaces around '**' 
and spaces around '+' and '*', but you are free to use your preferences.

Your task is to write the function poly and the following additional functions:

    is_poly, add, sub, mul, power, deriv, integral

They are described below; see the test_poly function for examples.
"""


def poly(coefs):
    """Return a function that represents the polynomial with these coefficients.
    For example, if coefs=(10, 20, 30), return the function of x that computes
    '30 * x**2 + 20 * x + 10'.  Also store the coefs on the .coefs attribute of
    the function, and the str of the formula on the .__name__ attribute.'"""
    # your code here (I won't repeat "your code here"; there's one for each function)
    formula = getFormula(coefs)
    def p(x):
        return eval(formula.replace('x', str(x)))
    p.coefs = coefs
    p.__name__ = formula
    return p

def getFormula(coefs):
    coefs_list = list(coefs)
    coefs_list.reverse()
    #(10, 20, 30) results in '30 * x**2 + 20 * x + 10'
    return ' + '.join(map_coef(coef, len(coefs_list) - index - 1) for index, coef in enumerate(coefs_list) if map_coef(coef, len(coefs_list) - index - 1) != '')

def map_coef(coef, index):
    """
    map_coef(7, 3)  = '7 * x**3'
    map_coef(10, 2) = '10 * x**2'
    map_coef(5, 1)  = '5 * x'
    map_coef(0, 2)  = ''      <-- 0 * x**2
    map_coef(1, 2)  = 'x**2'  <-- 1 * x**2 
    map_coef(3, 0)  = '3'
    """
    if index == 0:
        return str(coef) if coef != 0 else ''
    elif index == 1:
        if coef == 0: 
            return ''
        elif coef == 1: 
            return 'x'
        else: 
            return str(coef) + ' * x'
    else:
        if coef == 0:
            return ''
        if coef == 1:
            return 'x**' + str(index)
        else:
            return str(coef) + ' * x**' + str(index)

def coefsDictionaryToTuple(coefs_dict):
    dict_to_list = coefs_dict.items()
    dict_to_list.sort()
    return tuple((ele[1] for ele in dict_to_list))

def coefs_product(coefs1, coefs2):
    #coef1=(10, 20, 30), coefs2=(1, 2, 3)
    prod = []
    for index1,coef1 in enumerate(coefs1):
        for index2, coef2 in enumerate(coefs2):
            prod.append((index1 + index2, coef1 * coef2))
    #prod => [(0, 10), (1, 20), (2, 30), (1, 20), (2, 40), (3, 60), (2, 30), (3, 60), (4, 90)]
    coefs_dict = {} #we will store tuples of same format in this dict but add up coefs with same index
    for ele in prod:
        if ele[0] not in coefs_dict:
            #we create entry
            coefs_dict[ele[0]] = ele[1]
        else:
            #we update entry by adding current coef
            coefs_dict[ele[0]] = coefs_dict[ele[0]] + ele[1]
    return coefsDictionaryToTuple(coefs_dict)

def coefs_add(coefs1, coefs2):
    return coefs_op(coefs1, coefs2, lambda x,y: x + y)

def coefs_sub(coefs1, coefs2):
    return coefs_op(coefs1, coefs2, lambda x,y: x - y)

def coefs_op(coefs1, coefs2, op):
    coefs_dict = {}
    for index, coef in enumerate(coefs1):
        coefs_dict[index] = coef
    for index, coef in enumerate(coefs2):
        if index not in coefs_dict:
            #we create entry
            coefs_dict[index] = coef
        else:
            #we update entry by adding current coef
            coefs_dict[index] = op(coefs_dict[index], coef)
    return coefsDictionaryToTuple(coefs_dict)
       
def test_poly():
    global p1, p2, p3, p4, p5, p9 # global to ease debugging in an interactive session

    p1 = poly((10, 20, 30))
    assert p1(0) == 10
    for x in (1, 2, 3, 4, 5, 1234.5):
        assert p1(x) == 30 * x**2 + 20 * x + 10
    assert same_name(p1.__name__, '30 * x**2 + 20 * x + 10')

    assert is_poly(p1)
    assert not is_poly(abs) and not is_poly(42) and not is_poly('cracker')

    p3 = poly((0, 0, 0, 1))
    assert p3.__name__ == 'x**3'
    p9 = mul(p3, mul(p3, p3))
    assert p9(2) == 512
    p4 =  add(p1, p3)
    assert same_name(p4.__name__, 'x**3 + 30 * x**2 + 20 * x + 10')

    assert same_name(poly((1, 1)).__name__, 'x + 1')
    assert (power(poly((1, 1)), 10).__name__ == 
            'x**10 + 10 * x**9 + 45 * x**8 + 120 * x**7 + 210 * x**6 + 252 * x**5 + 210' +
            ' * x**4 + 120 * x**3 + 45 * x**2 + 10 * x + 1')

    assert add(poly((10, 20, 30)), poly((1, 2, 3))).coefs == (11,22,33)
    assert sub(poly((10, 20, 30)), poly((1, 2, 3))).coefs == (9,18,27) 
    assert mul(poly((10, 20, 30)), poly((1, 2, 3))).coefs == (10, 40, 100, 120, 90)
    assert power(poly((1, 1)), 2).coefs == (1, 2, 1) 
    assert power(poly((1, 1)), 10).coefs == (1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1)

    assert deriv(p1).coefs == (20, 60)
    assert integral(poly((20, 60))).coefs == (0, 20, 30)
    p5 = poly((0, 1, 2, 3, 4, 5))
    assert same_name(p5.__name__, '5 * x**5 + 4 * x**4 + 3 * x**3 + 2 * x**2 + x')
    assert p5(1) == 15
    assert p5(2) == 258
    assert same_name(deriv(p5).__name__,  '25 * x**4 + 16 * x**3 + 9 * x**2 + 4 * x + 1')
    assert deriv(p5)(1) == 55
    assert deriv(p5)(2) == 573


def same_name(name1, name2):
    """I define this function rather than doing name1 == name2 to allow for some
    variation in naming conventions."""
    def canonical_name(name): return name.replace(' ', '').replace('+-', '-')
    return canonical_name(name1) == canonical_name(name2)

def is_poly(x):
    "Return true if x is a poly (polynomial)."
    ## For examples, see the test_poly function
    return hasattr(x, '__call__') and isinstance(x(1), int)  and x.__name__.find('x') != -1

def add(p1, p2):
    "Return a new polynomial which is the sum of polynomials p1 and p2."
    return poly(coefs_add(p1.coefs, p2.coefs))


def sub(p1, p2):
    "Return a new polynomial which is the difference of polynomials p1 and p2."
    return poly(coefs_sub(p1.coefs, p2.coefs))

def mul(p1, p2):
    "Return a new polynomial which is the product of polynomials p1 and p2."
    return poly(coefs_product(p1.coefs, p2.coefs))

def power(p, n):
    "Return a new polynomial which is p to the nth power (n a non-negative integer)."
    if n in [0,1]:
        return p
    else:
        return mul(p, power(p,n-1))   


"""
If your calculus is rusty (or non-existant), here is a refresher:
The deriviative of a polynomial term (c * x**n) is (c*n * x**(n-1)).
The derivative of a sum is the sum of the derivatives.
So the derivative of (30 * x**2 + 20 * x + 10) is (60 * x + 20).

The integral is the anti-derivative:
The integral of 60 * x + 20 is  30 * x**2 + 20 * x + C, for any constant C.
Any value of C is an equally good anti-derivative.  We allow C as an argument
to the function integral (withh default C=0).
"""
    
def deriv(p):
    "Return the derivative of a function p (with respect to its argument)."
    coefs_new = tuple((index * coef for index, coef in enumerate(p.coefs) if index > 0))
    return poly(coefs_new)

def integral(p, C=0):
    "Return the integral of a function p (with respect to its argument)."
    #The integral of 60 * x + 20  ==  30 * x**2 + 20 * x + C, for any constant C.
    #assert integral(poly((20, 60))).coefs == (0, 20, 30)
    coefs_new = tuple([C] + [coef / (index + 1)  for index, coef in enumerate(p.coefs)])
    return poly(coefs_new)


"""
Now for an extra credit challenge: arrange to describe polynomials with an
expression like '3 * x**2 + 5 * x + 9' rather than (9, 5, 3).  You can do this
in one (or both) of two ways:

(1) By defining poly as a class rather than a function, and overloading the 
__add__, __sub__, __mul__, and __pow__ operators, etc.  If you choose this,
call the function test_poly1().  Make sure that poly objects can still be called.

(2) Using the grammar parsing techniques we learned in Unit 5. For this
approach, define a new function, Poly, which takes one argument, a string,
as in Poly('30 * x**2 + 20 * x + 10').  Call test_poly2().
"""


def test_poly1():
    # I define x as the polynomial 1*x + 0.
    x = poly((0, 1))
    # From here on I can create polynomials by + and * operations on x.
    newp1 =  30 * x**2 + 20 * x + 10 # This is a poly object, not a number!
    assert p1(100) == newp1(100) # The new poly objects are still callable.
    assert p1.__name__ == newp1.__name__
    assert (x + 1) * (x - 1) == x**2 - 1 == poly((-1, 0, 1))

def test_poly2():
    newp1 = Poly('30 * x**2 + 20 * x + 10')
    assert p1(100) == newp1(100)
    assert p1.__name__ == newp1.__name__
    assert Poly('x + 1') * Poly('x - 1') == Poly('x**2 - 1')


final exam CS212: Logic Puzzle

This is the second question from the Udacity CS212 final exam. I will update this article with my solution in 1 week. Please do not comment anything during the final exam week !!
"""
UNIT 2: Logic Puzzle

You will write code to solve the following logic puzzle:

1. The person who arrived on Wednesday bought the laptop.
2. The programmer is not Wilkes.
3. Of the programmer and the person who bought the droid,
   one is Wilkes and the other is Hamming.
4. The writer is not Minsky.
5. Neither Knuth nor the person who bought the tablet is the manager.
6. Knuth arrived the day after Simon.
7. The person who arrived on Thursday is not the designer.
8. The person who arrived on Friday didn't buy the tablet.
9. The designer didn't buy the droid.
10. Knuth arrived the day after the manager.
11. Of the person who bought the laptop and Wilkes,
    one arrived on Monday and the other is the writer.
12. Either the person who bought the iphone or the person who bought the tablet
    arrived on Tuesday.

You will write the function logic_puzzle(), which should return a list of the
names of the people in the order in which they arrive. For example, if they
happen to arrive in alphabetical order, Hamming on Monday, Knuth on Tuesday, etc.,
then you would return:

['Hamming', 'Knuth', 'Minsky', 'Simon', 'Wilkes']

(You can assume that the days mentioned are all in the same week.)
"""


def logic_puzzle():
    "Return a list of the names of the people, in the order they arrive."
    ## your code here; you are free to define additional functions if needed
    


My solution:
"""
UNIT 2: Logic Puzzle

You will write code to solve the following logic puzzle:

1. The person who arrived on Wednesday bought the laptop.
2. The programmer is not Wilkes.
3. Of the programmer and the person who bought the droid,
   one is Wilkes and the other is Hamming.
4. The writer is not Minsky.
5. Neither Knuth nor the person who bought the tablet is the manager.
6. Knuth arrived the day after Simon.
7. The person who arrived on Thursday is not the designer.
8. The person who arrived on Friday didn't buy the tablet.
9. The designer didn't buy the droid.
10. Knuth arrived the day after the manager.
11. Of the person who bought the laptop and Wilkes,
    one arrived on Monday and the other is the writer.
12. Either the person who bought the iphone or the person who bought the tablet
    arrived on Tuesday.

You will write the function logic_puzzle(), which should return a list of the
names of the people in the order in which they arrive. For example, if they
happen to arrive in alphabetical order, Hamming on Monday, Knuth on Tuesday, etc.,
then you would return:

['Hamming', 'Knuth', 'Minsky', 'Simon', 'Wilkes']

(You can assume that the days mentioned are all in the same week.)
"""


def logic_puzzle():
    import itertools
    "Return a list of the names of the people, in the order they arrive."
    days = monday, tuesday, wednesday, thursday, friday = [1,2,3,4,5]
    orderings = list(itertools.permutations(days))
    (Wilkes, Hamming, Minsky, Knuth, Simon) = next((Wilkes, Hamming, Minsky, Knuth, Simon)
        for (Wilkes, Hamming, Minsky, Knuth, Simon) in orderings
            if Knuth == Simon + 1              # from [6]
        for (programmer, writer, manager, designer, unemployed) in orderings
            if programmer == Hamming           # from [2] and [3]
            and writer != Minsky               # from [4]
            and Knuth != manager               # from [5]
            and designer != thursday           # from [7]
            and Knuth == manager + 1           # from [10]
            and monday != writer               # from [11]
        for (laptop, droid, tablet, iphone, nothing) in orderings
            if laptop == wednesday             # from [1]
            and programmer != droid            # from [2] and [3]
            and droid == Wilkes                # from [2] and [3]
            and tablet != manager              # from [5]
            and tablet != friday               # from [8]
            and designer != droid              # from [9]
            and monday in [laptop, Wilkes]     # from [11]
            and writer in [laptop, Wilkes]     # from [11]
            and tuesday in [iphone, tablet]    # from [12]
    )
    solution = [
                (Wilkes, 'Wilkes'), 
                (Hamming, 'Hamming'), 
                (Minsky, 'Minsky'),
                (Knuth, 'Knuth'),
                (Simon, 'Simon')
               ]
    solution.sort()
    return [element[1] for element in solution]

print logic_puzzle()

Final exam CS212: bowling puzzler

This is the first question from the Udacity CS212 final exam. I will update this article with my solution in 1 week. Please do not comment anything during the final exam week !!
"""
UNIT 1: Bowling:

You will write the function bowling(balls), which returns an integer indicating
the score of a ten-pin bowling game.  balls is a list of integers indicating
how many pins are knocked down with each ball.  For example, a perfect game of
bowling would be described with:

    >>> bowling([10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10])
    300

The rules of bowling are as follows:

(1) A game consists of 10 frames. In each frame you roll one or two balls,
except for the tenth frame, where you roll one, two, or three.  Your total
score is the sum of your scores for the ten frames.
(2) If you knock down fewer than ten pins with your two balls in the frame,
you score the total knocked down.  For example, bowling([8, 1, 7, ...]) means
that you knocked down a total of 9 pins in the first frame.  You score 9 point
for the frame, and you used up two balls in the frame. The second frame will
start with the 7.
(3) If you knock down all ten pins on your second ball it is called a 'spare'
and you score 10 points plus a bonus: whatever you roll with your next ball.
The next ball will also count in the next frame, so the next ball counts twice
(except in the tenth frame, in which case the bonus ball counts only once).
For example, bowling([8, 2, 7, ...]) means you get a spare in the first frame.
You score 10 + 7 for the frame; the second frame starts with the 7.
(4) If you knock down all ten pins on your first ball it is called a 'strike'
and you score 10 points plus a bonus of your score on the next two balls.
(The next two balls also count in the next frame, except in the tenth frame.)
For example, bowling([10, 7, 3, ...]) means that you get a strike, you score
10 + 7 + 3 = 20 in the first frame; the second frame starts with the 7.

"""

def bowling(balls):
    "Compute the total score for a player's game of bowling."
    #TODO: write your code here

def test_bowling():
    assert   0 == bowling([0] * 20)
    assert  20 == bowling([1] * 20)
    assert  80 == bowling([4] * 20)
    assert 190 == bowling([9,1] * 10 + [9])
    assert 300 == bowling([10] * 12)
    assert 200 == bowling([10, 5,5] * 5 + [10])
    assert  11 == bowling([0,0] * 9 + [10,1,0])
    assert  12 == bowling([0,0] * 8 + [10, 1,0])

test_bowling()   
My solution:
"""
UNIT 1: Bowling:

You will write the function bowling(balls), which returns an integer indicating
the score of a ten-pin bowling game.  balls is a list of integers indicating
how many pins are knocked down with each ball.  For example, a perfect game of
bowling would be described with:

    >>> bowling([10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10])
    300

The rules of bowling are as follows:

(1) A game consists of 10 frames. In each frame you roll one or two balls,
except for the tenth frame, where you roll one, two, or three.  Your total
score is the sum of your scores for the ten frames.
(2) If you knock down fewer than ten pins with your two balls in the frame,
you score the total knocked down.  For example, bowling([8, 1, 7, ...]) means
that you knocked down a total of 9 pins in the first frame.  You score 9 point
for the frame, and you used up two balls in the frame. The second frame will
start with the 7.
(3) If you knock down all ten pins on your second ball it is called a 'spare'
and you score 10 points plus a bonus: whatever you roll with your next ball.
The next ball will also count in the next frame, so the next ball counts twice
(except in the tenth frame, in which case the bonus ball counts only once).
For example, bowling([8, 2, 7, ...]) means you get a spare in the first frame.
You score 10 + 7 for the frame; the second frame starts with the 7.
(4) If you knock down all ten pins on your first ball it is called a 'strike'
and you score 10 points plus a bonus of your score on the next two balls.
(The next two balls also count in the next frame, except in the tenth frame.)
For example, bowling([10, 7, 3, ...]) means that you get a strike, you score
10 + 7 + 3 = 20 in the first frame; the second frame starts with the 7.

"""

def bowling(balls):
    "Compute the total score for a player's game of bowling."
    balls.reverse()
    score = countScore(balls, 0, 0)
    return score

def countScore(balls, frame, score):
    frame += 1
    if not balls:
        return score
    ball1 = balls.pop()
    if ball1 == 10:
        #we got a strike so we need to add two next balls
        newscore = score + ball1 + (balls.pop() if frame == 10 else balls[-1]) + (balls.pop() if frame == 10 else balls[len(balls) - 2])
        return countScore(balls, frame, newscore)
    if ball1 + balls[-1] == 10:
        #we got a spare so we pop the second one as well
        ball2 = balls.pop() 
        newscore = score + ball1 + ball2 + (balls.pop() if frame == 10 else balls[-1])
        return countScore(balls, frame, newscore)
    #else we just add up the scores of the first two balls for this frame
    ball2 = balls.pop()
    newscore = score + ball1 + ball2
    return countScore(balls, frame, newscore) 
           

def test_bowling():
    assert   0 == bowling([0] * 20)
    assert  20 == bowling([1] * 20)
    assert  80 == bowling([4] * 20)
    assert 190 == bowling([9,1] * 10 + [9])
    assert 300 == bowling([10] * 12)
    assert 200 == bowling([10, 5,5] * 5 + [10])
    #here we throw in frame 10 a strike and we add 1 and 0 to the final score
    assert  11 == bowling([0,0] * 9 + [10,1,0])
    #here we throw a strike in frame 9 (10 + 1) and in frame 10 we throw 1 and 0 so this adds up to 11 + 1
    assert  12 == bowling([0,0] * 8 + [10, 1,0])

test_bowling()

Saturday, May 26, 2012

Using named and default arguments

This time I inlined some comments in REPL output just in case you wondered how that got there.
scala> def orderBigMacMenu(drink: String = "Coke", withMayo: Boolean = true): String = {
     |    /** the meal gets prepared **/
     |    "You ordered BigMac menu with " + drink + (if (withMayo) " with " else " without ") + "mayonaise"
     | }
orderBigMacMenu: (drink: String, withMayo: Boolean)String

scala>

scala>

scala> orderBigMacMenu("drinkA", false)
res4: String = You ordered BigMac menu with drinkA without mayonaise

scala> orderBigMacMenu("drinkB", true)
res5: String = You ordered BigMac menu with drinkB with mayonaise

/** code below works because compiler tries to use arguments provided from left to right 
and "drinkc" is of type String **/
scala> orderBigMacMenu("drinkC")
res6: String = You ordered BigMac menu with drinkC with mayonaise

/** code below fails because compiler tries to use arguments provided from left to right 
and "true" is of type Boolean **/
scala> orderBigMacMenu(true)
:9: error: type mismatch;
 found   : Boolean(true)
 required: String
Error occurred in an application involving default arguments.
              orderBigMacMenu(true)

/** When using named arguments, there is no issue. You can even swap them around if you want to. **/
scala> orderBigMacMenu(withMayo=false)
res8: String = You ordered BigMac menu with Coke without mayonaise

scala> orderBigMacMenu(withMayo=false, drink="Beer")
res9: String = You ordered BigMac menu with Beer without mayonaise

Friday, May 25, 2012

Importance of immutability for concurrency

Let's take a look at how much performance we may gain when applying immutability to our code. I will let the code snippets speak for themselves. Below a generic trait with 3 methods of which two are important: the find and save method.
package robbypelssers.concurrency

trait Store[K,V] {
    def find(k: K): Option[V]
    def save(v: V): Unit
    def getName(): String
}

Now we create a mutable and immutable store (both insert key-value pairs (index mapped to fibonacci number) in respectively a mutable and immutable hashmap.
package robbypelssers.concurrency

import collection.mutable.HashMap

class MutableFibonacciStore extends Store[Int, Int] with Fibonacci {
  
  val store = new HashMap[Int, Int]

  def find(n: Int): Option[Int] = synchronized(store.get(n))

  def save(n: Int): Unit = synchronized(store.put(n, fibonacci(n)))
  
  def getName() = "MutableFibonacciStore"

}

package robbypelssers.concurrency

import collection.immutable.HashMap

class ImmutableFibonacciStore extends Store[Int, Int] with Fibonacci {

  var store = new HashMap[Int,Int]
  
  def find(n: Int): Option[Int] = store.get(n)

  def save(n: Int): Unit = synchronized(store = store + ((n, fibonacci(n))))
  
  def getName() = "ImmutableFibonacciStore"

}

package robbypelssers.concurrency

trait Fibonacci {

    def fibonacci(n: Int): Int = n match {
        case 0 => 0
        case 1 => 1
        case _ => fibonacci(n-2) + fibonacci(n-1)
    }  
  
}

Below a very simple profiler which will give some idea of how long both stores will take to do a lot of calls to find and save.
package robbypelssers.concurrency

import java.util.Date

object Profiler {

  /**
   * profile method works like an Around Advice in AspectOriented programming
   */
  def profile[T](body: => T) = {
      val start = new Date()
      val result = body
      val end = new Date()
      println("Execution took " + (end.getTime() - start.getTime()) / 1000 + " seconds") 
      result
  }
  
}

package robbypelssers.concurrency

import java.util.Date
import Profiler._
object StoreConcurrencyTest extends App {

  val immutableStore = new ImmutableFibonacciStore()
  val mutableStore = new MutableFibonacciStore()
  val numberOfOperations = 40
  
  def useStore(store: Store[Int,Int], n: Int) {
        println("using " + store.getName())
        for (x:Int <- 1 to n) {
              store.save(x)
        }
        for (x:Int <- 1 to n) {
              store.find(x)
        }
  }
  
  profile(useStore(immutableStore, numberOfOperations))
  profile(useStore(mutableStore, numberOfOperations))
  
}

using ImmutableFibonacciStore
Execution took 1 seconds
using MutableFibonacciStore
Execution took 4 seconds

3 golden rules for implementing equality

  • If two objects are equal, they should have the same hashCode. 
  • A hashCode computed for an object won’t change for the life of the object. 
  • When sending an object to another JVM, equality should be determined using attributes available in both JVMs.

Overloading primary constructor in Scala

scala> class Employee(employeeId: Int, isFulltimeEmployed: Boolean) {
     |     /** we can overload the primary constructor **/
     |     def this(employeeId: Int) = this(employeeId, true)
     |     override def toString() = employeeId + " works " + (if (isFulltimeEmployed) "fulltime" else "parttime")
     | }
defined class Employee

scala>

scala> val john = new Employee(12545, true)
john: Employee = 12545 works fulltime

scala> val belinda = new Employee(32567, false)
belinda: Employee = 32567 works parttime

scala> val herman = new Employee(56784)
herman: Employee = 56784 works fulltime

Reference Immutatibility vs object immutability

It's important to understand the difference between immutability of reference and immutability of objects.
scala> class Car(brand:String, year:Int) {
     |      var fuelPercentage = 20
     |      def getBrand() = brand
     |      def getYear() = year
     |      def fillTank(): Unit = fuelPercentage = 100
     |      def getFuelPercentage() = fuelPercentage
     |      override def toString = getBrand() + " from " + year
     | }
defined class Car

scala>

scala> val mycar = new Car("Citroen", 2011)
mycar: Car = Citroen from 2011

scala> mycar.getFuelPercentage()
res2: Int = 20

scala> mycar.fillTank()

scala> mycar.getFuelPercentage()
res4: Int = 100

scala> mycar = new Car("Audi", 2012)
:9: error: reassignment to val
       mycar = new Car("Audi", 2012)
             ^

scala> var hiscar = new Car("Audi", 2012)
hiscar: Car = Audi from 2012

scala> hiscar = new Car("Porsche", 2012)
hiscar: Car = Porsche from 2012

scala>

As you can see mycar is an immutable reference because we used the 'val' keyword. hiscar on the other hand is a mutable reference due to using the keyword 'var'.  Both car objects are mutable. We can fill the tank up and the fuelpercentage will change.

Scala promotes expression oriented programming

Scala promotes immutability and expression-oriented programming. Most scala constructs return a value as we will come to see in following examples.
First let's take a look at type matching:
scala> def replyMessage(message:Any): Any = message match {
     |     case s:String => "Your message is the string " + s
     |     case i:Int => "Your message is the number " + i
     |     case _ => "Your message is of unknown type"
     | }
replyMessage: (message: Any)Any

scala> replyMessage("Hello world")
res1: Any = Your message is the string Hello world

scala> replyMessage(5)
res2: Any = Your message is the number 5

scala> replyMessage(true)
res3: Any = Your message is of unknown type

Next let's take a look regular pattern matching using Fibonacci as an example
scala> def fibonacci(n: Int): Int = n match {
     |     case 0 => 0
     |     case 1 => 1
     |     case _ => fibonacci(n-2) + fibonacci(n-1)
     | }
fibonacci: (n: Int)Int

scala>

scala> (for (n <- 0 to 10) yield fibonacci(n)).toList
res15: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

Also the if-else construct returns a value
scala> val fname = "Robby"
fname: java.lang.String = Robby

scala> if (fname.startsWith("B")) "Your name does start with B" else "Hey Mr R"
res19: java.lang.String = Hey Mr R

As a rule of thumb, just remember that you can omit the return statement. Scala will return the last expression in a block statement.
scala> def someComplexMethod(n: Int): Int = {
     |     val x = "blabla"
     |     n * 2
     | }
someComplexMethod: (n: Int)Int

scala>

scala> someComplexMethod(3)
res22: Int = 6

Using Scala interpreter from Eclipse

It is possible to use the Scala interpreter from most IDE's. Here is a short description how to use it in Eclipse. You will first need to create a new Scala project however.
  • Window => Open perspective =>  Scala
  • Create new Scala project
  • Window => Show view => Scala interpreter
  • Select the newly created project and press ok
  • Start typing any expression in the Evaluate textbox and press enter

Scala project management and continuous compilation

There are a few ways to manage your Scala projects among to name a few:
Expect more articles about usage some time in the future.

How to workaround Class and Companion object in REPL

As you can see below the companion object can't access the private variable from the Class Person. This is due to a different scope. To fix it you will need to define a container (can be called something else by the way).
scala> class Person {
     | private var firstname = "Robby"
     | private var lastname = "Pelssers"
     | }
defined class Person

scala> object Person {
     | def getFirstName(p: Person) = p.firstname
     | }
:9: error: variable firstname in class Person cannot be accessed in Person
       def getFirstName(p: Person) = p.firstname

scala> object container {
     |   class Person {
     |      private var firstname = "Robby"
     |      private var lastname = "Pelssers"
     |   }
     |
     |   object Person {
     |       def getFirstName(p: Person) = p.firstname
     |   }
     | }
defined module container

scala> import container.Person
import container.Person

scala> val person = new Person()
person: container.Person = container$Person@1a71d29a

scala> Person.getFirstName(person)
res0: java.lang.String = Robby

Important side note!! As of Scala 2.9.x you can use the :paste command and everything will work normally.
scala> :paste
// Entering paste mode (ctrl-D to finish)

class Person {
  private var firstname = "Robby"
  private var lastname = "Pelssers"
}

object Person {
  def getFirstName(p: Person) = p.firstname
}

// Exiting paste mode, now interpreting.

defined class Person
defined module Person

scala> Person.getFirstName(new Person())
res0: java.lang.String = Robby

Scala REPL is smart

Apparently the REPL is smart enough to figure out when you declare a function as it waits for the closing bracket to return. It auto-injects the | for you as you enter new lines. I read that there are a few use cases it can't handle very well yet like defining a class and companion object. Once I've tested this with current version of the REPL I will blog about these cases.
scala> def addTwo(x: Int) = {
     |    x + 2
     | }
addTwo: (x: Int)Int

scala> addTwo(5)
res5: Int = 7

scala>

Playing with the Scala REPL

The first thing you want to verify is that Scala is installed correctly. During installation you get asked if Scala should be added to your path, make sure to do so. If you're working on windows like me, you can now open the command line. Press Start button and type cmd into the 'Search programs and files'. This will open a DOS shell. Next type scala and the REPL (Read Eval Print Loop) will start.
C:\Users\nxp10009>scala
Welcome to Scala version 2.9.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_30).
Type in expressions to have them evaluated.
Type :help for more information.

scala> "Hello"
res0: java.lang.String = Hello

scala> "Hello".filter(_ != 'l')
res1: String = Heo

scala> 5
res2: Int = 5

Preparing for Scala development

I fell in love with Scala the moment I read 'Programming in Scala' from Martin Odersky, the creator of Scala. Unfortunately at the time being Scala didn't have good tooling support. Neither was it a widely adopted language and as none of my colleagues had any experience yet, it would be risky to start using it. Times have changed and the ecosystem around Scala is blossoming. Typesafe was created in 2011 around basically two stacks, Scala itself and Akka. Meanwhile Typesafe added playframework to its stack. No excuses left for me to keep postponing diving deeper into the internals of Scala and hence I bought 'Scala in depth' this week which I started reading with great interest. Anyway, if you're ready to start exploring the Scala language make sure to keep an eye on this blog ;-)

Preparation:

Wednesday, May 23, 2012

Mimicking mkdir Unix in Python

I got inspired by a tweet from @paulgreg today: 'Man. I love Unix shell : mkdir -p src/{main,test}/{java,resources} #unix #shell'. I wanted to find out how difficult this would be to implement in Python and here is a first working draft.
import os
from itertools import product

def mkdir(pathExpr):
    """
    example of pathExpr: src/{main,test}/{java,resources}
    creates following folders:
        - src/main/java
        - src/main/resources
        - src/test/java
        - src/test/resources
    """

    for foldercombi in product(*(getFolderParts(expression) for expression in pathExpr.split('/'))):
        dirname =  '/'.join(foldercombi)
        try:
            os.makedirs(dirname)
        except OSError:
            if os.path.exists(dirname):
                pass

def getFolderParts(expression):
    if expression[0] == '{' and expression[-1] == '}':
        return [part for part in expression[1:-1].split(',')]
    else:
        return [expression]

mkdir('C:/tmp/src/{main,test}/{java,resources}')

Tuesday, May 22, 2012

Nested for comprehensions

I think nested for loops seem a bit counterintuitive at first sight but the basic rule is that you start with outer loop(s) and end with inner loop(s). The only thing to remember is that you collect the result from the last inner loop at the very beginning.
text = 'Check carefully how nested for loops work!'
print ' '.join([letter.upper() for word in text.split() for letter in word]) 

C H E C K C A R E F U L L Y H O W N E S T E D F O R L O O P S W O R K !

You can also use guards (if statements) in for comprehensions. Below an example filtering out words that contain the letter 'o'.
text = 'Check carefully how nested for loops work!'
print ' '.join([letter.upper() for word in text.split() if word.find('o') != -1 for letter in word]) 

H O W F O R L O O P S W O R K !

Creating set of unique words from a text file

Quick way of creating set of words from file. Content of file c:/tmp/story.txt
This is a story about a sailor and a whale called Moby Dick

words =  set((str.upper(file('c:/tmp/story.txt').read())).split())
print words

set(['A', 'AND', 'STORY', 'THIS', 'IS', 'DICK', 'ABOUT', 'SAILOR', 'MOBY', 'WHALE', 'CALLED'])

Thursday, May 17, 2012

Using Dependency Injection

Take a good look at the current implementation below for expectedvalue. There is no way to write a proper test for this function as it involves randomness. So how do we work our way around this? We can parameterize the random part of our implementation and pass in a non-random implementation in order to test. This principle of switching components at runtime is called Dependency Injection.
import random

def cointoss(n):
    for i in range(n):
        yield random.choice(['head', 'tail'])

def expectedvalue(n):
    #Returns our win or loss after tossing coin for n times
    #head: we win 1 dollar, tail: we loose one dollar
    returnvalue = {'head': 1, 'tail': -1} 
    return sum([returnvalue[coinflip] for coinflip in cointoss(n)])

print expectedvalue(100)
print expectedvalue(100)
print expectedvalue(100)
print expectedvalue(100)

-2
14
16
4

Now let's take a look how we can do this in Python. We see that cointoss is the random part so we parameterize it as a function parameter.
import random

def cointoss(n):
    for i in range(n):
        yield random.choice(['head', 'tail'])

def expectedvalue(n, tossing_func=cointoss):
    #Returns our win or loss after tossing coin for n times
    #head: we win 1 dollar, tail: we loose one dollar
    #default tossing_func = cointoss
    returnvalue = {'head': 1, 'tail': -1} 
    return sum([returnvalue[coinflip] for coinflip in tossing_func(n)])

def always_loose(n):
    for i in range(n):
        yield 'tail'

def always_win(n):
    for i in range(n):
        yield 'head'


assert expectedvalue(100, always_loose) == -100
assert expectedvalue(100, always_win) == 100
print expectedvalue(100)

-22

Programming under uncertainty

If you need to write a program that deals with stochastic events, you should definitely take a look at the random module. It offers a lot of nice methods to generate random elements. Just to show a few examples:
import random
for i in range(0,4):
    print random.choice(['head', 'tails'])
print '----------------'
for i in range(0,4):
    print random.randint(3,6)
print '----------------'
for i in range(0,4):
    print random.randrange(2,15,3)

head
tails
head
head
----------------
4
6
3
6
----------------
5
14
2
8