import json def get_key(id): return 'e' + str(id) def create_r_graph(f): emp_id_pos = 0 total_sub_pos = 1 subs_pos = 2 teams = {} team_size = 0 team_count = 0 ind_count = 0 for line in f: if ' ' not in line: team_size = int(line) team_count += 1 ind_count = 0 continue inputs = line.split(' ') emp_id = int(inputs[emp_id_pos]) subs = int(inputs[total_sub_pos]) for emp in map(lambda x: int(x), inputs[subs_pos:]): if get_key(emp) in teams: teams.get(get_key(emp)).append(emp_id) else: teams.update({get_key(emp): [emp_id]}) ind_count += 1 if team_count == total_team and ind_count == team_size: break return teams def find_orders(f): orders = [] for line in f: if ' ' not in line: team_order = line continue orders.append(tuple(map(lambda x: int(x), line.split(' ')))) return orders def find_paths(orders, teams): inc = 0 for o in orders: find_r_path(o[0], o[1], teams) inc += 1 # if inc > 1: # break def find_r_path(sender, receiver, teams): direct_boss = [] rejection = 'no' found = False if not get_key(receiver) in teams: print rejection # print 'Scanning %d' % (receiver), 0 team = teams.get(get_key(receiver)) trail = [receiver] found, trail = \ find_ind_team(sender, team, trail) if found: print 'Order directive %d->%d' % (sender, receiver), \ 'Result', len(trail) - 2, trail else: print 'Order directive %d->%d' % (sender, receiver), rejection def find_ind_team(sender, team, trail): # print 'Scanned', scanned skip_size = 0 direct_boss = [] found = False shortest_connection = 99 shortest_trail = [] for person in team: if person in trail: skip_size += 1 if skip_size == len(team): break continue direct_boss.append(person) if person == sender: found = True trail.append(person) break if found: return found, trail direct_boss = filter(lambda x: x not in trail, direct_boss) if direct_boss: for boss in direct_boss: new_trail = [] + trail new_trail.append(boss) team = teams.get(get_key(boss)) found, new_trail = \ find_ind_team(sender, team, new_trail) if found: if len(new_trail) < shortest_connection: shortest_connection = len(new_trail) shortest_trail = new_trail return found, shortest_trail if __name__ == '__main__': f = open('startup_input.txt') total_input = f.readline().split(' ') total_team = int(total_input[0]) total_emp = int(total_input[1]) # print 'Team', total_team # print 'Emp', total_emp teams = create_r_graph(f) orders = find_orders(f) # print json.dumps(teams, sort_keys=True, # indent=2) find_paths(orders, teams)