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

<hr /> <h4>Repository <p dir="auto"><span><a href="https://github.com/python" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">https://github.com/python <h4>What will I learn <ul> <li>Findall <li>2D list <li>Sets <h4>Requirements <ul> <li>Python 3.7.2 <li><a href="https://pypi.org/project/pipenv/" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Pipenv <li>git <h4>Difficulty <ul> <li>basic <hr /> <h3>Tutorial <h4>Preface <p dir="auto">This tutorial is part of a course where solutions to puzzles from <a href="https://adventofcode.com/2018/" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">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. <p dir="auto">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 <a href="https://www.codecademy.com/learn/learn-python" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Learn Python2 from Codeacademy should be sufficient. Even though the course is for Python two, while Python 3 is used. <p dir="auto">This tutorial will look at <a href="https://adventofcode.com/2018/day/3" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">puzzle 3 <p dir="auto">The code for this tutorial can be found on <a href="https://github.com/Juless89/tutorials-aoc" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Github! <h4>Part one <blockquote> <p dir="auto">How many square inches of fabric are within two or more claims? <p dir="auto">This puzzle comes with a list claims that come with a x, y coordinates and the size of a grid. <pre><code>#1 @ 1,3: 4x4 #2 @ 3,1: 4x4 #3 @ 5,5: 2x2 <p dir="auto">These claims can be plotted in a grid. An <code>x represents a field with multiple claims. <pre><code>........ ...2222. ...2222. .11XX22. .11XX22. .111133. .111133. ........ <p dir="auto"><br /> <blockquote> <p dir="auto">The whole piece of fabric they're working on is a very large square - at least 1000 inches on each side. <p dir="auto">This puzzle can be solved by creating a grid of at least <code>1000x1000 and going over the claims. Then going over each field to see if there are more than 1 claims. <h4>findall <p dir="auto">The input for this puzzle is more complicated than seen so far. Te retrieve all the numbers from each line a <code>regular expression can be used in combination with <code>findall(). A regular expression defines a search pattern, in this case to search for any numbers of any length <code>r'\d+' is used. Where <code>\d represents a digit and <code>+ specifies any length, <code>r in front of the string makes it a regular expression. More information about regular expressions can be found <a href="https://www.guru99.com/python-regular-expressions-complete-tutorial.html" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">here. <pre><code># 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)) <h4>2D list <p dir="auto">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 <code>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. <pre><code># 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)] <p dir="auto"><br /><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 <code>x and <code>y and adding the height <code>h and width <code>w to them. <pre><code># 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) <p dir="auto">The amount of fields that contain more than one id is calculated by going over each field in the grid. <pre><code># 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 <p dir="auto">This can also be achieved with a one liner by using a list comprehension. <pre><code>sum([sum([len(field[x][y]) > 1 for x in range(field_w)]) for y in range(field_h)])) <p dir="auto"><br /><br /> This list comprehension creates a list with Booleans for each <code>x value. From this list the <code>sum is taken and put into a list for each <code>y value. Again the <code>sum is taken returning the <code>total. <code>True has the value of <code>1 and <code>False of <code>0 when taking the sum of Booleans. <h4>Part two <blockquote> <p dir="auto">What is the ID of the only claim that doesn't overlap? <p dir="auto">This puzzle can be solved by using sets. One set that contains <code>all the ids and another set that <code>invalid ids. That is for fields that contain more than one id. Subtracting the <code>invalid ids set from the <code>all ids set results in the <code>valid id. <h4>Sets <p dir="auto">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 <code>- operations work on sets. <p dir="auto"><center><img src="https://images.hive.blog/0x0/https://cdn.steemitimages.com/DQmUXtbKEsnZTJyo4rHP1QSaqxdDnAwqBU6a6Ztau5AHvSu/Apr-08-2019%2004-33-39.gif" alt="Apr-08-2019 04-33-39.gif" /> <pre><code># 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) <h4>Running the code <p dir="auto">Run the code with: <code>python main.py <pre><code>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)}') <p dir="auto"><center><img src="https://images.hive.blog/0x0/https://cdn.steemitimages.com/DQmQjDF8GUirbFaNMcZj3LUmPYDupBu2ZyaTNvPFB26H25h/Apr-08-2019%2004-50-41.gif" alt="Apr-08-2019 04-50-41.gif" /> <h4>Curriculum <p dir="auto"><a href="https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-1---solving-puzzles-from-advent-of-code-2018" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Part 1, <a href="https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-2---solving-puzzles-from-advent-of-code-2018" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Part 2 <hr /> <p dir="auto">The code for this tutorial can be found on <a href="https://github.com/Juless89/tutorials-aoc" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Github! <p dir="auto"><span>This tutorial was written by <a href="/@juliank">@juliank.