Advent of Code 2018 Day 6: Chronal Coordinates
Tags: aoc2018, python, puzzle, challenge
Published: 2019-05-14 19:39:07

---
title: "Advent of Code 2018 Day 6: Chronal Coordinates"
tags: ["aoc2018", "python", "puzzle", "challenge"]
published: true
categories: ["Advent of Code 2018"]
description: Why could the Elves not just give us the manual?
---

> This post originally appeared on [steadbytes.com](https://steadbytes.com/blog/advent-of-code-2018/05/)

> Complete solution can be found on [GitHub](https://github.com/SteadBytes/advent-of-code-2018/blob/fa4c0cc437a942ad8cdeb727a4bc8264cd15e419/06/solution.py)

## Part One

We are asked to find the **largest finite area** surrounding area of a coordinate from the list of coordinates in the [puzzle input](https://github.com/SteadBytes/advent-of-code-2018/blob/fa4c0cc437a942ad8cdeb727a4bc8264cd15e419/06/input.txt).

### Parsing Input

Each line of the input contains a pair of `X,Y` coordinates separated by `,`:

```
1, 1
1, 6
8, 3
3, 4
5, 5
8, 9
```

To obtain a list of _integer_ coordinates:

1. Initialise a `list` to store the coordinates
2. For each line of input:
   - Split the line on `,`
   - Cast each split item to an `int`
   - Append a `tuple` of integer coordinates to a list

```python
with open("input.txt") as f:
    coords = []
    for line in f.readlines():
        x, y = line.split(", ")
        coords.append((int(x), int(y)))
```

This works fine, but can be cleaned up and made more _Pythonic_ using a list comprehension:

```python
with open("input.txt") as f:
    coords = [tuple(int(s) for s in line.split(", ")) for line in f.readlines()]
```

### Calculating Coordinate Area

From here on, the term _coordinate_ will refer to one of the X, Y positions extracted from the puzzle input and _location_ will refer to any X, Y position in the search grid.

The puzzle includes some important constraints:

- Calculations must use the [Manhattan Distance](https://en.wikipedia.org/wiki/Taxicab_geometry)
- The _area_ around a coordinate is the number of **integer** X, Y locations that are **closest** to it
  - X, Y locations cannot be _equal_ distance with another coordinate
- The desired coordinate must have a **finite** area
  - i.e. the coordinate is enclosed on all sides by another coordinate

1. Find the min/max X, Y limits of the coordinates
2. Within these limits, generate all possible integer X, Y locations
3. Calculate the Manhattan Distance from each coordinate to each location
4. For each location, determine the closest coordinate
5. For each coordinate, calculate the area by summing up the number of locations for which it is closest
6. Return the largest area

Finding the limits of the coordinates is a case of finding the minimum and maximum values for the X, Y components of the puzzle input:

```python
def coords_limits(coords):
    min_x = min(coords, key=lambda c: c[0])[0]
    max_x = max(coords, key=lambda c: c[0])[0]
    min_y = min(coords, key=lambda c: c[1])[1]
    max_y = max(coords, key=lambda c: c[1])[1]

    return ((min_x, max_x), (min_y, max_y))

coords_limits(
    [(1, 1), (1, 6), (8, 3), (3, 4), (5, 5), (8, 9)]
)
# ((1, 8), (1, 9))
```

Now a nested loop between each set of limits can be used to enumerate all the possible locations:

```python
def gen_locations(x_lims, y_lims):
    for x in range(x_lims[0], x_lims[1] + 1):
        for y in range(y_lims[0], y_lims[1] + 1):
            yield (x, y)
```

Note that I'm using a [generator](https://wiki.python.org/moin/Generators) here for lazy evaluation. This means that each location will be calculated on demand as it is required, instead of building up the entire list at once. The benefit of this will become clear in the next steps.

To calculate the distance between the coordinates and locations, I will first generate a tuple of `(<location>, <coord>)` for each combination:

```python
def gen_locations_coords(coords):
    x_lims, y_lims = coords_limits(coords)
    for x, y in gen_locations(x_lims, y_lims):
        for cx, cy in coords:
            yield ((x, y), (cx, cy))
```

Then calculate the Manhattan Distance for each of these, generating tuples of `((<location>, <cood>), <distance>)`:

```python
def manhattan_distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

def gen_locations_coords_dists(coords):
    for (x, y), (cx, cy) in gen_locations_coords(coords):
        d = manhattan_distance(cx, cy, x, y)
        yield ((x, y), (cx, cy), d)
```

Using generators here is incredibly powerful, allowing a 'chain' of iteration logic to be split up over multiple functions without building and passing around large data structures (in this case a list of locations).

To determine the closest coordinate to each location, I iterate over the combinations of locations, coordinate and distances produced by `gen_locations_coords_dists` updating a mapping between the pairing with the shortest distance:

```python
# location: closest coordinate
closest_coord_map = {}
# location: shortest distance
closest_coord_dists = defaultdict(lambda: float("inf"))
for (x, y), (cx, cy), d in gen_locations_coords_dists(coords):
    # shortest distance seen so far
    closest = closest_coord_dists[(x, y)]
    if d < closest:
        # current pairing is shorter
        closest_coord_map[(x, y)] = (cx, cy)
        closest_coord_dists[(x, y)] = d
    elif d == closest and closest_coord_map[(x, y)] != (cx, cy):
        # same distance, not the same X,Y values
        # locations with multiple equal distance coords don't count towards area
        closest_coord_map[(x, y)] = None
```

Using this `closest_coord_map`, the area for each coordinate can be calculated, by counting the number of locations where each coordinate is closest:

```python
x_lims, y_lims = coords_limits(coords)
coords_areas = defaultdict(int)
for xy, coord in closest_coord_map.items():
    if coord is None:
        # location was equal distance to coordinates
        continue
    if xy[0] in x_lims or xy[1] in y_lims:
        # location at edge of coordinate limits
        # must have an infinite area
        coords_areas[coord] = float("-inf")
    coords_areas[coord] += 1
largest_area = max(coords_areas.values())
```

These last two steps can be wrapped up into a function for Part 1:

```python
def part_1(coords):
    closest_coord_map = {}
    closest_coord_dists = defaultdict(lambda: float("inf"))
    for (x, y), (cx, cy), d in gen_locations_coords_dists(coords):
        closest = closest_coord_dists[(x, y)]
        if d < closest:
            closest_coord_map[(x, y)] = (cx, cy)
            closest_coord_dists[(x, y)] = d
        elif d == closest and closest_coord_map[(x, y)] != (cx, cy):
            closest_coord_map[(x, y)] = None

    x_lims, y_lims = coords_limits(coords)
    coords_areas = defaultdict(int)
    for xy, coord in closest_coord_map.items():
        if coord is None:
            continue
        if xy[0] in x_lims or xy[1] in y_lims:
            coords_areas[coord] = float("-inf")
        coords_areas[coord] += 1
    return max(coords_areas.values())
```

For my puzzle input, the result is **3358**.

## Part Two

We are now asked to find the \*\*size of the region containing all locations which have a total distance to all given coordinates of less than 10000`. The puzzle actually provides us an algorithm for finding the desired region (using a smaller size of 32):

> For each location, add up the distances to all of the given coordinates; if the total of those distances is less than 32, that location is within the desired region.

All of the hard work has been done in part one, we can already generate the distances between all locations and all coordinates. The final step is to sum up the distances for each location to find the total distance to all coordinates in the region, filter these to where the total distance is less than 10000 and count them up!

```python
def part_2(coords):
    total_dists_to_coords = defaultdict(int)
    for (x, y), (cx, cy), d in gen_locations_coords_dists(coords):
        # calculate region size for each location
        total_dists_to_coords[(x, y)] += d
    # filter and count
    return len([l for l, d in total_dists_to_coords.items() if d < 10000])
```

For my puzzle input, the result is **45909**

## A note on Lazy Evaluation

This puzzle was a great fit for generators and lazy evaluation. It provides a very interesting programming paradigm which can be extremely useful for large datasets (and fun of course). I would highly encourage reading [Structure and Interpretation of Computer Programs](https://sarabander.github.io/sicp/html/3_002e5.xhtml) chapter 3.5 on Streams for an excellent introduction to the topic.

### Resources

- [Manhattan Distance](https://en.wikipedia.org/wiki/Taxicab_geometry)
- [Generators](https://wiki.python.org/moin/Generators)
- [`defaultdict`](https://docs.python.org/3/library/collections.html#collections.defaultdict)
- [Structure and Interpretation of Computer Programs](https://sarabander.github.io/sicp/html/3_002e5.xhtml) chapter 3.5 on Streams.