Coefficient of variation

Write a python function that calculates the coefficient of variation for a list of numbers.

This is a trivial case, if we can use the numpy library. However let's do it without first. Even better, I start with a dummy that always returns zero:

def cv(data):
    """
    :param data a list of numbers
    :returns its coefficient of variation, or NaN.
    :rtype float
    """
    return 0.0

Now I can write a few test cases for it:

class CV(unittest.TestCase):
    def test_none(self):
        coll = None
        self.assertTrue(math.isnan(cv(coll)))

    def test_empty(self):
        self.assertTrue(math.isnan(cv([])))

    def test_zero_mean(self):
        coll = [1, 2, 0, -1, -2]
        self.assertTrue(math.isnan(cv(coll)))

    def test_std_var_0(self):
        coll = [42, 42, 42]
        self.assertEqual(cv(coll), 0)

    def test_1(self):
        coll = [0, 0, 6, 6]
        self.assertEqual(cv(coll), 1)

    def test_dot5(self):
        coll = [10, 4, 12, 15, 20, 5]
        self.assertAlmostEqual(cv(coll), 0.503, delta=0.001)

Following the line of the previous post, I have decided that my function should return NaN if the caller passes a None or an empty list in. I remarked this requisite with the first two test cases, test_none and test_empty.
The other test cases should be look quite clear, once we know what the coefficient of variation is. In a few words, it is the standard deviation of a population divided by its mean. This implies that we can't calculate it when the mean is zero. In that case the function should return NaN, as showed by test_zero_mean test case.

Said that, this implementation should look quite straightforward:

def cv(data):
    """
    :param data a list of numbers
    :returns its coefficient of variation, or NaN.
    :rtype float
    """
#1
    if not data:
        return float('NaN')  
#2
    mean = sum(data) / float(len(data))
    if mean == 0:
        return float('NaN')
#3 
    sq_sum = 0.0
    for d in data:
        sq_sum += (d - mean) ** 2
    stddev = math.sqrt(sq_sum / len(data))
#4
    return stddev / mean

1. When the user passes a None or an empty list, NaN is returned.
2. Calculate the mean. If it is zero, NaN is returned.
3. Calculate the standard deviation.
4. Return the coefficient of variation.

As I hinted above, using numpy makes the code so much cleaner:

def cv_(data):
    """
    :param data a list of numbers
    :returns its coefficient of variation, or NaN.
    :rtype float
    """
    if not data:
        return float('NaN')

    mean = numpy.mean(data)
    if mean == 0.0:
        return float('NaN')

    return numpy.std(data) / mean

Full code and test cases are on github.

Strings standard deviation

Implement a function that gets in input a list of strings and gives back the standard deviation of the lengths of the strings.

I have found this problem while following the Introduction to Computational Thinking and Data Science MIT course hosted by edX.

As usual, I wrote a first implementation for the function, to be extended after setting up a series of test cases:

def standard_deviation(strings):
    """
    :param strings: a list of strings
    :returns the standard deviation of the lengths of the strings, or NaN.
    :rtype float
    """
    return 0.0

The function docstring specifies what I expect as input parameter and what the caller should expect to get as output.
For the moment, my no-brainer implementation always returns a floating point zero.

Then I wrote a number of test cases, many of them given informally as part of the problem:

class StdDevTest(unittest.TestCase):
    def test_none(self):
        self.assertTrue(math.isnan(standard_deviation(None)))

    def test_empty(self):
        strings = []
        self.assertTrue(math.isnan(standard_deviation(strings)))

    def test_1(self):
        strings = ['a', 'z', 'p']
        self.assertEqual(standard_deviation(strings), 0)

    def test_2(self):
        strings = ['apples', 'oranges', 'kiwis', 'pineapples']
        self.assertAlmostEqual(standard_deviation(strings), 1.8708, delta=0.0001)

    def test_3(self):
        strings = ['mftbycwac', 'rhqbqawnfl', 'clgzh', 'ilqy', 'ckizvsgpnhlx', 'kziugguuzvqarw', 'xqewrmvu', 'ktojfqkailswnb']
        self.assertEqual(standard_deviation(strings), 3.5355339059327378)

    def test_4(self):
        strings = ['zgbljwombl', 'slkpmjqmjaaw', 'nddl', 'irlzne', '', 'poieczhxoqom', 'waqyiipysskxk', 'dloxspi', 'sk']
        self.assertEqual(standard_deviation(strings), 4.447221354708778)

    def test_bad_data(self):
        with self.assertRaises(TypeError):
            standard_deviation([1, 2, 3])

