Skip to content

Instantly share code, notes, and snippets.

@RobGThai
Created January 19, 2016 17:04
Show Gist options
  • Save RobGThai/e736410ee9e854dc3aea to your computer and use it in GitHub Desktop.
Save RobGThai/e736410ee9e854dc3aea to your computer and use it in GitHub Desktop.
For Codehew 2016, question 2 Start Up.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment