Solution for Advent of Code 2018 - Day 7: The Sum of Its Parts

Link to the puzzle text

Part 1

In this puzzle, we have a list of tasks and their requirements in terms of other tasks. A task can only run, if all previous tasks have been completed. We are asked to find the order in which the tasks can be completed.

This ordering is also known as topological sorting, so we could have used the networkx library, where the function is implemented. But instead we wrote our own topological sort. We keep a list of solved tasks and for each unsolved task check if all requirements are already met. If yes, we add the new task to our ordering and the solved tasks.

Part 2 

In part 2, each task is given a length and we have a pool of 5 workers, who can work on tasks independently. Using all workers, we are asked to find the time required to fulfill all tasks

We simulated the work timestep wise. In each timestep, we looked for tasks with all requirements fulfilled and assigned it to a worker if available. We kept track how far each task was done until now and updated the solved tasks once the remaining time was zero.

This could have also been solved with networkx and with finding the critical path. We just need to make sure, there are a maximum of 5 tasks concurrently for the 5 workers. But we decided to implement if ourselves instead of relying on a library.

Link to my solutions