Localization problems in R

Just a hint. If you see your R environment behaving strangely, it could be a problem of localization.

Look for the Sys.getlocale function in the R documentation, here is a handy link, courtesy of the Zurich polytechnic.

For my case, to solve the problem I called:

Sys.setlocale("LC_ALL", "C")

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)