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

in #utopian-io3 years ago (edited)

#### Repository

https://github.com/python

#### What will I learn

• Parsing the input
• Comparing sets
• Lexicographical order
• Topological sort

• 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
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)
``````

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 = []

# 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__":
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)

``````

#### Curriculum

The code for this tutorial can be found on Github!

This tutorial was written by @juliank.

Sort:

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, as well as a predefined set of questions pertaining to the category.

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!

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.

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).

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!

 Happy Birthday! - You are on the Steem blockchain for 2 years!

You can view your badges on your Steem Board and compare to others on the Steem Ranking

STEEM 0.27
TRX 0.07
JST 0.034
BTC 24307.13
ETH 1933.34
USDT 1.00
SBD 3.38