create account

Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018 by steempytutorials

View this thread on: hive.blogpeakd.comecency.com
· @steempytutorials ·
$22.71
Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018
<center>![banner.png](https://www.digifloor.com/wp-content/uploads/2016/07/python-banner.jpg)</center>

---

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

#### What will I learn

- Findall
- 2D list
- Sets

#### 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 3](https://adventofcode.com/2018/day/3)

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

#### Part one

> How many square inches of fabric are within two or more claims?

This puzzle comes with a list claims that come with a x, y coordinates and the size of a grid. 

```
#1 @ 1,3: 4x4
#2 @ 3,1: 4x4
#3 @ 5,5: 2x2
```

These claims can be plotted in a grid. An `x` represents a field with multiple claims.

```
........
...2222.
...2222.
.11XX22.
.11XX22.
.111133.
.111133.
........
```
<br>
> The whole piece of fabric they're working on is a very large square - at least 1000 inches on each side.

This puzzle can be solved by creating a grid of at least `1000x1000` and going over the claims. Then going over each field to see if there are more than 1 claims.

#### findall

The input for this puzzle is more complicated than seen so far. Te retrieve all the numbers from each line a `regular expression` can be used in combination with `findall()`. A regular expression defines a search pattern, in this case to search for any numbers of any length `r'\d+'` is used. Where `\d` represents a digit and `+` specifies any length, `r` in front of the string makes it a regular expression. More information about regular expressions can be found [here](https://www.guru99.com/python-regular-expressions-complete-tutorial.html).

```
# read input file and convert to list
import re

with open('input.txt', 'r') as file:
    lines = list(file)

    for line in lines:
        id, x, y, w, h = map(int, re.findall(r'\d+', line))
```

#### 2D list

The field can be represented by a two dimensional list. Which is a list of lists. Accessing the list is done by using both indexes. For example `list[x][y]`. Creating the list is done by using a list comprehension. In this example an empty list is set for each field in the grid.

```
# create 2d list of empty lists
field_w, field_h = 1000, 1000
field = [[[] for x in range(field_w)] for y in range(field_h)]
```
<br>
The 2D list is then filled by going over each line from the input. The coordinates for the the fields inside the grid are calculated by taking the start coordinates `x` and `y` and adding the height `h` and width `w` to them.

```
# go over each input line, extracts numbers
# by using a regular expression.
for line in lines:
    id, x, y, w, h = map(int, re.findall(r'\d+', line))

    # use starting coordinates x, y with grid
    # size w, h to add the id to the correct field
    for a in range(y, y + h):
        for b in range(x, x + w):
            field[a][b].append(id)
```

The amount of fields that contain more than one id is calculated by going over each field in the grid.

```
# loop through entire 2d list to count 
# which fields hold more than 1 id
multiple_claims = 0
for a in range(0, field_h):
    for b in range(0, field_h):
        if len(field[a][b]) > 1:
            multiple_claims += 1
```

This can also be achieved with a one liner by using a list comprehension.

```
sum([sum([len(field[x][y]) > 1 for x in range(field_w)]) for y in range(field_h)]))
```
<br>
This list comprehension creates a list with Booleans for each `x` value. From this list the `sum` is taken and put into a list for each `y` value. Again the `sum` is taken returning the `total`. `True` has the value of `1` and `False` of `0` when taking the sum of Booleans.


#### Part two

> What is the ID of the only claim that doesn't overlap?

This puzzle can be solved by using sets. One set that contains `all` the ids and another set that `invalid` ids. That is for  fields that contain more than one id. Subtracting the `invalid` ids set from the `all` ids set results in the `valid` id.

#### Sets

Sets are unordered collections of unique variables. This means that adding a variable to a set that already contains this variable does not expand the set. Also different sets with the same variables but a different order are equal. Furthermore `-` operations work on sets.


<center>![Apr-08-2019 04-33-39.gif](https://cdn.steemitimages.com/DQmUXtbKEsnZTJyo4rHP1QSaqxdDnAwqBU6a6Ztau5AHvSu/Apr-08-2019%2004-33-39.gif)</center>

```
# sets
all = set()
invalid = set()

# loop through all fields in the grid
for a in range(0, len(field)):
    for b in range(0, len(field[0])):
        # add each id to all set
        for id in field[a][b]:
            all.add(id)
        # for each field that contains more than
        # 1 id add id to invalid set
        if len(field[a][b]) > 1:
            for id in field[a][b]:
                invalid.add(id)

# subtracts invalid ids set from all ids set
return (all-invalid)
```

#### Running the code

Run the code with: `python main.py`

```
if __name__ == "__main__":
    # read input file and convert to list
    with open('input.txt', 'r') as file:
        lines = list(file)

    field = create_field(lines)

    print(f'Part 1 Answer: {part_1(field)}')
    print(f'Part 2 Answer: {part_2(field)}')
```
<center>![Apr-08-2019 04-50-41.gif](https://cdn.steemitimages.com/DQmQjDF8GUirbFaNMcZj3LUmPYDupBu2ZyaTNvPFB26H25h/Apr-08-2019%2004-50-41.gif)</center>

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

---

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

This tutorial was written by @juliank.
πŸ‘  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , and 151 others
properties (23)
authorsteempytutorials
permlinklearn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018
categoryutopian-io
json_metadata{"tags":["utopian-io","tutorials","course","python","programming"],"app":"steem-plus-app"}
created2019-04-08 03:03:18
last_update2019-04-08 03:03:18
depth0
children6
last_payout2019-04-15 03:03:18
cashout_time1969-12-31 23:59:59
total_payout_value17.073 HBD
curator_payout_value5.634 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length6,705
author_reputation31,094,047,689,691
root_title"Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018"
beneficiaries
0.
accountsteemplus-pay
weight100
1.
accountutopian.pay
weight500
max_accepted_payout100,000.000 HBD
percent_hbd10,000
post_id82,668,227
net_rshares38,538,752,980,068
author_curate_reward""
vote details (215)
@mcfarhat ·
$6.44
Thank you for your contribution!
- It is always intriguing to try and solve puzzles with coding. Thumbs up for that!
- A short intro about the puzzle itself would have helped, in addition to the link to the puzzle original source. It disrupts the reader a bit.
- I liked how low level your explanations were. Very helpful for starters.
- A short description about the results prior to displaying your output would have been helpful as well.
- You had few minor typos across your text. Titles could have been slightly more elaborate, such as your use of just findall and Sets.
Overall, good job!

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/3-2-1-1-1-2-2-3-).

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

[[utopian-moderator]](https://join.utopian.io/)
πŸ‘  , , , , , , , , , , , , , , , , , ,
properties (23)
authormcfarhat
permlinkre-steempytutorials-learn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018-20190408t084858567z
categoryutopian-io
json_metadata{"tags":["utopian-io"],"links":["https://join.utopian.io/guidelines","https://review.utopian.io/result/8/3-2-1-1-1-2-2-3-","https://discord.gg/uTyJkNm","https://join.utopian.io/"],"app":"steemit/0.1"}
created2019-04-08 08:49:03
last_update2019-04-08 08:49:03
depth1
children2
last_payout2019-04-15 08:49:03
cashout_time1969-12-31 23:59:59
total_payout_value4.942 HBD
curator_payout_value1.496 HBD
pending_payout_value0.000 HBD
promoted0.000 HBD
body_length1,046
author_reputation150,651,671,367,256
root_title"Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id82,678,891
net_rshares10,397,821,051,828
author_curate_reward""
vote details (19)
@steempytutorials ·
Thanks for the feedback @mcfarhat
properties (22)
authorsteempytutorials
permlinkre-mcfarhat-re-steempytutorials-learn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018-20190408t121653169z
categoryutopian-io
json_metadata{"tags":["utopian-io"],"users":["mcfarhat"],"app":"steemit/0.1"}
created2019-04-08 12:16:54
last_update2019-04-08 12:16:54
depth2
children0
last_payout2019-04-15 12:16:54
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_length33
author_reputation31,094,047,689,691
root_title"Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id82,685,954
net_rshares0
@utopian-io ·
Thank you for your review, @mcfarhat! Keep up the good work!
properties (22)
authorutopian-io
permlinkre-re-steempytutorials-learn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018-20190408t084858567z-20190411t024519z
categoryutopian-io
json_metadata"{"app": "beem/0.20.17"}"
created2019-04-11 02:45:21
last_update2019-04-11 02:45:21
depth2
children0
last_payout2019-04-18 02:45:21
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"Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id82,852,135
net_rshares0
@steem-plus ·
SteemPlus upvote
Hi, @steempytutorials!

You just got a **0.42%** 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
permlinklearn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018---vote-steemplus
categoryutopian-io
json_metadata{}
created2019-04-08 15:36:54
last_update2019-04-08 15:36:54
depth1
children0
last_payout2019-04-15 15:36:54
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_length443
author_reputation247,952,188,232,400
root_title"Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id82,696,520
net_rshares0
@steem-ua ·
#### 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 (22)
authorsteem-ua
permlinkre-learn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018-20190408t120058z
categoryutopian-io
json_metadata"{"app": "beem/0.20.19"}"
created2019-04-08 12:01:00
last_update2019-04-08 12:01:00
depth1
children0
last_payout2019-04-15 12:01:00
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_length295
author_reputation23,214,230,978,060
root_title"Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id82,685,293
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-learn-how-to-program-with-python-3---solving-puzzles-from-advent-of-code-2018-20190408t184204z
categoryutopian-io
json_metadata"{"app": "beem/0.20.17"}"
created2019-04-08 18:42:06
last_update2019-04-08 18:42:06
depth1
children0
last_payout2019-04-15 18:42:06
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"Learn how to program with Python #3 - Solving Puzzles from Advent of Code 2018"
beneficiaries[]
max_accepted_payout1,000,000.000 HBD
percent_hbd10,000
post_id82,705,141
net_rshares0