create account

Python #7 part 1 - Advent of Code 2018 - Topological Sort by steempytutorials

View this thread on: hive.blogpeakd.comecency.com
· @steempytutorials · (edited)
$10.88
Python #7 part 1 - Advent of Code 2018 - Topological Sort
![banner.png](https://www.digifloor.com/wp-content/uploads/2016/07/python-banner.jpg)

---

#### Repository
https://github.com/python

#### What will I learn

- Parsing the input  
- Adding sets (union)
- Comparing sets
- Lexicographical order
- Topological sort

#### Requirements

- Python 3.7.2
- [Pipenv](https://pypi.org/project/pipenv/)
- git

#### Difficulty

- basic

---

### Tutorial

#### Preface

This tutorial is part of a course where solutions to puzzles from [Advent of Code 2018](https://adventofcode.com/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](https://www.codecademy.com/learn/learn-python) should be sufficient. Even though the course is for Python two, while Python 3 is used.

This tutorial will look at [puzzle 7](https://adventofcode.com/2018/day/7)

The code for this tutorial can be found on [Github](https://github.com/Juless89/tutorials-aoc)!

#### 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-----
```

<br>
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.
```
<br>
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)
```
<br>
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])
```
<br>
<center>![May-13-2019 18-16-16.gif](https://cdn.steemitimages.com/DQmVqrAMZuZtbFpXiHAUsWbWBYqfNXe9BspiDLcVhHXZdEq/May-13-2019%2018-16-16.gif)</center>
#### 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
```
<br>
<center>![May-13-2019 18-16-48.gif](https://cdn.steemitimages.com/DQmUQgsi3jEJn4WGEtWSeiNg1qLTiDKcQNDhyquo8xnzwrW/May-13-2019%2018-16-48.gif)</center>

#### 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'
```
<br>
<center>![May-13-2019 18-17-43.gif](https://cdn.steemitimages.com/DQmUvKsPARjGLsffV6hTAFwMNMcdP4USs3uM8RKWMLETWdt/May-13-2019%2018-17-43.gif)</center>
#### 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)))
```
<br>
`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)}')
```
<br>
![Screenshot 2019-05-13 at 18.08.55.png](https://cdn.steemitimages.com/DQmWBekP9kEW8Dhec77prRsQ5SBthgZKAdUSukLqEKgGVBE/Screenshot%202019-05-13%20at%2018.08.55.png)

#### Curriculum
[Part 1](https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-1---solving-puzzles-from-advent-of-code-2018), [Part 2](https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-2---solving-puzzles-from-advent-of-code-2018), [Part 3](https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018), [Part 4](https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-4---solving-puzzles-from-advent-of-code-2018), [Part 5](https://steemit.com/utopian-io/@steempytutorials/-learn-how-to-program-with-python-4---solving-puzzles-from-advent-of-code-2018), [Part 6](https://steemit.com/utopian-io/@steempytutorials/python-6---advent-of-code-2018---distances-between-points)

---

The code for this tutorial can be found on [Github](https://github.com/Juless89/tutorials-aoc)!

This tutorial was written by @juliank.
πŸ‘  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , and 10 others
properties (23)
authorsteempytutorials
permlinkpython-7-part-1---advent-of-code-2018---topological-sort
categoryutopian-io
json_metadata{"tags":["utopian-io","tutorials","python","course","programming"],"app":"steemit/0.1","users":["juliank"],"image":["https://www.digifloor.com/wp-content/uploads/2016/07/python-banner.jpg","https://cdn.steemitimages.com/DQmVqrAMZuZtbFpXiHAUsWbWBYqfNXe9BspiDLcVhHXZdEq/May-13-2019%2018-16-16.gif","https://cdn.steemitimages.com/DQmUQgsi3jEJn4WGEtWSeiNg1qLTiDKcQNDhyquo8xnzwrW/May-13-2019%2018-16-48.gif","https://cdn.steemitimages.com/DQmUvKsPARjGLsffV6hTAFwMNMcdP4USs3uM8RKWMLETWdt/May-13-2019%2018-17-43.gif","https://cdn.steemitimages.com/DQmWBekP9kEW8Dhec77prRsQ5SBthgZKAdUSukLqEKgGVBE/Screenshot%202019-05-13%20at%2018.08.55.png"],"links":["https://github.com/python","https://pypi.org/project/pipenv/","https://adventofcode.com/2018/","https://www.codecademy.com/learn/learn-python","https://adventofcode.com/2018/day/7","https://github.com/Juless89/tutorials-aoc","https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-1---solving-puzzles-from-advent-of-code-2018","https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-2---solving-puzzles-from-advent-of-code-2018","https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018","https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-4---solving-puzzles-from-advent-of-code-2018","https://steemit.com/utopian-io/@steempytutorials/-learn-how-to-program-with-python-4---solving-puzzles-from-advent-of-code-2018","https://steemit.com/utopian-io/@steempytutorials/python-6---advent-of-code-2018---distances-between-points"],"format":"markdown"}
created2019-05-13 16:13:06
last_update2019-05-13 16:20:12
depth0
children7
last_payout2019-05-20 16:13:06
cashout_time1969-12-31 23:59:59
total_payout_value8.212 HBD
curator_payout_value2.670 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length7,439
author_reputation31,094,047,689,691
root_title"Python #7 part 1 - Advent of Code 2018 - Topological Sort"
beneficiaries
0.
accountsteemplus-pay
weight100
1.
accountutopian.pay
weight500
max_accepted_payout100,000.000 HBD
percent_hbd10,000
post_id84,785,371
net_rshares22,404,299,102,215
author_curate_reward""
vote details (74)
@steem-plus ·
SteemPlus upvote
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](https://steemit.com/@steem-plus) to see the many ways in which SteemPlus can improve your Steem experience on Steemit and Busy.
properties (22)
authorsteem-plus
permlinkpython-7-part-1---advent-of-code-2018---topological-sort---vote-steemplus
categoryutopian-io
json_metadata{}
created2019-05-14 06:54:09
last_update2019-05-14 06:54:09
depth1
children0
last_payout2019-05-21 06:54:09
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length440
author_reputation247,952,188,232,400
root_title"Python #7 part 1 - Advent of Code 2018 - Topological Sort"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id84,820,002
net_rshares0
@steem-ua ·
$0.03
#### 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](https://discord.gg/KpBNYGz)**
πŸ‘  
properties (23)
authorsteem-ua
permlinkre-python-7-part-1---advent-of-code-2018---topological-sort-20190518t143732z
categoryutopian-io
json_metadata"{"app": "beem/0.20.19"}"
created2019-05-18 14:37:33
last_update2019-05-18 14:37:33
depth1
children0
last_payout2019-05-25 14:37:33
cashout_time1969-12-31 23:59:59
total_payout_value0.019 HBD
curator_payout_value0.006 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length295
author_reputation23,214,230,978,060
root_title"Python #7 part 1 - Advent of Code 2018 - Topological Sort"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id85,084,954
net_rshares46,647,842,509
author_curate_reward""
vote details (1)
@steemitboard ·
Congratulations @steempytutorials! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

<table><tr><td><img src="https://steemitimages.com/60x70/http://steemitboard.com/@steempytutorials/votes.png?201908041256"></td><td>You distributed more than 3000 upvotes. Your next target is to reach 4000 upvotes.</td></tr>
</table>

<sub>_You can view [your badges on your Steem Board](https://steemitboard.com/@steempytutorials) and compare to others on the [Steem Ranking](https://steemitboard.com/ranking/index.php?name=steempytutorials)_</sub>
<sub>_If you no longer want to receive notifications, reply to this comment with the word_ `STOP`</sub>



###### [Vote for @Steemitboard as a witness](https://v2.steemconnect.com/sign/account-witness-vote?witness=steemitboard&approve=1) to get one more award and increased upvotes!
properties (22)
authorsteemitboard
permlinksteemitboard-notify-steempytutorials-20190804t133950000z
categoryutopian-io
json_metadata{"image":["https://steemitboard.com/img/notify.png"]}
created2019-08-04 13:39:48
last_update2019-08-04 13:39:48
depth1
children0
last_payout2019-08-11 13:39:48
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length880
author_reputation38,975,615,169,260
root_title"Python #7 part 1 - Advent of Code 2018 - Topological Sort"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id89,129,470
net_rshares0
@steemitboard ·
Congratulations @steempytutorials! You received a personal award!

<table><tr><td>https://steemitimages.com/70x70/http://steemitboard.com/@steempytutorials/birthday2.png</td><td>Happy Birthday! - You are on the Steem blockchain for 2 years!</td></tr></table>

<sub>_You can view [your badges on your Steem Board](https://steemitboard.com/@steempytutorials) and compare to others on the [Steem Ranking](https://steemitboard.com/ranking/index.php?name=steempytutorials)_</sub>


###### [Vote for @Steemitboard as a witness](https://v2.steemconnect.com/sign/account-witness-vote?witness=steemitboard&approve=1) to get one more award and increased upvotes!
properties (22)
authorsteemitboard
permlinksteemitboard-notify-steempytutorials-20191230t023003000z
categoryutopian-io
json_metadata{"image":["https://steemitboard.com/img/notify.png"]}
created2019-12-30 02:30:03
last_update2019-12-30 02:30:03
depth1
children0
last_payout2020-01-06 02:30:03
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length652
author_reputation38,975,615,169,260
root_title"Python #7 part 1 - Advent of Code 2018 - Topological Sort"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id93,850,957
net_rshares0
@utopian-io ·
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](https://chrome.google.com/webstore/detail/steemplus/mjbkjgcplmaneajhcbegoffkedeankaj?hl=en) or [Steeditor](https://steeditor.app)).

**Want to chat? Join us on Discord https://discord.gg/h52nFrV.**

<a href='https://steemconnect.com/sign/account-witness-vote?witness=utopian-io&approve=1'>Vote for Utopian Witness!</a>
properties (22)
authorutopian-io
permlinkre-python-7-part-1---advent-of-code-2018---topological-sort-20190518t153101z
categoryutopian-io
json_metadata"{"app": "beem/0.20.17"}"
created2019-05-18 15:31:03
last_update2019-05-18 15:31:03
depth1
children0
last_payout2019-05-25 15:31:03
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length598
author_reputation152,955,367,999,756
root_title"Python #7 part 1 - Advent of Code 2018 - Topological Sort"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id85,087,424
net_rshares0
@yokunjon ·
$3.63
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**
 
  * Structure of your post is good, but I think individual topics need more attention. So, I would use header markdowns bigger in size if I were you.

* **Language**

  * Language is superb. I really appreciate usage of third person.

----
Your contribution has been evaluated according to [Utopian policies and guidelines](https://join.utopian.io/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](https://review.utopian.io/result/8/2-2-1-1-1-2-1-4-).

---- 
Need help? Chat with us on [Discord](https://discord.gg/uTyJkNm).

[[utopian-moderator]](https://join.utopian.io/)
πŸ‘  , , , , , , , , , , , , , , , , , ,
properties (23)
authoryokunjon
permlinkre-steempytutorials-python-7-part-1---advent-of-code-2018---topological-sort-20190518t141002054z
categoryutopian-io
json_metadata{"tags":["utopian-io"],"links":["https://join.utopian.io/guidelines","https://review.utopian.io/result/8/2-2-1-1-1-2-1-4-","https://discord.gg/uTyJkNm","https://join.utopian.io/"],"app":"steemit/0.1"}
created2019-05-18 14:09:57
last_update2019-05-18 14:09:57
depth1
children1
last_payout2019-05-25 14:09:57
cashout_time1969-12-31 23:59:59
total_payout_value2.793 HBD
curator_payout_value0.835 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length932
author_reputation19,266,807,595,513
root_title"Python #7 part 1 - Advent of Code 2018 - Topological Sort"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id85,084,005
net_rshares6,545,287,289,923
author_curate_reward""
vote details (19)
@utopian-io ·
Thank you for your review, @yokunjon! Keep up the good work!
properties (22)
authorutopian-io
permlinkre-re-steempytutorials-python-7-part-1---advent-of-code-2018---topological-sort-20190518t141002054z-20190521t120521z
categoryutopian-io
json_metadata"{"app": "beem/0.20.17"}"
created2019-05-21 12:05:24
last_update2019-05-21 12:05:24
depth2
children0
last_payout2019-05-28 12:05:24
cashout_time1969-12-31 23:59:59
total_payout_value0.000 HBD
curator_payout_value0.000 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length60
author_reputation152,955,367,999,756
root_title"Python #7 part 1 - Advent of Code 2018 - Topological Sort"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id85,240,629
net_rshares0