richmilne · October 17, 2015 12:43
diff --git a/test_count_invers.py b/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)
	"""
	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)