The last part was difficult for me! Took me some time to figure out the small details to take care of.
For now here is my Python code. I am sure it can be simplified by a lot and made much more easy to read. Hopefully I will find time to do it later.
I am building a tree to solve this problem.
importcopywithopen('input')asf:data=f.readlines()classNode:def__init__(self,name,parents,children):self.name=nameself.parents=parentsself.parents_copy=parentsself.children=childrendef__repr__(self):parents=[p.nameforpinself.parents]ifself.parentselseNonechildren=[c.nameforcinself.children]ifself.childrenelseNonereturn'Node(name={}, parents={}, children={})'.format(self.name,parents,children)defadd_parent(self,parent):ifself.parents:self.parents.append(parent)else:self.parents=[parent]self.parents_copy=self.parents[:]defremove_parent(self,parent):ifself.parents_copy:self.parents_copy.remove(parent)defadd_child(self,child):ifself.children:self.children.append(child)else:self.children=[child]defis_root(self):returnself.parents_copy==[]nodes={}fordindata:node=nodes.get(d[5],Node(d[5],[],[]))child=nodes.get(d[36],Node(d[36],[],[]))node.add_child(child)child.add_parent(node)nodes[d[5]]=nodenodes[d[36]]=childnodes_bak=copy.deepcopy(nodes)# Part 1:
# Traverse the tree:
path=[]job_times={}whilelen(nodes):# Find roots:
roots=[nforninnodes.values()ifn.parents_copy==[]]first_root=min(roots,key=lambdan:n.name)# Execute first_node and remove it as parent from its children:
forcinfirst_root.children:c.remove_parent(first_root)# Remove node from global nodes list:
delnodes[first_root.name]path.append(first_root.name)print('Part 1:')print(''.join(path))# Part 2:
# Traverse the tree:
nodes=nodes_bakpath=[]worker_times={'0':0,'1':0,'2':0,'3':0,'4':0}job_times={}whilelen(nodes):# Find roots:
roots=[nforninnodes.values()ifn.parents_copy==[]]# Select first_root by earliest time to add:
min_time=float('inf')first_root=roots[0]forrinroots:# Time for all parents to have finished
iflen(r.parents)>=2:max_parent_time=max(job_times.get(p.name,0)forpinr.parents)eliflen(r.parents)==1:max_parent_time=job_times.get(r.parents[0].name,0)else:max_parent_time=0ifmax_parent_time<=min_time:ifmax_parent_time==min_time:first_root=min(first_root,r,key=lambdan:n.name)else:first_root=rmin_time=max_parent_time# Select the worker that finishes earliest:
earliest_worker=min(worker_times,key=worker_times.get)worker_times[earliest_worker]=(max(min_time,worker_times[earliest_worker])+ord(first_root.name)-4# Converts ASCII to decimal with time adjustment
)# Adding total time it took for job to finish:
job_times[first_root.name]=worker_times[earliest_worker]# Execute first_node and remove it as parent from its children:
forcinfirst_root.children:c.remove_parent(first_root)# Remove node from global nodes list:
delnodes[first_root.name]print('Part 2:')print(max(worker_times.values()))
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
The last part was difficult for me! Took me some time to figure out the small details to take care of.
For now here is my Python code. I am sure it can be simplified by a lot and made much more easy to read. Hopefully I will find time to do it later.
I am building a tree to solve this problem.