Search code examples
pythonpython-2.7checksumbubble-sort

Unsure why program similar to bubble-sort is not working


I have been working on a programming challenge, problem here, which basically states:

Given integer array, you are to iterate through all pairs of neighbor elements, starting from beginning - and swap members of each pair where first element is greater than second.

And then return the amount of swaps made and the checksum of the final answer. My program seemingly does both the sorting and the checksum according to how it wants. But my final answer is off for everything but the test input they gave.

So: 1 4 3 2 6 5 -1 Results in the correct output: 3 5242536 with my program.

But something like:

2 96 7439 92999 240 70748 3 842 74 706 4 86 7 463 1871 7963 904 327 6268 20955 92662 278 57 8 5912 724 70916 13 388 1 697 99666 6924 2 100 186 37504 1 27631 59556 33041 87 9 45276 -1

Results in: 39 1291223 when the correct answer is 39 3485793.

Here's what I have at the moment:

# Python 2.7

def check_sum(data):
    data = [str(x) for x in str(data)[::]]
    numbers = len(data)
    result = 0

    for number in range(numbers):
        result += int(data[number])
        result *= 113
        result %= 10000007

    return(str(result))

def bubble_in_array(data):
    numbers = data[:-1]
    numbers = [int(x) for x in numbers]
    swap_count = 0

    for x in range(len(numbers)-1):
        if numbers[x] > numbers[x+1]:
            temp = numbers[x+1]
            numbers[x+1] = numbers[x]
            numbers[x] = temp
            swap_count += 1

    raw_number = int(''.join([str(x) for x in numbers]))
    print('%s %s') % (str(swap_count), check_sum(raw_number))
bubble_in_array(raw_input().split())

Does anyone have any idea where I am going wrong?


Solution

  • The issue is with your way of calculating Checksum. It fails when the array has numbers with more than one digit. For example:

    2 96 7439 92999 240 70748 3 842 74 706 4 86 7 463 1871 7963 904 327 6268 20955 92662 278 57 8 5912 724 70916 13 388 1 697 99666 6924 2 100 186 37504 1 27631 59556 33041 87 9 45276 -1
    

    You are calculating Checksum for 2967439240707483842747064867463187179639043276268209559266227857859127247091613388169792999692421001863750412763159556330418794527699666 digit by digit while you should calculate the Checksum of [2, 96, 7439, 240, 70748, 3, 842, 74, 706, 4, 86, 7, 463, 1871, 7963, 904, 327, 6268, 20955, 92662, 278, 57, 8, 5912, 724, 70916, 13, 388, 1, 697, 92999, 6924, 2, 100, 186, 37504, 1, 27631, 59556, 33041, 87, 9, 45276, 99666]

    The fix:

    # Python 2.7
    
    def check_sum(data):
        result = 0
    
        for number in data:
            result += number
            result *= 113
            result %= 10000007
    
        return(result)
    
    def bubble_in_array(data):
        numbers = [int(x) for x in data[:-1]]
        swap_count = 0
    
        for x in xrange(len(numbers)-1):
            if numbers[x] > numbers[x+1]:
                numbers[x+1], numbers[x] = numbers[x], numbers[x+1]
                swap_count += 1
    
        print('%d %d') % (swap_count, check_sum(numbers))
    
    bubble_in_array(raw_input().split())
    

    More notes:

    • To swap two variables in Python, you dont need to use a temp variable, just use a,b = b,a.
    • In python 2.X, use xrange instead of range.