Python #6 - Advent of Code 2018 - Distances between points

<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>Coverting points to coordinate tuples <li>Finding the outer bounds of the grid <li>Calculating the distance between two locations <li>Calculating sum of distances to all locations <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/6" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">puzzle 6 <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>Puzzle 6 <p dir="auto">The puzzle is about calculating distances between coordinates in an infinite grid. <h4>Part one <p dir="auto">A list of coordinates is given which describe locations in a grid. Points in the grid that are closest to these locations belong to that specific location. Points that are equally far from multiple locations are denoted by <code>.. Locations are denominated in capital characters while the points belonging to these location are denoted in smaller case characters. <pre><code>aaaaa.cccc aAaaa.cccc aaaddecccc aadddeccCc ..dDdeeccc bb.deEeecc bBb.eeee.. bbb.eeefff bbb.eeffff bbb.ffffFf <p dir="auto"><br /><br /> The questions for the first part of the puzzle is: <blockquote> <p dir="auto">What is the size of the largest area that isn't infinite? <p dir="auto">Points alongside the edges expand infinitely. So only locations that are enclosed by other locations have a non infinite size. <h4>Coverting points to coordinate tuples <p dir="auto">The input for the puzzle comes as a list of points that are separated by a <code>,. <pre><code>181, 47 337, 53 331, 40 137, 57 200, 96 <p dir="auto">Reading these from the file, extracting the digits, converting them to digits and creating tuples can be done with a list comprehension. <pre><code># parse lines into (x, y) tuples with open('input.txt', 'r') as file: points = [tuple(map(int, re.findall(r'\d+', x))) for x in file] <p dir="auto"><br /><br /> This code is equivalent to: <pre><code>locations = [] for line in file: // extract digits digits = re.findall(r'\d+', line) // convert to int inside tuple location = tuple(map(int, digits)) locations.append(location) <p dir="auto"><br /><br /> Where <code>re.findall(r'\d+', line) extracts all the digits, <code>map() applies <code>int() to each value extracted and <code>tuple() convert the list to a set. <h4>Finding the outer bounds of the grid <p dir="auto">While the grid is infinite in size the locations are in a finite grid. Calculating the borders of this grid can be done by looking for the <code>min and <code>max values of both the <code>x and <code>y coordinates. <pre><code># find the min / max bounds of all locations x0, x1 = min(x for x, y in locations), max(x for x, y in locations) y0, y1 = min(y for x, y in locations), max(y for x, y in locations) <p dir="auto"><br /> <h4>Calculating the distance between two locations <p dir="auto">To calculate the distance between two locations the <a href="https://en.wikipedia.org/wiki/Taxicab_geometry" target="_blank" rel="noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Manhattan distance is given. <pre><code># manhattan distance def distance(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2) <p dir="auto"><br /><br /> With the finite grid the distance to each locations from each point inside the grid can be calculated. Each location that has a infinite size has to be discarded. Points that are alongside the borders can be assumed to extend infinitely, the location that they belong to will be discarded. <pre><code>counts = defaultdict(int) infinite = set() <p dir="auto"><br /><br /> The results are stored inside <code>counts while infinite locations are stored inside <code>infinite. <pre><code># loop over each point in the finite grid for y in range(y0, y1 + 1): for x in range(x0, x1 + 1): # find the distance to each location. Sort result by distance. ds = sorted((distance(x, y, px, py), i) for i, (px, py) in enumerate(locations)) # when the first and second result are not the same there is no tie # and the point belongs to a location. if ds[0][0] != ds[1][0]: counts[ds[0][1]] += 1 # points along the border are part of an infinite location if x == x0 or y == y0 or x == x1 or y == y1: infinite.add(ds[0][1]) # discard all infinite locations for k in infinite: counts.pop(k) <p dir="auto"><br /><br /> <code>for i, (px, py) in enumerate(points) extracts the coordinates of each location and enumerates the location as <code>i. This number is then used to refer back to the location. <code>(distance(x, y, px, py), i) then calcuclates the distance to each location and stores this inside a tuple. <code>sorted then sorts all the tuples by their first value, which is the distance. <p dir="auto"><code>if ds[0][0] != ds[1][0] Looks at the distance from the first and second tuple. When they are not equal there is no tie and the size of the area that it is closest to get increased by 1 <code>counts[ds[0][1]] += 1 <p dir="auto">Points along the border are part of an infinite region and get discarded. <pre><code>return max(counts.values()) <p dir="auto"><br /><br /> Returns the maximum value sorted by the values of the dict. <p dir="auto"><center><img src="https://images.hive.blog/0x0/https://cdn.steemitimages.com/DQmR7gkMf51QWCQ9AeS7fR7sU4sPwb3kZzq58AdUUJbxBtA/May-11-2019%2021-23-02.gif" alt="May-11-2019 21-23-02.gif" /> <h4>Part two <blockquote> <p dir="auto">What is the size of the region containing all locations which have a total distance to all given coordinates of less than 10000? <p dir="auto">The second part of the puzzle is relatively easy. Instead of sorting for the shortest distance take the sum of all distances and check if this value is smaller than 10000 is sufficient. <h4>Calculating sum of distances to all locations <pre><code>counter = 0 # loop over each point in the finite grid for y in range(y0, y1 + 1): for x in range(x0, x1 + 1): # calculate distances to each locations and sum all the values # if the total value is smaller than 10000 add 1 to the counter if sum(distance(x, y, px, py) for px, py in locations) < 10000: counter += 1 <p dir="auto"><br /><br /> <code>sum(distance(x, y, px, py) for px, py in points) takes the coordinates for each location and calculates the distance from the point to each location. These values are then added together with <code>sum(). <p dir="auto"><center><img src="https://images.hive.blog/0x0/https://cdn.steemitimages.com/DQmThHZKrGZW2YpXL66JZsecuR2JimWd72xum4qiQhaLaj2/May-11-2019%2021-23-30.gif" alt="May-11-2019 21-23-30.gif" /> <h4>Running the code <p dir="auto">Run the code with: <code>python main.py. This returns both answers for the first and second part of the puzzle. <pre><code>if __name__ == "__main__": # read input file and convert to string with open('input.txt', 'r') as file: string = str([x.strip() for x in file][0]) print(f'Part 1 Answer: {part_1(string)}') print(f'Part 2 Answer: {part_2(string)}') <p dir="auto"><br /><br /> <center><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmUgHqeqMnH9QQCTCSDxLCPpgXddvVYCNi1ANZTsvu1L4N/Screenshot%202019-05-11%20at%2021.25.37.png" alt="Screenshot 2019-05-11 at 21.25.37.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmUgHqeqMnH9QQCTCSDxLCPpgXddvVYCNi1ANZTsvu1L4N/Screenshot%202019-05-11%20at%2021.25.37.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmUgHqeqMnH9QQCTCSDxLCPpgXddvVYCNi1ANZTsvu1L4N/Screenshot%202019-05-11%20at%2021.25.37.png 2x" /> <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, <a href="https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-3---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 3, <a href="https://steemit.com/utopian-io/@steempytutorials/learn-how-to-program-with-python-4---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 4, <a href="https://steemit.com/utopian-io/@steempytutorials/-learn-how-to-program-with-python-4---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 5 <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.