some old python i wrote as a thought experiment after a coding interview... called it shard.py

python

#!/usr/bin/python


def get_shard_map(shardfile):

    shards = {}
    shards_fh = open(shardfile)
    for line in shards_fh:
        shard, host1, host2 = line.split()
        if shards.has_key(shard):
            if host1 not in shards[shard]:
                shards[shard].append(host1)
            if host2 not in shards[shard]:
                shards[shard].append(host2)
        else:
            shards[shard] = [host1, host2]

    return shards

def get_hosts(shards):
    hosts = []
    for shard in shards.keys():
        for host in shards[shard]:
            if host not in hosts:
                hosts.append(host)
    return set(hosts)

def get_shards(host, shard_map):
    shard_list = set()
    for shard in shard_map.keys():
        if host in shard_map[shard]:
            shard_list.add(shard)

    return shard_list

# given a shard map: shard -> host list
# return a host map: host -> shard list
def get_host_shard_map(shard_map, hosts):
    host_to_shard_map = {}
    for host in hosts:
        host_to_shard_map[host] = get_shards(host, shard_map)
    return host_to_shard_map


def main():

# shards.txt
#shard1 host1 host2
#shard2 host2 host3
#shard3 host4 host5
#shard4 host1 host6
#shard1 host3 host7
#shard4 host7 host8

    shards            = get_shard_map('shards.txt')
    hosts             = get_hosts(shards)
    host_to_shard_map = get_host_shard_map(shards, hosts)


    host_lists = []

    while len(hosts) > 0:

        host = hosts.pop()
        host_shard_set = host_to_shard_map[host]

        
        for host_lists_index in sorted(range(len(host_lists)), key=lambda x: len(host_lists[x]), reverse=True):

            my_shards = set()
            for host in host_lists[host_lists_index]:
                my_shards.add(host_to_shard_map[host])

            if len( host_shard_set.intersection(my_shards) ) == 0:
                host_lists[host_lists_index].append(host)
                host = None
                break

        if host != None:
            host_lists.append([host])


    print host_lists


if __name__ == '__main__':
    main()