daily_programmer_20150520

daily_programmer_20150520.py

#-------------------------------------------------------------------------------
# Name:        module1
# Purpose:
#
# Author:      mwoods
#
# Created:     20/05/2015
# Copyright:   (c) mwoods 2015
# Licence:     <your licence>
#-------------------------------------------------------------------------------

#https://www.reddit.com/r/dailyprogrammer/comments/36m83a/20150520_challenge_215_intermediate_validating/
import cProfile


class SortingNetwork(object):
    """wires: # of wires in Network
       comparators: List of Tuples each representing a Comparator in the Network.
    """
    def __init__(self, wires, comparators):
        self.wires = wires
        self.comparators = comparators

    def test_network(self):
        pad = '0'*self.wires
        comparisons = [['0']*(self.wires - n) + ['1']*n for n in range(self.wires + 1)]
        for n in xrange(2**self.wires - 1):
            
            #produces binary array representing integer n with leading zeroes could speed up with other mods 
            m = list((pad+bin(n)[2:])[-self.wires:])
            sorted_val =  comparisons[m.count('1')]
            self.sort(m)
            if m != sorted_val:
                return False
                break
        return True

    def sort(self, inp):
        """"inp as a list
            return sorted version of inp (mutates) input"""

        assert len(inp) == self.wires, 'Input has to be == to number of wires'

        for comp in self.comparators:
            lo_wire, hi_wire = comp
            if inp[lo_wire] > inp[hi_wire]:
                inp[lo_wire], inp[hi_wire] = inp[hi_wire], inp[lo_wire]
        return inp

if __name__ == "__main__":
    import random
    import time

    sample1 = (4, [(0, 2), (1, 3), (0, 1), (2, 3), (1, 2)])

    with open("C:\\challeng2.txt", "r") as f:
        line = f.readline()
        wires, _ = line.split()
        wires = int(wires)
        comps = []

        for line in f:
            a,b = line.split()
            comps.append((int(a), int(b)))

    S = SortingNetwork(wires, comps)
    print S.test_network()