test_none, test_empty: What the function should do in case of None passed as input parameter is not specified by the problem. I decided to let it behaves as it gets an empty list of strings in. Notice the use of the function isnan from the standard math library.
test_1: If all the strings have the same size, a standard deviation of zero should be returned.
test_2: The interesting point in this test case is that in the problem definition we are given an approximated expected result value (I guess it was just a bit of sloppiness). For this reason I used the "almost equal" assertion to check it.
test_3, test_4: Vanilla tests. Just check everything goes as expected.
test_bad_date: We are not required to behave politely if the user gives us garbage in. Here I stress the fact that in case of a list of numbers in, our function is expected to react throwing a TypeError exception.

Running these test cases on the current implementation for standard_deviation() should give a bunch of failures and a single success on test_1. We could do better. But we have to understand better the problem requisites.

Checking what standard deviation is, we see how we have to calculate the mean of the elements in the collection, then subtract it from each element, square the result, sum all these values, divide them by the size of the collection, and finally extract the square root.

Converting this in Python, you should get something like this:

lengths = [len(s) for s in strings] # 1
mean = math.fsum(lengths) / len(lengths) # 2

# 3
sq_sum = 0.0 
for l in lengths:
    sq_sum += (l - mean) ** 2

return math.sqrt(sq_sum / len(lengths)) # 4

1. Let's prepare the data in input, converting the strings to their sizes, that is what really matter to us.
2. Calculating the mean it's easy. Be careful only to get it as a floating point number. To achieve it, I used the fsum() math function instead of the plain sum(). An explicit cast to float would have worked equivalently.
3. Now, the trickiest part of the algorithm. I feel like if I were more expert in Python I could have written these three lines more succinctly. Anyway, it is just a matter of summing the squared difference of each string lengths against the mean.
4. Finally, I just have to divide by the size of the collection, extract the square root, and returning the result to the caller.

Just one thing more. Before starting to calculate the standard deviation, I'd better check the input against empty collections. I could do that in this way:

if not strings:
    return float('NaN')

This would catch both the case of an empty list of strings and a None passed by mistake.

Full python 2.7 code with test cases is available on github.

Merge for 2048

Implement a function to merge a line of the 2048 game, as a left movement was request.

If you don't know the 2048 game, have a look at its official page on github by Gabriele Cirulli. Pay attention, it could be gravely addictive!

The problem here is implementing a Python 2.7 function that gets in input a list of integers, where each element is a power of 2, or zero that stands for an empty place. We should return another list, same size of the input one, where all the elements are shifted to the left and merged as required.

So, for instance, an input of [2, 0, 2, 4] should result in an output of [4, 4, 0, 0], since the twos merge in a four, that won't merge with the other four given that newly merged element can't be part of this operation.

Here is my solution:

def merge(line):
    result = [] # 1
    check = False # 2
    for cur in line: # 3
        if check and result[-1] == cur: # 4
            result[-1] *= 2
            check = False
        elif cur != 0: # 5
            result.append(cur)
            check = True
    
    while len(result) < len(line): # 6
        result.append(0)
    return result

1. The result list, initialized empty.
2. Flag that states if the current element could be merged. Since this depends on the previous element, it is initialized to false.
3. Loop on all the element in the input list. If the current one is zero, I don't have to do anything, just move to the next one.
4. Otherwise, if the current element could be merged, I check the last element inserted in the result list, if they match, I merge them, and I signal that no merge could be done on the next element.
5. Usually, I append the current element to the result list, signal that a merge with the next element is possible, and continue looping.
6. The problem requires that the output list has the same size of the input one.

