Python test cases for first programming assignment in Coursera's "Algorithms: Design and Analysis, Part 1"

test_count_invers.py

"""
Test cases for the 'counting inversions' programming assignment, the first
assignment of the Coursera course "Algorithms: Design and Analysis, Part I".

This module incorporates most of the tests found in the course forum, in
this thread:

   https://class.coursera.org/algo-009/forum/thread?thread_id=2

To help check my work, I modified my merge_sort implementation to return
either the count of the inversions, or a list of the inversion tuples (see
the test cases in test_basics() to see what I mean). Here's my function
declaration:

    inversions, sorted_array = merge_sort(array, save_invers=[True|False])

If 'save_invers' is True, 'inversions' will be the list of the inversion
tuples, otherwise it'll be their count.

If you want to use these tests yourself, you'll have to modify your
implementation so that it has the same interface and returns the same
values, or provide a wrapper which does this.

If you don't want to write code to return the list of inversions, and would
still like to use these tests to check your output is sorted and the
inversion count is correct, modify your function/wrapper to return
inversions=None when save_invers == True, and then the comparisons of the
inversions array will be skipped.

Finally, this module can be used from the command line to sort and count the
inversions in an input file (consisting of lines of integers, one integer per
line.) If a filepath is given as an argument, this script will read and sort
the file contents, and print out a count of the inversions. If a number is
also given on the command line, the inversion count returned will be
compared with that number. Some examples:

$ python test_count_invers.py
...
----------------------------------------------------------------------
Ran 4 tests in 0.002s

OK

$ python test_count_invers.py IntegerArray.txt
Inversions returned: 8368

$ python test_count_invers.py IntegerArray.txt 642
Inversions returned: 8368; Inversions expected: 642
"""
import os
import sys
import random
import unittest

from merge_sort import merge_sort

def reversed(input):
    # .sort() sorts in-place and returns None. sorted() returns sorted copy of
    # of input. This is the equivalent function for .reverse(), except it
    # doesn't return a COPY of the array - it just returns the modified array,
    # so you've got something to chain with other functions.
    input.reverse()
    return input


def normalise_invers(invers):
    # Normalise a set of invers tuples, so that the tuple elements are ordered
    # the same way (larger, smaller) and all the tuples are ordered in ascending
    # order.
    return sorted([tuple(reversed(sorted(s))) for s in invers])


