Repository
What will I learn
- Findall
- 2D list
- Sets
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 3
The code for this tutorial can be found on Github!
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.
........
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.
# 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)]
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)]))
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.
# 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)}')
Curriculum
The code for this tutorial can be found on Github!
This tutorial was written by @juliank.
Thank you for your contribution!
Overall, good job!
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]
Thanks for the feedback @mcfarhat
Thank you for your review, @mcfarhat! 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 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 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!