Check for palindrome

In the Input and Output chapter of A Byte of Python, the code of a simple palindrome checker is presented. As homework exercise, we are required to improve it, so that it would accept as a palindrome something like "Rise to vote, sir." (courtesy of The Simpsons). That is, we have to skip punctuation and spaces, and not to care about case.

The main part of the code I have written gets a string as raw data from input, than is going to call a palindrome() function that returns True only when a palindrome is detected:

txt = raw_input('your input: ')
print 'This is',
if not palindrome(txt):
    print 'not',
print 'a palindrome'

Not much to say about it, I guess.

Following the Swaroop's suggestion to use a tuple to store the ignored characters and strip them from the original string in input, I wrote the palindrome() function in this way:

def palindrome(text):
    text = strip(text) # 1
    return text == text[::-1] # 2

1. A strip() function removes all the uninteresting characters from the original input.
2. I compare the stripped user input with its reverted representation, and return True only if they match. The string reverting is adequately commented by Swaroop. In brief, I create a copy of the original text by slicing, but saying that I want the entire interval to be considered. The third parameter says that I want to step negatively, and this result in reading the string form right to left.

And finally, here is how I have written my stripping function:

def strip(text):
    ignore = (',', '.', ' ') # 1

    stripped = '' # 2
    for c in text: # 3
        if c not in ignore: # 4
            stripped += c

    return stripped

1. This is the suggested ignore tuple. Actually, I put in it just three characters. Question mark, colon, semicolon, are just a few of the many candidates to enter in this selection.
2. The resulting string is initially empty.
3. Loop on all the characters in input.
4. If the current character is not in the ignore tuple I can add it to the output string.

This is it. Homework done. Still, the above #1 line it is quite painful. Can't we get rid of this manual initialization?

If we can relax a bit the original requirements, we could end up with a sleeker piece of code.
Say that is alright if we can happily get rid of any non-alphanumeric character. In this case we can use a very simple regular expression, and simplify the palindrome() function in this way:

import re # 1


def palindrome(text):
    text = re.sub(r'\W+', '', text) # 2
    return text == reverse(text)

1. I am using the python regular expression library.
2. I ask to re to substitute each non-alphanumeric subsequence in the original text with an empty one.

If you don't want to be so aggressive, you could write your own specific regular expression and strip just the characters you need to.

Ternary operator example

If you come to Python from a C (or related language as C++ and Java) experience, you have probably developed a taste for the ternary conditional operator (?:). However, Guido van Rossum didn't like it, and it wasn't part of the original language. Luckily for us, in the end he changed his mind, and since version 2.5 it is available a new construct that we can happily use to get this effect. See PEP 308 - Conditional Expressions for details. It goes in this way:

first if test else second

And it reads: check test, if it is true returns first, otherwise second. I found it sort of perlish, but I guess in a while I should get used to it. I reckoned it was sort of fun showing how to use it by a simple programming problem. Say that you have a file containing a bunch of integers, each one on a different line, do not worry about any error handling. You have to write a python script that read that file and output for each number in input a 0 for any odd number and 1 for the even ones. Here is how I solved it:

import sys

data = open(sys.argv[1], 'r')
for line in data:
    print(1 if int(line) % 2 == 0 else 0)

As comparison, In C++ I would have written the same piece of code like this:

int value;
while(file >> value)
    std::cout << (value % 2 == 0 ? 1 : 0) << std::endl;

Fibonacci for CodeEval

Just to have some fun, I was solving a not too complex problem on CodeEval. The description was sort of dodgy, but in the end I understood that it boiled down to calculate the Fibonacci number of the values passed as input (increased by one, to make the waters a bit muddier). I usually play those games in C++, that is my preferred programming language. Alas, on CodeEval we are forced to use a 32 bit C++98 compiler. Not exactly what you could call a state of the art tool. This is particularly annoying in this case, where I need to calculate huge numbers as the Fibonacci ones are. Luckily my basic knowledge of Python is enough to get me out of it. Here is my 2.7 solution, I know it is nothing special, but it sufficed to get me a shiny 100%:

import sys


def fib(n):
    if n == 0:
       return 0

    prev, cur = 0, 1
    for i in range(n - 1):
        prev, cur = cur, prev + cur
    return cur


if __name__ == '__main__':
    for line in open(sys.argv[1]):
        if len(line) > 0:
            print fib(int(line) + 1)

Argument type checking

If you come to Python from a background in a programming language that provides static type checking, you could find a bit confusing, albeit liberating, not having to specify the type of the objects you are using. This could get puzzling when you deal with passing parameters to a function. What if I design a function to accept in input a number but the user misunderstand it, passing in a string instead? You could be tempted to explicitly check for the argument, and reject the call if it doesn't satisfy your requirements. This works fine, but makes the code less terse, and it is not considered very pythonesque. The preferred way is not performing any preemptive check at all, and let the code fails if it has to. You can read this as moving the responsibility of the parameters check from the actual code to its caller. When you want your function to be less rough, you can try-catch (or should I say try-except) the sensible part of you code, to convert the original exception in your preferred way of signaling an error to the caller. Consider the distance() function I have written in the previous post. It is meant to accepts as argument four numbers representing the coordinates of two points, and should give in output their distance. In case of unexpected input it would result in a TypeError exception that should be caught by the caller, or would lead to an abrupt termination of the application. We could want to manage internally to distance() these kind of problems, and let it return the no-value object (a Python None, the counterpart of a C NULL, a C++ nullptr, a Java null, ...) instead. This batch of test cases shows the new expected behavior:

import unittest


class Tests(unittest.TestCase):
    def test_ax(self):
        dist = distance('alpha', 0, 0, 0)
        self.assertIsNone(dist)

    def test_ay(self):
        dist = distance(0, 'alpha', 0, 0)
        self.assertIsNone(dist)

    def test_bx(self):
        dist = distance(0, 0, 'alpha', 0)
        self.assertIsNone(dist)

    def test_by(self):
        dist = distance(0, 0, 0, 'alpha')
        self.assertIsNone(dist)

If any input parameter is not a number, the function is expected to return None. Notice that often this behavior does not improve much our code. Before we had to worry that distance() could throw and exception, now we have to move our concern to its returned value, that could be invalid. You should at least consider if it is more appropriate to leave distance() as was before, and maybe try-catch its call, or ensure that the passed parameters are actually numbers. In any case, if we really want to do it, we could do it in a few different ways. Non-Pythonic solutions There are a couple of Python built-in functions that let us check the type of an object, type() and isinstance(). Here is how I could check if an object has type int:

if type(ax) != 'int':
    return None

What type() does is what it says, it returns the type of the passed object. It knows nothing about polymorphism, for this reason it is not the preferred alternative. It is usually better to use its more advanced sister isinstance():

if not isinstance(ax, int):
    return None

In this way we check that ay is an int, or any possible subclass of int. Our distance() function should accept int, long, and float parameters. An overload of isinstance() is available to check an object against more than one type:

if not isinstance(ax, (int, long, float)):
    return None

In this way we are checking a single parameter for being of an expected type. We should replicate the test for each of them. The Pythonian way As I suggested above, the true Pythonesque way of dealing with this issue, would probably be leaving alone distance() and introducing some checks in its caller. If we really have some good reasons to shield the original exception to the caller, we would do something like this:

import math


def distance(ax, ay, bx, by):
    try:
        return math.sqrt((bx - ax) ** 2 + (by - ay) ** 2)
    except TypeError:
        return None

Just execute the original code. If it throws an exception, catch it and do what you want to do instead. Clean code, no extra price the caller should pay for checks, only the offending calls would result in the extra-slow management required to generate an exception in math.sqrt(), catching it in distance() and converting it to the expected behavior.