class TestInversions(unittest.TestCase):

    def test_basics(self):
        r"""
        Check various permutations of the numbers 1-6 are properly sorted
        by our implementation, and that it returns/calculates the expected
        inversions."""

        # First element is a space-separated string of unordered, distinct ints
        # Second is a list of all the inversions in that unorderd string, as
        # 2-element sequences. These sequences will be normalised, so it should
        # be possible to compare the test cases with what is returned from your
        # implementation.
        test_cases = [
            ('1 2 3',       []),
            ('2 3 1',       [(2, 1), (3, 1)]),
            ('3 1 2',       [[3, 1], [3, 2]]),
            ('2 1 3',       [(2, 1)]),
            ('1 3 2',       [(3, 2)]),
            ('3 2 1',       [(2, 1), (3, 1), (3, 2)]),
            ('1 3 5 2 4 6', [(3, 2), (5, 2), (5, 4)]),
            ('1 5 3 2 4',   [(3, 2), (5, 2), (5, 3), (5, 4), ]),
            ('1 6 3 2 4 5', [(3, 2), (6, 2), (6, 3), (6, 4), (6, 5)]),
        ]
        for idx, test in enumerate(test_cases):
            for save_invers in [True, False]:
                input, check_invers = test
                subset = [int(i) for i in input.split(' ')]
                check_invers = normalise_invers(check_invers)

                invers, new = merge_sort(subset, save_invers=save_invers)
                # print subset, str(save_invers).ljust(5), invers
                self.assertEqual((idx, new), (idx, sorted(subset)))

                if save_invers:
                    if invers is None:
                        check = True
                    else:
                        invers = normalise_invers(invers)
                        check = invers == check_invers
                else:
                    check = invers == len(check_invers)

                if not check:
                    print idx, ':', invers, '!=', check_invers
                self.assertTrue(check)

    def test_theory(self):
        """
        The largest possible number of inversions an n-element array can
        have is (n choose 2) = (n(n-1))/2. This occurs when the array is
        sorted in reverse order."""

        num_tests = 25
        smallest_len = 4
        largest_len = 16
        # Used to bound the length of the arrays that we want to test. Choose
        # numbers short enough to make tests meaningful, but not so long they
        # take too long

        for i in xrange(num_tests):
            n = random.randint(smallest_len, largest_len)
            num_invers = (n * (n-1)) / 2
            input = range(n, 0, -1)
            invers, new = merge_sort(input, save_invers=False)
            if invers != num_invers:
                print n, input
                msg = 'Inversions returned: %d; Inversions expected: %d'
                msg %= (num_invers, invers)
                print msg
            self.assertEqual(num_invers, invers)

    def compare_inversions(self, index, num_invers, input):
        check_invers, output = merge_sort(input, save_invers=False)
        self.assertEqual((index, output), (index, sorted(input)))
        self.assertEqual((index, check_invers), (index, num_invers))

    def test_soesilo_w(self):
        r"""
        Test cases taken directly from forum thread."""
        test_cases = [
            # Soesilo W's test cases
            (56,
             [9, 12, 3, 1, 6, 8, 2, 5, 14, 13, 11, 7, 10, 4, 0]),
            (590,
             [37, 7, 2, 14, 35, 47, 10, 24, 44, 17, 34, 11, 16, 48, 1, 39, 6,
              33, 43, 26, 40, 4, 28, 5, 38, 41, 42, 12, 13, 21, 29, 18, 3, 19,
              0, 32, 46, 27, 31, 25, 15, 36, 20, 8, 9, 49, 22, 23, 30, 45]),
            (2372,
             [4, 80, 70, 23, 9, 60, 68, 27, 66, 78, 12, 40, 52, 53, 44, 8, 49,
              28, 18, 46, 21, 39, 51, 7, 87, 99, 69, 62, 84, 6, 79, 67, 14,
              98, 83, 0, 96, 5, 82, 10, 26, 48, 3, 2, 15, 92, 11, 55, 63, 97,
              43, 45, 81, 42, 95, 20, 25, 74, 24, 72, 91, 35, 86, 19, 75, 58,
              71, 47, 76, 59, 64, 93, 17, 50, 56, 94, 90, 89, 32, 37, 34, 65,
              1, 73, 41, 36, 57, 77, 30, 22, 13, 29, 38, 16, 88, 61, 31, 85,
              33, 54]),
             # Chien-Yu Wei's test case
            (266,
             [18, 22, 4, 29, 15, 21, 13, 24, 20, 10, 11, 26, 27, 16, 12, 8,
              25, 14, 6, 17, 30, 9, 28, 5, 2, 1, 23, 7, 19, 3])
        ]
        for idx, test_case in enumerate(test_cases):
            num_invers, input = test_case
            self.compare_inversions(idx, num_invers, input)

    def test_not_unique(self):
        r"""
        Simple test to see if implementation can handle duplicate entries in
        the input. Example given in forum thread, from Arlene Batada."""
        test_cases = [
            (55,
             [1000, 7, 900, 6, 4, 9, 0, 5, 4, 8, 3, 7, 1])
        ]
        for idx, test_case in enumerate(test_cases):
            num_invers, input = test_case
            self.compare_inversions(idx, num_invers, input)


def parse_cmdline_args(args):
    input_file = None
    num_invers = None

    for arg in args:
        try:
            arg = int(arg)
            num_invers = arg
            continue
        except ValueError:
            pass

        filepath = os.path.abspath(arg)
        if os.path.isfile(filepath):
            input_file = filepath

    return (input_file, num_invers)


if __name__ == '__main__':

    input_file, num_invers = parse_cmdline_args(sys.argv[1:])

    if not input_file:
        unittest.main()#verbosity=2)
    else:
        contents = [int(n) for n in open(input_file).readlines()]
        check_invers, output = merge_sort(contents, save_invers=False)
        assert output == sorted(contents)
        line = ['Inversions returned: %d' % check_invers]
        if num_invers is not None and check_invers != num_invers:
            line.append('; Inversions expected: %d.' % (num_invers))
        else:
            line.append(', as expected.')
        print ''.join(line)