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

in #utopian-io6 years ago (edited)

banner.png


Repository

https://github.com/python

What will I learn

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

Requirements

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



May-13-2019 18-16-16.gif

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



May-13-2019 18-16-48.gif

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'



May-13-2019 18-17-43.gif

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)}')



Screenshot 2019-05-13 at 18.08.55.png

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.

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.

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 distributed more than 3000 upvotes. Your next target is to reach 4000 upvotes.

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

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

Coin Marketplace

STEEM 0.20
TRX 0.19
JST 0.033
BTC 88885.90
ETH 3279.02
USDT 1.00
SBD 2.99