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

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

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.