Python #7 part 1 - Advent of Code 2018 - Topological Sort
Repository
What will I learn
- Parsing the input
- Adding sets (union)
- Comparing sets
- Lexicographical order
- Topological sort
Requirements
- Python 3.7.2
- Pipenv
- git
Difficulty
- basic
Tutorial
Preface
This tutorial is part of a course where solutions to puzzles from Advent of Code 2018 are discussed to explain programming techniques using Python. Each puzzle contains two parts and comes with user specific inputs. It is recommended to try out the puzzle first before going over the tutorial. Puzzles are a great and fun way to learn about programming.
While the puzzles start of relatively easy and get more difficult over time. Basic programming understanding is required. Such as the different type of variables, lists, dicts, functions and loops etc. A course like Learn Python2 from Codeacademy should be sufficient. Even though the course is for Python two, while Python 3 is used.
This tutorial will look at puzzle 7
The code for this tutorial can be found on Github!
Puzzle 7
The first part of this puzzle is a topological sort where each step represents a node. As the puzzles are getting more complex this puzzle has been split up into two parts.
Part one
A list of requirements is given that dictate which steps are required to be done for a specific step. The goal is determine the order in which the steps have to be completed. When two steps are available based on their requirements the step that is first in alphabetically order has precedence. Steps are indicated with capital characters.
Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.
Leads to the following visual representation.
-->A--->B--
/ \ \
C -->D----->E
\ /
---->F-----
The questions for the first part of the puzzle is:
In what order should the steps in your instructions be completed?
Parsing the input
Each line comes with two tasks. Where is second task is the prerequisite for the first task.
Step W must be finished before step X can begin.
To solve this puzzle the set of all tasks has to be found and all the prerequisites have to be mapped to their respective task.
# set of all task names A - Z
tasks = set()
# maps task to prerequisites
deps = defaultdict(set)
Extracting the tasks can be done with a, b = re.findall(r' ([A-Z]) ', line)
. Each task is a capital character between A-Z that is surrounded by two whitespaces. These tasks can then be added to the tasks set, and the prerequisite task is mapped to their respective task.
with open('input.txt', 'r') as file:
for line in file:
a, b = re.findall(r' ([A-Z]) ', line)
tasks |= {a, b}
deps[b].add(a)
Adding sets (union)
In Python adding a set to another set is not done with the +
operator, instead the |
operator is used. When using sets this represents the union of two sets.
>>>s = {0, 1}
>>>s |= {1, 2}
>>>s
set([0, 1, 2])
>>>s = {0, 1}
>>>s |= {1, 2} | {3, 4}
>>>s
set([0, 1, 2, 3, 4])
Comparing sets
Sets can be compared with each with more operators than just ==
. A set can be checked to be smaller or larger than another set. A set is only smaller when it is a subset
of the larger set. This means that all elements contained in the smaller set are also inside the larger set.
>>> a = {1,2}
>>> b = {1,2,3}
>>> a > b
False
>>> a < b
True
>>> {4} < b
False
>>> {1} < b
True
>>> {1,4} < b
False
Lexicographical order
In Python min()
and max()
are lexicographic, meaning they are ordered by the alphabet. Casting these functions on a string or list will return the lowest or highest character based on the alphabet.
>>> s = ['a', 'f', 'y']
>>> min(s)
'a'
>>> max(s)
'y'
>>> min('afy')
'a'
Topological sort
Now by combing everything it is possible to solve part 1 of the puzzle.
# store tasks that are done
done = []
for _ in tasks:
# retrieve the min task that has all prerequisites done
done.append(min(x for x in tasks if x not in done and prereq[x] <= set(done)))
x for x in tasks if x not in done and prereq[x] <= set(done)
creates a list of each task that is not in done
and where the prereq
set is smaller or equal than the set of all that tasks that are done. min()
than takes the tasks with the lowest alphabetical order, after which it get's added to the done
list. for _ in tasks
makes sure this process is repeated for the amount of tasks, after which it can be assumed that all tasks are done.
# return tasks in order as a string
return ''.join(done)
The list is then joined and returned as a string, which is the answer.
Running the code
Run the code with: python main.py
. This returns the answer for part 1 of the puzzle.
if __name__ == "__main__":
tasks = set()
prereq = defaultdict(set)
with open('input.txt', 'r') as file:
for line in file:
# set of all task names A - Z
a, b = re.findall(r' ([A-Z]) ', line)
tasks |= {a, b}
# map task to prerequisites
prereq[b].add(a)
print(f'Part 1 Answer: {part_1(tasks, prereq)}')
Curriculum
Part 1, Part 2, Part 3, Part 4, Part 5, Part 6
The code for this tutorial can be found on Github!
This tutorial was written by @juliank.
I thank you for your contribution. Here are my thoughts. Note that, my thoughts are my personal ideas on your post and they are not directly related to the review and scoring unlike the answers I gave in the questionnaire;
Structure
Language
Your contribution has been evaluated according to Utopian policies and guidelines, as well as a predefined set of questions pertaining to the category.
To view those questions and the relevant answers related to your post, click here.
Need help? Chat with us on Discord.
[utopian-moderator]
Thank you for your review, @yokunjon! Keep up the good work!
Hi @steempytutorials!
Your post was upvoted by @steem-ua, new Steem dApp, using UserAuthority for algorithmic post curation!
Your post is eligible for our upvote, thanks to our collaboration with @utopian-io!
Feel free to join our @steem-ua Discord server
Hi, @steempytutorials!
You just got a 1% upvote from SteemPlus!
To get higher upvotes, earn more SteemPlus Points (SPP). On your Steemit wallet, check your SPP balance and click on "How to earn SPP?" to find out all the ways to earn.
If you're not using SteemPlus yet, please check our last posts in here to see the many ways in which SteemPlus can improve your Steem experience on Steemit and Busy.
Hey, @steempytutorials!
Thanks for contributing on Utopian.
We’re already looking forward to your next contribution!
Get higher incentives and support Utopian.io!
Simply set @utopian.pay as a 5% (or higher) payout beneficiary on your contribution post (via SteemPlus or Steeditor).
Want to chat? Join us on Discord https://discord.gg/h52nFrV.
Vote for Utopian Witness!
Congratulations @steempytutorials! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :
You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOP
Vote for @Steemitboard as a witness to get one more award and increased upvotes!
Congratulations @steempytutorials! You received a personal award!
You can view your badges on your Steem Board and compare to others on the Steem Ranking
Vote for @Steemitboard as a witness to get one more award and increased upvotes!
Good morning @steempytutorials
I've noticed that you've delegated some decent amount of steem power (SP) to smartsteem. Unfortunatelly, this curation program is dead already and you don't receive any payouts.
Check out our curation program and consider removing delegation from SmartSteem (you can do it using steemworld.org).
We offer decent weekly payout. Something you may find interesting and worth your time.
Cheers,
Piotr